中科大凸优化39-42

KaaPexei · 发表于 2022-4-22 17:56

本课程整理自中国科学技术大学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 敏感性分析

原问题

$s.t.\; f_i(x)\leq0,i=1:m$
$h_i(x)=0,i=1:p$
干扰问题

$s.t.\; f_i(x)\leq u_i,i=1:m$
$h_i(x)=w_i,i=1:p$

考虑最优值可变化从 $p^\star(0,0)$ 变为
约束变化后，有以下性质：
- 性质1：若原问题为凸问题，则为 $(u,w)$ 的凸函数
- 性质2：若原问题为凸问题，且满足Slater条件， $\lambda^\star,\eta^\star$ 为对偶问题最优解，则
  $p^\star(u,w)\geq p^\star(0,0)-(\lambda^\star )^Tu-(\eta^\star)^Tw$
  这个性质有以下用法
  1）若 $\lambda^\star_i$ 很大，且加紧第 $i$ 项约束，则急剧增加
  2）若为很大的正值，下降，或者相反若为很大的负值，上升，则急剧增加
  3）若 $\lambda_i^\star$ 很小，且 $u_i>0$ ，则几乎不变
  4）若为很小的正值，增加，或为很小的负值，下降，则几乎不变
- 性质3：（局部敏感性若原问题为凸问题，满足强对偶关系，且在 $(0,0)$ 处可微
  $\lambda^\star_i=-\frac{\partial p^\star(u,w)}{\partial u_i}|_{(0,0)}$

$\eta^\star_i=-\frac{\partial p^\star(u,w)}{\partial w_i}|_{(0,0)}$
$p^\star(u,w)= p^\star(0,0)-(\lambda^\star )^Tu-(\eta^\star)^Tw$
32 Primal Dual 与经典算法的联系

32.1 Boolean 线性规划松弛

原问题： $\min\;c^Tx$

            $s.t.\; Ax\leq b$
                     $x_i\in \{0,1\},i=1:n$
   这里的约束是 $x_i$ 只能取布尔值，非0即1，是离散的。

第一种做法是将这个离散的约束放缩为框约束 $0\leq x_i\leq1$ ，然后求解就比较容易了。写出拉格朗日函数

   $L(x,u,v,w)=c^T x+u^T(Ax-b)-v^Tx+w^T(x-1)$
                           $=(c+A^Tu-v+w)^Tx-b^Tu+\mathbf{1}^Tw$
   $g(u,v,w)=\inf\limits_x L(x,u,v,w)$ 上式是关于 $x$ 的线性函数，系数必须为0，这个函数才有意义。所以对偶问题为
   $\max\; -b^Tu-\mathbf{1}^Tw$
    $s.t. \;c+A^Tu-v+w=0$
             $u,v,w\geq0$

第二种做法是将原来的约束写成方程的形式 $x_i(1-x_i)=0$ ，此时拉格朗日函数为

   $L(x,u,v)=c^Tx+u^T(Ax-b)+\sum_iv_ix_i^2-\sum_iv_ix_i$
                  $=\sum_iv_ix_i^2+(c+A^Tu-v)^Tx-u^Tb$
   对偶函数为 $g(u,v)=\inf\limits_{x} L(x,u,v)=-u^Tb-\frac{1}{4}(c_i+a_i^Tu-v_i)^2/v_i$ ，此时乘子 $v\geq 0$ ，因为这个二次函数的系数在所有维度上都要非负，否则对偶函数(二次函数开口向下)就为负无穷了。
   对偶问题 $\max \; g(u,v)=\max\;-u^Tb-\frac{1}{4}\sum_i(c_i+a_i^Tu-v_i)^2/v_i$
先求关于的项，这是一个关于的二次函数（当 $v_i>0$ 时），解为 $v_i=c_i+a_i^Tu$ ，因为的非负性， $v_i=\min\{0,c_i+a_i^Tu\}$ ，则对偶问题写为如下
   $\max\limits_u\;-u^Tb+\sum_i \min\{0,c_i+a_i^Tu\}$
   $s.t. \;\lambda\geq0$
   引入一个松弛变量 $w_i\leq c_i+a_i^Tu$ 这个问题化为如下
   $\max\limits_u\;-u^Tb+\mathbf{1}^Tw$
   $s.t.\;u\geq0,w_i\leq a^T_iu+c_i,w_i\leq0$

第一种做法是求解松弛问题的对偶问题，第二种做法是求解对偶问题的拉格朗日松弛(Lagrange Relaxation)，对比最后形式，两种做法最终是等价问题

32.2 罚函数

例，带线性等式约束的可微凸优化问题

$s.t.\; Ax-b=0$
在罚函数法中，会将约束带一个乘子直接放在目标函数上
$\min \; f_0(x)+\frac{\alpha}{2}\|Ax-b\|^2_2$
这个形式与拉格朗日函数比较相似
例2，带线性不等式约束的可微凸优化问题

$s.t. \; Ax\geq b$

   这里罚函数法称为log-barrier法
    $\min\; f_0(x)-\sum_iu_i\log(a_i^Tx-b_i)$
   假设 $\tilde x$ 是其最优解，则 $\nabla f_0(\tilde x)-\sum_iu_ia_i/(a_i^T\tilde x -b_i)=0$
   这个稳定点也是如下优化问题的最优解
    $\tilde x=\arg\max\limits_x f_0(x)-\sum_i u_i \frac{a_i^Tx-b_i}{a_i^T\tilde x -b_i}$

   原问题的拉格朗日函数为 $L(x,\lambda)=f_0(x)+\sum_i\lambda_i(b_i-a_i^Tx)$
   当 $\lambda_i=u_i/(a_i^T\tilde x -b_i)$ 时，拉格朗日函数正是上面的优化问题目标函数

原问题-->惩罚-->惩罚因子，原问题-->对偶函数-->拉格朗日乘子（对应惩罚因子）

33 线搜索

从这里开始对应参考书上第六章的内容，讲解几种典型的算法，包括无约束优化算法，有约束优化算法，所有优化算法都是迭代算法
$x^{k+1}=x^k+\alpha^k d^k$
线搜索(line search)
1）黄金分割法(优选法)：与二分法试解类似，这里是按照黄金分割比例尝试步长，缩短搜索区间。

2）Amijo Rule
如果 $f_0(x^k+\alpha d^k)>f_0(x^k)+r\alpha \nabla f_0^T(x^k)d^k$ ， $r\in (0,0.5]$ 则 $\alpha\leftarrow \alpha\cdot\beta$ ，其中 $\beta\in (0,1)$ ，否则停止

推荐阅读
华年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条件

		自动登录	找回密码
密码			立即注册

中科大凸优化39-42

本帖子中包含更多资源