最优化第8章

第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础约束优化：线性约束规划ConstrainedOptimization:LinearlyConstrainedProgramming第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础解的情况：无可行解、无界、有解G是n阶对称方阵d，ai是n维常向量有解时：⊙G半正定KKT点即为全局极小点G正定：有唯一的极小点凸规划⊙G不定可能存在不是全局解的局部解找全局解是NP-难问题二次规划(quadraticprogramming)第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础有价证券的组合优化⊙投资组合：设对第i项投资的资金投放比例为xi⊙问题：对收益与风险的折衷进行建模投资集合{1,…,n}，可能收益为ri◇假定II所有资金均投资，不允许卖空◇假定I设是随机变量ri与rj的相关系数第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础有价证券的组合优化(续)⊙证券组合：证券组合的利润：其中G是协方差矩阵，是半正定的！⊙证卷组合优化(portfoliooptimization)：证券组合的期望收益和方差：极大化收益极小化风险：受约束于第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础有价证券的组合优化(续)Markowitz引入风险容许参数(risktoleranceparameter)保守型投资者：大的参数取值冒险型投资者：小的参数取值⊙Paretofrontier或者tradeoffcurve⊙参数，设定值依赖于投资者的个人偏好找出“最优的”证券投资组合！第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础Paretoefficiency,orParetooptimality,isaconceptineconomicswithapplicationsinengineeringandsocialsciences.ThetermisnamedafterVilfredoPareto,anItalianeconomistwhousedtheconceptinhisstudiesofeconomicefficiencyandincomedistribution.Givenasetofchoicesandawayofvaluingthem,theParetofrontier(tradeoffcurve)isthesetofchoicesthatareParetoefficient.TheParetofrontierisparticularlyusefulinengineering:byrestrictingattentiontothesetofchoicesthatarePareto-efficient,adesignercanmaketradeoffswithinthisset,ratherthanconsideringthefullrangeofeveryparameter.Givenaninitialallocationofgoodsamongasetofindividuals,achangetoadifferentallocationthatmakesatleastoneindividualbetteroffwithoutmakinganyotherindividualworseoffiscalledaParetoimprovement.AnallocationisdefinedasParetoefficientorParetooptimalwhennofurtherParetoimprovementscanbemade.Paretoefficiency/Paretooptimality第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础等式约束QPQP的积极集法线性等式约束规划线性约束规划第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础基本消元法消去x3代入目标函数，得回代，得第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础等式约束二次规划(续)核心思想：消元法(基本、广义)其中A是n×m阶矩阵，，假定:线性无关其中，A1可逆第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础基本消元法(续)找A的可逆子矩阵A1，进行消元如果正定，解方程组可得唯一解回代得，从而得代入目标函数，得第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础广义消元法考察方程组ATx=b:Yb是特解，通解x=Yb+s，其中s是齐次线性方程组ATs=0的解，且令和分别是与矩阵，满足非奇异，且如果正定，则原问题有唯一解，解方程组右乘任一可行解可表示为，代入目标函数，得第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础正交分解法构造和的正交分解法对矩阵A进行QR分解，即其中是阶正交阵，是阶的可逆上三角阵设矩阵和分别是矩阵的前m列和后n-m列，令求特解：解得求最优解：求乘子：第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础等式约束二次规划－广义消元法(续)第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础实用二次规划算法概述⊙经典的积极集法(active-setmethods)求解凸和非凸二次规划问题－－中小规模(成百上千个变量！)⊙梯度投影法(gradient-projectionmethods)简单约束的QP，比如BoxQP!⊙内点法(interior-pointmethods)大规模凸二次规划！第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础注记：线性约束规范(LCQ)成立!故QP的任一解x*均满足KKT条件其中G是n×n阶对称阵，ai,d是n维常向量解的情况：无可行解、无界、有解积极集法－问题最优积极集！有解时：⊙G半正定：KKT点即为全局极小点G正定：有唯一的极小点第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础积极集法－算法的动机(motivation)如果提前知道，求解第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础积极集法－算法的动机(motivation)对积极集的初始猜测不断修正，直到得到正确的！考虑第k次迭代：x(k)是可行点，设是积极集第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础积极集法－算法的原理(续)对积极集的初始猜测不断修正，直到得到正确的！考虑第k次迭代：x(k)是可行点，设是积极集令(8.2.1)第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础积极集法－算法的原理(续)⊙与不等式约束对应的乘子均非负，即◎x(k)(s=0)是当前等式约束问题的解令，求解新的子问题得p(k),沿p(k)作线搜索.⊙否则，设，有设当前等式约束问题的Lagrange乘子是，即则x(k)是原问题的KKT点，进而是全局解.P.158页，第3段-6行第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础,积极集法－算法的原理◎x(k)(s=0)不是当前等式约束问题的解，记解为s(k)⊙x(k)+s(k)满足其它约束条件称取到最小值的指标j对应的约束为阻滞(blocking)约束⊙否则，沿方向找到最好点无阻滞约束时，积极集不变；否则给积极集添加一个阻滞约束，积极集保持不变,(8.2.3)第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础求解凸二次规划的积极集法第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础⊙需要确定初始可行点－－比如人工变量法！⊙在恰当的假定下可证明－－算法有限步找到解！⊙可以推广来求解非凸二次规划积极集法－进一步说明⊙迭代次数有可能超过不等式约束的个数⊙选取初试积极集时，要求积极约束的梯度线性无关第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础解的情况：无可行解、无界、有解f(x)是n元函数；ai是n维常向量；bi是常数有解时⊙f(x)是凸函数KKT点即为全局极小点f(x)严格凸：有唯一的极小点凸规划⊙f(x)是非凸函数可能存在不是全局解的局部解找全局解是NP-难问题线性等式约束规划构造矩阵，使得且非奇异第8章约束优化：线性约束规划LHY-SMSS-BUAA数学规划基础f(x)是n元函数；ai是n维常向量；bi是常数线性约束规划对积极集的初始猜测不断修正，直到得到正确的！考虑第k次迭代：x(k)是可行点，设是积极集