贵州大学，数学与统计学院，贵州 贵阳

收稿日期：2022年9月26日；录用日期：2022年10月19日；发布日期：2022年10月28日

摘要

本文研究稀疏加组稀疏优化问题的非凸松弛模型，其中惩罚项既含有稀疏惩罚，又含有组稀疏惩罚，对稀疏惩罚和组稀疏惩罚均采用折叠凹惩罚函数进行连续松弛，得到复合非光滑非凸优化模型。为刻画此模型的最优性条件，给出了其方向导数刻画和方向稳定点，分析了方向稳定点的特征及其局部最优性质。为计算模型的方向稳定点，构造了模型的光滑化逼近问题，并证明了光滑化问题的一阶稳定点收敛于模型的方向稳定点，为使用光滑方法计算模型的方向稳定点提供了理论保证。

关键词

稀疏加组稀疏优化问题，非光滑非凸优化，折叠凹惩罚函数，光滑化方法，方向稳定点

Directional Stationary Points of Sparse plus Group Sparse Optimization Problems with Its Smoothing Methods

Yanyan Su, Dingtao Peng^*

School of Mathematics and Statistics, Guizhou University, Guizhou University, Guiyang Guizhou

Received: Sep. 26^th, 2022; accepted: Oct. 19^th, 2022; published: Oct. 28^th, 2022

ABSTRACT

In this paper, we study the nonconvex relaxation model for the sparse plus group sparse optimization problem, in which the penalty term contains both sparse penalty and group sparse penalty. As continuous relaxations, the folded concave penalty functions are used to relax both sparse penalty and group sparse penalty, which results the compound nonsmooth and nonconvex optimization model. In order to characterize the optimality of the nonconvex relaxation problem, the directional derivative and the directional stationary point are introduced, and then the characteristics of the directional stationary points and its local optimality are analyzed. To calculate the directional stationary points of the relaxation model, the smoothing approximation problem is constructed, and it is proved that the stationary points of the smoothing problem converge to the directional stationary point of the relaxation problem, which provides a theoretical guarantee for the calculation of the directional stationary point of the relaxation problem by using the smooth methods.

Keywords:Sparse plus Group Sparse Optimization Problem, Nonconvex and Nonsmooth Optimization, Folded Concave Penalty Function, Smoothing Method, Stationary Points

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

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

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

1. 引言

稀疏性是自然界中普遍存在的一种性质，利用该性质能够实现对信息的充分压缩，从而减少所需储存空间和信息的传输量，或是从海量的信息中过滤噪声影响提炼有效信息，随着大数据时代的到来，稀疏优化在压缩感知、变量选择、图像恢复等领域引起了广泛的关注，这些问题的主要目的是寻求欠定线性或非线性方程组的最稀疏解。

通常的稀疏性是对向量的每个分量而言的，而组稀疏是把向量的分量进行分组再考查各组是否整体为零，它体现为向量中非零分量或零分量会集中出现在某几个区域。组稀疏优化是一类具有分组结构的稀疏优化问题，利用变量之间结构关系的先验信息对变量进行分组分块，进而提高结果的可解释性和预测性能。对于一个n维变量 $x\in {ℝ}^n$，我们可以利用先验信息将x分成K组： $x={\left(x_{\left(1\right)}^{\top },\cdots ,x_{\left(K\right)}^{\top }\right)}^{\top }\in {ℝ}^n$，其中 $x_{\left(j\right)}={\left(x_{\left(j\right)1},\cdots ,x_{\left(j\right)n_j}\right)}^{\top }\in {ℝ}^{n_j}$ 表示x的第j个分组， $x_{\left(j\right)i}\in ℝ$ 表示 $x_{\left(j\right)}$ 的第i个元素，第j组中分量的个数为 $n_j$，${\displaystyle {\sum }_{j=1}^k{n}_j}=n$。近年来，组稀疏结构在机器学习、信号图像处理、数理统计、模式识别、生物信息学等领域引起了广泛的关注 [1] [2] [3] [4] [5]。

在应用中，有时真实信号/数据不仅具有稀疏结构，同时也具有组稀疏结构，这就需要考虑如下稀疏加组稀疏优化问题：

$\underset{x\in {ℝ}^n}{\min }f\left(x\right):=\mathcal{L}\left(x\right)+{\lambda }_1{\Vert x\Vert }_0+{\lambda }_2{\Vert x\Vert }_{2,0}$ (1)

其中 ${\lambda }_1,{\lambda }_2>0$，$\mathcal{L}:{ℝ}^n\to ℝ$ 连续可微， ${\Vert x\Vert }_0:=\#\left\{x_{\left(j\right)i}:x_{\left(j\right)i}\ne 0,j=1,\cdots ,K;i=1,\cdots ,n_j\right\}=$ {x中非零分量的个数}，而 ${\Vert x\Vert }_{2,0}:=\#\left\{x_{\left(j\right)}:\Vert x_{\left(j\right)}\Vert \ne 0,j=1,\cdots ,K\right\}=$ {x中非零组的个数}。

正则项中 ${\mathcal{l}}_0$ -范数与 ${\mathcal{l}}_{2,0}$ -范数的存在使得上述稀疏加组稀疏优化问题本质上是一类非凸、非光滑、非Lipschitz，甚至是不连续的NP难问题 [4] [6]。一种常见的处理方法是研究其松弛模型。 ${\mathcal{l}}_1$ -范数是 ${\mathcal{l}}_0$ -范数最常用的凸松弛，受到很多研究，人们提出了许多求解大规模 ${\mathcal{l}}_1$ 正则问题的高效算法 [7] [8] [9]。但 ${\mathcal{l}}_1$ -松弛容易导致过度松弛而产生有偏估计，模型的解也不具备orcale性质 [10] [11] [12]。Fan和Li [11] [12] 提出了一种折叠凹惩罚，并证明了该非凸优化能够得到具有无偏性和orcale性质的解。随后研究者们给出了一系列连续的非凸惩罚函数，包括对数罚 [11]、SCAD罚(Smoothly Clipped Absolute Deviation Penalty) [11]、MCP (Minimax Concave Penalty) [13]、Capped- ${\mathcal{l}}_1$ 罚 [14] [15]、分数罚 [16]、硬阈值罚(HTP) [17] [18] 和桥罚 [19] 等。

对稀疏加组稀疏优化问题(1)，本文考虑以下松弛模型：

$\begin{array}{l}\underset{x\in {\text{R}}^n}{\min }f\left(x\right):=\mathcal{L}\left(x\right)+{\lambda }_1{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\phi }_1}\left(\left|x_i\right|\right)+{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\phi }_2}\left(\Vert x_{\left(j\right)}\Vert \right)\\ =\mathcal{L}\left(x\right)+{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}{\lambda }_1}{\phi }_1\left(\left|x_{\left(j\right)i}\right|\right)+{\lambda }_2{\phi }_2\left(\Vert x_{\left(j\right)}\Vert \right)\right]},\end{array}$ (2)

其中 ${\lambda }_1,{\lambda }_2>0$，${\phi }_{\mathcal{l}}:R_{+}\to R_{+}\left(\mathcal{l}=1,2\right)$ 为满足以下条件的折叠凹罚函数：

${\phi }_{\mathcal{l}}$ 是局部Lipschitz连续的，在 $\left[0,\infty \right)$ 上单调不减，且 ${{\phi }^{\prime }}_{\mathcal{l}}\left(0\right):={{\phi }^{\prime }}_{\mathcal{l}}\left(0+\right)>0$ ；

${\phi }_{\mathcal{l}}\left(0\right)=0$，且当 $t>0$ 时， ${\phi }_{\mathcal{l}}\left(t\right)>0$。

本文结构如下，在第二节中，我们介绍方向稳定点和局部最优性质，并给出上述松弛模型的方向导数的表达式和方向稳定点的特征；第三节对松弛模型构造光滑化逼近函数，并给出了光滑化问题的一阶稳定点的刻画及性质；第四节研究光滑化问题一阶稳定点与松弛问题的方向稳定点的一致性，为使用光滑化方法求解松弛模型提供理论保证。

符号标记： $\mathcal{J}\left(x\right):=\left\{j\in \left\{1,\cdots ,K\right\}:x_{\left(j\right)}\ne 0\right\}$ 表示x中非零分组的下标， ${\mathcal{I}}_j\left(x\right):=\left\{i\in \left\{1,\cdots ,n_j\right\}:x_{\left(j\right)i}\ne 0\right\}$ 表示x的第j组中非零元素的下标， $\left|{\mathcal{I}}_j\left(x\right)\right|$ 表示第j组中非零元素的个数， $x_{{\mathcal{I}}_j\left(x\right)}$ 表示第j组中所有非零元素按原来的顺序组成的向量， $\mathcal{D}\left(x\right)=\left\{d\in {ℝ}^n:d_{\left(j\right)i}=0,\forall j=\left\{1,\cdots ,K\right\},i\notin {\mathcal{I}}_j\left(x\right)\right\}$，${\nabla }_{\left(j\right)i}\mathcal{L}\left(x\right)=\frac{\partial \mathcal{L}\left(x\right)}{\partial x_{\left(j\right)i}}$，${\nabla }_{\left(j\right)}\mathcal{L}\left(x\right)=\frac{\partial \mathcal{L}\left(x\right)}{\partial x_{\left(j\right)}}={\left(\frac{\partial \mathcal{L}\left(x\right)}{\partial x_{\left(j\right)1}},\cdots ,\frac{\partial \mathcal{L}\left(x\right)}{\partial x_{\left(j\right)n_j}}\right)}^{\top }$。

2. 问题(2)的方向稳定点

2.1. 方向稳定点的局部最优性

首先，我们介绍方向稳定点的定义 [20] [21] [22] [23]。

定义2.1 (方向稳定点)设 $f:{ℝ}^n\to ℝ$ 在给定点 $x^{*}\in {ℝ}^n$ 处方向可微，若 $\forall d\in {ℝ}^n$，f的方向导数

$f\prime \left(x^{*};d\right)=\underset{t\downarrow 0}{\lim }\frac{f\left(x^{*}+td\right)-f\left(x^{*}\right)}{t}\ge 0,$

则称 $x^{*}$ 为f的一个方向稳定点。

注意到，若f在 $x^{*}$ 处可微，则 $\nabla f\left(x^{*}\right)=0$，进而 $f\prime \left(x^{*};d\right)=\langle \nabla f\left(x^{*}\right),d\rangle =0,\forall d\in {ℝ}^n$。

为了方便表示，记 $m\left(x\right)=\Vert x\Vert$，则任意 $x,d\in {ℝ}^n$，$m\left(x\right)$ 的方向导数为：

$m\prime \left(x;d\right)=\{\begin{array}{ll}\Vert d\Vert ,\hfill & \Vert x\Vert =0\hfill \\ \frac{\langle x,d\rangle }{\Vert x\Vert },\hfill & \Vert x\Vert \ne 0\hfill \end{array}.$ (3)

特别的，当 $n=1$ 时， $m\left(x\right)=\Vert x\Vert =\left|x\right|$，因此

$m\prime \left(x;d\right)=\{\begin{array}{ll}\left|d\right|,\hfill & x=0\hfill \\ \frac{xd}{\left|x\right|},\hfill & x\ne 0\hfill \end{array}.$ (4)

文献 [24] 中指出，方向稳定点有以下局部最优性质。

引理2.1 (方向稳定点的局部最优性)设 $f:{ℝ}^n\to ℝ$ 在 $x\in {ℝ}^n$ 上是局部Lipschitz连续且方向可微的，则有下列结论：

(i) 如果 $\hat{x}$ 是f的局部极小点，则 $\hat{x}$ 也是f的方向稳定点。

(ii) f在 $\hat{x}$ 满足一阶增长性条件，即存在 $\hat{x}$ 的一个邻域 $\mathcal{V}$ 和 $\delta >0$，使得

$f\left(x\right)\ge f\left(\hat{x}\right)+\delta \Vert x-\hat{x}\Vert ,\forall x\in \mathcal{V},$

等价于在 $\hat{x}$ 满足

$f\prime \left(\hat{x};d\right)>0,\forall d\in {ℝ}^n\backslash \left\{0\right\}.$

2.2. 方向稳定点的特征

在本小节中，我们给出了问题(2)方向导数的计算公式和方向稳定点的特征。

前述折叠凹惩罚函数大多可以写成凸差(Difference-of-Convex)形式 [20]，即两个凸函数的差。我们的分析基于惩罚函数的凸差表示。因此，引进以下假设。

假设2.1罚函数 ${\phi }_{\mathcal{l}}:{ℝ}_{+}\to {ℝ}_{+},\left(\mathcal{l}=1,2\right)$ 具有凸差形式： ${\phi }_{\mathcal{l}}\left(t\right)\triangleq g_{\mathcal{l}}\left(t\right)-h_{\mathcal{l}}\left(t\right)$，其中 $h_{\mathcal{l}}\left(t\right)\triangleq {\max }_{1\le v\le \overline{v_{\mathcal{l}}}}\left\{h_{\mathcal{l}v}\left(t\right)\right\}$，$g_{\mathcal{l}},h_{\mathcal{l}v}\left(1\le v\le \overline{v_{\mathcal{l}}}\right)$ 在 $t\in \left(0,\infty \right)$ 上都是可微凸函数，且满足：

${g^{\prime }}_{\mathcal{l}}\left(0\right):={g^{\prime }}_{\mathcal{l}}\left(0+\right),{h^{\prime }}_{\mathcal{l}v}\left(0\right)={h^{\prime }}_{\mathcal{l}v}\left(0+\right)\left(1\le v\le \overline{v_{\mathcal{l}}}\right).$

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

$\underset{x\in {ℝ}^n}{\min }f\left(x\right):=\mathcal{L}\left(x\right)+\left\{{\lambda }_1{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[g_1\left(\left|x_{\left(j\right)i}\right|\right)-h_1\left(\left|x_{\left(j\right)i}\right|\right)\right]}}+{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[g_2\left(\Vert x_{\left(j\right)}\Vert \right)-h_2\left(\Vert x_{\left(j\right)}\Vert \right)\right]}\right\}.$ (5)

定理2.1若假设2.1成立，问题(2)的方向导数有以下计算公式：

$\begin{array}{l}f\prime \left(x;d\right):=\langle \nabla \mathcal{L}\left(x\right),d\rangle +{\lambda }_1{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[{g^{\prime }}_1\left(\left|x_{\left(j\right)i}\right|\right)-\underset{v_{\left(j\right)i}\in \mathcal{A}\left(x_{\left(j\right)i}\right)}{\max }h{\prime }_{1v_{\left(j\right)i}}\left(\left|x_{\left(j\right)i}\right|\right)\right]m\prime }}\left(x_{\left(j\right)i};d_{\left(j\right)i}\right)\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{g^{\prime }}_2\left(\Vert x_{\left(j\right)}\Vert \right)-\underset{v_{\left(j\right)}\in \mathcal{A}\left(x_{\left(j\right)}\right)}{\max }{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert x_{\left(j\right)}\Vert \right)\right]m\prime }\left(x_{\left(j\right)};d_{\left(j\right)}\right),\end{array}$ (6)

其中 $\mathcal{A}\left(x_{\left(j\right)i}\right)=\left\{v_{\mathcal{l}}\in \left\{1,2,\cdots ,\overline{v_{\mathcal{l}}}\right\}:h_{v_{\mathcal{l}}}\left(\left|x_{\left(j\right)i}\right|\right)=h\left(\left|x_{\left(j\right)i}\right|\right)\right\}$，$\mathcal{A}\left(x_{\left(j\right)}\right)=\left\{v_{\mathcal{l}}\in \left\{1,2,\cdots ,\overline{v_{\mathcal{l}}}\right\}:h_{v_{\mathcal{l}}}\left(\Vert x_{\left(j\right)}\Vert \right)=h\left(\Vert x_{\left(j\right)}\Vert \right)\right\}$ $\left(\mathcal{l}=1,2\right)$。

证明. [24] (定理2.3)中给出了组稀疏惩罚问题折叠凹松弛模型的方向导数的表达式，在该表达式基础上，加上稀疏惩罚项折叠凹松弛的方向导数表达式即可，而后者可以通过方向导数的定义直接计算得到。 $\square$

下面引理说明，在问题(2)的任意方向稳定点 $\hat{x}$ 处，对应于 $\hat{x}$ 的非零元素的支撑集上损失函数 $\mathcal{L}$ 的梯度值可以用 $g_{\mathcal{l}},h_{\mathcal{l}v}\left(\mathcal{l}=1,2\right)$ 的导数刻画，而对应于 $\hat{x}$ 的非零组中元素的位置上， $\mathcal{L}$ 的梯度值受到 $g_{\mathcal{l}}\left(0\right),h_{\mathcal{l}v}\left(0\right)$ 的控制。

引理2.2假设2.1成立， $\hat{x}\in {ℝ}^n$ 是问题(2)的一个方向稳定点，则可以得到以下结论： $\forall v_{\left(j\right)}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)}\right)$，$v_{\left(j\right)i}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)i}\right)$，

(i) $\forall j\in \mathcal{J}\left(\hat{x}\right),i\in {\mathcal{I}}_j(\; x\; ^\; )$

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|=\left|{\hat{x}}_{\left(j\right)i}\right|\left|{\lambda }_1\frac{\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]}{\left|{\hat{x}}_{\left(j\right)i}\right|}+{\lambda }_2\frac{\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right|.$

特别的，当 $\bar{v}=1$ 时， $\forall j\in \mathcal{J}\left(\hat{x}\right),i\in {\mathcal{I}}_j(\; x\; ^\; )$

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|=\left|{\hat{x}}_{\left(j\right)i}\right|\left|{\lambda }_1\frac{{{\phi }^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)}{\left|{\hat{x}}_{\left(j\right)i}\right|}+{\lambda }_2\frac{{{\phi }^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right|.$

(ii) 任取 $j\in \mathcal{J}\left(\hat{x}\right)$，满足 $\left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)\ne \varnothing$ (相当于 $\left|{\mathcal{I}}_j\left(\hat{x}\right)\right|<n_j$ 或 $x_{{\mathcal{I}}_j\left(\hat{x}\right)}\ne x_{\left(j\right)}$ )，则

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1\left[{g^{\prime }}_1\left(0\right)-h{\prime }_{1v_{\left(j\right)i}}\left(0\right)\right],\forall i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right),$

进而

$\left|{\sum }_{i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)}{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1{\sum }_{i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)}\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(0\right)\right].$

特别的，当 $\overline{v_{\mathcal{l}}}=1\left(\mathcal{l}=1,2\right)$ 时， $\forall j\in \mathcal{J}\left(\hat{x}\right)$，若 $\left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)\ne \varnothing$，则

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1{{\phi }^{\prime }}_1\left(0\right),\forall i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right),$ (7)

进而

$\left|{\sum }_{i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)}{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1\left(n_j-\left|I_j\left(\hat{x}\right)\right|\right){{\phi }^{\prime }}_1\left(0\right).$

证明. (i) 根据定理2.1， $\forall d\in {ℝ}^n$，$v_{\left(j\right)}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)}\right)$，$v_{\left(j\right)i}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)i}\right)$，可以得到：

$\begin{array}{c}0\le f^{\prime }\left(\hat{x};d\right)\\ =\langle \nabla \mathcal{L}\left(\hat{x}\right),d\rangle +{\lambda }_1{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-\underset{v_{\left(j\right)i}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)i}\right)}{\max }{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]m^{\prime }}}\left({\hat{x}}_{\left(j\right)i};d_{\left(j\right)i}\right)\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-\underset{v_{\left(j\right)}\in \mathcal{A}\left({\hat{x}}_{\left(j\right)}\right)}{\max }{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]m^{\prime }}\left({\hat{x}}_{\left(j\right)};d_{\left(j\right)}\right)\\ \le \langle \nabla \mathcal{L}\left(\hat{x}\right),d\rangle +{\lambda }_1{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]m^{\prime }}}\left({\hat{x}}_{\left(j\right)i};d_{\left(j\right)i}\right)\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]m^{\prime }}\left({\hat{x}}_{\left(j\right)};d_{\left(j\right)}\right).\end{array}$ (8)

特别地，任取 $d\in \mathcal{D}\left(\hat{x}\right)$，则根据(3)和(4)知

$m^{\prime }\left({\hat{x}}_{\left(j\right)i};d_{\left(j\right)i}\right)=\{\begin{array}{ll}\left|d_{\left(j\right)i}\right|=0,\hfill & {\hat{x}}_{\left(j\right)i}=0\hfill \\ \frac{{\hat{x}}_{\left(j\right)i}{d}_{\left(j\right)i}}{\left|{\hat{x}}_{\left(j\right)i}\right|},\hfill & {\hat{x}}_{\left(j\right)i}\ne 0\hfill \end{array},m^{\prime }\left({\hat{x}}_{\left(j\right)};d_{\left(j\right)}\right)=\{\begin{array}{ll}\Vert d_{\left(j\right)}\Vert =0,\hfill & \Vert {\hat{x}}_{\left(j\right)}\Vert =0\hfill \\ \frac{\langle {\hat{x}}_{\left(j\right)},d_{\left(j\right)}\rangle }{\Vert {\hat{x}}_{\left(j\right)}\Vert },\hfill & \Vert {\hat{x}}_{\left(j\right)}\Vert \ne 0\hfill \end{array}.$ (9)

因此，得到

$\begin{array}{c}0\le {\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left\{{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)d_{\left(j\right)i}+{\lambda }_1\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]m^{\prime }\left({\hat{x}}_{\left(j\right)i};d_{\left(j\right)i}\right)\right\}}}\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]m^{\prime }}\left({\hat{x}}_{\left(j\right)};d_{\left(j\right)}\right)\\ ={\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }{\displaystyle \underset{i\in {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }\left\{{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)d_{\left(j\right)i}+{\lambda }_1\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]\frac{{\hat{x}}_{\left(j\right)i}{d}_{\left(j\right)i}}{\left|{\hat{x}}_{\left(j\right)i}\right|}\right\}}}\\ +{\lambda }_2{\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}\frac{\langle {\hat{x}}_{\left(j\right)},d_{\left(j\right)}\rangle }{\Vert {\hat{x}}_{\left(j\right)}\Vert }\end{array}$

$\begin{array}{c}={\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }{\displaystyle \underset{i\in {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }{d}_{\left(j\right)i}}}{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\\ +{\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }{\displaystyle \underset{i\in {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }{\hat{x}}_{(j)i}\{\frac{{\lambda }_1\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]}{\left|{\hat{x}}_{\left(j\right)i}\right|}+\frac{{\lambda }_2\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\}}}\end{array}$

根据 $d\in \mathcal{D}\left(\hat{x}\right)$ 的任意性，可得 $\forall j\in \mathcal{J}\left(\hat{x}\right),i\in {\mathcal{I}}_j(\; x\; ^\; )$

$0={\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)+{\hat{x}}_{\left(j\right)i}\left\{\frac{{\lambda }_1\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]}{\left|{\hat{x}}_{\left(j\right)i}\right|}+\frac{{\lambda }_2\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right\}.$

因此 $\forall j\in \mathcal{J}\left(\hat{x}\right),i\in {\mathcal{I}}_j(\; x\; ^\; )$

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|=\left|{\hat{x}}_{\left(j\right)i}\right|\left|{\lambda }_1\frac{\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_{1v_{\left(j\right)i}}\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]}{\left|{\hat{x}}_{\left(j\right)i}\right|}+{\lambda }_2\frac{\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j\right)}}\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right|.$

当 $\bar{v}=1$ 时，可得 $\forall j\in \mathcal{J}\left(\hat{x}\right),i\in {\mathcal{I}}_j(\; x\; ^\; )$

$0={\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)+{\hat{x}}_{\left(j\right)i}\left[{\lambda }_1\frac{{{\phi }^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)}{\left|{\hat{x}}_{\left(j\right)i}\right|}+{\lambda }_2\frac{{{\phi }^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right],$ (10)

进而

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|=\left|{\hat{x}}_{\left(j\right)i}\right|\left|{\lambda }_1\frac{{{\phi }^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)}{\left|{\hat{x}}_{\left(j\right)i}\right|}+{\lambda }_2\frac{{{\phi }^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)}{\Vert {\hat{x}}_{\left(j\right)}\Vert }\right|.$

(ii) 任取满足 中条件的 $j_0$，${\hat{x}}_{\left(j_0\right)}={\left({\hat{x}}_{\left(j_0\right)1},\cdots ,{\hat{x}}_{\left(j_0\right)n_{j_0}}\right)}^{\top }$ 和任意取定 $i_0\in \left\{1,\cdots ,n_{j_0}\right\}\backslash {\mathcal{I}}_{j_0}\left(\hat{x}\right)$，定义 $d^{+},d^{-}$ 如下：

$d_{\left(j\right)i}^{+}=\{\begin{array}{ll}1,\hfill & j=j_0,i=i_0\hfill \\ 0,\hfill & 其它\hfill \end{array},d_{\left(j\right)i}^{-}=\{\begin{array}{ll}-1,\hfill & j=j_0,i=i_0\hfill \\ 0,\hfill & 其它\hfill \end{array},$

则有 $\langle x_{\left(j_0\right)},d_{\left(j_0\right)}^{\pm }\rangle =0$ 且 $\Vert d_{\left(j\right)}^{\pm }\Vert =0,\forall j\ne j_0$。从而由(3)和(4)知

$m\prime \left({\hat{x}}_{\left(j_0\right)};d_{\left(j_0\right)}^{\pm }\right)=\frac{\langle x_{\left(j_0\right)},d_{\left(j_0\right)}^{\pm }\rangle }{\Vert x_{\left(j_0\right)}\Vert }=0,m\prime \left({\hat{x}}_{\left(j_0\right)i_0};d_{\left(j_0\right)i_0}^{\pm }\right)=\left|d_{\left(j_0\right)i}^{\pm }\right|=1.$

根据(8)，可得

$\begin{array}{c}0\le f^{\prime }\left(\hat{x};d^{\pm }\right)\\ \le {\nabla }_{\left(j_0\right)i}\mathcal{L}\left(\hat{x}\right)d_{\left(j_0\right)i_0}^{\pm }+{\lambda }_1\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j_0\right)i_0}\right|\right)-{h^{\prime }}_{1v_{\left(j_0\right)i_0}}\left(\left|{\hat{x}}_{\left(j_0\right)i_0}\right|\right)\right]m^{\prime }\left({\hat{x}}_{\left(j_0\right)i_0};d_{\left(j_0\right)i_0}^{\pm }\right)\\ +{\lambda }_2\left[g_2\left(\Vert {\hat{x}}_{\left(j_0\right)}\Vert \right)-{h^{\prime }}_{2v_{\left(j_0\right)}}\left(\Vert {\hat{x}}_{\left(j_0\right)}\Vert \right)\right]m^{\prime }\left({\hat{x}}_{\left(j_0\right)};d_{\left(j_0\right)}^{\pm }\right)\\ \le \pm {\nabla }_{\left(j_0\right)i_0}\mathcal{L}\left(\hat{x}\right)+{\lambda }_1\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_{1v_{\left(j_0\right)i_0}}\left(0\right)\right],\end{array}$

因此

$\left|{\nabla }_{\left(j_0\right)i_0}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_{1v_{\left(j_0\right)i_0}}\left(0\right)\right].$

进而

$\left|{\sum }_{i\in \left\{1,\cdots ,n_{j_0}\right\}\backslash {\mathcal{I}}_{j_0}\left(\hat{x}\right)}{\nabla }_{\left(j_0\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\sum }_{i\in \left\{1,\cdots ,n_{j_0}\right\}\backslash {\mathcal{I}}_{j_0}\left(\hat{x}\right)}\left|{\nabla }_{\left(j_0\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1{\sum }_{i\in \left\{1,\cdots ,n_{j_0}\right\}\backslash {\mathcal{I}}_{j_0}\left(\hat{x}\right)}\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_{1v_{\left(j_0\right)i}}\left(0\right)\right].$

当 $\overline{v_{\mathcal{l}}}=1\left(\mathcal{l}=1,2\right)$ 时， $\forall j\in \mathcal{J}\left(\hat{x}\right)$，若 $\left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)\ne \varnothing$，则

$\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1{{\phi }^{\prime }}_1\left(0\right),$

进而

$\left|{\sum }_{i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)}{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_1\left(n_j-\left|I_j\left(\hat{x}\right)\right|\right)\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_1\left(0\right)\right]={\lambda }_1\left(n_j-\left|I_j\left(\hat{x}\right)\right|\right){{\phi }^{\prime }}_1\left(0\right).$

结论得证。 $\square$

当 ${\phi }_{\mathcal{l}}\left(\mathcal{l}=1,2\right)$ 是 $\left(0,\infty \right)$ 上两个可微凸函数的差(例如SCAD罚、MCP、Capped- ${\mathcal{l}}_1$ 罚)时，下述推论给出问题(2)的方向导数在其方向稳定点 $\hat{x}$ 处更加简洁的表达式，以及当 $f\prime \left(\hat{x};d\right)=0$ 时，方向d的特征。

推论2.1若假设2.1成立，且 ${\phi }_{\mathcal{l}}\left(t\right)=g_{\mathcal{l}}\left(t\right)-h_{\mathcal{l}}\left(t\right)$，其中 $g_{\mathcal{l}},h_{\mathcal{l}}\left(\mathcal{l}=1,2\right)$ 是 $\left(0,\infty \right)$ 上的可微凸函数。若 $\hat{x}$ 是问题(2)的方向稳定点，则下述结论成立：

(i) $\forall d\in {ℝ}^n$，

$f\prime \left(\hat{x};d\right)={\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i\notin {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }\left[{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)d_{\left(j\right)i}+{\lambda }_1{{\phi }^{\prime }}_1\left(0\right)\left|d_{\left(j\right)i}\right|\right]}}+{\lambda }_2{\displaystyle \underset{j\notin \mathcal{J}\left(\hat{x}\right)}{\sum }{{\phi }^{\prime }}_2}\left(0\right)\Vert d_{\left(j\right)}\Vert .$ (11)

(ii) 若 $j\notin \mathcal{J}\left(\hat{x}\right)$，则下述不等式成立：

$\begin{array}{l}\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|\le {\lambda }_2{{\phi }^{\prime }}_2\left(0\right)+{\lambda }_1{{\phi }^{\prime }}_1\left(0\right),\forall i\in \left\{1,\cdots ,n_j\right\},\\ 0\le {\lambda }_2{{\phi }^{\prime }}_2\left(0\right)\Vert d_{\left(j\right)}\Vert +{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)d_{\left(j\right)i}+{\lambda }_1{{\phi }^{\prime }}_1\left(0\right)\left|d_{\left(j\right)i}\right|\right]},\forall d\in {ℝ}^n.\end{array}$

(iii) 若 ${\lambda }_1{{\phi }^{\prime }}_1\left(0\right)>\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|,\forall j\in \mathcal{J}\left(\hat{x}\right),\forall i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right)$，则当方向 $d\in {ℝ}^n$ 满足 $f\prime \left(\hat{x};d\right)=0$ 时，必有

$d_{\left(j\right)i}=0,\forall j\in \mathcal{J}\left(\hat{x}\right),\forall i\in \left\{1,\cdots ,n_j\right\}\backslash {\mathcal{I}}_j\left(\hat{x}\right).$

(iv) 若 ${{\phi }^{\prime }}_2\left(0\right)>0$，${\lambda }_1{{\phi }^{\prime }}_1\left(0\right)>\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|,\forall j\in \mathcal{J}\left(\hat{x}\right),\forall i\in \left\{1,\cdots ,n_j\right\}$，则当方向 $d\in {ℝ}^n$ 满足 $f\prime \left(\hat{x};d\right)=0$ 时，必有

$d_{\left(j\right)}=0,\forall j\notin \mathcal{J}\left(\hat{x}\right).$

(v) 若 ${{\phi }^{\prime }}_2\left(0\right)>0$，${\lambda }_1{{\phi }^{\prime }}_1\left(0\right)>\left|{\nabla }_{\left(j\right)i}\mathcal{L}\left(\hat{x}\right)\right|,\forall j\in \left\{1,\cdots ,K\right\},i\in {\mathcal{I}}_j\left(\hat{x}\right)$，则当方向 $d\in {ℝ}^n$ 满足 $f\prime \left(\hat{x};d\right)=0$ 时，必有 ${\hat{x}}_{\left(j\right)i}=0\Rightarrow d_{\left(j\right)i}=0$.

证明. (i) 因为 $\bar{v}=1$，根据(6)知： $\forall d\in {ℝ}^n$，

$\begin{array}{l}f\prime \left(\hat{x};d\right)=\langle \nabla \mathcal{L}\left(\hat{x}\right),d\rangle +{\lambda }_1{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{n_j}{\sum }}\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]m\prime }}\left({\hat{x}}_{\left(j\right)i};d_{\left(j\right)i}\right)\\ +{\lambda }_2{\displaystyle \underset{j=1}{\overset{K}{\sum }}\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]m\prime }\left({\hat{x}}_{\left(j\right)};d_{\left(j\right)}\right).\end{array}$

由(3)和(4)可得

$\begin{array}{c}{f}^{\prime }\left(\hat{x};d\right)=\langle \nabla \mathcal{L}\left(\hat{x}\right),d\rangle +{\lambda }_1{\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }{\displaystyle \underset{i\in {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }\left[{g^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)-{h^{\prime }}_1\left(\left|{\hat{x}}_{\left(j\right)i}\right|\right)\right]}}\frac{{\hat{x}}_{\left(j\right)i}{d}_{\left(j\right)i}}{\left|{\hat{x}}_{\left(j\right)i}\right|}\\ +{\displaystyle \underset{j=1}{\overset{K}{\sum }}{\displaystyle \underset{i\notin {\mathcal{I}}_j\left(\hat{x}\right)}{\sum }{\lambda }_1}}\left[{g^{\prime }}_1\left(0\right)-{h^{\prime }}_1\left(0\right)\right]\left|d_{\left(j\right)i}\right|+{\lambda }_2{\displaystyle \underset{j\notin \mathcal{J}\left(\hat{x}\right)}{\sum }\left[{g^{\prime }}_2\left(0\right)-{h^{\prime }}_2\left(0\right)\right]}\Vert d_{\left(j\right)}\Vert \\ +{\lambda }_2{\displaystyle \underset{j\in \mathcal{J}\left(\hat{x}\right)}{\sum }\left[{g^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)-{h^{\prime }}_2\left(\Vert {\hat{x}}_{\left(j\right)}\Vert \right)\right]}\frac{\langle {\hat{x}}_{\left(j\right)},d_{\left(j\right)}\rangle }{\Vert {\hat{x}}_{\left(j\right)}\Vert }\end{array}$