对称锥规划：对称锥的增广拉格朗日乘子法（Semi-Smooth Newton Method解无约束优化子问题）

基础预备：

凸优化学习笔记（一）

约束优化：PHR-ALM 增广拉格朗日函数法

对称锥规划：锥与对称锥

对称锥的增广拉格朗日函数

从前面文章的分析中我们已经知道，对于一般优化问题，都可以使用PHR-ALM进行求解，那能否使用该方法求解对称锥规划问题呢？答案是否定的。因为在一般优化问题中，PHR-ALM中的增广项应该是凸且可微的，而对于锥规划的不等式约束，例如 $K=Qn={(x0,x1)T∈R×Rn−1∣x0≥∥x1∥2}\mathcal{K}=\mathcal{Q}^n=\left\{\left(x_0, x_1\right)^{\mathrm{T}} \in \mathbb{R} \times \mathbb{R}^{n-1} \mid x_0 \geq\left\|x_1\right\|_2\right\}$ ，若采用PHR-ALM直接构造 $g(x)=∥x1∥2−x0≤0g(x)=\|x_1\|_2-x_0 \leq 0$ ，那么增广项 $∥max⁡[g(x),0]∥2\left\|\max \left[g(x), 0\right]\right\|^2$ 是不可微的，会对无约束优化子问题的收敛速率和求解造成困难。

对于不等式约束 $\leq 0$ 也即 $\leq 0$ 而言，引入松弛变量 $s]^2$ 可将不等式约束转换成等式约束 $Ax+b+[s]^2=0$ 。利用该思想，换一种思路将不等式约束 $\leq 0$ 写成 $\geq 0$ ，结合前面关于Nonnegative Orthant的理解， $\in \mathcal{K}_i=\mathbb{R}_{\geq 0}^n$ ，可将普通的仿射不等式约束写成对称锥约束的形式。结合欧几里得若当代数可将对称锥写成一个平方操作，因此 $R≥0n\mathbb{R}^n_{\geq 0}$ 可用 ${x2:=x∘x∣x∈Rn}\left\{x^2:=x \circ x \mid x \in \mathbb{R}^n\right\}$ 平方操作替代，故可引入松弛变量 $s]^2$ 将 $R≥0n\mathbb{R}^n_{\geq 0}$ 写成等式约束。

核心思想是将对称锥约束写成广义不等式 $Aix+bi∈KiA_i x+b_i \in \mathcal{K}_i$ ，并不需要将 $Ki\mathcal{K}_i$ 进行显式表达：
$Aix+bi∈Ki,i=1,…,mGx=h\begin{aligned} \min _{x \in \mathbb{R}^n} & \; c^{\mathrm{T}} x \\ \text { s.t. } & A_i x+b_i \in \mathcal{K}_i, i=1, \ldots, m \\ & G x=h \end{aligned}$
直接引入 $si∘si∈Kis_i \circ s_i \in \mathcal{K}_i$ 将广义不等式写成等式形式：
$Aix+bi=si∘si,i=1,…,mGx=h\begin{array}{ll} \min _{x, s} & c^{\mathrm{T}} x \\ \text { s.t. } & A_i x+b_i=s_i \circ s_i, i=1, \ldots, m \\ & G x=h \end{array}$
套PHR-ALM将对称锥约束的增广拉格朗日函数写为：
$Lρ(x,s,λ,ν):=cTx+ρ2∥Gx−h+λρ∥2+ρ2∑i=1m∥Aix+bi−si∘si+νiρ∥2\mathcal{L}_\rho(x, s, \lambda, \nu):=c^{\mathrm{T}} x+\frac{\rho}{2}\left\|G x-h+\frac{\lambda}{\rho}\right\|^2+\frac{\rho}{2} \sum_{i=1}^m\left\|A_i x+b_i-s_i \circ s_i+\frac{\nu_i}{\rho}\right\|^2$
因为 $min⁡x,sLρ(x,s,λ,ν)=min⁡xmin⁡sLρ(x,s,λ,ν)\min _{x, s} \mathcal{L}_\rho(x, s, \lambda, \nu)= \min _{x} \min_s \mathcal{L}_\rho(x, s, \lambda, \nu)$ ，那么解无约束优化子问题的第一步就是解 $min⁡sLρ(x,s,λ,ν)\min_s \mathcal{L}_\rho(x, s, \lambda, \nu)$ 以消除引入的松弛变量 $s_i$ ：
$min⁡sLρ(x,s,λ,ν)=cTx+ρ2∥Gx−h+λρ∥2+ρ2∑i=1mmin⁡si∥Aix+bi−si∘si+νiρ∥2\min _s \mathcal{L}_\rho(x, s, \lambda, \nu)=c^{\mathrm{T}} x+\frac{\rho}{2}\left\|G x-h+\frac{\lambda}{\rho}\right\|^2+\frac{\rho}{2} \sum_{i=1}^m \min _{s_i}\left\|A_i x+b_i-s_i \circ s_i+\frac{\nu_i}{\rho}\right\|^2$
而核心是解 $min⁡si∥Aix+bi−si∘si+νiρ∥2\min _{s_i}\left\|A_i x+b_i-s_i \circ s_i+\frac{\nu_i}{\rho}\right\|^2$ 。令 $v=Aix+bi+νiρv=A_i x+b_i+\frac{\nu_i}{\rho}$ ，则 $min⁡s∥v−si∘si∥2=min⁡x∈K∥v−x∥2\min _s\left\|v-s_i \circ s_i\right\|^2=\min _{x \in \mathcal{K}}\|v-x\|^2$ ，这就是一个正交投影（最佳逼近）问题，在对称锥约束 $K\mathcal{K}$ 中找到一个 $x$ 使得 $v$ 和 $x$ 之间的距离最短，而最优的 $x$ 就是 $v$ 在锥 $K\mathcal{K}$ 上的投影，将其写为： $PK(v):=arg⁡min⁡x∈K∥v−x∥2P_{\mathcal{K}}(v):=\arg \min _{x \in \mathcal{K}}\|v-x\|^2$ 。如下图所示，利用对称锥的谱分解可求出 $v$ 在锥 $K\mathcal{K}$ 上的投影：
$PK(v=∑i=1θλiqi)=∑i=1θmax⁡[λi,0]qiP_{\mathcal{K}}\left(v=\sum_{i=1}^\theta \lambda_i q_i\right)=\sum_{i=1}^\theta \max \left[\lambda_i, 0\right] q_i$
在这里插入图片描述

对于Nonnegative Orthant和SOCP，利用谱分解求锥上的投影：

利用显式投影算子，我们可以得到：
$min⁡s∥v−si∘si∥2=∥v−PK(v)∥2\min _s\left\|v-s_i \circ s_i\right\|^2=\left\|v-P_{\mathcal{K}}(v)\right\|^2$
如下图所示，黄色虚线向量表示 $v−PK(v)v-P_{\mathcal{K}}(v)$ ，且 $v−PK(v)⊥PK(v)v-P_{\mathcal{K}}(v) \bot P_{\mathcal{K}}(v)$ ，根据对称性有 $v−PK(v)=−[−v−P−K(−v)]=v+P−K(−v)v-P_{\mathcal{K}}(v)=-[-v-P_{\mathcal{-K}}(-v)]=v+P_{\mathcal{-K}}(-v)$ ，其中 $P−K(−v)P_{\mathcal{-K}}(-v)$ 表示 $- v$ 投影到 $−K\mathcal{-K}$ 上。又将 $- v$ 投影到锥 $K\mathcal{K}$ 上可得到绿色实线向量 $PK(−v)P_{\mathcal{K}}(-v)$ ，此时灰色虚线、黄色虚线、粉红实线和绿色实线构成了一个长方形，因此 $PK(−v)=v+P−K(−v)P_{\mathcal{K}}(-v)=v+P_{\mathcal{-K}}(-v)$ ，由此推出 $v−PK(v)=PK(−v)v-P_{\mathcal{K}}(v)=P_{\mathcal{K}}(-v)$ ，这样我们可以得到更为简洁的形式：
$min⁡s∥v−si∘si∥2=∥PK(−v)∥2\min _s\left\|v-s_i \circ s_i\right\|^2=\left\|P_{\mathcal{K}}(-v)\right\|^2$
在这里插入图片描述

将上式带入原对称锥的增广拉格朗日函数中，可得到：
$min⁡sLρ(x,s,λ,ν)=cTx+ρ2∥Gx−h+λρ∥2+ρ2∑i=1m∥PKi(−Aix−bi−νiρ)∥2\min _s \mathcal{L}_\rho(x, s, \lambda, \nu)=c^{\mathrm{T}} x+\frac{\rho}{2}\left\|G x-h+\frac{\lambda}{\rho}\right\|^2+\frac{\rho}{2} \sum_{i=1}^m\left\|P_{\mathcal{K}_i}\left(-A_i x-b_i-\frac{\nu_i}{\rho}\right)\right\|^2$
可看出最小化后的增广拉格朗日函数与松弛变量 $s_i$ 无关。为了表达上的便捷性，我们令 $μ=−ν\mu=-\nu$ ，最终可得推导得到与上式等价的对称锥增广拉格朗日函数为：
$Lρ(x,λ,μ):=cTx+ρ2{∥Gx−h+λρ∥2+∑i=1m∥PKi(μiρ−Aix−bi)∥2}\mathcal{L}_\rho(x, \lambda, \mu):=c^{\mathrm{T}} x+\frac{\rho}{2}\left\{\left\|G x-h+\frac{\lambda}{\rho}\right\|^2+\sum_{i=1}^m\left\|P_{\mathcal{K}_i}\left(\frac{\mu_i}{\rho}-A_i x-b_i\right)\right\|^2\right\}$
对该函数的增广项进行分析，令 $ρ=1,μ=0,b=0,A=I\rho=1,\mu=0,b=0,A=I$ ，则 $ρ2∥PK(μρ−Ax−b)∥2=12∥PK(−x)∥2=12∥x−PK(x)∥2\frac{\rho}{2}\left\|P_{\mathcal{K}}\left(\frac{\mu}{\rho}-A x-b\right)\right\|^2=\frac{1}{2}\left\|P_{\mathcal{K}}(-x)\right\|^2=\frac{1}{2}\left\|x-P_{\mathcal{K}}(x)\right\|^2$ ，该惩罚项实际上惩罚的是 $x$ 到锥 $K\mathcal{K}$ 的欧氏距离的平方，是可微且凸的，如下图所示。综上所述，相比于直接构造 $g(x)=∥x1∥2−x0≤0g(x)=\|x_1\|_2-x_0 \leq 0$ 的方式，利用对称锥的欧几里得若当代数和谱分解性质可以提供一个可微且凸的增广项，降低了后续无约束优化子问题的求解难度。

算法迭代过程中的参数更新和终止条件如下图所示，其中内层无约束优化子问题的终止条件与一般优化问题的PHR-ALM一样。

Semi-Smooth Newton Method半光滑牛顿法

对称锥的ALM算法第一步就是求解一个无约束优化子问题 $argmin⁡xLρ(x,λ,μ)\operatorname{argmin}_x \mathcal{L}_\rho(x, \lambda, \mu)$ ，从前面的分析已知 $Lρ(x,λ,μ)\mathcal{L}_\rho(x, \lambda, \mu)$ 凸且一阶可微但二阶不连续（梯度函数分片连续但边界处不连续），如下图所示。该函数的Hessian矩阵只能在梯度分片连续的地方求解出来，在不连续的边界处无法求解。使用一些一阶算法（梯度下降、拟牛顿法等）也可以，但收敛到高精度解往往很慢。要想更快的收敛速度，可以考虑牛顿方法，但牛顿方法要求Hessian矩阵存在且无法保证全局收敛性。在这里，针对不可微问题，我们引入具有全局收敛性的半光滑牛顿法（Semi-Smooth Newton Method）。

广义雅可比

半光滑性

半光滑牛顿算法

半光滑性可保证牛顿型算法在迭代过程中具有局部超线性收敛（local superlinear convergence）或者局部二次收敛（local quadratic convergence）。对称锥增广拉格朗日的梯度是分段C2的，因此它是强半光滑的，通过对 $\in \partial_B \nabla_x \mathcal{L}_\rho(x, \lambda, \rho)$ 进行微小摄动保证正定性，我们可以计算出下面的半光滑牛顿步长 $d$ 来进行无约束优化。