最优化之 NExOS 方法

2022-01-12

很多非凸优化方法研究的问题，都是凸集上的非凸函数最小化。然而，实际中，问题的非凸性可能不来自于目标函数，而是来自于约束函数。最近，文献 [1] 提出了 Nonconvex Exterior-point Optimization Solver (NExOS) ，用于解决非凸集上的凸函数最小化问题，其可能在无线通信的一些场景中发挥作用。

目标问题

考虑凸函数在非凸约束下的最小化问题：

\[\min_ {\mathbf{x}\in\mathcal{X}}\;f(\mathbf{x})+\frac{\beta}{2}\lVert\mathbf{x}\rVert^2,\tag{1}\]

其中，$f(\mathbf{x})$ 为凸函数（正则化项 $\frac{\beta}{2}\lVert\mathbf{x}\rVert^2$ 是文献为了收敛性证明所额外引入的，实际 $\beta$ 可取一很小值，如 $10^{-8}$）；可行域 $\mathcal{X}$ 为一闭集，可能非凸，但满足在局部最优点处具有 Prox-regular 性质：集合 $\mathcal{X}$ 在点 $\mathbf{x}\in\mathcal{X}$ 处是 Prox-regular 的，当其在 $\mathbf{x}$ 邻域内的投影具有单值（singleton）。Prox-regular 集可被视为闭凸集的一种弱化（到闭凸集的投影一定是单值的）。

文章考虑了两种 Prox-regular 非凸集：

矩阵低秩约束，$\mathcal{N}=\{\mathbf{X}\in\mathbb{R}^{m\times n}\mid \mathrm{rank}(\mathbf{X})\leq k\}$.
矢量稀疏约束，$\mathcal{N}=\{\mathbf{x}\in\mathbb{R}^n\mid\lVert\mathbf{x}\rVert_ 0\leq k\}$.

注意，Prox-regular 集和有界闭凸集的交集会继承 Prox-regular 性质，也就是说，问题 (1) 中除约束 $\mathcal{N}$ 外，还可以包含其它凸约束。

NExOS 方法

1. 问题转化

首先，引入集合 $\mathcal{X}$ 的示性函数 $\iota(\mathbf{x})$，其当 $\mathbf{x}\in\mathcal{X}$ 时取 $0$，否则取 $+\infty$。问题 (1) 可以表示为无约束的形式：

\[\min_ {\mathbf{x}}\;f(\mathbf{x})+\frac{\beta}{2}\lVert\mathbf{x}\rVert^2+\iota(\mathbf{x}).\tag{2}\]

为了处理 $\iota(\mathbf{x})$ 的非凸性，进一步将 $\iota(\mathbf{x})$ 替换为其 Moreau 包络：

\[{}^\mu\iota(\mathbf{x})=\min_ {\mathbf{y}}\;\iota(\mathbf{y})+\frac{1}{2\mu}\lVert\mathbf{y}-\mathbf{x}\rVert^2\\ =\min_ {\mathbf{y}\in\mathcal{X}}\;\frac{1}{2\mu}\lVert\mathbf{y}-\mathbf{x}\rVert^2=\frac{1}{2\mu}d^2(\mathbf{x}),\tag{3}\]

其中，$d(\mathbf{x})$ 点 $\mathbf{x}$ 到集合 $\mathcal{X}$ 的欧氏距离函数。相比于 $\iota(\mathbf{x})$，函数 ${}^\mu\iota(\mathbf{x})$ 具有性质：

${}^\mu\iota(\mathbf{x})\leq\iota(\mathbf{x}),\,\forall\mathbf{x}$；
$\lim_ {\mu\rightarrow 0}{}^\mu\iota(\mathbf{x})=\iota(\mathbf{x})$；
$\forall\beta>0$，${}^\mu\iota(\cdot)+\frac{\beta}{2}\lVert\cdot\rVert^2$ 在局部最优点的邻域内是凸可导函数，且此邻域的大小随 $\mu$ 的增大而单调扩大。

从而，可以获得问题 (2) 的一个渐近精确近似：

\[\mathcal{P}_ \mu:\;\;\min_ \mathbf{x}\;f(\mathbf{x})+\underbrace{\frac{\beta}{2}\lVert\mathbf{x}\rVert^2+{}^\mu\iota(\mathbf{x})}_ {g_ \mu(\mathbf{x})}.\tag{4}\]

由此，通过逐次求解子问题 $\mathcal{P}_ \mu$，随着 $\mu$ 的减小，最终逼近原问题 (1) 的（局部）最优解。Algorithm 1 给出了 NExOS 算法的全貌：

Nonconvex Exterior-point Optimization Solver (NExOS)

其中，$\pmb{\Pi}$ 表示到可行域 $\mathcal{X}$ 的投影算子，即 $\pmb{\Pi}(\mathbf{x})=\mathrm{prox}_ {\mu\iota}(\mathbf{x})=\arg\min_ {\mathbf{x}}{}^\mu\iota(\mathbf{x})=\arg\min_ {\mathbf{x}\in\mathcal{X}}\;\lVert\mathbf{y}-\mathbf{x}\rVert^2$，终止条件表示 $\mathcal{P}_ \mu$ 的目标函数足够接近原始的目标函数。

单纯从形式上看，NExOS 算法其实就是一种外点罚函数法（惩罚函数 $\mu\beta\lVert\cdot\rVert^2+d^2(\cdot)$，罚因子 $\frac{1}{2\mu}$ ）。其优势在于，通过利用可行域的 Prox-regular 性质，Algorithm 1 保证了：

子问题 $\mathcal{P}_ \mu$ 的目标函数在其最优点附近是局部强凸且光滑的。
迭代过程具有递归收敛性，即（在很温和的条件下，）$\mathbf{z}^ 0:=\mathbf{z}_ \mu$ 落在子问题 $\mathcal{P}_ {\rho\mu}$ 满足凸且光滑的区域内。

2. 算法实现

无约束子问题 $\mathcal{P}_ \mu$ 可以使用邻近分裂方法（Proximal Splitting Method）进行求解，文章使用了 Douglas-Rachford 分裂算法^[2]：

\[\mathbf{0}\in\gamma\partial(f+g_ \mu)(\mathbf{x})=\gamma\partial f(\mathbf{x})+\gamma\partial g_ \mu(\mathbf{x})\;\Rightarrow\;\begin{cases} \mathbf{x}:=\mathrm{prox}_ {\gamma f}(\mathbf{z})\\ \mathbf{y}:=\mathrm{prox}_ {\gamma g_ \mu}(2\mathbf{x}-\mathbf{z})\\ \mathbf{z}:=\mathbf{z}+\mathbf{y}-\mathbf{x} \end{cases}\,.\tag{5}\]

代入 $g_ \mu(\cdot)=\frac{\beta}{2}\lVert\cdot\rVert^2+{}^\mu\iota(\cdot)$，并利用 $\mathrm{prox}_ {\gamma g_ \mu}(\mathbf{x})=\kappa\theta\mathbf{x}+(1-\theta)\pmb{\Pi}(\kappa\mathbf{x})$，其中 $\kappa=\frac{1}{\beta\gamma+1}$ 和 $\theta=\frac{\mu}{\gamma\kappa+\mu}$，即得到求解子问题 $\mathcal{P}_ \mu$ 的 Algorithm 2，如下所示：

Inner algorithm for solving Pu

其中，$\pmb{\Pi}$ 表示到可行域 $\mathcal{X}$ 的投影算子，即 $\pmb{\Pi}(\mathbf{x})=\arg\min_ {\mathbf{x}\in\mathcal{X}}\;\lVert\mathbf{y}-\mathbf{x}\rVert^2$，利用 $\mathcal{X}$ 的 Prox-regular 性质，$\pmb{\Pi}(\mathbf{x})$ 在局部最优点附近具有单值。对于充分大的 $\mu$，容易找到初始点 $\mathbf{z}^ 0$ 落在 $\mathcal{P}_ \mu$ 满足强凸且光滑的区域内，因此 Algorithm 2 线性收敛到 $\mathcal{P}_ \mu$ 的局部最优解。

Algorithm 2 的主要操作在于计算两个邻近算子 $\mathrm{prox}_ {\gamma f}$ 和 $\pmb{\Pi}=\mathrm{prox}_ {\gamma\iota}$。对于后者，文章考虑的两种非凸约束都对应闭式的投影算子：

$\mathcal{N}=\{\mathbf{X}\in\mathbb{R}^{m\times n}\mid \mathrm{rank}(\mathbf{X})\leq k,\,\lVert\mathbf{X}\rVert_ 2\leq M\}$，有 $\pmb{\Pi}_ {\mathcal{N}}(\mathbf{X})=\mathbf{U\tilde{\pmb{\Sigma}}\mathbf{V}^{\mathrm{T}}}$，其中， $\mathbf{X}=\mathbf{U}\pmb{\Sigma}\mathbf{V}$ 是矩阵 $\mathbf{X}$ 的奇异值分解（SVD），$\tilde{\Sigma}_ {ii}=\min{\Sigma_ {ii},M},i=1,\cdots,k;\;\tilde{\Sigma}_ {ii}=0,i>k$。
$\mathcal{N}=\{\mathbf{x}\in\mathbb{R}^n\mid\lVert\mathbf{x}\rVert_ 0\leq k\}$，有 $\pmb{\Pi}_ {\mathcal{N}}(\mathbf{x})={\mathbf{y}\mid y_ i=x_ i,i\in\mathcal{I}_ k(\mathbf{x});\;y_ i=0,i\notin\mathcal{I}_ k(\mathbf{x})}$，其中 $\mathcal{I}_ k(\mathbf{x})$ 是 $\mathbf{x}$ 的前 $k$ 个最大绝对值元素的指标集。

对于 $\mathrm{prox}_ {\gamma f}$，文章主要讨论主要是二次函数 $f(\cdot)$，其邻近算子具有闭式解；对于更一般的函数，可能需要进行数值计算（求解一个无约束凸优化问题）。如果函数 $f$ 是光滑的，一种可能的改进是使用 Forward-Backward 分裂算法^[2]求解 $\mathcal{P}_ \mu$——

\[\mathbf{0}\in\gamma\partial(f+g_ \mu)(\mathbf{x})=\gamma\nabla f(\mathbf{x})+\gamma\partial g_ \mu(\mathbf{x})\;\Rightarrow\;\begin{cases} \mathbf{x}:=\mathbf{z}-\gamma\nabla f(\mathbf{z})\\ \mathbf{y}:=\mathrm{prox}_ {\gamma g_ \mu}(\mathbf{x})\\ \mathbf{z}:=\mathbf{z}+\mathbf{y}-\mathbf{x} \end{cases}\,.\tag{6}\]

此时，Algorithm 2 的步骤 5 改为梯度下降：$\mathbf{x}^{n+1}:=\mathbf{z}^n-\gamma\nabla f(\mathbf{z}^n)$，即只需要计算 $\nabla f$。

通信问题中的（可能）应用

Transmit Beamforming for Physical-Layer Multicasting^[3]

\[\max_ {\mathbf{S}\succeq\mathbf{0}}\,\min_ {i}\;\mathrm{tr}\left(\mathbf{S}\frac{\mathbf{h}_ i\mathbf{h}_ i^\mathrm{H}}{\sigma^2_ 2}\right)\\ \mathrm{s.t.}\;\;\mathrm{tr}(\mathbf{S})\leq P,\qquad\quad\\ \mathrm{rank}(\mathbf{S})=1.\tag{7}\]

Rank-constrained MIMO capacity under per-antenna power constraints^[4]

\[\max_ {\mathbf{S}\succeq\mathbf{0}}\;\lvert\mathbf{I}_ M+\mathbf{H}\mathbf{S}\mathbf{H}^\mathrm{H}\rvert\\ \mathrm{s.t.}\;[\mathbf{S}]_ {ii}\leq p_i,\quad\;\\ \quad\mathrm{rank}(\mathbf{S})\leq r.\tag{8}\]

Rank-Constrained Noncooperative Game in $K$-Pair MIMO Interference Networks^[5]

\[\max_ {\mathbf{S}_ j\succeq\mathbf{0},\forall j}\;\;\lvert\mathbf{I}_ {M_ j}+\mathbf{H}_ {jj}\mathbf{S}_ j\mathbf{H}_ {jj}^\mathrm{H}\mathbf{R}_ j^{-1}\rvert\\ \mathrm{s.t.}\;\;\mathrm{tr}(\mathbf{S}_ j)\leq P_j,\qquad\;\;\\ \mathrm{rank}(\mathbf{S}_ j)\leq r_ j.\tag{9}\]