凸优化经典算法宝典

1.证明函数为凸函数并求其共轭函数凸函数证明我们考虑函数:nfRR1()logexp(),mTiiifxaxb其中11,...,,,...,nmmaaRbbR。利用()()fxAxbg，其中1()log(exp)miiyyg，我们可以得到f的Hessian矩阵的简单公式。通过求偏导数，或者利用2'2''()(())()(())()().Thxfxfxfxfxfxgg并注意到g是log和1expmiiy的复合函数，可以得到2()(())()(),Tydiagyyygggg其中()yg由11exp1()...expexpmimiyyyyg给出。利用复合公式我们有:2211()(()),()TTTTfxAdiagzzzAzz11其中exp(),1,...,Tiiizaxbim。指数和的对数函数的Hessian矩阵为221()(()()),()TTTfxzdiagzzzz11其中1(,...,)nxxzee。为了说明2()0fx，我们证明对任意v，有2()0Tvfxv，即22221111()()()()0.()nnnTiiiiiTiiivfxvzvzvzz1上述不等式可以应用Cauchy-Schwarz不等式2()()()TTTaabbab得到，此时向量a和b的分量为,iiiiiavzbz。共轭函数求解为了得到指数和的对数函数1()log()inxifxe的共轭函数，首先考察y取何值时()Tyxfx的最大值可以得到。对x求导，令其为零，我们得到如下条件1,1,...,.ijxinxjeyine当且仅当0y以及1Ty1时上述方程有解。将iy的表达式代入()Tyxfx可以得到*1()logniiifyyy。根据前面的约定，0log0等于0，因此只要满足0y以及1Ty1，即使当y的某些分量为零时，*f的表达式仍然正确。事实上*f的定义域即为1Ty1，0y。为了说明这一点，假设y的某个分量是负的，比如说0ky，令,0,,kixtxik令t趋向于无穷，()Tyxfx无上界。如果0y但是1Ty1，令xt1，可得()log.TTyxfxtytn1若1Ty1，当t时上述表达式无界；当1Ty1时，若t时其无界。总之，*1log0()1iTniiyyyyfy1如果且其他情况换言之，指数和函数的对数函数的共轭函数是概率单纯形内的负熵函数。2.求半正定规划的拉格朗日对偶minimizecxsubjectto11...0nnxFxFG（5.93）其中1,...,knFFGS。（此时，1f是仿射的，锥为半正定锥kS。）、对约束引入一个对偶变量或者乘子kZS，因此Largrange函数为11(,)((...))TnnLxZcxtrxFxFGZ111(())...(())(),nnnxctrFZxctrFZtrGZ其对x是仿射的。对偶函数可以描述为()()0,1,...,()inf(,)iixtrGZtrFZcin其他情xZ况gZL所以对偶问题可以写成max()imizetrGZ()0,1,...,iisubjecttotrFZcin0Z(在这里我们用到了kS是自对偶的性质，即*()kkSS)(非负象限中。锥nR的对偶是它本身：0,00.Tyxxy我们称这种锥自对偶)若半定规划（5.93）是严格可行的，即存在一点x满足下式11...0nnxFxFG则强对偶性成立。3.简述KKT条件现在假设函数01,...,,...mpffhh可微（因此定义域是开集），但是并不假设这些函数是凸函数。非凸问题的KKT条件和前面一样，令*x和**(,)分别是原问题和对偶问题的某对最优解，对偶间隙为零。因为**(,,)Lxv关于x求极小在*x处取得最小值，因此函数在*x处的导数必须为零，即，*****011()()()0pmiiiiiifxfxvhx因此，我们有*()01,...,ifxim*()0,1,...,ihxip*0,1,...,(5.49)iim**()0,1,...,iifxim*****011()()()0pmiiiiiifxfxvhx我们称上式为Karush-Kuhn-Tucker(KKT)条件。总之，对于目标函数和约束函数可微的任意优化问题，如果强对偶性成立，那么任何一对原问题最优解和对偶问题的最优解必须满足KKT条件（5.49）。凸问题的KKT条件当原问题是凸问题时，满足KKT条件的点也是原、对偶最优解。换言之，如果函数if是凸函数，ih是仿射函数，,,xv是任意满足KKT条件的点。()0,1,...,ifxim()0,1,...,ihxip0,1,...,iim()0,1,...,iifxim011()()()0,pmiiiiiifxfxvhx那么x和(,)v分别是原问题和对偶问题的最优解，对偶间隙为零。为了说明这一点，注意到前两个条件说明了x是原问题的可行解。因为0i，(,,)Lxv是x的凸函数;最后一个KKT条件说明在xx处，Lagrange函数的导数为零。因此(,,)Lxv关于x求极小在x处取得最小值。我们得出结论(,)(,,)vLxvg011()()()pmiiiiiifxfxvhx0()fx最后一行成立是因为()0ihx以及()0iifx。这说明原问题的解x和对偶问题的解(,)v之间的对偶间隙为零，因此分别是原、对偶最优解。总之，对目标函数和约束函数可微的任意凸优化问题，任意满足KKT条件的点分别是原、对偶最优解，对偶间隙为零。若某个凸优化问题具有可微的目标函数和约束函数，且满足Slater条件，那么KKT条件是最优性的充要条件：slater条件意味着最优对偶间隙为零且对偶最优解可以达到，因此x是原问题最优解，当且仅当存在(,)v，二者满足KKT条件。KKT条件在优化领域有着重要的作用。在一些特殊的情形下，是可以解析求解KKT条件的（也因此可以求解优化问题）。更一般地，很多求解凸优化问题的方法可以认为或者理解为求解KKT条件的方法。