稀疏加组稀疏优化问题的一阶和二阶方向稳定点研究

On the First-Order and Second-Order Directional Stationary Points of Sparse Plus Group Sparse Optimization Problems

摘要: 在本文中，我们考虑一类非凸非光滑的无约束稀疏加组稀疏优化问题，其损失函数是二阶连续可微函数(可能非凸)，惩罚项是稀疏惩罚与组稀疏惩罚的组合，其稀疏惩罚是ℓ1范数，组稀疏惩罚是折叠凹惩罚函数。目前，计算这类带有凸加非凸惩罚优化问题的方向稳定点的研究较少，但利用方向导数定义的方向稳定点比次微分所定义的稳定点(critical点、lifted稳定点等)能更好的刻画解的局部最优性质。因此，本文主要通过方向稳定点来刻画模型的最优性条件。首先，本文引入了一阶、二阶方向稳定点的概念，探讨了它们与问题局部解的关系。其次，给出了一阶、二阶方向导数的具体表达式，这为进一步分析和求解此类问题提供了理论基础。

Abstract: In this paper, we consider a class of nonconvex, nonsmooth and unconstrained sparse plus group sparse optimization problems, in which the loss function is a twice continuously differentiable function (possibly nonconvex), and the penalty term is a combination of sparse penalty and group sparse penalty, where the sparse penalty is a ℓ1 norm, and the group sparse penalty is a general folded concave penalty function. At present, there are few studies on the calculation of directional stationary points for this type of optimization problems with convex plus nonconvex penalties, and directional stationary points characterized by directional derivatives can better show the local optimal properties of solutions than other stationary points defined by subdifferentials (e.g. critical points, lifted stationary points, etc.). Therefore, in this paper, the optimal-ity conditions of the model are characterized by means of directional stationary points. Firstly, we introduce the concepts of first-order and second-order directional stationary points, and discuss their relations with local solutions of the problem. Secondly, the concrete expressions of the first and second order directional derivatives are given, which provide a theoretical basis for further analyzing and solving this kind of problems.

1. 引言

近年来，稀疏加组稀疏优化问题得到了广泛的研究，包括图像恢复、变量选择、机器学习等众多领域 [1] [2] [3] [4] 。一般的稀疏加组稀疏优化问题 [3] 如下：

$\underset{x\in {ℝ}^n}{\min }F\left(x\right)=f\left(x\right)+{\lambda }_1{\Vert x\Vert }_0+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\#\left({\Vert x_{\left(j\right)}\Vert }_2\right)\mathrm{,}$ (1)

其中，损失函数 $f\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 二阶连续可微(可能非凸)，本文用 $\Vert .\Vert$ 表示 ${\mathcal{l}}_2$ 范数。变量 $x={\left(x_{\left(1\right)}^{\text{T}}\mathrm{,}{x}_{\left(2\right)}^{\text{T}}\mathrm{,}\cdots \mathrm{,}{x}_{\left(J\right)}^{\text{T}}\right)}^{\text{T}}\in {ℝ}^n$ 具有J个分组结构，第j组变量 $x_{\left(j\right)}\in {ℝ}^{n^j}$ ， ${\displaystyle {\sum }_{j=1}^J}{n}^j=n$ ， ${\Vert x\Vert }_0$ 表示 $x$ 中非零分量的个数， $\Vert x_{\left(j\right)}\Vert$ 表示 $x$ 的第j组变量 $x_{\left(j\right)}$ 的 ${\mathcal{l}}_2$ 范数， ${\displaystyle {\sum }_{j=1}^J}\#\left({\Vert x_{\left(j\right)}\Vert }_2\right)$ 表示 $x$ 中非零组的个数，正则化参数 ${\lambda }_1,{\lambda }_2>0$ 。

稀疏优化问题的主要目的是寻求欠定线性方程组的稀疏解，从而提高模型的计算效率和可解释性。稀疏性通常用 ${\mathcal{l}}_0$ 范数刻画，即 $x\in {ℝ}^n$ ， ${\Vert x\Vert }_0\ll n$ 。 ${\mathcal{l}}_0$ 范数可以直接惩罚非零元素的数量，有助于找到仅有少数重要特征或特征组合的解，去除无用或冗余的特征，从而降低数据表示的复杂度，提高预测识别的准确性。2006年Yuan和Lin [4] 首次提出将组稀疏性作为先验信息，组稀疏性考虑了特征之间的相关性，是把向量的分量进行分组再考察各组是否整体为零，体现为向量中非零分量或零分量集中出现在某些区域。因此，综合考虑变量的稀疏和组稀疏结构可以获得更具实际意义的结果。

然而，问题(1)的正则项是非凸、非光滑、非Lipschitz甚至不连续的NP难问题 [5] [6] 。Donoho等人 [7] 提出将 ${\mathcal{l}}_0$ 范数凸松弛为 ${\mathcal{l}}_1$ 范数。Fan和Li [6] [8] 提出了一种折叠凹惩罚函数，并证明了该非凸非光滑优化模型的解具有无偏性、oracle等性质。后来，学者们给出了一系列折叠凹惩罚函数，包括 ${\mathcal{l}}_p\left(0<p<1\right)$ 范数、SCAD罚(Smooothly Clipped Absolute Deviation Penalty) [6] 、MCP (Minimax Concave Penalty) [9] 、Capped- ${\mathcal{l}}_1$ 罚(Continuous Exact ${\mathcal{l}}_0$ Penalty) [10] 等，非凸非光滑松弛问题已经成为近年来研究热点之一 [5] [11] [12] [13] [14] [15] 。常用的折叠凹惩罚函数有以下几类：

1) Capped- ${\mathcal{l}}_1$ 罚函数为

${\varphi }^{Capped-{\mathcal{l}}_1}\left(t\right):=\lambda \min \left\{\frac{t}{\alpha },1\right\}=(\begin{array}{ll}\frac{\lambda t}{\alpha },\hfill & 0\le t\le \alpha ,\hfill \\ \lambda ,\hfill & \alpha <t.\hfill \end{array}\left(\lambda >0,\alpha >0\right)$

2) MCP函数为

${\varphi }^{MCP}\left(t\right):=\lambda {\displaystyle {\int }_0^t}{\left(1-\frac{\tau }{\alpha \lambda }\right)}_{+}\text{d}\tau =(\begin{array}{ll}\lambda t-\frac{t^2}{2\alpha },\hfill & 0\le t\le \alpha \lambda ,\hfill \\ \frac{1}{2}\alpha {\lambda }^2,\hfill & \alpha \lambda <t.\hfill \end{array}\left(\lambda >0,\alpha >1\right)$

3) SCAD罚函数为

${\varphi }^{SCAD}\left(t\right):=\lambda {\displaystyle {\int }_0^t}\min \left\{1,\frac{{\left(\alpha -\frac{\tau }{\lambda }\right)}_{+}}{\alpha -1}\right\}\text{d}\tau =(\begin{array}{ll}\lambda t,\hfill & 0\le t\le \lambda ,\hfill \\ \frac{1}{\alpha -1}\left(-\frac{{\lambda }^2}{2}+\alpha \lambda t-\frac{1}{2}{t}^2\right),\hfill & \lambda <t\le \alpha \lambda ,\hfill \\ \frac{1}{2}\left(\alpha +1\right){\lambda }^2,\hfill & \alpha \lambda <t.\hfill \end{array}\left(\lambda >0,\alpha >2\right)$

其中 ${\beta }_{+}:=(\begin{array}{ll}0,\hfill & \beta \le 0,\hfill \\ \beta ,\hfill & \beta >0.\hfill \end{array}$ 。

对于问题(1)，本文考虑如下非凸松弛模型：

$\underset{x\in {ℝ}^n}{\min }F\left(x\right)=f\left(x\right)+{\lambda }_1{\Vert x\Vert }_1+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\varphi \left(\Vert x_{\left(j\right)}\Vert \right)\mathrm{,}$ (2)

其中，正则化参数 ${\lambda }_1,{\lambda }_2>0$ ， ${\Vert x\Vert }_1:={\displaystyle {\sum }_{i=1}^n}\left|x_i\right|$ ， $\varphi \mathrm{<mo>\; :\; </mo>}{ℝ}^{+}\to {ℝ}^{+}$ 为一般折叠凹惩罚函数形式，只需满足以下性质：

1) $\varphi$ 在 $\left[\mathrm{0,}\infty \right)$ 上是局部Lipschitz的，单调不减， $\varphi \left(0\right)=0$ 且当 $t>0$ 时， $\varphi \left(t\right)>0$ ；

2) ${\varphi }^{\prime }\left(0\right):={\varphi }^{\prime }\left(0^{+}\right)>0$ 。易见，Capped- ${\mathcal{l}}_1$ 、MCP、SCAD等惩罚函数均满足上述条件。

对于无约束非凸非光滑问题，Ahn和Pang [16] [17] 通过方向导数定义了一阶、二阶d-稳定点，Cui [18] 指出通过方向导数定义的d-稳定点可以推导出lifted稳定点、critical稳定点等，进而得出非光滑问题的一阶、二阶d-稳定点强于次微分所定义的稳定点。然而，目前的研究表明计算非光滑问题的一阶、二阶d-稳定点是困难的。2020年Peng和Chen [19] 给出了无约束组稀疏优化问题的一阶、二阶d-稳定点的有效刻画以及与该问题局部最优解的关系，提出了光滑化方法，并证明了光滑化问题与松弛问题二阶d-稳定点的一致性。在此基础上，Su [20] 对稀疏加组稀疏优化问题的连续松弛模型的一阶d-稳定点进行了刻画，并给出了光滑化问题和松弛问题一阶d-稳定点的一致性。不同于上述研究，本文考虑的稀疏惩罚是凸函数加组稀疏惩罚是一类折叠凹惩罚函数的组合问题，研究此类问题的一阶、二阶d-稳定点的有效刻画以及局部最优性质，并给出了一阶、二阶方向导数的具体表达式。

本文的结构如下：在第二节，我们介绍了一阶d-稳定点及其局部最优性质，并给出松弛问题(2)的一阶d-稳定点的特征和相关结论；在第三节，我们给出了二阶d-稳定点的概念和性质，并给出了问题(2)的二阶d-稳定点的具体表达式；最后一节是一个简单的总结。

符号标记：对于 $n\in {\mathbb{N}}^{+}$ ， $\left[n\right]\mathrm{<mo>\; :\; </mo>}=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ ， $J\left(x\right):=\left\{j:x_{\left(j\right)}\ne 0,j\in \left[J\right]\right\}$ 表示向量 $x$ 的非零组的下标。 $I_j\left(x\right)\mathrm{<mo>\; :\; </mo>}=\left\{i:x_{\left(j\right)i}\ne 0,\forall j\in \left[J\right],i\in \left[n^j\right]\right\}$ 表示向量 $x$ 的第j组中非零元素的下标。设 $A\mathrm{,}B$ 为两个集合， $A\backslash B\mathrm{<mo>\; :\; </mo>}=\left\{i\mathrm{<mo>\; :\; </mo>}i\in A且i\notin B\right\}$ 。 $D\left(x\right):=\left\{y\in {ℝ}^n:I_j\left(y\right)=I_j\left(x\right),\forall j\in \left[J\right]\right\}$ 表示与 $x$ 有相同的非零元素下标的向量全体。

2. 一阶d-稳定点

2.1. 一阶d-稳定点的局部最优性

本节引入问题(2)的几个重要概念：凸差函数、方向导数以及方向稳定点 [16] [19] [21] 。

为方便分析，本节假定惩罚函数可以改写为凸差(Difference-of-Convex)形式，即设设惩罚函数具有下述形式。

假设2.1 [16] [19] (凸差函数)设折叠凹惩罚函数 $\varphi \mathrm{<mo>\; :\; </mo>}{ℝ}^{+}\to {ℝ}^{+}$ 具有凸差形式： $\varphi \left(t\right)\mathrm{<mo>\; :\; </mo>}=g\left(t\right)-h\left(t\right)$ ，其中 $h\left(t\right)\mathrm{<mo>\; :\; </mo>}={\max }_{1\le \upsilon \le \bar{\upsilon }}{h}_{\upsilon }\left(t\right)$ ， $\upsilon$ 和 $\bar{\upsilon }\in {\mathbb{N}}^{+}$ ，g和 $h_{\upsilon }$ 在 $t\in \left(\mathrm{0,}\infty \right)$ 上都是可微凸函数，且满足：

$g^{\prime }\left(0\right)\mathrm{<mo>\; :\; </mo>}=g^{\prime }\left(0^{+}\right)\mathrm{,}{h^{\prime }}_{\upsilon }\left(0\right)\mathrm{<mo>\; :\; </mo>}={h^{\prime }}_{\upsilon }\left(0^{+}\right)\mathrm{,}\forall 1\le \upsilon \le \bar{\upsilon }\mathrm{.}$

容易验证，前述几类折叠凹惩罚函数均具有凸差形式：

1) Capped- ${\mathcal{l}}_1$ 罚函数：

${\varphi }^{Capped-{\mathcal{l}}_1}\left(t\right)=g^{Capped-{\mathcal{l}}_1}\left(t\right)-h^{Capped-{\mathcal{l}}_1}(\; t\; )$

$g^{Capped-{\mathcal{l}}_1}\left(t\right)=\frac{\lambda t}{\alpha },h^{Capped-{\mathcal{l}}_1}\left(t\right)=\max \left\{0,\frac{\lambda t}{\alpha }-\lambda \right\},\left(\alpha >0,\lambda >0\right)$

2) MCP函数：

${\varphi }^{MCP}\left(t\right)=g^{MCP}\left(t\right)-h^{MCP}(\; t\; )$

$g^{MCP}\left(t\right)=\lambda t,h^{MCP}\left(t\right)=(\begin{array}{ll}\frac{t^2}{2\alpha },\hfill & 0\le t\le \alpha \lambda ,\hfill \\ \lambda t-\frac{1}{2}\alpha {\lambda }^2,\hfill & \alpha \lambda <t,\hfill \end{array}\left(\alpha >1,\lambda >0\right)$

3) SCAD罚函数：

${\varphi }^{SCAD}\left(t\right)=g^{SCAD}\left(t\right)-h^{SCAD}(\; t\; )$

$g^{SCAD}\left(t\right)=\lambda t,h^{SCAD}\left(t\right)=(\begin{array}{ll}0,\hfill & 0\le t\le \lambda ,\hfill \\ \frac{{\left(t-\lambda \right)}^2}{2\left(\alpha -1\right)},\hfill & \lambda <t\le \alpha \lambda ,\hfill \\ \lambda t-\frac{1}{2}\left(\alpha +1\right){\lambda }^2,\hfill & \alpha \lambda <t.\hfill \end{array}\left(\alpha >2,\lambda >0\right)$

在假设2.1之下，问题(2)可以写成如下形式：

$\begin{array}{c}\underset{x\in {ℝ}^n}{\min }F\left(x\right)=f\left(x\right)+{\lambda }_1{\Vert x\Vert }_1+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g\left(\Vert x_{\left(j\right)}\Vert \right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h}_{\upsilon }\left(\Vert x_{\left(j\right)}\Vert \right)\right]\\ =f\left(x\right)+{\lambda }_1{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{\displaystyle \underset{i=1}{\overset{n^j}{\sum }}}\left|x_{{\left(j\right)}_i}\right|+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g\left(\Vert x_{\left(j\right)}\Vert \right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h}_{\upsilon }\left(\Vert x_{\left(j\right)}\Vert \right)\right]\mathrm{.}\end{array}$ (3)

当 $\bar{\upsilon }=1$ 时，问题(3)可退化为

$\underset{x\in {ℝ}^n}{\min }F\left(x\right)=f\left(x\right)+{\lambda }_1{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{\displaystyle \underset{i=1}{\overset{n^j}{\sum }}}\left|x_{{\left(j\right)}_i}\right|+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g\left(\Vert x_{\left(j\right)}\Vert \right)-h\left(\Vert x_{\left(j\right)}\Vert \right)\right]\mathrm{.}$

为了方便表述，令 $u\left(x\right)={\Vert x\Vert }_1$ ， $w\left(x\right)=\Vert x\Vert$ ，则问题(3)可以改写为：

$\underset{x\in {ℝ}^n}{\min }F\left(x\right)=f(x)+{\lambda }_1{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{\displaystyle \underset{i=1}{\overset{n^j}{\sum }}}u\left(x_{{\left(j\right)}_i}\right)+{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g\circ w\left(x_{\left(j\right)}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h}_{\upsilon }\circ w\left(x_{\left(j\right)}\right)\right].$ (4)

d-稳定点是描述方向导数的必要条件，接下来我们介绍一阶d-稳定点的定义以及局部最优性质。

定义2.1 [19] [21] (一阶d-稳定点)设 $Q\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 在给定点 $x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ 处方向可微，若Q的方向导数 $Q^{\prime }$ 满足

$Q^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}x-x^{\mathrm{<mo>\; *\; </mo>}}\right)=\underset{t\downarrow 0}{lim}\frac{Q\left(x^{\mathrm{<mo>\; *\; </mo>}}+t\left(x-x^{\mathrm{<mo>\; *\; </mo>}}\right)\right)-Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{t}\ge \mathrm{0,}\forall x\in {ℝ}^n\mathrm{,}$

则称 $x^{\mathrm{<mo>\; *\; </mo>}}$ 为Q的一阶(方向) d-稳定点。值得注意的是，若Q在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 处可微，则有 $Q^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}x-x^{\mathrm{<mo>\; *\; </mo>}}\right)=\langle \nabla Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}x-x^{\mathrm{<mo>\; *\; </mo>}}\rangle =0$ 。

引理2.1 [19] (一阶d-稳定点的局部最优性质)已知 $F\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 在 $x\in {ℝ}^n$ 上是局部Lipschitz连续且方向可微的，则以下结论成立：

1) 如果 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是F的局部极小点，则 $x^{\mathrm{<mo>\; *\; </mo>}}$ 也是F的一阶d-稳定点；

2) 如果F在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 满足一阶增长性条件，即存在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 的一个领域 $\Theta$ 和 $\delta >0$ ，使得

$F\left(x\right)\ge F\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)+\delta \Vert x-x^{\mathrm{<mo>\; *\; </mo>}}\Vert \mathrm{,}\forall x\in \Theta \mathrm{,}$

等价于在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 满足

$F^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}x-x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{<mo>\; >\; </mo>0,}\forall x\in {ℝ}^n\backslash \left\{x^{\mathrm{<mo>\; *\; </mo>}}\right\}\mathrm{.}$

Peng和Chen在 [19] 中给出了引理2.1的证明。根据定义2.1，对任意 $x\mathrm{,}y\in {ℝ}^n$ ， $u\left(x\right)$ ， $w\left(x\right)$ 的一阶方向导数如下：

$u^{\prime }\left(x;y\right)=(\begin{array}{ll}{\Vert y\Vert }_1,\hfill & \Vert x\Vert =0,\hfill \\ \mathrm{sgn}{\left(x\right)}^{\text{T}}y,\hfill & \Vert x\Vert \ne 0.\hfill \end{array}{w}^{\prime }\left(x;y\right)=(\begin{array}{ll}\Vert y\Vert ,\hfill & \Vert x\Vert =0,\hfill \\ \frac{\langle x,y\rangle }{\Vert x\Vert },\hfill & \Vert x\Vert \ne 0.\hfill \end{array}$ (5)

其中 $\mathrm{sgn}\left(a\right):=(\begin{array}{ll}1,\hfill & a>0,\hfill \\ 0,\hfill & a=0,\hfill \\ -1,\hfill & a<0.\hfill \end{array}$ 进一步， $\forall j\in \left[J\right]$ ， $i\in \left[n^j\right]$ ，有

$u^{\prime }\left(x_{\left(j\right)i};y_{\left(j\right)i}\right)=(\begin{array}{ll}\left|y_{\left(j\right)i}\right|,\hfill & \left|x_{\left(j\right)i}\right|=0,\hfill \\ \mathrm{sgn}\left(x_{\left(j\right)i}\right)y_{\left(j\right)i},\hfill & \left|x_{\left(j\right)i}\right|\ne 0,\hfill \end{array}{w}^{\prime }\left(x_{\left(j\right)};y_{\left(j\right)}\right)=(\begin{array}{ll}\Vert y_{\left(j\right)}\Vert ,\hfill & \Vert x_{\left(j\right)}\Vert =0,\hfill \\ \frac{\langle x_{\left(j\right)},y_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}\Vert },\hfill & \Vert x_{\left(j\right)}\Vert \ne 0.\hfill \end{array}$ (6)

实际上，在一维情况下 ${\mathcal{l}}_1$ 范数和 ${\mathcal{l}}_2$ 范数是等价的。

2.2. 问题(3)的一阶d-稳定点

本节给出问题(3)的一阶d-稳定点的具体表达式以及特征刻画。

定理2.1 在假设2.1成立的条件下，问题(3)在点 $x^{\mathrm{<mo>\; *\; </mo>}}$ 处的方向导数具体表达式如下：

$\begin{array}{l}{F}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle \nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}y\rangle +{\lambda }_1{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]}{\sum }}\left|y_{\left(j\right)i}\right|+{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left|y_{\left(j\right)i}\right|\\ +{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\mathrm{sgn}\left(x_{\left(j\right)i}\right)y_{\left(j\right)i}+{\lambda }_2{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\Vert y_{\left(j\right)}\Vert \\ +{\lambda }_2{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\mathrm{,}\forall y\in {\text{R}}^n\mathrm{.}\end{array}$ (7)

证明. 首先，注意到凸函数 $h_{\upsilon }\mathrm{<mo>\; :\; </mo>}{ℝ}^{+}\to {ℝ}^{+}$ ， $w\mathrm{<mo>\; :\; </mo>}{ℝ}^{n^j}\to {ℝ}^{+}$ 和复合函数 $h_{\upsilon }\circ w\mathrm{<mo>\; :\; </mo>}{ℝ}^{n^j}\to {ℝ}^{+}$ 均是方向可微的。 $\forall j\in \left[J\right]$ ，有

${\left(h\circ w\right)}^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{x}_{\left(j\right)}-x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)=h^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \mathrm{<mo>\; ;\; </mo>}{x}_{\left(j\right)}-x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)=\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h}^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{x}_{\left(j\right)}-x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{.}$

同理，函数g也可得出上述结论。根据定义2.1和(6)，可得

$\begin{array}{c}{F}^{\prime }\left(x^{*};x-x^{*}\right)=\langle \nabla f\left(x^{*}\right),x-x^{*}\rangle +{\lambda }_1{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{\displaystyle \underset{i=1}{\overset{n^j}{\sum }}}{u}^{\prime }\left(x_{\left(j\right)i}^{*};x_{\left(j\right)i}-x_{\left(j\right)i}^{*}\right)\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]w^{\prime }\left(x_{\left(j\right)}^{*};x_{\left(j\right)}-x_{\left(j\right)}^{*}\right)\\ =\langle \nabla f\left(x^{*}\right),x-x^{*}\rangle +{\lambda }_1{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]}{\sum }}{u}^{\prime }\left(x_{\left(j\right)i}^{*};x_{\left(j\right)i}-x_{\left(j\right)i}^{*}\right)\\ +{\lambda }_1{\displaystyle \underset{j\in J\left(x^{*}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{u}^{\prime }\left(x_{\left(j\right)i}^{*};x_{\left(j\right)i}-x_{\left(j\right)i}^{*}\right)+{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{*}\right)}{\sum }}{u}^{\prime }\left(x_{\left(j\right)i}^{*};x_{\left(j\right)i}-x_{\left(j\right)i}^{*}\right)\\ +{\lambda }_2{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]w^{\prime }\left(x_{\left(j\right)}^{*};x_{\left(j\right)}-x_{\left(j\right)}^{*}\right)\\ +{\lambda }_2{\displaystyle \underset{j\in J\left(x^{*}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]w^{\prime }\left(x_{\left(j\right)}^{*};x_{\left(j\right)}-x_{\left(j\right)}^{*}\right).\end{array}$

$\forall y=x-x^{*}\in {ℝ}^n$ 有

$\begin{array}{l}{F}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle \nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}y\rangle +{\lambda }_1{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]}{\sum }}\left|y_{\left(j\right)i}\right|+{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left|y_{\left(j\right)i}\right|\\ +{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\mathrm{sgn}\left(x_{\left(j\right)i}\right)y_{\left(j\right)i}+{\lambda }_2{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\Vert y_{\left(j\right)}\Vert \\ +{\lambda }_2{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\mathrm{.}\end{array}$

故得结论。 □

定理2.2 在假设2.1成立的条件下，设 $x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ 是问题(3)的一个一阶d-稳定点，则下述结论成立：

1) $\forall j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|=\left|{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)i}^{*}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{*}\right)\right]\frac{x_{\left(j\right)i}^{*}}{\Vert x_{\left(j\right)}^{*}\Vert }\right|,$

特别地，当 $\bar{\upsilon }=1$ 时，

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|=\left|{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)i}^{*}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)-h^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)\right]\frac{x_{\left(j\right)i}^{*}}{\Vert x_{\left(j\right)}^{*}\Vert }\right|.$

2) $\forall j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ 若满足 $\left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\ne \varnothing$ (即 $\left|I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|<n^j$ )，则对任意 $i\in \left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|\le {\lambda }_1.$

3) $\forall j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}i\in \left[n^j\right]$ ，有

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|\le {\lambda }_1{n}^j\left(J-\left|J\left(x^{*}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{*}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right].$

特别地，当 $\bar{\upsilon }=1$ 时，

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|\le {\lambda }_1{n}^j\left(J-\left|J\left(x^{*}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{*}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-h^{\prime }\circ w\left(0\right)\right].$

证明. 1) 根据定理2.2， $\forall y=x-x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ ，有

$\begin{array}{c}0\le {\displaystyle \underset{j\in \left[J\right]}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]}{\sum }}{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}{y}_{\left(j\right)i}+{\lambda }_1{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]}{\sum }}\left|y_{\left(j\right)i}\right|+{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in \left[n^j\right]\backslash I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left|y_{\left(j\right)i}\right|\\ +{\lambda }_1{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}sign\left(x_{\left(j\right)i}^{*}\right)y_{\left(j\right)i}+{\lambda }_2{\displaystyle \underset{j\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h}^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\Vert y_{\left(j\right)}\Vert \\ +{\lambda }_2{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }.\end{array}$ (8)

特别地，任取 $y\in D\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，得

$0\le {\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left\{{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)i}+{\lambda }_{1}sign\left(x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\right\}\cdot y_{\left(j\right)i}\mathrm{,}$ (9)

由 $y\in D\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ 的任意性，对任意 $j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ， $i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有

$0={\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)i}+{\lambda }_{1}sign\left(x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\mathrm{,}$ (10)

即

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|=\left|{\lambda }_{1}sign\left(x_{\left(j\right)i}^{*}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{*}\right)\right]\frac{x_{\left(j\right)i}^{*}}{\Vert x_{\left(j\right)}^{*}\Vert }\right|.$

当 $\bar{\upsilon }=1$ 时，

$\left|{\left[\nabla f\left(x^{*}\right)\right]}_{\left(j\right)i}\right|=\left|{\lambda }_{1}sign\left(x_{\left(j\right)i}^{*}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)-h^{\prime }\circ w\left(x_{\left(j\right)}^{*}\right)\right]\frac{x_{\left(j\right)i}^{*}}{\Vert x_{\left(j\right)}^{*}\Vert }\right|.$

2) 根据已知条件，我们可取任意满足(8)的 $\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ， $x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}={\left(x_{\left(\hat{j}\right)1}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{x}_{\left(\hat{j}\right)2}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}\cdots \mathrm{,}{x}_{\left(\hat{j}\right)n^{\hat{j}}}^{\mathrm{<mo>\; *\; </mo>}}\right)}^{\text{T}}\in {ℝ}^{n^{\hat{j}}}$ 和任意取 $\hat{i}\in \left[n^{\hat{j}}\right]\backslash I_{\hat{i}}\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，定义 $y^{+}$ ， $y^{-}$ 如下：

$y_{\left(j\right)i}^{+}=(\begin{array}{ll}1,\hfill & j=\hat{j},i=\hat{i},\hfill \\ 0,\hfill & 其他,\hfill \end{array}{y}_{\left(j\right)i}^{-}=(\begin{array}{ll}-1,\hfill & j=\hat{j},i=\hat{i},\hfill \\ 0,\hfill & 其他.\hfill \end{array}$

则 $\langle x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(\hat{j}\right)}^{\pm }\rangle =0$ ， $\Vert y_{\left(\hat{j}\right)}^{\pm }\Vert =1$ ，且 ${\bar{y}}_{\left(j\right)i}^{\pm }=0$ ， $\forall j\ne \bar{j}$ ， $i\in \left[n^j\right]$ 。根据(6)可得

$u^{\prime }\left(x_{\left(\hat{j}\right)\hat{i}}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(\hat{j}\right)\hat{i}}^{\pm }\right)=u^{\prime }\left(\mathrm{0\; <mo>\; ;\; </mo>}{y}_{\left(\hat{j}\right)\hat{i}}^{\pm }\right)=\left|y_{\left(\hat{j}\right)\hat{i}}^{\pm }\right|=\mathrm{1,}{w}^{\prime }\left(x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(\hat{j}\right)}^{\pm }\right)=\frac{\langle x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(\hat{j}\right)}^{\pm }\rangle }{\Vert x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }=0.$

进而，由(8)可得

$\begin{array}{c}0\le {\displaystyle \underset{\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\hat{i}\in \left[n^{\hat{j}}\right]\backslash I_{\hat{j}}\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\hat{j}\right)\hat{i}}{y}_{\left(\hat{j}\right)\hat{i}}^{\pm }+{\lambda }_1{\displaystyle \underset{\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\hat{i}\in \left[n^{\hat{j}}\right]\backslash I_{\hat{j}}\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left|y_{\left(\hat{j}\right)\hat{i}}^{\pm }\right|\\ +{\lambda }_2{\displaystyle \underset{\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{\langle x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(\hat{j}\right)}^{\pm }\rangle }{\Vert x_{\left(\hat{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\\ ={\displaystyle \underset{\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\hat{i}\in \left[n^{\hat{j}}\right]\backslash I_{\hat{j}}\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\pm {\mathrm{<mo\; stretchy="false">\; [\; </mo>}}_{\nabla }+{\displaystyle \underset{\hat{j}\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\hat{i}\in \left[n^{\hat{j}}\right]\backslash I_{\hat{j}}\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\lambda }_1\mathrm{,}\end{array}$

即 $\pm {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\hat{j}\right)\hat{i}}\le {\lambda }_1$ ，从而 $\left|{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\hat{j}\right)\hat{i}}\right|\le {\lambda }_1$ 。

3) 与2)的证明类似，任取 $\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ， $\bar{i}\in \left[n^{\bar{j}}\right]$ ，可知 $x_{\left(\bar{j}\right)\bar{i}}^{\mathrm{<mo>\; *\; </mo>}}=0$ ，定义 $y^{+}$ ， $y^{-}$ 如下：

${\bar{y}}_{\left(j\right)i}^{+}=(\begin{array}{ll}1,\hfill & j=\bar{j},i=\bar{i},\hfill \\ 0,\hfill & 其他,\hfill \end{array}{\bar{y}}_{\left(j\right)i}^{-}=(\begin{array}{ll}-1,\hfill & j=\bar{j},i=\bar{i},\hfill \\ 0,\hfill & 其他,\hfill \end{array}$

则 $\langle x_{\left(\bar{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{y}_{\left(\bar{j}\right)}^{\pm }\rangle =0$ ，且 ${\bar{y}}_{\left(j\right)i}^{\pm }=0$ ， $\forall j\ne \bar{j}$ ， $i\in \left[n^j\right]$ 。由(8)得

$\begin{array}{c}0\le {\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}{\bar{y}}_{\left(\bar{j}\right)\bar{i}}^{\pm }+{\lambda }_1{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}\left|{\bar{y}}_{\left(\bar{j}\right)\bar{i}}^{\pm }\right|\\ \mathrm{<mi>\; </mi>\; <mi>\; </mi>}+{\lambda }_2{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(x_{\left(\bar{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(\bar{j}\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\Vert y_{\left(\bar{j}\right)}^{\pm }\Vert \\ ={\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}\pm {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}+{\lambda }_1{n}^{\bar{j}}\left(J-\left|J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|\right)+{\lambda }_2{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right]\Vert y_{\left(\bar{j}\right)}^{\pm }\Vert \\ \le {\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}\pm {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}+{\lambda }_1{n}^{\bar{j}}\left(J-\left|J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right]\mathrm{,}\end{array}$

即

${\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}\pm {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}\le {\lambda }_1{n}^{\bar{j}}\left(J-\left|J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right],$

${\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{\bar{i}\in \left[n^{\bar{j}}\right]}{\sum }}\left|{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}\right|\le {\lambda }_1{n}^{\bar{j}}\left(J-\left|J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right]\mathrm{,}$

从而

$\left|{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(\bar{j}\right)\bar{i}}\right|\le {\lambda }_1{n}^{\bar{j}}\left(J-\left|J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right|\right)+{\lambda }_2\sqrt{n}{\displaystyle \underset{\bar{j}\in \left[J\right]\backslash J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[g^{\prime }\circ w\left(0\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(0\right)\right]\mathrm{.}$ □

3. 二阶d-稳定点

3.1. 二阶d-稳定点的局部最优性

首先，我们介绍二阶d-稳定点的定义 [19] [21] ，本文采用沿一个方向的二阶方向导数来定义问题(2)的二阶d-稳定点，这样定义的导数简单易理解。

定义3.1 [19] (二阶方向导数)设 $Q\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 是局部Lipschitz连续且方向可微的，对任意 $x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}y\in {ℝ}^n$ ，若以下极限存在：

$\underset{z\to y\mathrm{,}t\downarrow 0}{\lim }\frac{Q\left(x^{\mathrm{<mo>\; *\; </mo>}}+tz\right)-Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)-t{Q}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}z\right)}{\frac{1}{2}{t}^2}\mathrm{,}$ (11)

则称Q在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 处沿方向 $y$ 二阶方向可导，其极限称为Q在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 处沿方向 $y$ 二阶方向导数，记为 $Q^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)$ 。若 $\forall y\in {ℝ}^n$ ，上述极限均存在，则Q在点 $x^{\mathrm{<mo>\; *\; </mo>}}$ 二阶方向可微。

事实上，极限(11)存在表明对 $\forall \epsilon >0,\exists \delta >0$ ，使得 $\forall x\in {ℝ}^n$ ，有

$(\begin{array}{l}\Vert x-x^{\mathrm{<mo>\; *\; </mo>}}\Vert \le \delta \mathrm{,}\mathrm{0\; <mo>\; <\; </mo>}t\le \delta \\ \Vert \frac{x-x^{\mathrm{<mo>\; *\; </mo>}}}{t}-y\Vert \le \delta \end{array}\Rightarrow \left|\frac{Q\left(x\right)-Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)-t{Q}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}\frac{x-x^{\mathrm{<mo>\; *\; </mo>}}}{t}\right)}{\frac{1}{2}{t}^2}-Q^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)\right|\le \epsilon$

成立。显然，若极限(11)存在，则有下式成立

$Q^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\underset{t\downarrow 0}{\lim }\frac{Q\left(x^{\mathrm{<mo>\; *\; </mo>}}+ty\right)-Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)-t{Q}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)}{\frac{1}{2}{t}^2}\mathrm{.}$

假设Q在点 $x^{\mathrm{<mo>\; *\; </mo>}}$ 二阶可微，则Hessian阵 ${\nabla }^{2}Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ 存在，且 $\forall y\in {ℝ}^n$ ，有

$Q^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle {\nabla }^{2}Q\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)y\mathrm{,}y\rangle \mathrm{.}$

定义3.2 [19] (二阶d-稳定点)设 $Q\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 在 $x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ 处二阶方向可微，若 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是Q的一阶d-稳定点，且

$\forall y\in {ℝ}^n\mathrm{,}{Q}^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=0\Rightarrow Q^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)\ge \mathrm{0,}$

则称 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是Q的二阶d-稳定点。

文献 [19] [21] 给出了如下F二阶方向可微时的局部最优性质。

引理3.1 [19] (二阶d-稳定点的局部最优性质)已知 $F\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 在 $x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ 处二阶方向可微，则以下结论成立：

1) 若 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是F的局部极小点，则 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是F的二阶d-稳定点；

2) 若 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是F的强局部极小点(即：存在 $x^{\mathrm{<mo>\; *\; </mo>}}$ 的邻域 $\Theta$ 和标量 $\delta >0$ ，使得 $\forall x\in \Theta$ ，都有 $F\left(x\right)\ge F\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)+\delta {\Vert x-x^{\mathrm{<mo>\; *\; </mo>}}\Vert }^2$ )，当且仅当 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是F的一阶d-稳定点，且 $\forall y\in {ℝ}^n\backslash \left\{0\right\}$ ，有

$F^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=0\Rightarrow F^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)>0.$

根据定义3.1可计算得出在点 $x$ 处的 ${\mathcal{l}}_1$ 范数和 ${\mathcal{l}}_2$ 范数的二阶方向导数如下：

$u^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)=\mathrm{0,}{w}^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)=(\begin{array}{ll}\mathrm{0,}\hfill & {\Vert x\Vert }_2=\mathrm{0,}\hfill \\ \frac{{\left(\Vert x\Vert \Vert y\Vert \right)}^2-{\left|\langle x\mathrm{,}y\rangle \right|}^2}{{\Vert x\Vert }^3}\mathrm{,}\hfill & {\Vert x\Vert }_2\ne 0.\hfill \end{array}$ (12)

对于任意 $j\in \left[J\right]$ ，有

$w^{\left(2\right)}\left(x_{\left(j\right)}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=(\begin{array}{ll}\mathrm{0,}\hfill & {\Vert x_{\left(j\right)}\Vert }_2=\mathrm{0,}\hfill \\ \frac{{\left(\Vert x_{\left(j\right)}\Vert \Vert y_{\left(j\right)}\Vert \right)}^2-{\left|\langle x_{\left(j\right)}\mathrm{,}{y}_{\left(j\right)}\rangle \right|}^2}{{\Vert x_{\left(j\right)}\Vert }^3}\mathrm{,}\hfill & {\Vert x_{\left(j\right)}\Vert }_2\ne 0.\hfill \end{array}$ (13)

为了求出复合函数的二阶方向导数，文献[22, Proposition 3.2]和[19, Lemma 3.2]给出了如下引理。

引理3.2 [19] 设 $\rho \mathrm{<mo>\; :\; </mo>}{ℝ}^m\to ℝ$ 是在 $\Phi \left(x\right)\in {ℝ}^m$ 上局部Lipschitz连续，且 $\Phi \mathrm{<mo>\; :\; </mo>}{ℝ}^n\to {ℝ}^m$ 在 $x\in {ℝ}^n$ 上局部Lipshitz连续。若复合函数 $G=\rho \circ \Phi \mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ\in {ℝ}^n$ 满足以下条件中的任意一条，则G在点 $x$ 处二阶方向可微：

1) $\rho$ 在 $\Phi \left(x\right)$ 处半光滑可微(即： $\rho$ 在 $\Phi \left(x\right)$ 附近方向可微， $\nabla \rho$ 在 $\Phi \left(x\right)$ 处半光滑)，且 $\Phi$ 在点 $x$ 处二阶方向可微；

2) $\rho$ 在 $\Phi \left(x\right)$ 处二阶方向可微，且 $\Phi$ 在点 $x$ 附近分段仿射(线性)；

3) $\rho$ 在 $\Phi \left(x\right)$ 附近分段仿射(线性)，且 $\Phi$ 在点 $x$ 处二阶方向可微。

此外， $\forall y\in {ℝ}^n$ ，有

当(1)成立， $G^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)={\Phi }^{\prime }{\left(x\mathrm{<mo>\; ;\; </mo>}y\right)}^{\text{T}}{\left(\nabla \rho \right)}^{\prime }\left(\Phi \left(x\right)\mathrm{<mo>\; ;\; </mo>}{\Phi }^{\prime }\left(x\mathrm{<mo>\; ;\; </mo>}y\right)\right)+\nabla \rho {\left(\Phi \left(x\right)\right)}^{\text{T}}{\Phi }^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)\mathrm{,}$ (14)

当(2)成立， $G^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)={\rho }^{\left(2\right)}\left(\Phi \left(x\right)\mathrm{<mo>\; ;\; </mo>}{\Phi }^{\prime }\left(x\mathrm{<mo>\; ;\; </mo>}y\right)\right)\mathrm{,}$ (15)

当(3)成立， $G^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)={\rho }^{\prime }\left(\Phi \left(x\right)\mathrm{<mo>\; ;\; </mo>}{\Phi }^{\left(2\right)}\left(x\mathrm{<mo>\; ;\; </mo>}y\right)\right)\mathrm{.}$ (16)

3.2. 问题(2)的二阶d-稳定点

为了研究问题(2)的二阶d-稳定点，给出如下假设。

假设3.1 [19] 惩罚函数 $\varphi \mathrm{<mo>\; :\; </mo>}{ℝ}^{+}\to {ℝ}^{+}$ 具有凸差形式， $\varphi \left(t\right):=g\left(t\right)-h\left(t\right)$ ，其中g是 $t\in \left[\mathrm{0,}\infty \right)$ 上的仿射(线性)函数，且 $g^{\prime }\left(0\right):=g^{\prime }\left(0^{+}\right)$ ，h是 $t\in \left(\mathrm{0,}\infty \right)$ 上的凸函数且半光滑可微， $h^{\prime }\left(0\right)\mathrm{<mo>\; :\; </mo>}=h^{\prime }\left(0^{+}\right)$ 。

容易验证，前述的折叠凹惩罚函数中MCP、SCAD满足假设3.1的条件。

定理3.1 若假设3.1成立， $\forall y\in {ℝ}^n$ ，则问题(2)在点 $x^{\mathrm{<mo>\; *\; </mo>}}$ 处的二阶方向导数有以下表达式：

$\begin{array}{c}{F}^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle {\nabla }^{2}f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)y\mathrm{,}y\rangle +{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)-h^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)\right]w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\\ -{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{w}^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)H^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \mathrm{<mo>\; ;\; </mo>}{w}^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right)\mathrm{,}\end{array}$ (17)

其中 $w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)$ 和 $w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)$ 可分别由(6)和(13)得到，对任意 $t\in \left[\mathrm{0,}\infty \right)$ ， $H\left(t\right):=h^{\prime }\left(t\right)$ 。

证明. 因为f是二阶连续可微的，因此 $f^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle {\nabla }^{2}f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)y\mathrm{,}y\rangle$ 。由于 ${\mathcal{l}}_1$ 范数的二阶方向导数为零，式中凸差部分的二阶方向导数可由[19, Lemma 3.5]中的证明得到。 □

下面给出问题(2)在假设3.1条件下的二阶d-稳定点的特征。

推论3.1 若假设3.1成立，设 $x^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^n$ 是问题(2)的二阶d-稳定点，则 $\forall y\in D\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有

$\langle {\nabla }^{2}f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)y\mathrm{,}y\rangle +{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[{\left(g\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)-{\left(h\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right]\ge \mathrm{0,}$ (18)

其中 $\forall j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，

$w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=\frac{\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}},y_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert },$

$w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=\frac{{\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \Vert y_{\left(j\right)}\Vert \right)}^2-{\left|\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}},y\rangle \right|}^2}{{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }^3},$

${\left(g\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=g^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right),$

${\left(h\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)H^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert ;w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right)+h^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right).$

证明. 因为 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是问题(2)的二阶d-稳定点，则 $x^{\mathrm{<mo>\; *\; </mo>}}$ 一定是问题(2)的一阶d-稳定点，根据定理2.3证明中的(9)，对任意的 $y\in D\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有

$0\le {\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}{\displaystyle \underset{i\in I_j\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left\{{\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)i}+{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-\underset{1\le \upsilon \le \bar{\upsilon }}{\max }{h^{\prime }}_{\upsilon }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)i}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\right\}\cdot y_{\left(j\right)i}\mathrm{.}$

从而

${\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)}+{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-h^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }=\mathrm{0,}$

$\Rightarrow {\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\langle {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)}+{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-h^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\mathrm{,}{y}_{\left(j\right)}\rangle =\mathrm{0,}$

$\Rightarrow {\displaystyle \underset{j=1}{\overset{J}{\sum }}}\langle {\left[\nabla f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\left(j\right)}+{\lambda }_1\mathrm{sgn}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)+{\lambda }_2\left[g^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)-h^{\prime }\circ w\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\right)\right]\frac{x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}}{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }\mathrm{,}{y}_{\left(j\right)}\rangle =\mathrm{0,}$

因此

$0=F^{\prime }\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)\mathrm{.}$

因为 $x^{\mathrm{<mo>\; *\; </mo>}}$ 是问题(2)的二阶d-稳定点，故有 $F^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)\ge 0$ ，由定义3.2和定理3.1，得

$\begin{array}{l}0\le \langle {\nabla }^{2}f\left(x^{*}\right)y,y\rangle +{\displaystyle \underset{j=1}{\overset{J}{\sum }}}\left[g^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)-h^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)\right]w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\\ -{\displaystyle \underset{j=1}{\overset{J}{\sum }}}{w}^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)H^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert ;w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right).\end{array}$

根据(6)和(13)， $\forall j\notin J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有 $w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=0$ ，进而 $\forall j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ ，有

$w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=\frac{\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}},y_{\left(j\right)}\rangle }{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert },$

$w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=\frac{{\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \Vert y_{\left(j\right)}\Vert \right)}^2-{\left|\langle x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}},y\rangle \right|}^2}{{\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert }^3},$

${\left(g\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=g^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right),$

${\left(h\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)=w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)H^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert ;w^{\prime }\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right)+h^{\prime }\left(\Vert x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\Vert \right)w^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right).$

故

$F^{\left(2\right)}\left(x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}y\right)=\langle {\nabla }^{2}f\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)y\mathrm{,}y\rangle +{\displaystyle \underset{j\in J\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)}{\sum }}\left[{\left(g\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)-{\left(h\circ w\right)}^{\left(2\right)}\left(x_{\left(j\right)}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; ;\; </mo>}{y}_{\left(j\right)}\right)\right]\ge 0.$ □

4. 总结

本文研究了带有 ${\mathcal{l}}_1$ 稀疏惩罚和非凸折叠凹组稀疏惩罚的稀疏加组稀疏优化问题(2)，分别对问题(2)的一阶、二阶d-稳定点进行了刻画和分析，并分析了问题(2)中d-稳定点和局部最优解的关系。这为进一步分析和求解此类问题提供了一定理论基础。后续我们的工作将围绕此类问题的其他稳定点的具体刻画以及约束优化问题的稳定点做进一步的分析。

基金项目

国家自然科学基金项目(11861020，12261020)、贵州省科技计划项目(ZK [2021] 009，[2018] 5781)、贵州省高层次留学人才创新创业择优资助重点项目([2018] 03)和贵州省教育厅青年科技人才成长项目([2018] 121)。

NOTES

^*通讯作者。