Proximal Operator

$$prox_{f}(x) = \arg\min_u (f(u) + \frac 1 2 \|u - x\|^2)$$

• $f(x)$：凸函数

• 由于$L_2$范数的强凸性，近端算子也强凸，解总是唯一存在
• 直观理解：寻找距离点$x$不太远、$f(u)$尽可能小的$u$
• 以下算法都是近端算法的特例
  • shrinkage thresholding algorithm
  • projected Landweber
  • projected gradient
  • alternating projections
  • alternating-directions method of multipliers
  • alternating split Bregman

• 近端算子连续可微

Moreau Envolop

$$\begin{align*} M_{\gamma, f}(x) & = prox_{\gamma, f}(x) \\ &= \arg\min_u (f(u) + \frac 1 {2\gamma} \|u - x\|^2) \\ \nabla prox_{\gamma, f}(x) & = \frac 1 {\gamma}(x - prox_f(x)) \end{align*}$$

• $\gamma > 0$：平衡参数，$\gamma = 1$即为普通近端算子

近端算子求解

• 对一般凸$f(x)$，通常使用次梯度进行优化，其近端算子解为 （即解变动方向$p-x$为负次梯度方向）

  $$p = prox_f(x) \Leftrightarrow x - p \in \partial f(p) \quad (\forall (x,p) \in R^N * R^N)$$

• 对光滑凸函数$f$，上述等式对其近端算子约简为 （即解变动方向$p-x$为负梯度方向）

  $$p = prox_f(x) \Leftrightarrow x-p = \bigtriangledown f(p)$$

性质

分离函数

$$\begin{align*} f(x_1, \cdots, x_m) & = \sum_{i=1}^m f_i(x_i) \\ prox_f(x_1, \cdots, x_m) & = [prox_{f_1}(x_1), \cdots, prox_{fm}(x_m)] \end{align*}$$

• 取$f(x) = |x|_1$，即可得即软阈值算子

  $$(prox_{\gamma, f}(x))_i = \left \{ \begin{array}{l} x_i - \gamma, & x_i \geq \gamma \\ 0, & |x_i| < \gamma \\ x_i + \gamma, & x_i \leq -\gamma \end{array} \right.$$

  • 参考坐标下降：近端算子中二次项中各分量无关，所以一轮 迭代即为最优解

仿射函数分解

$$\begin{align*} f(x) & = g(Ax + b) \\ prox_f(x) & = x + \frac 1 {\alpha} A^T (prox_{\alpha g}(Ax + b) - Ax - b) \end{align*}$$

• $A^T A = \alpha I, \alpha > 0$：线性变换
• $g$：良好闭凸函数

第一投影定理

• 取$f(x)$为示性函数、约束条件，即得到投影算子

$$\begin{align*} prox_{\gamma, f}(x) & = proj_C(x) = \arg\min_{u \in C} \|u - x\|_2^2 \\ f(x) & = I_C(x) = \left \{ \begin{array}{l} 0, x \in C \\ \infty, x \notin C \end{array} \right. \end{align*}$$

第二临近定理

• $f$为良好闭凸函数，则以下三条等价

  • $y = prox_f(x)$
  • $x - y \in \partial f(y)$：由近端算子定义即得
  • $\forall z, \leq f(z) - f(y)$

Moreau Decomposition

$$\begin{align*} prox_f(x) + prox_{f^{*}}(x) & = x \\ prox_{\lambda f}(x) + \lambda prox_{f^{*}/lambda}(x/\lambda) & = x, \lambda > 0 \end{align*}$$

最小值

$$\begin{align*} \min_x prox_f(x) & = \min_x f(x) \\ \arg\min_x prox_f(x) & = \arg\min_x f(x) \end{align*}$$

证明

$$\begin{align*} f(x_f) & = f(x_f) + \frac 1 2 \|x_f - x_f\|_2^2 \\ & \geq \min_u {f(u) + \frac 1 2 \|u - x_f\|_2^2} \\ & = prox_f(x_f) \\ & \geq prox_f(x_p) \\ & = f(x_p) + \frac 1 2 \|x_p - x_f\|_2^2 \\ & \geq f(x_p) \geq f(x_f) \end{align*}$$

• $x_f = \arg\min_x f(x)$
• $x_p = \arg\min_x prox_f(x)$

例

• $f(x)=c$：$prox_{f}(x) = x$

Projection Operator

投影算子

$$\begin{align*} proj_C(x) & = \arg\min_{y \in C} \|y - x\|^2 \\ & = \arg\min_{y \in R^N} l_C(x) + \frac 1 2 \|y-x\|^2 \end{align*}$$

• 点$x$在凸集$C$上的投影：$X$上距离$x$的欧式距离最近的点

Alternating Projection Method

POCS/project onto convex sets method：用于解同时满足多个 凸约束的算法

• $f_i$作为非空闭凸集$C_i$示性函数，表示一个约束，则整个 问题约简为convex feasibility problem

• 只需要找到位于所有$C_i$交集的解即可

• 每次迭代

  $$x^{(k+1)} = P_{C_1}P_{C_2} \cdots P_{C_n}x_k$$

• 在其他问题中投影算子不再适合，需要更一般的算子，在其他 各种同样的凸投影算子中，近端算子最合适

Proximal Gradient Method

近端算法：分两步分别优化可微凸$F(x)$、凸$R(x)$，近似优化目标 函数整体，不断迭代直至收敛

$$\min_{x \in \mathcal{H}}F(x) + R(x)$$

• $F(x)$：可微、凸函数
• $\nabla F(x)$：Lipschitz continous、利普希茨常数为$L$
• $R(x)$：下半连续凸函函数，可能不光滑
• $\mathcal{H}$：目标函数定义域集合，如：希尔伯特空间

• gredient step：从$x^{(k)}$处沿$F(x)$负梯度方向微小移动 达到$x^{(k.5)}$

  $$x^{(k.5)} = x^{(k)} - \gamma \nabla F(x^{(k)})$$

• proximal operator step：在$x^{(k.5)}$处应用$R(x)$近端 算子，即寻找$x^{(k.5)}$附近且使得$R(x)$较小点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k.5)})$$

目标函数推导

$$\begin{align*} prox_{\gamma R}(x - \gamma \nabla F(x)) & = \arg\min_u (R(u) + \frac 1 {2\gamma} \|u - x + \gamma \nabla F(x)\|_2^2) \\ & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + F(x) + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u - x\|_2^2) \\ & \approx \arg\min_u(R(u) + F(u)) \end{align*}$$

• $\frac {\gamma} 2 |\nabla F(x)|_2^2, F(x)$：与$u$无关 ，相互替换不影响极值
• $0 < \gamma \leq \frac 1 L$：保证最后反向泰勒展开成立

• 则$prox_{\gamma R}(x-\gamma \nabla F(x))$解即为 “原问题最优解”（若泰勒展开完全拟合$F(x)$）

  • 近端算法中距离微调项部分可加法分离
  • 若$R(x)$部分也可分离，则整个目标函数可以分离，可以 拆分为多个一元函数分别求极值

• 考虑泰勒展开是局部性质，$u$作为极小值点只能保证在$x$附近 领域成立，可将近端算子解作为下个迭代点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k)} - \gamma \nabla F(x^{(k)}))$$

• 迭代终止条件即

  $$\hat x = prox_{\gamma R}(\hat x - \gamma \nabla F(\hat x))$$

二阶近似证明

$$\begin{align*} F(u) & = F(x) + \nabla F(x)^T (u - x) + \frac 1 2 (u - x)^T \nabla^2 F(\zeta)(u - x) \\ & \geq F(x) + \nabla F(x)^T (u - x) \\ & \leq F(x) + \nabla F(x)^T (u - x) + \frac L 2 \|u-x\|^2 \end{align*}$$

• $\nabla^2 F(\zeta)$：凸函数二阶导正定
• $|\nabla F(u) - \nabla F(x)|_2 \leq L |u-x|_2$： $\nabla F(x)$利普希茨连续性质

参数确定

• $L$已知时，可直接确定$\gamma \in (0, \frac 1 L]$，

• 否则可线性迭代搜索$\gamma := \beta \gamma,\beta < 1$， 直至

  $$F(x - PG_{\gamma R}(x)) \leq F(x) - \nabla F(x) PG_{\gamma R}(x) + \frac 1 2 \|PG_{\gamma R}(x)\|_2^2$$

  • $PG{\gamma R}(x)=x-prox{\gamma R}(x-\gamma \nabla F(x))$
  • 直接根据下述利普希茨条件须求Hasse矩阵，计算量较大

反向推导

• 对$F(x)+R(x)$在$x_0$附近作泰勒展开

  $$F(u)+R(u) \leq F(x) + \nabla F(x)^T (u - x) + \frac 1 {2\gamma} \|u - x\|_2^2 + R(x)$$

  • $\lambda \in (0, \frac 1 L]$
  • $L$：$F(x)$利普希茨常数
  • $\leq$：由Lipschitz连续可取

  • 则不等式右边就是$F(x)+R(x)$的一个上界，可以对将对其 求极小化转化对此上界求极小

• 考虑对极小化目标添加常数项不影响极值，对不等式右侧添加 与$u$无关项$\frac \gamma 2 |\nabla F(x)|_2^2$、剔除 剔除$F(x)$凑出近端算子

  $$\begin{align*} prox_{\gamma R} & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + \|u - x + \frac 1 {2\gamma} \nabla F(x)\|_2^2) \end{align*}$$

近端算法推广

问题推广

• 求解non-differentiable凸优化问题的通用投影形式

$$\min_{x \in R^N} \sum_{i=1}^N f_i(x)$$

• $f_i(x)$：凸函数，不一定处处可微

• 目标函数中包含不处处连续可微函数，整个目标函数不光滑

  • 无法使用传统的光滑优化手段，如：最速下降、共轭梯度
  • 极小化条件为$0 \in \partial(F+R)(x)$

• 分开考虑各个函数，对非光滑函数使用近端算子处理

算子推广

• 考虑使用Bregman Divergence替代近端算子中欧式距离

$$prox_{\gamma, f}(x) = \arg\min_u (f(u) + \mu(u) - \mu(x) + <\nabla \mu(x), u - x>)$$

• 取$\mu(x) = \frac 1 2 |x|_2^2$时，即为普通近端算子

Legendre Transformation

勒让德变换：用 $f^{ * }(p)$ 表示凸、可导函数 $f(x)$ 的变换，其中 $p$ 是 $f(x)$ 导数

$$f^{*}(p) = p^T x - f(x)|_{\frac {d(p^T x - f(x))} {dx} = 0}$$

• $x$：参数，满足 $\frac {d(p^T x - f(x))} {dx} = 0$，随 $p$ 取值改变
• 可导：有导数；凸：导数唯一

• 勒让德变换是实变量的实值凸函数的对合变换
  • 把定义在线性空间上的函数变换至对偶空间的函数
  • 是点、（切）线之间对偶关系的应用
    • 严格凸函数中，切线、导数一一对应
    • 函数关系 $f(x)$ 可使用 $(x, y=f(x))$ 点集表示，也可用切线集合表示

• involution 对合：对合函数 $f$ 的反函数的为自身，即 $f(f(x))=x$；对合线性变换 $V$ 满足 $V^2 = E$

Legendre 变换理解（按 Fenchel 共轭）

• $f^{*}(p)$：可理解为斜率为 $p$、同 $f(x)$ 有交点 $x_0$ 的直线在零点处值（截距）和 $f(x_0)$ 的最大差

  

• $x$：可以理解为函数 $f(x)$ 上距离给定斜率为 $p$、过原点的直线 $f(x)=px$ 竖直距离最大的点

  

  • 类似一个端点为 $0$ 的 Bregman 散度

• Legendre 变换为对合变换，进行两次的变换得到原函数

  

  $$\begin{align*} f^{**}(x) & = \sup_{p \in dom(f^{*})} [x^T p - f^{*}(p)] \\ & = \sup_{u \in dom(f)}[x^T \nabla f(u) - \nabla f(u)^T u + f(u)] \\ & = \sup_{u \in dom(f)}[f(u) + \nabla f(u)^T (x-u)] \\ & = f(x) \end{align*}$$

• 若视凸函数 $f(x)$ 视为积分，则其共轭 $f^{ * }(x)$ 为对另一轴积分，二者导函数互为反函数

  $$f(x) + f^{*}(p) = xp, p = \frac {df(x)} {dx}$$

• 以上性质均按 Fenchel 共轭，但要求 $f(x)$ 为凸、可导函数，故等价于 Legendre 变换

Legendre 变换最大值式定义

$$\begin{align*} L(p, x) &= px - f(x) \\ \frac {\partial (px - f(x))} {\partial x} &= p - \frac {df(x)} {dx} = 0 \\ \Rightarrow & p = \frac {df(x)} {dx} \end{align*}$$

• Legendre 变换可以视为寻找 $px-f(x)$ 最大值（如前述）
  • $f(x)$ 为凸函数，则 $p=\frac {df(x)} {dx}$ 是最大值点
  • 则将 $f(x)$ 导函数的反函数 $x=f^{-1}(p)$ 带入即可

Legendre 变换数学性质

• 标度性质

  $$\begin{align*} f(x) & = a g(x) \rightarrow f^{*}(p) = a g^{*}(\frac p a) \\ f(x) & = g(ax) \rightarrow f^{*}(p) = g^{*}(\frac p a) \end{align*}$$

  由此，$r$次齐次函数的勒让德变换是$s$次齐次函数，满足

  $$\frac 1 r + \frac 1 s = s$$

• 平移性质

  $$\begin{align*} f(x) & = g(x) + b \rightarrow f^{*}(p) = g^{*}(p) - b f(x) & = g(x+y) \rightarrow f*^{*}(p) = g^{*}(p) - py \end{align*}$$

• 反演性质

  $$f(x) = g^{-1}(x) \rightarrow f^{*}(p) = -p g^{*}(\frac 1 p)$$

• 线性变换性质

  $$(Af)^{*} = f^{*}A^{*}$$

  • $f$：$R^n$上的凸函数
  • $A$：$R^n \rightarrow R^m$的线性变换
  • $A^{}: <Ax, y^{}> = $：$A$伴随算子

Fenchel Conjugate / 凸共轭

$$f^{*}(p) = \sup_{x \in R}{p^Tx - f(x)}$$

• Fenchel 共轭是对 Legendre 变换的扩展，不再局限于凸、可导函数
  • Fenchel 共轭可类似 Legendre 理解，但是适用范围更广
  • 对凸函数 Fenchel 共轭的共轭即为原函数，对非凸函数 Fenchel 共轭得到原函数凸包
  • 用罗尔中值定理描述极值、导数关系：兼容 Legendre 变换中导数支撑面

• 非凸函数线性外包络是凸函数

Fenchel-Young不等式

$$f(x) + f^{*}(p) \geq <p, x>$$

• 证明

  $$\begin{align*} f(x) + f^{*}(p) & = f(x) + \sup_{x \in dom(f)} {(x^T p - f(x))} \\ & \geq f(x) + x^T p - f(x) = x^T p \end{align*}$$

• 按积分理解，仅$p$为$x$共轭时取等号

  

Fenchel Conjugate 推导 Lagrange Duality

• 原问题 Prime

  $$\begin{align*} & \min {f(x)} \\ s.t. & g(x) \leq 0 \\ \end{align*}$$

• 约束条件 $g(x) \leq 0$ 扰动函数化、求 Fenchel 共轭

  $$\begin{align*} p(u) & = \inf_{x \in X, g(x) \leq u} f(x) \\ p^{*}(y) & = \sup_{y \in R^r} \{u^T y - p(u)\} \end{align*}$$

• 记 $\lambda = -y$，并将 $y=-\lambda$ 带入 $-p^{*}(y)$ 中得到

  $$\begin{align*} -p^{*}(y) & = \inf_{u \in R^r} \{p(u) - u^T y\} \\ d(\lambda) & = \inf_{u \in R^r} \{p(u) + u^T \lambda\} \\ & = \inf_{u \in R^r} \{\inf_{x \in X, g(x) \leq u} f(x) + \lambda^T u\} \end{align*}$$

  • $\lambda = -y$

• 将 $\inf_{x \in X, g(x) \leq u}$ 外提，并考虑到约束 $g(x) \leq u$（即 $u \geq g(x)$），则

  $$\begin{align*} \lambda \geq 0 & \Rightarrow \lambda^T g(x) \leq \lambda u \\ d(\lambda) & = \left \{ \begin{array}{l} \inf_{x \in X} \{f(x) + \lambda^T g(x)\}, & \lambda \geq 0 \\ -\infty, & otherwise \end{array} \right. \end{align*}$$

• 考虑 Fenchel 不等式

  $$\begin{align*} p(u) + p^{*}(-y) & \geq u^T (-y) \\ p(0) + p^{*}(-y) & \geq 0 \\ p(0) & \geq -p^{*}(-y) \\ p(0) & \geq d(\lambda) \end{align*}$$

• 则可得 Lagrange 对偶 Prime、Dual 最优关系

  $$L(x, \lambda) = f(x) + \lambda^T g(x), \lambda \geq 0 \\ D^{*} := \max_{\lambda \geq 0} \min_x L(x, \lambda) \leq \min_x \max_{\lambda \geq 0} L(x, \lambda) =: P^{*}$$

  

Lagrange Duality 推导 Fenchel 对偶

• Fenchel 对偶可以视为 Lagrange 对偶的应用

• 原问题、等价问题

  $$\begin{align*} & \min_x & f(x) - g(x) \\ \Leftrightarrow & \min_{x,z} & f(x) - g(z) \\ & s.t. & x = z \end{align*}$$

• 对上式取 Lagrange 对偶 $L(u)$、等价得到

  $$\begin{align*} L(u) &= \min_{x,z} f(x) - g(z) + u^T(z-x) \\ &= -(f^{*}(u) - g^{(-u)}) \end{align*}$$

• Fenchel 对偶：寻找截距差值最大的平行切线

Projected Gradient Descent

受限优化问题

$$\min_{x \in C} f(x)$$

• $C \subseteq R^d$：受限凸集

投影梯度下降：采用后处理的方式，将迭代位置拉回到约束条件内

• 使用一般下降算法进行位置更新，新位置$x_{t+1}^{‘}$可能 不再满足约束条件

• 为使新位置$x{t+1}^{‘}$符合受限集合，可以选择在$L_2$范数 下距离受限集合$C$最近的的点 $x{t+1}=\arg\min{x \in C} |x - x{t+1}^{‘}|$作为下步 真正迭代位置

线性约束

Projection Matrix

• 投影矩阵：矩阵$P \in R^{n*n}$，若满足$P^T = P, P^2 = P$
• 若$A \in R^{m*n}$为行满秩矩阵，则$A$的零空间为 $L_A = {x \in R^{n} | Ax = 0}$，对应正交空间为 $L_A^{\perp} = {A^T y | y \in R^m}$

对$\forall x \in R^n$进行正交分解

$$\begin{align*} \forall x \in R^n, x & = x_1 + x_2, x_1 \in L_A, x_2 \in L_A^{\perp} \\ x_1 & = P_A x \end{align*}$$

• $P_A = I - A^T (A A^T)^{-1} A$：$A$的投影矩阵
• 投影矩阵$P_A$可由点对线性约束的投影定义，利用拉格朗日 求解

证明

$$\begin{align*} x_1 & = x - x_2 = x - A^T y \\ A x_1 & = A x - A A^T y \\ \Rightarrow y & = (A A^T)^{-1} A (x - x_1) \\ \Rightarrow x_1 & = x - A^T[(A A^T)^{-1} A (x - x_1)] \\ & = x - A^T (A A^T)^{-1} A x - A^T (A A^T)^{-1} A x_1 \\ & = (I - A^T (A A^T)^{-1} A) x = P_A x \end{align*}$$

• 投影矩阵$P$对值应用多次线性变换和只应用一次结果相同， 保持像不变

Projection Operator

$$\begin{array}{l} \min & f(x) \\ s.t. & A_1 x \leq b_1 \\ & A_2 x = b_2 \end{array}$$

• 设$x^{k}$为当前迭代点，记$A{11}$、$A{12}$分别为紧、松 约束，即

  $$\begin{align*} A_1 & = \begin{bmatrix} A_{1,1} \\ A_{1,2} \end{bmatrix}, & b_1 & = \begin{bmatrix} b_{1,1} \\ b_{1,2} \end{bmatrix} \\ A_{1,1} x^k & = b_{1,1}, & A_{1,2} x^k & \leq b_{1,2} \end{align*}$$

• 记$M = [A_{1,1}^T, A_2^T]^T$，则$s \in L_M$时是可行方向

• 对负梯度$\nabla f(x^k)$，通过$M$的投影矩阵$P_M$将其投影 至$L_M$上即得可行下降方向$s^k = -P_M \nabla f(x^k)$

  • $s^k \neq 0$：为$x^k$处可行下降方向
  • $s^k = 0$：作如下讨论

投影方向为0

• 记$w = [u, v]^T = -(M M^T)^{-1}M \nabla f(x^k)$，则有

  $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + [A_{1,1}^T, A_2^T] \begin{bmatrix} u \\ v \end{bmatrix} \\ & = \nabla f(x^k) + A_{1,1}^T u + A_2^T v \end{align*}$$

• 若$u \geq 0$，则$x^{k}$是KKT点

  $$\nabla f(x^k) + A_{1,1}^T u + A_{1,2}^T v = 0 \Rightarrow x^k 为KKT点$$

• 否则若$u$中有负分量，可设$u0 < 0$，记$\bar M$为$M$中 去除对应列矩阵，则$\bar s^k = -P{\bar M}\nabla f(x^k)$ 为$x^k$可行下降方向

  • 先反证法证明$\bar s^k \neq 0$，若$\bar s^k = 0$

    $$\begin{align*} 0 & = \nabla f(x^k) - \bar M^T (\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \\ & = \nabla f(x^k) + \bar M^T \beta \\ \beta & = -(\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \end{align*}$$

    考虑到

    $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \end{align*}$$

    • $\alpha_0$：$M$中$u_0$对应行

    则有

    $$u_0 \alpha_0 + \bar M^T (\bar w - \beta) = 0$$

    与$M$行满秩条件矛盾，故$\bar s^k \neq 0$

  • 证明$\bar s^k$为下降方向

    $$\begin{align*} \nabla f(x^k)^T \bar s^k & = -\nabla f(x^k) P_{\bar M} \nabla f(x^k) \\ & = -\nabla f(x^k) P_{\bar M}^T P_{\bar M} \nabla f(x^k) \\ & = -\|P_{\bar M} \nabla f(x^k)\|_2^2 \leq 0 \end{align*}$$

  • 证明$\bar s^k$方向可行（满足约束）

    • 由$P{\bar M}$定义：$\bar M P{\bar M} = 0$，则

      $$\begin{align*} \bar M \bar s^k & = -\bar M \bar P_{\bar M} \nabla f(x^k) \\ & = \begin{bmatrix} \bar A_{1,1} \\ A_2 \end{bmatrix} \bar s^k = 0 \end{align*}$$

    • 则只需证明$\alpha_0^T \bar s^k < 0$

      $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \\ \Rightarrow & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k + \bar w^T \bar M \bar s^k \\ & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k \end{align*}$$

      考虑到$u_0 < 0$，则$\alpha_0^T \bar s^k < 0$

  • 即此时有紧约束变为松约束

算法

• 初始化：初始点$x^0$、$k=0$、精度参数$\epsilon > 0$

• 构造$M = [A_{1,1}^T, A_2^T]^T$

  • 若$M=0$（在可行域内），令$s^k = -\nabla f(x^k)$为 迭代方向
  • 否则令$s^k = -P_M \nabla f(x^k)$为迭代方向

• 若$|s^k|_2^2 \geq \epsilon$

  • 若$M$为空（无可下降方向），停止
  • 若$M$非空、$u > 0$，停止
  • 否则，构建$M = \bar M$继续

• 若$|s^k|_2^2 > \epsilon$，确定步长$\lambda_k$

  • 显然只需保证$A_2 x_k + \lambda_k A_2 d_k \leq b_2$ 即可

  • 若$A_2 d_k < 0$，则$\lambda_k$无约束，否则

    $$\lambda_k = \max \{\frac {(b_2 - A_2 x_k)_i} {(A_2 d_k)_i}\}$$

  • 即单纯型法中确定步长方法

• 得到新迭代点$x^{k+1} = x^k + \lambda_k s^k$、$k=k+1$

约束问题局部解

$$\begin{array}{l} \min & f(x), x \in R^n \\ s.t. & c_i(x) = 0, i \in E = \{1,2,\cdots,l\}, \\ & c_i(x) \leq 0, i \in I = \{l,l+1,\cdots,l+m\} \end{array}$$

• 对于一般约束优化问题，记其可行域为

  $$D = \{x| c_i(x) = 0, i \in E, c_i(x) \leq 0, i \in I\}$$

• 若 $\forall x^{} \in D, \exists \epsilon$，使得当 $x \in D, |x - x^{}| \leq \epsilon$ 时，总有

  $$f(x) \geq f(x^{*})$$

  则称$x^{*}$为约束问题的局部解，简称为最优解

• 若 $x \in D, 0 < |x - x^{*}| \leq \epsilon$ 时，总有

  $$f(x) > f(x^{*})$$

  则称$x^{*}$是约束问题的严格局部最优解

约束问题局部解一阶必要条件

定理1

• 设 $a_1,a_2,\cdots,a_m$ 和 $w \in R^n$，$C$ 定义如下 $$

    C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0,
    i=1,2,\cdots,m \}
  

  $$若 $w \notin C$，则存在超平面 $d^T w = 0$，分离 $C$ 和 $w$，即$$ \begin{align*}

    d^T w & \leq 0 \\
    d^T w & > 0
  

  \end{align*}$$

• 显然C是闭凸集，则$\exists d \in R^n, d \neq 0$， $\alpha \in R$，使得

  $$\begin{array}{l} d^T x \leq \alpha, & \forall x \in C \\ d^T w > \alpha & \end{array}$$

• 又C是锥，有$0 \in C$，所以$\alpha \geq 0$，即$d^T w > 0$

• 若$\exists \bar x \in C, d^T \bar x > 0$，则 $\forall \lambda \geq 0, \lambda \bar x \in C$，则有

  $$\lambda d^T \bar x \leq \alpha$$

  而$\lambda \rightarrow \infty$，左端趋于无穷，矛盾

Farkas引理

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下两个系统有且 仅有一个有解

  • 系统I：存在$d$满足 $$\begin{align*} a_i^T d & \leq 0, & i=1,2,\cdots,m \\ w^T d & > 0 \end{align*}$$
  • 系统II：存在非负常数$\lambda_1,\cdots,\lambda_m$使得 $$w =\sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统II有解，即存在$\lambda_1,…,\lambda_m$且 $\lambda_i \geq 0,i=1,2,\cdot,m$，使得

    $$w = \sum_{i=1}^m \lambda_i a_i$$

  • 若系统I有解，则有

    $$0 < w^T d = \sum_{i=1}^m \lambda_i a_i^T d \leq 0$$

    矛盾，因此系统I无解

• 若系统II无解，则系统I有解

  • 系统II误解，构造闭凸锥

    $$C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0, i=1,2,\cdots,m \}$$

    显然$w \notin C$

  • 由定理1，存在d满足

    $$\begin{array}{l} d^T x \leq 0, & \forall x \in C, \\ d^T w & > 0 \end{array}$$

• 此定理就是点要么在凸锥C内、边缘（系统II），要么在凸锥 外（系统I）

推论1

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下系统有且仅有 一个有解

  • 系统I：存在d满足 $$\begin{array}{l} a_i^T d \leq 0, & i=1,2,\cdots,m \\ d_j \geq 0, & j=1,2,\cdots,n \\ w^T d > 0 & \end{array}$$
  • 系统II：存在非负常数$\lambda_1,…,\lambda_m$使得 $$w \leq \sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统I有解，取d带入矛盾

• 若系统II无解，则系统I有解

  • 若系统I无解

    todo

推论2

• 设$a1,a_2,\cdots,a{l+m}$和$w \in R^n$，则以下两个系统 有且进一有一个存在解

  • 存在d满足 $$\begin{array}{l} a_i^T d = 0, & i=1,2,\cdots,l \\ a_i^T d \leq 0, & i=l+1,l+2,\cdots,l+m \\ w^T d > 0 \end{array}$$
  • 存在常数$\lambda1,\lambda_2,\cdots,\lambda{l+m}$ 且$\lambda_i \geq 0, i=l+1, l+2, \cdots, l+m$使得 $$w = \sum_{i+1}^{l+m} \lambda_i a_i$$

迭代求解

参数部分更新

参数部分更新：每次更新一个或一组待估参数

• 应用场合

  • 适合待估参数较少、同时估计较慢，待估参数较多可能更新 速度慢，往往需要多次迭代更新参数
  • 一般用在机器学习算法中比较多

• 特点（某些算法）

  • 良好的并行特性：能够同时更新多个参数

    • Alternating Direction Method of Multipliers

  • 采用贪心策略的算法：可能无法得到最优解

    • 前向回归
    • 深度学习：网络层次太深，有些算法采用固化部分 网络结构，估计剩余部分

  • 能够平衡全局、局部：得到较好的解

    • LARS

Langrangian Duality

拉格朗日对偶

• 考虑优化问题：找到$f(x)$满足约束的最好下界

  $$z^{*} = \min_{x} f(x) \\ \begin{align*} s.t. \quad & g_i(x) \leq 0, i=1,2,\cdots,m \\ & x \in X \end{align*}$$

• 考虑方程组

  $$\left \{ \begin{array}{l} f(x) < v \\ g_i(x) \leq 0, i=1,2,\cdots,m \end{array} \right.$$

  • 方程组无解：$v$是优化问题的一个下界

  • 方程组有解：则可以推出

    $$\forall \lambda \geq 0, \exists x, f(x) + \sum_{i=1}^m \lambda_ig_i(x) < v$$

    • 显然，取$g_1 + g_2 = 0, g_1(x) > 0$是反例，不能 推出原方程有解

  • 由以上方程组有解逆否命题：方程组无解充分条件如下

    $$\exists \lambda \geq 0, \min_{x} f(x) + \sum _{i=1}^m \lambda_ig_i(x) \geq v$$

• 由此方法推出的最好下界，即拉格朗日对偶问题

  $$v^{*} = \max_{\lambda \geq 0} \min_{x} f(x) + \sum_{i=1}^m \lambda_ig_i(x)$$

说明

• 拉格朗日对偶对实数域上的优化问题都存在，对目标函数、 约束函数都没有要求

• 强对偶定理：$v^{} = z^{}$，需要$f,g$满足特定条件才成立

  • 线性规划
  • 半正定规划
  • 凸优化

  • 即需要给约束条件加以限制，使得 $$\forall \lambda \geq 0, \exists x, f(x) + \sum_{i=1}^m \lambda_ig_i(x) < v$$ 是上述方程组有解的冲要条件

• 弱对偶定理：$v^{} \leq z^{}$，永远成立（以上即可证）

  • 通过弱对偶定理，可以得到原问题的一个下界
  • 对求解原问题有帮助，比如：分支界限法中快速求下界

• 对偶问题相关算法往往原问题算法在实际应用中往往更加有效

  • dual-simplex
  • primal-dual interior point method
  • augmented Lagrangian Method

原始问题

约束最优化问题

$$\begin{array}{l} \min_{x \in R^n} & f(x) \\ s.t. & c_i(x) \leq 0, i = 1,2,\cdots,k \\ & h_j(x) = 0, j = 1,2,\cdots,l \end{array}$$

Generalized Lagrange Function

• 引入Generalized Lagrange Function

  $$L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)$$

  • $x=(x_1, x_2, \cdots, x_n) \in R^n$
  • $\alpha_i \geq 0, \beta_j$：拉格朗日乘子

• 考虑关于x的函数

  $$\theta_P(x) = \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)$$

  • $P$：primal，原始问题

  • 若x满足原始问题的两组约束条件，则$\theta_P(x)=f(x)$

  • 若x违反等式约束j，取$\beta_j \rightarrow \infty$， 则有$\theta_P(x) \rightarrow \infty$

  • 若x违反不等式约束i，取$\alpha_i \rightarrow \infty$ ，则有$\theta_P(x) \rightarrow \infty$

  则有

  $$\theta_P(x) = \left \{ \begin{array}{l} f(x), & x 满足原始问题约束条件 \\ +\infty, & 其他 \end{array} \right.$$

• 则极小化问题，称为广义拉格朗日函数的极小极大问题

  $$\min_x \theta_P(x) = \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)$$

  与原始最优化问题等价，两问题最优值相同，记为

  $$p^{*} = \min_x \theta_P(x)$$

对偶问题

• 定义

  $$\theta_D (\alpha, \beta) = \min_x L(x, \alpha, \beta)$$

• 再考虑极大化$\theta_D(\alpha, \beta)$，得到广义拉格朗日 函数的极大极小问题，即

  $$\max_{\alpha, \beta: \alpha \geq 0} \theta_D(\alpha, \beta) = \max_{\alpha, \beta: \alpha \geq 0} \min_x L(x, \alpha, \beta)$$

  表示为约束最优化问题如下

  $$\begin{align*} \max_{\alpha, \beta} & \theta_D(\alpha, \beta) = \max_{\alpha, \beta} \min_x L(x, \alpha, \beta) \\ s.t. & \alpha_i \geq 0, i=1,2,\cdots,k \end{align*}$$

  称为原始问题的对偶问题，其最优值定义记为

  $$d^{*} = \max_{\alpha, \beta: \alpha \geq 0} \theta_D(\alpha, \beta)$$

原始、对偶问题关系

定理1

• 若原始问题、对偶问题都有最优值，则 $$d^{*} = \max_{\alpha, \beta: \alpha \geq 0} \min_x L(x, \alpha, \beta) \leq \min_x \max_{\alpha, \beta: \alpha \geq 0} L(x, \alpha, \beta) = p^{*}$$

• $\forall x, \alpha, \beta$有

  $$\theta_D(\alpha, \beta) = \min_x L(x, \alpha, \beta) \leq L(x, \alpha, \beta) \leq \max_{\alpha, \beta: \alpha \geq 0} = \theta_P(x)$$

  即

  $$\theta_D(\alpha, \beta) \leq \theta_P(x)$$

• 而原始、对偶问题均有最优值，所以得证

• 设$x^{}$、$\alpha^{}, \beta^{}$分别是原始问题、对偶 问题的可行解，且$d^{} = p^{*}$，则其分别是原始问题、 对偶问题的最优解