中科大凸优化39-42
本课程整理自中国科学技术大学2011年课程《最优化理论》，[*]主讲人：凌青老师
https://cse.sysu.edu.cn/content/3112
[*]课程主要教材
Boyd S , Vandenberghe L . Convex Optimization. Cambridge University Press, 2004.
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
[*]课程视频网上有很多，这里只放一个链接
https://www.bilibili.com/video/BV1Jt411p7jE
[*]本文彩色插图由 @陌上疏影凉 提供
[*]本教程已收录到专栏
[*]本文内容对应视频lec39-42，本文对应3个知识点
[*]敏感性分析
[*]Primal Dual 与经典算法的联系
[*]线搜索
31 敏感性分析
[*]原问题
https://www.zhihu.com/equation?tex=s.t.%5C%3B+f_i%28x%29%5Cleq0%2Ci%3D1%3Am
https://www.zhihu.com/equation?tex=h_i%28x%29%3D0%2Ci%3D1%3Ap
[*]干扰问题
https://www.zhihu.com/equation?tex=s.t.%5C%3B+f_i%28x%29%5Cleq+u_i%2Ci%3D1%3Am
https://www.zhihu.com/equation?tex=h_i%28x%29%3Dw_i%2Ci%3D1%3Ap
[*]考虑最优值可变化从https://www.zhihu.com/equation?tex=p%5E%5Cstar%280%2C0%29变为
[*]约束变化后，有以下性质：
[*]性质1：若原问题为凸问题，则为https://www.zhihu.com/equation?tex=%28u%2Cw%29的凸函数
[*]性质2：若原问题为凸问题，且满足Slater条件，https://www.zhihu.com/equation?tex=%5Clambda%5E%5Cstar%2C%5Ceta%5E%5Cstar为对偶问题最优解，则
https://www.zhihu.com/equation?tex=p%5E%5Cstar%28u%2Cw%29%5Cgeq+p%5E%5Cstar%280%2C0%29-%28%5Clambda%5E%5Cstar+%29%5ETu-%28%5Ceta%5E%5Cstar%29%5ETw
这个性质有以下用法
1）若https://www.zhihu.com/equation?tex=%5Clambda%5E%5Cstar_i很大，且加紧第https://www.zhihu.com/equation?tex=i项约束，则急剧增加
2）若为很大的正值，下降，或者相反若为很大的负值，上升，则急剧增加
3）若https://www.zhihu.com/equation?tex=%5Clambda_i%5E%5Cstar+很小，且https://www.zhihu.com/equation?tex=u_i%3E0，则几乎不变
4）若为很小的正值，增加，或为很小的负值，下降，则几乎不变
[*]性质3：（局部敏感性若原问题为凸问题，满足强对偶关系，且在https://www.zhihu.com/equation?tex=%280%2C0%29处可微
https://www.zhihu.com/equation?tex=%5Clambda%5E%5Cstar_i%3D-%5Cfrac%7B%5Cpartial+p%5E%5Cstar%28u%2Cw%29%7D%7B%5Cpartial+u_i%7D%7C_%7B%280%2C0%29%7D
https://www.zhihu.com/equation?tex=%5Ceta%5E%5Cstar_i%3D-%5Cfrac%7B%5Cpartial+p%5E%5Cstar%28u%2Cw%29%7D%7B%5Cpartial+w_i%7D%7C_%7B%280%2C0%29%7D
https://www.zhihu.com/equation?tex=p%5E%5Cstar%28u%2Cw%29%3D+p%5E%5Cstar%280%2C0%29-%28%5Clambda%5E%5Cstar+%29%5ETu-%28%5Ceta%5E%5Cstar%29%5ETw
32 Primal Dual 与经典算法的联系
32.1 Boolean 线性规划松弛
[*]原问题：https://www.zhihu.com/equation?tex=%5Cmin%5C%3Bc%5ETx
https://www.zhihu.com/equation?tex=s.t.%5C%3B+Ax%5Cleq+b
https://www.zhihu.com/equation?tex=x_i%5Cin+%5C%7B0%2C1%5C%7D%2Ci%3D1%3An
这里的约束是https://www.zhihu.com/equation?tex=x_i只能取布尔值，非0即1，是离散的。
[*]第一种做法是将这个离散的约束放缩为框约束https://www.zhihu.com/equation?tex=0%5Cleq+x_i%5Cleq1，然后求解就比较容易了。写出拉格朗日函数
https://www.zhihu.com/equation?tex=L%28x%2Cu%2Cv%2Cw%29%3Dc%5ET+x%2Bu%5ET%28Ax-b%29-v%5ETx%2Bw%5ET%28x-1%29
https://www.zhihu.com/equation?tex=%3D%28c%2BA%5ETu-v%2Bw%29%5ETx-b%5ETu%2B%5Cmathbf%7B1%7D%5ETw
https://www.zhihu.com/equation?tex=g%28u%2Cv%2Cw%29%3D%5Cinf%5Climits_x+L%28x%2Cu%2Cv%2Cw%29上式是关于https://www.zhihu.com/equation?tex=x的线性函数，系数必须为0，这个函数才有意义。所以对偶问题为
https://www.zhihu.com/equation?tex=%5Cmax%5C%3B+-b%5ETu-%5Cmathbf%7B1%7D%5ETw
https://www.zhihu.com/equation?tex=s.t.+%5C%3Bc%2BA%5ETu-v%2Bw%3D0
https://www.zhihu.com/equation?tex=u%2Cv%2Cw%5Cgeq0
[*]第二种做法是将原来的约束写成方程的形式https://www.zhihu.com/equation?tex=x_i%281-x_i%29%3D0，此时拉格朗日函数为
https://www.zhihu.com/equation?tex=L%28x%2Cu%2Cv%29%3Dc%5ETx%2Bu%5ET%28Ax-b%29%2B%5Csum_iv_ix_i%5E2-%5Csum_iv_ix_i
https://www.zhihu.com/equation?tex=%3D%5Csum_iv_ix_i%5E2%2B%28c%2BA%5ETu-v%29%5ETx-u%5ETb
对偶函数为https://www.zhihu.com/equation?tex=g%28u%2Cv%29%3D%5Cinf%5Climits_%7Bx%7D+L%28x%2Cu%2Cv%29%3D-u%5ETb-%5Cfrac%7B1%7D%7B4%7D%28c_i%2Ba_i%5ETu-v_i%29%5E2%2Fv_i，此时乘子https://www.zhihu.com/equation?tex=v%5Cgeq+0，因为这个二次函数的系数在所有维度上都要非负，否则对偶函数(二次函数开口向下)就为负无穷了。
对偶问题https://www.zhihu.com/equation?tex=%5Cmax+%5C%3B+g%28u%2Cv%29%3D%5Cmax%5C%3B-u%5ETb-%5Cfrac%7B1%7D%7B4%7D%5Csum_i%28c_i%2Ba_i%5ETu-v_i%29%5E2%2Fv_i
先求关于的项，这是一个关于的二次函数（当https://www.zhihu.com/equation?tex=v_i%3E0时），解为https://www.zhihu.com/equation?tex=v_i%3Dc_i%2Ba_i%5ETu，因为的非负性，https://www.zhihu.com/equation?tex=v_i%3D%5Cmin%5C%7B0%2Cc_i%2Ba_i%5ETu%5C%7D，则对偶问题写为如下
https://www.zhihu.com/equation?tex=%5Cmax%5Climits_u%5C%3B-u%5ETb%2B%5Csum_i+%5Cmin%5C%7B0%2Cc_i%2Ba_i%5ETu%5C%7D
https://www.zhihu.com/equation?tex=s.t.+%5C%3B%5Clambda%5Cgeq0
引入一个松弛变量https://www.zhihu.com/equation?tex=w_i%5Cleq+c_i%2Ba_i%5ETu这个问题化为如下
https://www.zhihu.com/equation?tex=%5Cmax%5Climits_u%5C%3B-u%5ETb%2B%5Cmathbf%7B1%7D%5ETw
https://www.zhihu.com/equation?tex=s.t.%5C%3Bu%5Cgeq0%2Cw_i%5Cleq+a%5ET_iu%2Bc_i%2Cw_i%5Cleq0
[*]第一种做法是求解松弛问题的对偶问题，第二种做法是求解对偶问题的拉格朗日松弛(Lagrange Relaxation)，对比最后形式，两种做法最终是等价问题
32.2 罚函数
[*]例，带线性等式约束的可微凸优化问题
https://www.zhihu.com/equation?tex=s.t.%5C%3B+Ax-b%3D0
在罚函数法中，会将约束带一个乘子直接放在目标函数上
https://www.zhihu.com/equation?tex=%5Cmin+%5C%3B+f_0%28x%29%2B%5Cfrac%7B%5Calpha%7D%7B2%7D%5C%7CAx-b%5C%7C%5E2_2
这个形式与拉格朗日函数比较相似
[*]例2，带线性不等式约束的可微凸优化问题
https://www.zhihu.com/equation?tex=s.t.+%5C%3B+Ax%5Cgeq+b
这里罚函数法称为log-barrier法
https://www.zhihu.com/equation?tex=%5Cmin%5C%3B+f_0%28x%29-%5Csum_iu_i%5Clog%28a_i%5ETx-b_i%29
假设https://www.zhihu.com/equation?tex=%5Ctilde+x+是其最优解，则https://www.zhihu.com/equation?tex=%5Cnabla+f_0%28%5Ctilde+x%29-%5Csum_iu_ia_i%2F%28a_i%5ET%5Ctilde+x+-b_i%29%3D0
这个稳定点也是如下优化问题的最优解
https://www.zhihu.com/equation?tex=%5Ctilde+x%3D%5Carg%5Cmax%5Climits_x+f_0%28x%29-%5Csum_i+u_i+%5Cfrac%7Ba_i%5ETx-b_i%7D%7Ba_i%5ET%5Ctilde+x+-b_i%7D
原问题的拉格朗日函数为https://www.zhihu.com/equation?tex=L%28x%2C%5Clambda%29%3Df_0%28x%29%2B%5Csum_i%5Clambda_i%28b_i-a_i%5ETx%29
当https://www.zhihu.com/equation?tex=%5Clambda_i%3Du_i%2F%28a_i%5ET%5Ctilde+x+-b_i%29时，拉格朗日函数正是上面的优化问题目标函数
[*]原问题-->惩罚-->惩罚因子，原问题-->对偶函数-->拉格朗日乘子（对应惩罚因子）
33 线搜索
[*]从这里开始对应参考书上第六章的内容，讲解几种典型的算法，包括无约束优化算法，有约束优化算法，所有优化算法都是迭代算法
https://www.zhihu.com/equation?tex=x%5E%7Bk%2B1%7D%3Dx%5Ek%2B%5Calpha%5Ek+d%5Ek
[*]线搜索(line search)
[*]1）黄金分割法(优选法)：与二分法试解类似，这里是按照黄金分割比例尝试步长，缩短搜索区间。
[*]2）Amijo Rule
如果https://www.zhihu.com/equation?tex=f_0%28x%5Ek%2B%5Calpha+d%5Ek%29%3Ef_0%28x%5Ek%29%2Br%5Calpha+%5Cnabla+f_0%5ET%28x%5Ek%29d%5Ek，https://www.zhihu.com/equation?tex=r%5Cin+%280%2C0.5%5D则https://www.zhihu.com/equation?tex=%5Calpha%5Cleftarrow+%5Calpha%5Ccdot%5Cbeta，其中https://www.zhihu.com/equation?tex=%5Cbeta%5Cin+%280%2C1%29，否则停止
推荐阅读
华年ss：中科大凸优化1-4
华年ss：中科大凸优化5-8
华年ss：中科大凸优化9-12：凸函数
华年ss：中科大凸优化13-16
华年ss：中科大凸优化17-20
华年ss：中科大凸优化21-24：凸优化问题
华年ss：中科大凸优化25-28：典型凸优化问题
华年ss：中科大凸优化29-32：对偶
华年ss：中科大凸优化35-38：KKT条件
页:
[1]