大数据计算方法 课件 chap9-约束优化解法与对偶原理

1大数据计算方法Chap9：约束优化解法与对偶原理等式约束优化问题不等式约束优化问题对偶方法与KKT条件Outline2求解等式约束优化问题线性等式约束子空间约减方法拉格朗日乘子法(重点：线性等式约束的两种解法)3带约束的非线性优化

4s.t.

s.t.子空间约减法

5s.t.pxn

p列n-p列

非奇异上三角方阵

s.t.

nx(n-p)

p列p列

子空间约减法6s.t.pxn做LU分解的开销小于对A做QRCP分解即使A为稀疏阵,变量代换后优化变量前的矩阵F都是很稠密的,将导致后续求解无约束优化问题时开销大一般的等式约束问题

拉格朗日乘子法7s.t.

曲面的法向为

即垂直于这p个切面的交集拉格朗日乘子法可处理一般的等式约束问题等价于例子:8s.t.s.t.最优解

垂直于g(x)等值面,即沿其梯度方向可用牛顿法解方程组未必好解；未必是凸优化极值点x*满足:

拉格朗日乘子法

9s.t.

,其中pxnn个方程求解方法：

拉格朗日乘子-牛顿法

拉格朗日乘子法处理线性等式约束若代价函数对一般的非线性代价函数,将方程整体看成用牛顿法求解迭代公式:10s.t.pxn比子空间约减法易保持稀疏性任意初始,k1后,每步解此方程还可以使用阻尼牛顿法等技巧处理线性等式约束例子:用牛顿法求解设拉格朗日乘子法11s.t.pxn可行解

s.t.若不是可行解若已是可行解求解不等式约束优化问题线性等式约束+不等式约束内点法—对数障碍法半正定规划12主要考虑凸优化假设等式约束均为线性等式约束注意:一般情况下，可行集未必是凸集处理不等式约束定义一个指示函数(indicator)注意:

在计算过程中也要保证新的优化问题只含线性等式约束,但函数I()不可导,无法直接使用拉格朗日乘子-牛顿法带不等式约束的优化问题13s.t.s.t.要求,否则代价函数无穷大u0I(u)凸函数处理不等式约束用带参数的光滑函数近似函数I()相继求解一系列问题,其中每个都

可以用牛顿法可靠地求解对数障碍法(logarithmicbarrier)带不等式约束的优化问题14s.t.s.t.homotopymethod参数t

另一种障碍函数当t0时非常近似I(u)障碍函数对数障碍函数消去不等式约束,且代价函数光滑注意:计算中仍要保证hj(x)<0例:新的代价函数是凸的吗?内点法15s.t.s.t.x*(t)处等值面与超平面相切从可行集内部的点开始也是凸函数!s.t.若是凸函数,半正定

对数障碍法1.选择初始t值和初始解x(0)2.求解线性等式约束的非线性优化

得到最优解x*

(拉格朗日乘子-牛顿法)3.令x(0)=x*,t=t(取值10~20)4.重复上述第2、第3步,直到x*趋于收敛如何选初始的x(0)

?必须是可行的，即预处理步骤:求解整体流程:对数障碍法解预处理问题得到初始解,再解原问题内点法16s.t.s.t.凸优化凸函数注意：得到的是近似解，总是不满足

约束中的=s.t.若最优解s*>0,原问题不可行;否则,得到可行的初始解用对数障碍法解它初始解容易设置内点法17s.t.凸函数特殊的不等式约束例:最大内切椭球问题这种广义不等式表示矩阵半正定,该问题称为半正定规划半正定规划一般形式:处理半正定约束条件的方法一定是凸函数半正定规划18(Semidefiniteprogramming)s.t.有些约束条件不是此形式

可看成是广义的不等式s.t.对称矩阵(其他常见约束)上面的属于这一般形式吗?

使用相应的对数障碍函数:线性函数与凸函数的复合可行集凸吗?

用对数障碍法求解要保证正定怎么选初始x(0)是问题在预处理步骤,求解解预处理问题时,

可任意取初始x(0),总可以找到足够大s(0)使得满足约束小结半正定规划s.t.s.t.若最优解s*>0,原问题不可行,否则得到可行的x使用对数障碍法线性等式约束二次优化线性等式约束优化

含不等式约束的优化

(包括半正定规划)解一次线性方程组拉格朗日乘子-牛顿法内点法(对数障碍法)Ipop19

对偶方法与KKT条件对偶函数对偶问题强对偶KKT条件20带约束非线性优化问题拉格朗日函数:它是关于x的非线性函数,但关于u和v是线性函数拉格朗日对偶(dual)函数拉格朗日对偶函数21s.t.拉格朗日乘子

一定是个凹函数!(下确界)若x*是优化问题的解且v

0,则定理9.2：d(u,v)是f(x*)的下界例9.8:拉格朗日对偶函数22s.t.拉格朗日对偶函数:(当v

0时)s.t.

例9.7:可行集为区间[-0.46,0.46]f(x)周围的虚线表示拉格朗

日函数

在v=0.1,0.2,…,1时的曲线拉格朗日对偶函数当0v1时,d(v)的曲线?且d(v)是凹函数拉格朗日对偶函数23s.t.,当v>0时f(x),h(x)如右图对偶问题:例9.9:对偶问题一定是凸优化问题!对偶问题24s.t.原问题s.t.v是对应的拉格朗日系数s.t.对偶问题:s.t.其解u*,v*满足：称为弱对偶条件为最优对偶间隔(optimaldualitygap)

s.t.即弱对偶普遍成立通过解对偶问题,可得原问题最优值的下界强对偶:并非总成立;若原问题为凸优化,经常成立对凸优化问题若可行集有内点,即可行集中

使得,

则强对偶成立。精细的Slater条件:若某些hj是线性函数,则可以去掉条件中它们对应的<0要求强对偶25s.t.对偶问题s.t.s.t.,均为凸函数这个条件称为Slater条件这些都是判断强对偶的充分条件!即最优对偶间隔为0定理9.4线性规划问题都满足Slater条件！

强对偶26对偶问题可表示为:凸的半正定规划!非凸优化、但满足强对偶对偶函数由于互补松弛(complementaryslackness)若强对偶成立,x*为原问题最优解,u*,v*为对偶问题最优解等号成立,则,j=1,2,…,qKKT条件(Karush-Kuhn-Tucker)若强对偶成立,且相关函数可微

是的最小值点KKT条件27s.t.注意:(互补松弛条件)若则若则激活约束未激活约束(驻点条件)

KKT条件28s.t.

KKT条件与强对偶都成立问题(a):小结29对于强对偶成立的凸优化问题,KKT条件也是充分的优化问题的解法总结内点法+牛顿法(主要对凸优化)如果强对偶条件成立(如针对凸