ABSTRACT

This article starts from the variational characterization of zero-norm, then changes such a combination optimization problem to an equivalent model which has bi-linear structure and global Lipschitz continuous. This article also designed multi-stage convex relaxation methods to solve the zero-norm regularized composite optimization problem, and analyzed the convergence for it.

Keywords:Zero-Norm Regularization, MPEC Problem, Exact Penalty, Multi-Stage Convex Relaxation

一类零模正则复合优化问题的多阶段 凸松弛法

吕佩雯

华南理工大学，广东 广州

收稿日期：2019年1月14日；录用日期：2019年1月26日；发布日期：2019年2月2日

摘 要

本文从零模函数的变分刻画入手，将这类带有组合性质的优化问题等价转化为具有拟双线性结构且全局Lipshitz连续的优化模型，以此设计了求解零模正则化复合优化问题的多阶段凸松弛方法，并对该方法进行了收敛性分析。

关键词 :零模正则化，MPEC问题，精确罚，多阶段凸松弛

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在过去几十年，高维回归在基因学、金融、图像处理、气候科学、传感器网络等领域有着广泛应用。经典的高维线性回归模型假设预测变量的维数n总是大于样本的数量m，尽管有效的预测变量的维数s总是远小于n的。零模正则化在统计、机器学习、信号与图像处理、稀疏模型选择和误差修正、金融工程及量子计算等领域中有着广泛的应用。这种非凸正则为稀疏恢复提供了一种有效的方法。然而，在高维的问题中却很难分析。

2. 零模正则复合优化问题

2.1. 零模正则问题

设 $R^n$ 是赋予了内积 $\langle \cdot ,\cdot \rangle$ 及诱导范数 $\Vert \cdot \Vert$ 的有限维向量空间。考虑零模正则规划：

(1)

其中 $\nu >0$ 是正则项系数， $\psi :R^m\to (-\infty ,+\infty ]$ 为连续可微强凸函数， $A:={\left[a_1^T,a_2^T,\cdots ,a_m^T\right]}^T\in R^{m\times n}$ 为设计矩阵， $c$ 为已知向量， $\mu >0$ 为任意小的常数， $x\in R^n$ 为系数向量， ${\Vert x\Vert }_0$ 为向量 $x$ 中非零元个数。该模型将为以后的逻辑回归研究作铺垫 [1] [2]。记，则函数 $f$ 是全局Lipschitz连续的，记其Lipschitz常数为 $L_f$ [3]。由于零模函数的不连续性和非凸性质，(1)这种问题通常是NP难的，难以求得其全局最优解。一个常用的处理方法是使用凸松弛技术，这种方法通过解一个或一系列在数值上易于处理的凸优化问题来产生一个理想的局部最优解或至少一个可行解。

2.2. 零模问题的等价Lipschitz替代

本文将从问题(1)的等价MPEC问题和这个MPEC问题的全局精确罚问题中得到解估计 $\hat{x}$ ，并证明 $\hat{x}$ 可以通过求解一个精确罚问题得到。令 $\Phi$ 代表闭适当凸函数 $\phi :R\to (-\infty ，+\infty ]$ 且 $\left[0,1\right]\subseteq \mathrm{int}\left(dom\varphi \right)$ 的函数

族，其中 $\varphi$ 满足下面的条件： $\varphi \left(1\right)=1$，$1>t^{\ast }：=\underset{0\le t\le 1}{\arg \min }\varphi \left(t\right)$，且这样的 $t^{\ast }$ 是唯一的。

令 $\bar{t}$ 为 ${\left(\partial \varphi \right)}^{-1}\left(\frac{1}{1-t^{\ast }}\right)\cap [t^{\ast },1)$ 中的最小元素，由下面引理(参考文献 [4] 引理5)可知这样的 $\bar{t}$ 存在：

引理1：令 $\varphi \in \Phi$ ，存在 $$ 使得 $$ ，且对任意给定的 $\omega \ge 0$ 和 $\rho >0$ ，最优值 $v^{\ast }:=\underset{t\in \left[0,1\right]}{\min }\{\varphi \left(t\right)+\rho \omega \left(1-t\right)\}$ 满足：

$\{\begin{array}{cc}\begin{array}{l}{v}^{\ast }=1,\\ v^{\ast }\ge \frac{\rho \omega \left(1-t_0\right)}{{{\varphi }^{\prime }}_{-}\left(1\right)\left(1-t^{\ast }\right)},\\ v^{\ast }\ge \rho \omega \left(1-t_0\right),\end{array}& \begin{array}{l}若\rho \omega \in \left({{\varphi }^{\prime }}_{-}\left(1\right),+\infty \right);\\ 若\rho \omega \in \left[\frac{1}{1-t^{\ast }},{{\varphi }^{\prime }}_{-}\left(1\right)\right];\\ 若\rho \omega \in \left[0,\frac{1}{1-t^{\ast }}\right).\end{array}\end{array}$

下面将说明对任意 $\varphi \in \Phi$ ，问题(1)可以重写为一个等价MPEC问题。不难验证：对任意给定的 $x\in R^n$ 和 $\varphi \in \Phi$，

${\Vert x\Vert }_0=\underset{\theta \in R^n}{\min }\left\{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\varphi \left({\theta }_i\right)}:{\Vert x\Vert }_1-\langle \theta ,\left|x\right|\rangle =0,0\le \theta \le e\right\}$ (2)

因此问题(1)等价于：

$\underset{x\in R^n,\theta \in R^n}{\min }\left\{\nu f\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}\varphi \left({\theta }_i\right):\langle e-\theta ,\left|x\right|\rangle =0,0\le \theta \le e}\right\}$ (3)

假设问题(1)有非空全局最优解集且最优值为 ${\varpi }^{\ast }$ ，由文献 [4] 可得如下引理：

引理2：令 $\varphi \in \Phi$ ，零模正则问题(1)等价于问题(3)。当 $x^{\ast }$ 是问题(1)的全局最优解时， $\left(x^{\ast },\max \left(sign\left(\left|x^{\ast }\right|\right),t^{\ast }e\right)\right)$ 是问题(3)的全局最优解且最优值等于 ${\varpi }^{\ast }$ ；相反的，若 $\left(x^{\ast },{\theta }^{\ast }\right)$ 是问题(3)的全局最优解，那么 $x^{\ast }$ 是问题(1)的全局最优解且 ${\Vert x^{\ast }\Vert }_0={\displaystyle {\sum }_{i=1}^n\varphi \left({\theta }_i^{\ast }\right)}$。

问题(3)的可行集中包含着如下互补约束： $e-\theta \ge 0$，$\left|x\right|\ge 0$ 且 $\langle e-\theta ,\left|x\right|\rangle =0$。这说明零模正则化问题也是一个带有互补约束的数学规划问题(MPEC)，但是MPEC在优化中也是一类很难的问题。虽然(3)的目标函数比原问题(1)简单，但却含有非凸互补约束 $\langle e-\theta ,\left|x\right|\rangle =0$ ，这将比非凸目标函数更难处理。为解决这个非凸约束，考虑问题(3)的罚问题：

$\underset{x\in R^n,\theta \in \left[0,e\right]}{\min }\{vf\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}[\varphi \left({\theta }_i\right)}+\rho \left(1-{\theta }_i\right)\left|x_i\right|]\}$ (4)

其中 $\rho >0$ 是罚参数。下面的定理将说明问题(4)是问题(3)的全局精确罚，即它们有相同的全局最优解集 [4]。

定理1：令 $\varphi \in \Phi$。对所有 $\rho >\bar{\rho }=v{L}_f\frac{\left(1-t^{\ast }\right){{\varphi }^{\prime }}_{-}\left(1\right)}{1-\bar{t}}$ ，有 $S_{\rho }^{\ast }=S^{\ast }$。这里 $S_{\rho }^{\ast }$ 是与 $\rho$ 相关的问题(4)的全局最优解集， $S^{\ast }$ 是问题(3)的全局最优解集。

由定理1，零模正则问题(1)的解估计量 $\hat{x}$ 可在 $\rho >\bar{\rho }$ 时，由求解问题(4)得到，即：

$\left(\hat{x},\hat{\theta }\right)\in \underset{x\in R^n,\theta \in \left[0,e\right]}{\min }\{vf\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}[\varphi \left({\theta }_i\right)}+\rho \left(1-{\theta }_i\right)\left|x_i\right|]\}$ ，其中 $\rho >\bar{\rho }$。 (5)

由于 $\left[0,1\right]\subseteq \mathrm{int}\left(dom\phi \right)$ ，函数 $$ 在 $\left[0,e\right]$ 上是Lipschitzian连续的，所以问题(5)在其可行集 $$ 上也是Lipschitzian连续的。对任意 $\varphi \in \Phi$ ，定义相应的函数 $\varphi :=R\to (-\infty ,+\infty ]$ ：若 $$，$\phi \left(t\right)=\varphi \left(t\right)$ ；若 $t\notin \left[0,1\right]$，$\phi \left(t\right)=+\infty$。问题(5)可以重新写为更简便的形式：

$\underset{x\in R^n,\theta \in R^n}{\min }\{vf\left(x\right)+\rho {\Vert x\Vert }_1+{\displaystyle \underset{i=1}{\overset{n}{\sum }}[\varphi \left({\theta }_i\right)}-\rho {\theta }_i\left|x_i\right|]\}$。

由共轭函数的定义和以上讨论，可以得到：

$\hat{x}\in \underset{x\in R^n}{\arg \min }\left\{vf\left(x\right)+\rho {\Vert x\Vert }_{\text{1}}-{\displaystyle \underset{\text{i}=\text{1}}{\overset{\text{n}}{\sum }}{\phi }^{\ast }\left(\rho \left|x_i\right|\right)}\right\}$ ，其中 $\rho >\bar{\rho }$ (6)

这意味着下面的函数是 ${\Vert x\Vert }_0$ 的等价DC替代： $\Theta \left(x\right):=\rho {\Vert x\Vert }_1-{\displaystyle {\sum }_{i=1}^n{\phi }^{\ast }\left(\rho \left|x_i\right|\right)}$。

3. 多阶段凸松弛法

从上一节可知，求解零模正则化问题的解估计 $\hat{x}$ ，对于 $\varphi \in \Phi$ 且 $\rho >\bar{\rho }$ 时，可由求解罚问题(5)得到。当给定 $v>0$ 时，阀值 $\bar{\rho }>0$ 是容易计算得到的。对一个给定的 $\rho >\bar{\rho }$ ，虽然罚问题(5)是非凸的，但是这种结构使得它比零模正则化问题更好解决。特别的，当变量 $\theta$ 选定时，问题(5)退化为关于 $x$ 的凸的极小化问题；当变量 $x$ 选定时，问题(5)退化为关于 $\theta$ 的凸的极小化问题，后面将看到这样的问题是有闭式解的。基于此，本文将通过使用多阶段凸松弛法交替求解问题(5)来得到解估计 $\hat{x}$ [5]。

算法1. (GEP-MSCRA求解 $\hat{x}$ )

Step 0：取 $\varphi \in \Phi$，$v>0$ 和初始点 ${\theta }^0\in \left[0,\bar{t}e\right]$。置 $k:=1$。

Step 1：令 $v^{k-1}=e-{\theta }^{k-1}$ 并计算下面的极小化问题： $x^k\in \underset{x\in R^n}{\arg \min }\{f(x)+\lambda {\displaystyle {\sum }_{i=1}^n{v}_i^{k-1}\left|x_i\right|}\}$。 (7)

若 $k=1$ ，由 $x^1$ 的取值选取参数并使 $\lambda =\rho v^{-1}$。

Step 2：计算下面的极小化问题： ${\theta }^k\in \underset{\theta \in \left[0,e\right]}{\arg \min }\{{\displaystyle {\sum }_{i=1}^n\left[\varphi \left({\theta }_i\right)-\rho {\theta }_i\left|x_i^k\right|\right]}\}$。 (8)

Step 3：置 $k\leftarrow k+1$ ，返回(S. 1)步。

注1：由函数 $\phi$ 的定义， ${\theta }^k$ 是(8)的最优解当且仅当 ${\theta }_i^k\in \partial {\phi }^{\ast }\left(\rho \left|x_i^k\right|\right)$，$i=1,\cdots ,n$。由于 ${\phi }^{\ast }$ 是R上的凸函数，次微分 $\partial {\phi }^{\ast }\left(\rho \left|x_i^k\right|\right)$ 是容易求得的。因此，多阶段凸松弛法每次迭代的计算难度都在于解决问题(7)，即一个加权 $L_1-$ 范数正则化问题 [6] [7] [8]。这是一类凸优化问题，它可以通过标准的凸优化方法求解，比如：增广拉格朗日法，内点法 [9]，IRLS-LARS [10]，路径跟踪法，迭代加权最小二乘法等。对于多阶段凸松弛法，下面的命题(参考文献 [4] 注释3.1)说明一旦满足互补条件，迭代点 $x^k$ 就是原问题(1)的局部最优解。

命题1：对任意的 $k\ge 1$，$\left(x^k,{\theta }^k\right)$ 为算法1生成的迭代点。若 ${\displaystyle {\sum }_{i=1}^n\left(1-{\theta }_i^{k-1}\right)}\left|x_i^k\right|=0$ ，则 $x^k$ 是原问题(1)的局部最优解；且当 ${\displaystyle {\sum }_{i=1}^n\varphi \left({\theta }_i^{k-1}\right)}={\Vert x^k\Vert }_0$ 时，对于 $\rho >\bar{\rho }$，$\left(x^k,\max \left(sign\left(\left|x^k\right|\right),t^{\ast }e\right)\right)$ 是问题(5)的局部最优解。

4. 理论分析

这节内容主要关注在限制强凸条件下，针对 $f\left(x\right):=\psi \left(Ax\right)+\langle c,x\rangle +\frac{\mu }{2}{\Vert x\Vert }^2$ ，多阶段凸松弛法的收敛性分析。假设 $\bar{x}$ 是真实解，本文将建立迭代点 $x^k$ 到真实解 $$ 的误差界，并证明误差数列随着 $k$ 的增长是严格下降的。记 $\bar{S}:=\{i:{\bar{x}}_i\ne 0\}$，$\bar{r}=\left|\bar{S}\right|={\Vert \bar{x}\Vert }_0<n$ ，则 ${\bar{S}}^c:=\{i:{\bar{x}}_i=0\}$。对 $\bar{S}$ 和整数 $$ ，定义集合：

$C\left(\bar{S},l\right):=\{x\in R^n:\exists S\supseteq \bar{S}且\left|S\right|\le l,使得{\displaystyle {\sum }_{i\in S^c}\left|x_i\right|\le \frac{2}{1-\bar{t}}{\displaystyle {\sum }_{i\in S}\left|x_i\right|}}\}$。

若矩阵A满足：对任意 $x\in C$，$\frac{\alpha }{2}{\Vert Ax\Vert }^2\ge \kappa {\Vert x\Vert }^2$ 成立，则称矩阵A在集合 $C$ 上满足 $$ ，其中 $\kappa >0$。假设噪音向量 $\epsilon$ 中的元素是独立次高斯的，则下面的假设成立：

假设1：假设 ${\epsilon }_i\left(i=1,\cdots ,m\right)$ 是独立次高斯分布的，即：存在 $\sigma >0$ ，使得对所有 $i$ 和 $t\in R$，

$E\left[\exp \left(t{\epsilon }_i\right)\right]\le \exp \left(\frac{{\sigma }^2{t}^2}{2}\right)$。

为给出每一迭代步 $x^k$ 到真实解 $\bar{x}$ 的误差界，需要将参考文献 [4] 引理7,8拓展为下面一些引理：

引理3：对于 $k\ge 1$ ，记 ${\Delta }^k=x^k-\bar{x}$，$$。若存在一个指标集 $S^{k-1}\supseteq \bar{S}$ ，使得 $\underset{i\in {\left(S^{k-1}\right)}^c}{\min }{\theta }_i^{k-1}\le \bar{t}$ ，则当 $\lambda \ge \frac{\left(3-\bar{t}\right){\Vert \hat{\epsilon }\Vert }_{\infty }}{1-\bar{t}}$ 时，下式成立： ${\displaystyle \underset{i\in {\left(S^{k-1}\right)}^c}{\sum }\left|{\Delta }_i^k\right|}\le \frac{2}{1-\bar{t}}{\displaystyle \underset{i\in S^{k-1}}{\sum }\left|{\Delta }_i^k\right|}$。

证明：对于问题(7)， $$ 和 $\bar{x}$ 分别代表最优解和可行解，则有：

$\psi \left(A{x}^k\right)+\langle c,x^k\rangle +\frac{\mu }{2}{\Vert x^k\Vert }^2+\lambda {\displaystyle {\sum }_{i=1}^n{v}_i^{k-1}\left|x_i^k\right|}\le \psi \left(A\bar{x}\right)+\langle c,\bar{x}\rangle +\frac{\mu }{2}{\Vert \bar{x}\Vert }^2+\lambda {\displaystyle {\sum }_{i=1}^n{v}_i^{k-1}\left|{\bar{x}}_i\right|}$

由于 $\hat{\epsilon }=A^T\nabla \psi \left(A\bar{x}\right)+c+\mu \bar{x}$ ，所以：

$\begin{array}{l}\psi \left(A{x}^k\right)-\psi \left(A\bar{x}\right)+\langle c,{\Delta }^k\rangle +\frac{\mu }{2}{(\Vert x^k\Vert }^2-{\Vert \bar{x}\Vert }^2)-\langle \hat{\epsilon },{\Delta }^k\rangle \\ \le -\langle \hat{\epsilon },{\Delta }^k\rangle +\lambda {\displaystyle {\sum }_{i=1}^n{v}_i^{k-1}\left(\left|{\bar{x}}_i\right|-\left|x_i^k\right|\right)}\\ \le {\displaystyle {\sum }_{i=1}^n\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\lambda {\displaystyle {\sum }_{i\in \bar{S}}{v}_i^{k-1}}\left(\left|{\bar{x}}_i\right|-\left|x_i^k\right|\right)-\lambda {\displaystyle {\sum }_{i\in {\bar{S}}^c}{v}_i^{k-1}}\left|x_i^k\right|\\ \le {\displaystyle {\sum }_{i=1}^n\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\lambda {\displaystyle {\sum }_{i\in \bar{S}}{v}_i^{k-1}}\left|{\Delta }_i^k\right|-\lambda {\displaystyle {\sum }_{i\in {\left(S^{k-1}\right)}^c}{v}_i^{k-1}}\left|{\Delta }_i^k\right|\\ \le {\displaystyle {\sum }_{i\in S^{k-1}\backslash \bar{S}}\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\left(\lambda +{\Vert \hat{\epsilon }\Vert }_{\infty }\right){\displaystyle {\sum }_{i\in \bar{S}}\left|{\Delta }_i^k\right|}+{(\Vert \hat{\epsilon }\Vert }_{\infty }-\lambda \left(1-\bar{t}\right)){\displaystyle {\sum }_{i\in {\left(S^{k-1}\right)}^c}\left|{\Delta }_i^k\right|}\end{array}$ (9)

由于 $$ 在 $R^m$ 上是强凸的，即： $\psi \left(A{x}^k\right)-\psi \left(A\bar{x}\right)-\langle A^T\nabla \psi \left(A\bar{x}\right),{\Delta }^k\rangle \ge \alpha /2{\Vert A{\Delta }^k\Vert }^2\ge 0$ ，且 $\mu /2\left({\Vert x^k\Vert }^2-{\Vert \bar{x}\Vert }^2\right)-\langle \mu \bar{x},{\Delta }^k\rangle =\mu /2{\Vert {\Delta }^k\Vert }^2$ ，所以，

$\left(\lambda \left(1-\bar{t}\right)-{\Vert \hat{\epsilon }\Vert }_{\infty }\right){\displaystyle {\sum }_{i\in {\left(S^{k-1}\right)}^c}\left|{\Delta }_i^k\right|}\le {\displaystyle {\sum }_{i\in S^{k-1}\backslash \bar{S}}\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\left(\lambda +{\Vert \hat{\epsilon }\Vert }_{\infty }\right){\displaystyle {\sum }_{i\in \bar{S}}\left|{\Delta }_i^k\right|}\le \left(\lambda +{\Vert \hat{\epsilon }\Vert }_{\infty }\right){\displaystyle {\sum }_{i\in S^{k-1}}\left|{\Delta }_i^k\right|}$ (10)

再由引理条件 $\lambda \ge \frac{\left(3-\bar{t}\right){\Vert \hat{\epsilon }\Vert }_{\infty }}{1-\bar{t}}$ ，即可得到不等式。证毕。

引理4：对于 $k\ge 1$ ，若存在一个指标集 $S^{k-1}\supseteq \bar{S}$ ，使得 $\underset{i\in {\left(S^{k-1}\right)}^c}{\min }{\theta }_i^{k-1}\le \bar{t}$ ，且矩阵A在集合 $C\left(\bar{S}，\left|S^{k-1}\right|\right)$ 上满足常数 ${\gamma }_k>0$ 的限制强凸条件(RSC)，则当 $\lambda \ge \frac{\left(3-\bar{t}\right){\Vert \hat{\epsilon }\Vert }_{\infty }}{1-\bar{t}}$ 时，下式成立：

$\Vert {\Delta }^k\Vert \le \frac{1}{{\gamma }_k}\left(\Vert {\hat{\epsilon }}_{S^{k-1}}\Vert +\lambda \sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{\left(v_i^{k-1}\right)}^2}}\right)$。

证明：由引理3可知， ${\Delta }^k\in C\left(\bar{S},\left|S^{k-1}\right|\right)$ ，再由(9)式得到：

$\begin{array}{c}{\gamma }_k{\Vert {\Delta }^k\Vert }^2\le \left({\gamma }_k+\mu /2\right){\Vert {\Delta }^k\Vert }^2\le {\displaystyle {\sum }_{i=1}^n\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\lambda {\displaystyle {\sum }_{i\in \bar{S}}{v}_i^{k-1}}\left|{\Delta }_i^k\right|-\lambda {\displaystyle {\sum }_{i\in {\left(S^{k-1}\right)}^c}{v}_i^{k-1}}\left|{\Delta }_i^k\right|\\ \le {\displaystyle {\sum }_{i=1}^n\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\lambda {\displaystyle {\sum }_{i\in \bar{S}}{v}_i^{k-1}}\left|{\Delta }_i^k\right|-\lambda \left(1-\bar{t}\right){\displaystyle {\sum }_{i\in {\left(S^{k-1}\right)}^c}\left|{\Delta }_i^k\right|}\\ \le {\displaystyle {\sum }_{i\in S^{k-1}}\left|{\hat{\epsilon }}_i\right|}\left|{\Delta }_i^k\right|+\lambda {\displaystyle {\sum }_{i\in \bar{S}}{v}_i^{k-1}}\left|{\Delta }_i^k\right|\\ \le \sqrt{{\displaystyle {\sum }_{i\in S^{k-1}}{\left|{\hat{\epsilon }}_i\right|}^2}}\Vert {\Delta }^k\Vert +\lambda \sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{\left(v_i^{k-1}\right)}^2}}\Vert {\Delta }^k\Vert \end{array}$ (11)

因此，结论得证。证毕。

下面给出迭代点到真实解的误差界。由参考文献 [4] 定理4.1可得：

定理2：令 $\hat{\epsilon }=A^T\nabla \psi \left(A\bar{x}\right)+c+\mu \bar{x}$ ，假设矩阵A在集合 $C\left(\bar{S},1.5\bar{r}\right)$ 上满足常数 $\kappa >0$ 的限制强凸条件(RSC)，且 $\frac{\sqrt{3}\left(4-2\bar{t}\right)\left(1-t^{\ast }\right)}{\left(3-\bar{t}\right)\kappa }\le v\le \frac{1-\bar{t}}{\left(3-\bar{t}\right){\Vert \hat{\epsilon }\Vert }_{\infty }}$。若 $\frac{v\left(3-\bar{t}\right){\Vert \hat{\epsilon }\Vert }_{\infty }}{1-\bar{t}}\le \rho \le \sqrt{\frac{\left(3-\bar{t}\right)\kappa v}{\sqrt{3}\left(4-2\bar{t}\right)\left(1-t^{\ast }\right)}}$ ，则

$\Vert x^k-\bar{x}\Vert \le \{\begin{array}{c}\frac{v^{-1}\left(4-2\bar{t}\right)}{\kappa \left(3-\bar{t}\right)}\sqrt{1.5\bar{r}},若k=1;\\ \frac{\rho v^{-1}\left(4-2\bar{t}\right)}{\kappa \left(3-\bar{t}\right)}\sqrt{1.5\bar{r}},若k=2,3,\cdots .\end{array}$

定理2虽然给出了多阶段凸松弛法产生的迭代点的误差界，但是依然不清楚当前迭代点 $x^k$ 的误差界是否优于先前迭代点 $x^{k-1}$ ，即误差界数列是否下降。下面的定理3(参考文献 [4] 定理4.2)对所有 $i\in \bar{S}$ ，通过 ${{\rm I}}_{\Lambda }\left(i\right)$ 和 ${{\rm I}}_{F^k}\left(i\right)$ 界定 ${\left(v_i^{k-1}\right)}^2$ 解决了这一问题，其中 $\Lambda :=\{i:\left|{\bar{x}}_i\right|\le 2{{\varphi }^{\prime }}_{-}\left(1\right)/\rho \}$，$F^k:=\{i:\left|\left|x_i^k\right|-\left|{\bar{x}}_i\right|\right|\ge {\left[\left(1-t^{\ast }\right)\rho \right]}^{-1}\}$，$k=1,2,\cdots$ 且 $F^0=\bar{S}$。首先对 $i\in \bar{S}$ ，通过 $$ 和 ${{\rm I}}_{F^k}\left(i\right)$ ，给出 ${\left(v_i^{k-1}\right)}^2$ 的上界(参考文献 [4] 引理9)。

引理5：对每一个，令 $F^k$ 为上面定义的指标集，则有： $\sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{\left(v_i^{k-1}\right)}^2}}\le \sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{{\rm I}}_{\Lambda }\left(i\right)}}+\sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{{\rm I}}_{F^{k-1}}\left(i\right)}}$。

定理3：假设矩阵A在集合 $C\left(\bar{S},1.5\bar{r}\right)$ 上满足常数 $\kappa >0$ 的限制强凸条件(RSC)，若参数 $$ 和 $\rho$ 的选取与定理2一样，则对所有的 $k\ge 1$ ：

$\Vert x^k-\bar{x}\Vert \le \frac{\sqrt{3}}{\kappa \left(\sqrt{3}-1\right)}\left[\Vert {\hat{\epsilon }}_{\bar{S}}\Vert +\rho v^{-1}\sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{{\rm I}}_{\Lambda }\left(i\right)}}\right]+{\left(\frac{1}{\sqrt{3}}\right)}^{k-1}\Vert x^1-\bar{x}\Vert$。

由定理3可知： $x^1$ 的误差界与 $x^k\left(k\ge 2\right)$ 的误差界紧密相关，且若前者充分小，则后者也将很小。然而，若 $\rho$ 选择恰当，即使 $x^1$ 的误差界很大， $x^k\left(k\ge 2\right)$ 的误差界也将很小。定理还说明误差数列随着 $k$ 增大而递减，递减到 $\frac{\sqrt{3}}{\kappa \left(\sqrt{3}-1\right)}\left[\Vert {\hat{\epsilon }}_{\bar{S}}\Vert +\lambda \sqrt{{\displaystyle {\sum }_{i\in \bar{S}}{{\rm I}}_{\Lambda }\left(i\right)}}\right]$ ，称之为统计误差。统计误差包含两部分：第一部分是由噪声引起的，第二部分是由 $\varphi$，$\rho$ 和 $\lambda$ 的选择产生的。

5. 结论

本文从零模函数的变分刻画入手,将这类带有组合性质的优化问题等价转化为具有拟双线性结构且全局Lipshitz连续的优化模型，以此设计了求解零模正则化复合优化问题的多阶段凸松弛方法，并对该方法进行了收敛性分析。在理论方面，本文证实了将文献 [4] 的理论结果即：在比限制等距性质(RIP)更弱的限制强凸条件下，定量刻画了多阶段凸松弛法每阶段最优解的误差界，且每阶段最优解的误差界递减拓展到复合模型的有效性，将为以后研究逻辑回归奠定理论基础。以后将证明当阶段数达到一定条件后，误差界保持不变且精确识别真实解的支撑集。

致谢

感谢贲树军师兄给予的帮助。

文章引用

吕佩雯. 一类零模正则复合优化问题的多阶段凸松弛法
GEP-MSCRA for a Kind of Zero-Norm Regularized Composite Optimization Problem[J]. 运筹与模糊学, 2019, 09(01): 65-71. https://doi.org/10.12677/ORF.2019.91008

参考文献