稀疏加组稀疏优化问题的方向稳定点及其光滑化方法-凯发娱乐官网

期刊菜单

稀疏加组稀疏优化问题的方向稳定点及其光滑化方法
directional stationary points of sparse plus group sparse optimization problems with its smoothing methods

doi: , , html, , 被引量国家自然科学基金支持
作者: 苏妍妍, 彭定涛^*：贵州大学，数学与统计学院，贵州贵阳
关键词: ；；；；；；；；；

摘要: 本文研究稀疏加组稀疏优化问题的非凸松弛模型，其中惩罚项既含有稀疏惩罚，又含有组稀疏惩罚，对稀疏惩罚和组稀疏惩罚均采用折叠凹惩罚函数进行连续松弛，得到复合非光滑非凸优化模型。为刻画此模型的最优性条件，给出了其方向导数刻画和方向稳定点，分析了方向稳定点的特征及其局部最优性质。为计算模型的方向稳定点，构造了模型的光滑化逼近问题，并证明了光滑化问题的一阶稳定点收敛于模型的方向稳定点in this paper, we study the nonconvex relaxation model for the sparse plus group sparse optimiza-tion 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 sta-tionary 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.，为使用光滑方法计算模型的方向稳定点提供了理论保证。

文章引用：苏妍妍, 彭定涛. 稀疏加组稀疏优化问题的方向稳定点及其光滑化方法[j]. 应用数学进展, 2022, 11(10): 7464-7477.

1. 引言

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

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

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

$\min_{x \in ℝ^{n}} f (x) : = l (x) λ_{1} {‖ x ‖}_{0} λ_{2} {‖ x ‖}_{2, 0}$ (1)

其中 $λ_{1}, λ_{2} > 0$ ， $l : ℝ^{n} \to ℝ$ 连续可微， ${‖ x ‖}_{0} : = # {x_{(j) i} : x_{(j) i} \neq 0, j = 1, \dots, k; i = 1, \dots, n_{j}} =$ {x中非零分量的个数}，而 ${‖ x ‖}_{2, 0} : = # {x_{(j)} : ‖ x_{(j)} ‖ \neq 0, j = 1, \dots, k} =$ {x中非零组的个数}。

正则项中 $l_{0}$ -范数与 $l_{2, 0}$ -范数的存在使得上述稀疏加组稀疏优化问题本质上是一类非凸、非光滑、非lipschitz，甚至是不连续的np难问题 [4] [6]。一种常见的处理方法是研究其松弛模型。 $l_{1}$ -范数是 $l_{0}$ -范数最常用的凸松弛，受到很多研究，人们提出了许多求解大规模 $l_{1}$ 正则问题的高效算法 [7] [8] [9]。但 $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- $l_{1}$ 罚 [14] [15]、分数罚 [16]、硬阈值罚(htp) [17] [18] 和桥罚 [19] 等。

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

$\begin{array}{l} \min_{x \in r^{n}} f (x) : = l (x) λ_{1} \sum_{i = 1}^{n} φ_{1} (| x_{i} |) λ_{2} \sum_{j = 1}^{k} φ_{2} (‖ x_{(j)} ‖) \\ = l (x) \sum_{j = 1}^{k} [\sum_{i = 1}^{n_{j}} λ_{1} φ_{1} (| x_{(j) i} |) λ_{2} φ_{2} (‖ x_{(j)} ‖)], \end{array}$ (2)

其中 $λ_{1}, λ_{2} > 0$ ， $φ_{l} : r_{} \to r_{} (l = 1, 2)$ 为满足以下条件的折叠凹罚函数：

$φ_{l}$ 是局部lipschitz连续的，在 $[0, \infty)$ 上单调不减，且 ${φ^{'}}_{l} (0) : = {φ^{'}}_{l} (0) > 0$ ；

$φ_{l} (0) = 0$ ，且当 $t > 0$ 时， $φ_{l} (t) > 0$ 。

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

符号标记： $j (x) : = {j \in {1, \dots, k} : x_{(j)} \neq 0}$ 表示x中非零分组的下标， $i_{j} (x) : = {i \in {1, \dots, n_{j}} : x_{(j) i} \neq 0}$ 表示x的第j组中非零元素的下标， $| i_{j} (x) |$ 表示第j组中非零元素的个数， $x_{i_{j} (x)}$ 表示第j组中所有非零元素按原来的顺序组成的向量， $d (x) = {d \in ℝ^{n} : d_{(j) i} = 0, \forall j = {1, \dots, k}, i \notin i_{j} (x)}$ ， $\nabla_{(j) i} l (x) = \frac{\partial l (x)}{\partial x_{(j) i}}$ ， $\nabla_{(j)} l (x) = \frac{\partial l (x)}{\partial x_{(j)}} = {(\frac{\partial l (x)}{\partial x_{(j) 1}}, \dots, \frac{\partial l (x)}{\partial x_{(j) n_{j}}})}^{⊤}$ 。

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

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

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

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

$f' (x^{*}; d) = \lim_{t ↓ 0} \frac{f (x^{*} t d) - f (x^{*})}{t} \geq 0,$

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

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

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

$m' (x; d) = {\begin{array}{l} ‖ d ‖, & ‖ x ‖ = 0 \\ \frac{〈 x, d 〉}{‖ x ‖}, & ‖ x ‖ \neq 0 \end{array} .$ (3)

特别的，当 $n = 1$ 时， $m (x) = ‖ x ‖ = | x |$ ，因此

$m' (x; d) = {\begin{array}{l} | d |, & x = 0 \\ \frac{x d}{| x |}, & x \neq 0 \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}$ 的一个邻域 $v$ 和 $δ > 0$ ，使得

$f (x) \geq f (\hat{x}) δ ‖ x - \hat{x} ‖, \forall x \in v,$

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

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

2.2. 方向稳定点的特征

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

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

假设2.1罚函数 $φ_{l} : ℝ_{} \to ℝ_{}, (l = 1, 2)$ 具有凸差形式： $φ_{l} (t) ≜ g_{l} (t) - h_{l} (t)$ ，其中 $h_{l} (t) ≜ \max_{1 \leq v \leq \bar{v_{l}}} {h_{l v} (t)}$ ， $g_{l}, h_{l v} (1 \leq v \leq \bar{v_{l}})$ 在 $t \in (0, \infty)$ 上都是可微凸函数，且满足：

${g^{'}}_{l} (0) : = {g^{'}}_{l} (0), {h^{'}}_{l v} (0) = {h^{'}}_{l v} (0) (1 \leq v \leq \bar{v_{l}}) .$

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

$\min_{x \in ℝ^{n}} f (x) : = l (x) {λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} [g_{1} (| x_{(j) i} |) - h_{1} (| x_{(j) i} |)] λ_{2} \sum_{j = 1}^{k} [g_{2} (‖ x_{(j)} ‖) - h_{2} (‖ x_{(j)} ‖)]} .$ (5)

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

$\begin{array}{l} f' (x; d) : = 〈 \nabla l (x), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} [{g^{'}}_{1} (| x_{(j) i} |) - \max_{v_{(j) i} \in a (x_{(j) i})} h'_{1 v_{(j) i}} (| x_{(j) i} |)] m' (x_{(j) i}; d_{(j) i}) \\ λ_{2} \sum_{j = 1}^{k} [{g^{'}}_{2} (‖ x_{(j)} ‖) - \max_{v_{(j)} \in a (x_{(j)})} {h^{'}}_{2 v_{(j)}} (‖ x_{(j)} ‖)] m' (x_{(j)}; d_{(j)}), \end{array}$ (6)

其中 $a (x_{(j) i}) = {v_{l} \in {1, 2, \dots, \bar{v_{l}}} : h_{v_{l}} (| x_{(j) i} |) = h (| x_{(j) i} |)}$ ， $a (x_{(j)}) = {v_{l} \in {1, 2, \dots, \bar{v_{l}}} : h_{v_{l}} (‖ x_{(j)} ‖) = h (‖ x_{(j)} ‖)}$ $(l = 1, 2)$ 。

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

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

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

(i) $\forall j \in j (\hat{x}), i \in i_{j} ( x ^ )$

$| \nabla_{(j) i} l (\hat{x}) | = | {\hat{x}}_{(j) i} | | λ_{1} \frac{[{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)]}{| {\hat{x}}_{(j) i} |} λ_{2} \frac{[{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)]}{‖ {\hat{x}}_{(j)} ‖} | .$

特别的，当 $\bar{v} = 1$ 时， $\forall j \in j (\hat{x}), i \in i_{j} ( x ^ )$

$| \nabla_{(j) i} l (\hat{x}) | = | {\hat{x}}_{(j) i} | | λ_{1} \frac{{φ^{'}}_{1} (| {\hat{x}}_{(j) i} |)}{| {\hat{x}}_{(j) i} |} λ_{2} \frac{{φ^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)}{‖ {\hat{x}}_{(j)} ‖} | .$

(ii) 任取 $j \in j (\hat{x})$ ，满足 ${1, \dots, n_{j}} \ i_{j} (\hat{x}) \neq \emptyset$ (相当于 $| i_{j} (\hat{x}) | < n_{j}$ 或 $x_{i_{j} (\hat{x})} \neq x_{(j)}$ )，则

$| \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} [{g^{'}}_{1} (0) - h'_{1 v_{(j) i}} (0)], \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x}),$

进而

$| \sum_{i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})} \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} \sum_{i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})} [{g^{'}}_{1} (0) - {h^{'}}_{1 v_{(j) i}} (0)] .$

特别的，当 $\bar{v_{l}} = 1 (l = 1, 2)$ 时， $\forall j \in j (\hat{x})$ ，若 ${1, \dots, n_{j}} \ i_{j} (\hat{x}) \neq \emptyset$ ，则

$| \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} {φ^{'}}_{1} (0), \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x}),$ (7)

进而

$| \sum_{i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})} \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} (n_{j} - | i_{j} (\hat{x}) |) {φ^{'}}_{1} (0) .$

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

$\begin{matrix} 0 \leq f^{'} (\hat{x}; d) \\ = 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - \max_{v_{(j) i} \in a ({\hat{x}}_{(j) i})} {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)] m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) \\ λ_{2} \sum_{j = 1}^{k} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - \max_{v_{(j)} \in a ({\hat{x}}_{(j)})} {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)] m^{'} ({\hat{x}}_{(j)}; d_{(j)}) \\ \leq 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)] m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) \\ λ_{2} \sum_{j = 1}^{k} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)] m^{'} ({\hat{x}}_{(j)}; d_{(j)}) . \end{matrix}$ (8)

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

$m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) = {\begin{array}{l} | d_{(j) i} | = 0, & {\hat{x}}_{(j) i} = 0 \\ \frac{{\hat{x}}_{(j) i} d_{(j) i}}{| {\hat{x}}_{(j) i} |}, & {\hat{x}}_{(j) i} \neq 0 \end{array}, m^{'} ({\hat{x}}_{(j)}; d_{(j)}) = {\begin{array}{l} ‖ d_{(j)} ‖ = 0, & ‖ {\hat{x}}_{(j)} ‖ = 0 \\ \frac{〈 {\hat{x}}_{(j)}, d_{(j)} 〉}{‖ {\hat{x}}_{(j)} ‖}, & ‖ {\hat{x}}_{(j)} ‖ \neq 0 \end{array} .$ (9)

因此，得到

$\begin{matrix} 0 \leq \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} {\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)] m^{'} ({\hat{x}}_{(j) i}; d_{(j) i})} \\ λ_{2} \sum_{j = 1}^{k} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)] m^{'} ({\hat{x}}_{(j)}; d_{(j)}) \\ = \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)] \frac{{\hat{x}}_{(j) i} d_{(j) i}}{| {\hat{x}}_{(j) i} |}} \\ λ_{2} \sum_{j \in j (\hat{x})} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)] \frac{〈 {\hat{x}}_{(j)}, d_{(j)} 〉}{‖ {\hat{x}}_{(j)} ‖} \end{matrix}$

$\begin{matrix} = \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} d_{(j) i} \nabla_{(j) i} l (\hat{x}) \\ \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\hat{x}}_{(j) i} {\frac{λ_{1} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)]}{| {\hat{x}}_{(j) i} |} \frac{λ_{2} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)]}{‖ {\hat{x}}_{(j)} ‖}} \end{matrix}$

根据 $d \in d (\hat{x})$ 的任意性，可得 $\forall j \in j (\hat{x}), i \in i_{j} ( x ^ )$

$0 = \nabla_{(j) i} l (\hat{x}) {\hat{x}}_{(j) i} {\frac{λ_{1} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1 v_{(j) i}} (| {\hat{x}}_{(j) i} |)]}{| {\hat{x}}_{(j) i} |} \frac{λ_{2} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2 v_{(j)}} (‖ {\hat{x}}_{(j)} ‖)]}{‖ {\hat{x}}_{(j)} ‖}} .$

因此 $\forall j \in j (\hat{x}), i \in i_{j} ( x ^ )$

当 $\bar{v} = 1$ 时，可得 $\forall j \in j (\hat{x}), i \in i_{j} ( x ^ )$

$0 = \nabla_{(j) i} l (\hat{x}) {\hat{x}}_{(j) i} [λ_{1} \frac{{φ^{'}}_{1} (| {\hat{x}}_{(j) i} |)}{| {\hat{x}}_{(j) i} |} λ_{2} \frac{{φ^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)}{‖ {\hat{x}}_{(j)} ‖}],$ (10)

进而

(ii) 任取满足中条件的 $j_{0}$ ， ${\hat{x}}_{(j_{0})} = {({\hat{x}}_{(j_{0}) 1}, \dots, {\hat{x}}_{(j_{0}) n_{j_{0}}})}^{⊤}$ 和任意取定 $i_{0} \in {1, \dots, n_{j_{0}}} \ i_{j_{0}} (\hat{x})$ ，定义 $d^{}, d^{-}$ 如下：

$d_{(j) i}^{} = {\begin{array}{l} 1, & j = j_{0}, i = i_{0} \\ 0, & 其它 \end{array}, d_{(j) i}^{-} = {\begin{array}{l} - 1, & j = j_{0}, i = i_{0} \\ 0, & 其它 \end{array},$

则有 $〈 x_{(j_{0})}, d_{(j_{0})}^{\pm} 〉 = 0$ 且 $‖ d_{(j)}^{\pm} ‖ = 0, \forall j \neq j_{0}$ 。从而由(3)和(4)知

$m' ({\hat{x}}_{(j_{0})}; d_{(j_{0})}^{\pm}) = \frac{〈 x_{(j_{0})}, d_{(j_{0})}^{\pm} 〉}{‖ x_{(j_{0})} ‖} = 0, m' ({\hat{x}}_{(j_{0}) i_{0}}; d_{(j_{0}) i_{0}}^{\pm}) = | d_{(j_{0}) i}^{\pm} | = 1.$

根据(8)，可得

$\begin{matrix} 0 \leq f^{'} (\hat{x}; d^{\pm}) \\ \leq \nabla_{(j_{0}) i} l (\hat{x}) d_{(j_{0}) i_{0}}^{\pm} λ_{1} [{g^{'}}_{1} (| {\hat{x}}_{(j_{0}) i_{0}} |) - {h^{'}}_{1 v_{(j_{0}) i_{0}}} (| {\hat{x}}_{(j_{0}) i_{0}} |)] m^{'} ({\hat{x}}_{(j_{0}) i_{0}}; d_{(j_{0}) i_{0}}^{\pm}) \\ λ_{2} [g_{2} (‖ {\hat{x}}_{(j_{0})} ‖) - {h^{'}}_{2 v_{(j_{0})}} (‖ {\hat{x}}_{(j_{0})} ‖)] m^{'} ({\hat{x}}_{(j_{0})}; d_{(j_{0})}^{\pm}) \\ \leq \pm \nabla_{(j_{0}) i_{0}} l (\hat{x}) λ_{1} [{g^{'}}_{1} (0) - {h^{'}}_{1 v_{(j_{0}) i_{0}}} (0)], \end{matrix}$

因此

$| \nabla_{(j_{0}) i_{0}} l (\hat{x}) | \leq λ_{1} [{g^{'}}_{1} (0) - {h^{'}}_{1 v_{(j_{0}) i_{0}}} (0)] .$

进而

$| \sum_{i \in {1, \dots, n_{j_{0}}} \ i_{j_{0}} (\hat{x})} \nabla_{(j_{0}) i} l (\hat{x}) | \leq \sum_{i \in {1, \dots, n_{j_{0}}} \ i_{j_{0}} (\hat{x})} | \nabla_{(j_{0}) i} l (\hat{x}) | \leq λ_{1} \sum_{i \in {1, \dots, n_{j_{0}}} \ i_{j_{0}} (\hat{x})} [{g^{'}}_{1} (0) - {h^{'}}_{1 v_{(j_{0}) i}} (0)] .$

当 $\bar{v_{l}} = 1 (l = 1, 2)$ 时， $\forall j \in j (\hat{x})$ ，若 ${1, \dots, n_{j}} \ i_{j} (\hat{x}) \neq \emptyset$ ，则

$| \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} {φ^{'}}_{1} (0),$

进而

$| \sum_{i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})} \nabla_{(j) i} l (\hat{x}) | \leq λ_{1} (n_{j} - | i_{j} (\hat{x}) |) [{g^{'}}_{1} (0) - {h^{'}}_{1} (0)] = λ_{1} (n_{j} - | i_{j} (\hat{x}) |) {φ^{'}}_{1} (0) .$

结论得证。 $□$

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

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

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

$f' (\hat{x}; d) = \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |] λ_{2} \sum_{j \notin j (\hat{x})} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ .$ (11)

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

$\begin{array}{l} | \nabla_{(j) i} l (\hat{x}) | \leq λ_{2} {φ^{'}}_{2} (0) λ_{1} {φ^{'}}_{1} (0), \forall i \in {1, \dots, n_{j}}, \\ 0 \leq λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \sum_{i = 1}^{n_{j}} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |], \forall d \in ℝ^{n} . \end{array}$

(iii) 若 $λ_{1} {φ^{'}}_{1} (0) > | \nabla_{(j) i} l (\hat{x}) |, \forall j \in j (\hat{x}), \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})$ ，则当方向 $d \in ℝ^{n}$ 满足 $f' (\hat{x}; d) = 0$ 时，必有

$d_{(j) i} = 0, \forall j \in j (\hat{x}), \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x}) .$

(iv) 若 ${φ^{'}}_{2} (0) > 0$ ， $λ_{1} {φ^{'}}_{1} (0) > | \nabla_{(j) i} l (\hat{x}) |, \forall j \in j (\hat{x}), \forall i \in {1, \dots, n_{j}}$ ，则当方向 $d \in ℝ^{n}$ 满足 $f' (\hat{x}; d) = 0$ 时，必有

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

(v) 若 ${φ^{'}}_{2} (0) > 0$ ， $λ_{1} {φ^{'}}_{1} (0) > | \nabla_{(j) i} l (\hat{x}) |, \forall j \in {1, \dots, k}, i \in i_{j} (\hat{x})$ ，则当方向 $d \in ℝ^{n}$ 满足 $f' (\hat{x}; d) = 0$ 时，必有 ${\hat{x}}_{(j) i} = 0 \Rightarrow d_{(j) i} = 0$ .

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

$\begin{array}{l} f' (\hat{x}; d) = 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1} (| {\hat{x}}_{(j) i} |)] m' ({\hat{x}}_{(j) i}; d_{(j) i}) \\ λ_{2} \sum_{j = 1}^{k} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)] m' ({\hat{x}}_{(j)}; d_{(j)}) . \end{array}$

由(3)和(4)可得

$\begin{matrix} f^{'} (\hat{x}; d) = 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} [{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1} (| {\hat{x}}_{(j) i} |)] \frac{{\hat{x}}_{(j) i} d_{(j) i}}{| {\hat{x}}_{(j) i} |} \\ \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} λ_{1} [{g^{'}}_{1} (0) - {h^{'}}_{1} (0)] | d_{(j) i} | λ_{2} \sum_{j \notin j (\hat{x})} [{g^{'}}_{2} (0) - {h^{'}}_{2} (0)] ‖ d_{(j)} ‖ \\ λ_{2} \sum_{j \in j (\hat{x})} [{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)] \frac{〈 {\hat{x}}_{(j)}, d_{(j)} 〉}{‖ {\hat{x}}_{(j)} ‖} \end{matrix}$

$\begin{matrix} = \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} d_{(j) i} {\nabla_{(j) i} l (\hat{x}) λ_{1} {\hat{x}}_{(j) i} \frac{{g^{'}}_{1} (| {\hat{x}}_{(j) i} |) - {h^{'}}_{1} (| {\hat{x}}_{(j) i} |)}{| {\hat{x}}_{(j) i} |}} \\ \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} {\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} [{g^{'}}_{1} (0) - {h^{'}}_{1} (0)] | d_{(j) i} |} λ_{2} \sum_{j \notin j (\hat{x})} [{g^{'}}_{2} (0) - {h^{'}}_{2} (0)] ‖ d_{(j)} ‖ \\ λ_{2} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\hat{x}}_{(j) i} d_{(j) i} \frac{{g^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) - {h^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)}{‖ {\hat{x}}_{(j)} ‖} \\ = \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} d_{(j) i} {\nabla_{(j) i} l (\hat{x}) {\hat{x}}_{(j) i} [λ_{1} \frac{{φ^{'}}_{1} (| {\hat{x}}_{(j) i} |)}{| {\hat{x}}_{(j) i} |} λ_{2} \frac{{φ^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖)}{‖ {\hat{x}}_{(j)} ‖}]} \\ \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |] λ_{2} \sum_{j \notin j (\hat{x})} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \end{matrix}$

根据(10)，可得

(ii) 根据等式(11)， $\forall d \in ℝ^{n}$ ，

$\begin{array}{l} f' (\hat{x}; d) = \sum_{j \in j (\hat{x})} \sum_{i \notin i_{j} (\hat{x})} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |] \\ \sum_{j \notin j (\hat{x})} {λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \sum_{i = 1}^{n_{j}} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |]} . \end{array}$ (12)

任取 $j_{0} \notin j (\hat{x})$ ，任取 $i_{0} \in {1, \dots, n_{j_{0}}}$ ，定义 $d^{0}$ 如下：

$d_{(j) i}^{0} = {\begin{array}{l} - \nabla_{(j_{0}) i_{0}} l (\hat{x}), & j = j_{0}, i = i_{0} \\ 0, & 其它 \end{array} .$

注意到 $\hat{x}$ 是问题(2)的方向稳定点，可得

$\begin{matrix} 0 \leq f^{'} (\hat{x}; d^{0}) = λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j_{0})}^{0} ‖ \nabla_{(j_{0}) i_{0}} l (\hat{x}) d_{(j_{0}) i_{0}}^{0} λ_{1} {φ^{'}}_{1} (0) | d_{(j_{0}) i_{0}}^{0} | \\ = | \nabla_{(j_{0}) i_{0}} l (\hat{x}) | [λ_{2} {φ^{'}}_{2} (0) - | \nabla_{(j_{0}) i_{0}} l (\hat{x}) | λ_{1} {φ^{'}}_{1} (0)] . \end{matrix}$

再根据 $j_{0}, i_{0}$ 的任意性，可得

$| \nabla_{(j) i} l (\hat{x}) | \leq λ_{2} {φ^{'}}_{2} (0) λ_{1} {φ^{'}}_{1} (0), \forall j \notin j (\hat{x}), \forall i \in {1, \dots, n_{j}} .$

任取 $j_{g} \notin j (\hat{x})$ ，定义 $d^{g}$ 如下：

$d_{(j)}^{g} = {\begin{array}{l} d_{j_{g}}, & j = j_{g} \\ 0, & 其它 \end{array} .$

根据(12)，可得

$\begin{matrix} 0 \leq f' (\hat{x}; d^{g}) = λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j_{g})}^{g} ‖ \sum_{i = 1}^{n_{j_{g}}} [\nabla_{(j_{g}) i} l (\hat{x}) d_{(j_{g}) i}^{g} λ_{1} {φ^{'}}_{1} (0) | d_{(j_{g}) i}^{g} |] \\ = λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j_{g})} ‖ \sum_{i = 1}^{n_{j_{g}}} [\nabla_{(j_{g}) i} l (\hat{x}) d_{(j_{g}) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j_{g}) i} |] . \end{matrix}$

再由 $j_{g}$ 的任意性，，知

$0 \leq λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \sum_{i = 1}^{n_{j}} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |], \forall j \notin j (\hat{x}), d \in ℝ^{n} .$

(iii) 根据(12)知

$\begin{matrix} f' (\hat{x}; d) \geq \sum_{j \in j (\hat{x})} \sum_{i \notin i_{j} (\hat{x})} | d_{(j) i} | [λ_{1} {φ^{'}}_{1} (0) - | \nabla_{(j) i} l (\hat{x}) |] \\ \sum_{j \notin j (\hat{x})} {λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \sum_{i = 1}^{n_{j}} [\nabla_{(j) i} l (\hat{x}) d_{(j) i} λ_{1} {φ^{'}}_{1} (0) | d_{(j) i} |]} . \end{matrix}$ (13)

根据不等式(7)和推论3.1 (ii)，知

$f' (\hat{x}; d) \geq \sum_{j \in j (\hat{x})} \sum_{i \notin i_{j} (\hat{x})} | d_{(j) i} | [λ_{1} {φ^{'}}_{1} (0) - | \nabla_{(j) i} l (\hat{x}) |] \geq 0.$

再由条件 $f' (\hat{x}; d) = 0$ ，得

$0 = \sum_{j \in j (\hat{x})} \sum_{i \notin i_{j} (\hat{x})} | d_{(j) i} | [λ_{1} {φ^{'}}_{1} (0) - | \nabla_{(j) i} l (\hat{x}) |] .$

因 $λ_{1} {φ^{'}}_{1} (0) > | \nabla_{(j) i} l (\hat{x}) |, \forall j \in j (\hat{x}), \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x})$ ，故

$d_{(j) i} = 0, \forall j \in j (\hat{x}), \forall i \in {1, \dots, n_{j}} \ i_{j} (\hat{x}) .$

(iv) 由(12)得

$\begin{array}{l} f' (\hat{x}; d) \geq \sum_{j \in j (\hat{x})} \sum_{i \notin i_{j} (\hat{x})} | d_{(j) i} | [λ_{1} {φ^{'}}_{1} (0) - | \nabla_{(j) i} l (\hat{x}) |] \sum_{j \notin j (\hat{x})} \sum_{i = 1}^{n_{j}} | d_{(j) i} | [λ_{1} {φ^{'}}_{1} (0) - | \nabla_{(j) i} l (\hat{x}) |] \\ \sum_{j \notin j (\hat{x})} λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ . \end{array}$

根据不等式(7)以及条件 $λ_{1} {φ^{'}}_{1} (0) > | \nabla_{(j) i} l (\hat{x}) |, \forall j \notin j (\hat{x}), \forall i \in {1, \dots, n_{j}}$ ，知

$f' (\hat{x}; d) \geq \sum_{j \notin j (\hat{x})} λ_{2} {φ^{'}}_{2} (0) ‖ d_{(j)} ‖ \geq 0.$

再由条件 $f' (\hat{x}; d) = 0$ 和 ${φ^{'}}_{2} (0) > 0$ ，得 $d_{(j)} = 0, \forall j \notin j (\hat{x})$ 。

(v)综合(iii)和(iv)即得。 $□$

3. 问题(2)的光滑化模型

我们已知问题(2)的方向稳定点具有良好的局部最有性质，但考虑到正则项的非凸非光滑性质，直接计算问题(2)的方向稳定点是困难的。在实际应用中，光滑逼近的方法广泛应用于科学计算和实验，例如 [24] [25] [26] [27]。因此本文探讨使用光滑化方法来计算非光滑问题(2)的方向稳定点。

首先构造其光滑化模型。考虑到光滑函数的复合函数仍然是光滑函数，可以通过分别将 $φ_{l} (t) (l = 1, 2)$ 和 $m (x)$ 进行光滑化，得到连续可微的函数 ${\tilde{φ}}_{l μ} (t) (l = 1, 2)$ 和 ${\tilde{m}}_{μ} (x)$ ，再将它们重新复合，就得到了 $φ_{l} (‖ x ‖)$ 的光滑逼近函数 ${\tilde{φ}}_{l μ} ° {\tilde{m}}_{μ} (x)$ 。

$m (x)$ 的光滑化：取 ${\tilde{m}}_{μ} (x) = \sqrt{{‖ x ‖}^{2} μ} \geq 0$ 作为 $m (x) = ‖ x ‖$ 的参数为 $μ$ 的光滑化函数，其中 $μ \in (0, \infty)$ 。显然 ${\tilde{m}}_{μ} (x)$ 关于x二阶连续可微，关于 $μ$ 单调递增。注意到， $\forall x, d \in ℝ^{n}$ ， ${\tilde{m}}^{'}_{μ} (x; d)$ 的方向导数和梯度为：

${\tilde{m}}^{'}_{μ} (x; d) = 〈 \nabla {\tilde{m}}_{μ} (x), d 〉, \nabla {\tilde{m}}_{μ} (x) = \frac{x}{\sqrt{{‖ x ‖}^{2} μ}} .$ (14)

特别地，对 $x_{(j) i} \in ℝ$ ，有

$m (x_{(j) i}) = | x_{(j) i} |, {\tilde{m}}_{μ} (x_{(j) i}) = \sqrt{{(x_{(j) i})}^{2} μ},$ (15)

${\tilde{m}}^{'}_{μ} (x_{(j) i}) = \frac{x_{(j) i}}{\sqrt{{(x_{(j) i})}^{2} μ}}, {\tilde{m}}^{'}_{μ} (x_{(j) i}; d_{(j) i}) = \frac{x_{(j) i} d_{(j) i}}{\sqrt{{(x_{(j) i})}^{2} μ}} .$ (16)

容易验证， ${\tilde{m}}_{μ} (x)$ 满足如下收敛性质： $\forall x, d \in ℝ^{n}$ ，

(i) (光滑化函数的一致收敛性)： $\lim_{x' \to x, μ ↓ 0} {\tilde{m}}_{μ} (x^{'}) = m (x)$ ；

(ii) (方向导数的一致收敛与弱一致收敛性)：

在 $x \neq 0$ 点， $\lim_{x' \to x, μ ↓ 0} 〈 \nabla {\tilde{m}}_{μ} (x'), d 〉 = 〈 \nabla m (x), d 〉 = m' (x; d)$ ；

对 $x = 0$ 点， $\lim {sup}_{x' \to 0, μ ↓ 0} 〈 \nabla {\tilde{m}}_{μ} (x^{'}), d 〉 = ‖ d ‖ = m' (0; d)$ 。

受peng和chen [24] 的启发，对于 $φ_{l} (t) (l = 1, 2)$ 的光滑化函数，本文作出下述假设。

假设3.1设 $φ_{l} (t) (l = 1, 2)$ 的光滑化函数 $φ_{l μ} (t) (l = 1, 2)$ 满足以下条件：

(i) $\lim_{μ ↓ 0, t \to s} {\tilde{φ}}_{l μ} (t) = φ_{l} (s)$ 。

(ii) 当 $s = 0$ 时， $\underset{μ ↓ 0, t ↓ 0}{\lim sup} {\tilde{φ}}^{'}_{l μ} (t) = {φ^{'}}_{l} (0) = {φ^{'}}_{l} (0) \geq 0$ ；当 $s \neq 0$ 时， $\lim_{μ ↓ 0, t \to s} {\tilde{φ}}^{'}_{l μ} (t) = {φ^{'}}_{l} (s)$ 。

需要强调的是，在许多情况下，满足假设3.1的光滑化函数是存在的，例如peng和chen在 [24] 中给出了mcp、scad、capped- $l_{1}$ 三类典型罚函数的光滑化函数，并验证了它们满足假设3.1。

若光滑化函数 $φ_{l} (t) (l = 1, 2)$ 满足假设3.1，则可得问题(2)的光滑化模型：

$\min_{x \in ℝ^{n}} {\tilde{f}}_{μ} (x) : = l (x) \sum_{j = 1}^{k} [\sum_{i = 1}^{n_{j}} λ_{1} {\tilde{φ}}_{1 μ} ° {\tilde{m}}_{μ} (x_{(j) i}) λ_{2} {\tilde{φ}}_{2 μ} ° {\tilde{m}}_{μ} (x_{(j)})] .$ (17)

基于其连续可微性，当 $μ > 0$ 时，对于任意方向 $d \in ℝ^{n}$ ， ${\tilde{f}}_{μ} (x)$ 的方向导数为：

${\tilde{f}}^{'}_{μ} (x; d) = 〈 \nabla {\tilde{f}}_{μ} (x), d 〉,$ (18)

其中

$\nabla {\tilde{f}}_{μ} (x) = \nabla l (x) λ_{2} (\begin{matrix} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} (x_{(1)}) \nabla {\tilde{m}}_{μ} (x_{(1)}) \\ ⋮ \\ {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} (x_{(k)}) \nabla {\tilde{m}}_{μ} (x_{(k)}) \end{matrix}) λ_{1} (\begin{matrix} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} (x_{(1) 1}) {\tilde{m}}^{'}_{μ} (x_{(1) 1}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} (x_{(1) n_{1}}) {\tilde{m}}^{'}_{μ} (x_{(1) n_{1}}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} (x_{(k) 1}) {\tilde{m}}^{'}_{μ} (x_{(k) 1}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} (x_{(k) n_{k}}) {\tilde{m}}^{'}_{μ} (x_{(k) n_{k}}) \end{matrix}) .$ (19)

问题(17)是光滑优化问题，其稳定点 ${\hat{x}}^{μ} \in r^{n}$ 定义为使 $\nabla {\tilde{f}}_{μ} ({\hat{x}}^{μ}) = 0$ 的点。

以下定理给出了光滑化问题(17)稳定点的特征，即在其稳定点处损失函数的梯度值 $\nabla l$ 可以用对应的惩罚函数 ${\tilde{φ}}_{l μ} ° {\tilde{m}}_{μ}$ 的值来刻画。

定理3.1 (光滑化问题稳定点的特征)记 ${\hat{x}}^{μ}$ 为光滑化参数为 $μ > 0$ 时光滑化问题(17)的稳定点，则

$| \nabla_{(j) i} l ({\hat{x}}^{μ}) | = | {\hat{x}}_{(j) i}^{μ} | | λ_{1} \frac{{\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(j) i}^{μ})}{\sqrt{{({\hat{x}}_{(j) i}^{μ})}^{2} μ}} λ_{2} \frac{{\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(j)}^{μ})}{\sqrt{{‖ {\hat{x}}_{(j)}^{μ} ‖}^{2} μ}} |, \forall j \in {1, \dots, k}, \forall i \in {1, \dots, n_{j}} .$

证明. 因为 ${\hat{x}}_{μ}$ 满足 $0 = \nabla {\tilde{f}}_{μ} ({\hat{x}}^{μ})$ ，根据(14)和(19)，可得

$0 = \nabla l ({\hat{x}}^{μ}) λ_{2} (\begin{matrix} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1)}^{μ}) \nabla {\tilde{m}}_{μ} ({\hat{x}}_{(1)}^{μ}) \\ ⋮ \\ {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k)}^{μ}) \nabla {\tilde{m}}_{μ} ({\hat{x}}_{(k)}^{μ}) \end{matrix}) λ_{1} (\begin{matrix} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1) 1}^{μ}) {\tilde{m}}^{'}_{μ} ({\hat{x}}_{(1) 1}^{μ}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1) n_{1}}^{μ}) {\tilde{m}}^{'}_{μ} ({\hat{x}}_{(1) n_{1}}^{μ}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k) 1}^{μ}) {\tilde{m}}^{'}_{μ} ({\hat{x}}_{(k) 1}^{μ}) \\ ⋮ \\ {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k) n_{k}}^{μ}) {\tilde{m}}^{'}_{μ} ({\hat{x}}_{(k) n_{k}}^{μ}) \end{matrix})$

$= \nabla l ({\hat{x}}^{μ}) (\begin{matrix} λ_{2} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1)}^{μ}) \frac{{\hat{x}}_{(1) 1}^{μ}}{\sqrt{{‖ {\hat{x}}_{(1)}^{μ} ‖}^{2} μ}} λ_{1} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1) 1}^{μ}) \frac{{\hat{x}}_{(1) 1}^{μ}}{\sqrt{{({\hat{x}}_{(1) 1}^{μ})}^{2} μ}} \\ ⋮ \\ λ_{2} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1)}^{μ}) \frac{{\hat{x}}_{(1) n_{1}}^{μ}}{\sqrt{{‖ {\hat{x}}_{(1)}^{μ} ‖}^{2} μ}} λ_{1} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(1) n_{1}}^{μ}) \frac{{\hat{x}}_{(1) n_{1}}^{μ}}{\sqrt{{({\hat{x}}_{(1) n_{1}}^{μ})}^{2} μ}} \\ ⋮ \\ λ_{2} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k)}^{μ}) \frac{{\hat{x}}_{(k) 1}^{μ}}{\sqrt{{‖ {\hat{x}}_{(k)}^{μ} ‖}^{2} μ}} λ_{1} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k) 1}^{μ}) \frac{{\hat{x}}_{(k) 1}^{μ}}{\sqrt{{({\hat{x}}_{(k) 1}^{μ})}^{2} μ}} \\ ⋮ \\ λ_{2} {\tilde{φ}}^{'}_{2 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k)}^{μ}) \frac{{\hat{x}}_{(k) n_{k}}^{μ}}{\sqrt{{‖ {\hat{x}}_{(k)}^{μ} ‖}^{2} μ}} λ_{1} {\tilde{φ}}^{'}_{1 μ} ° {\tilde{m}}_{μ} ({\hat{x}}_{(k) n_{k}}^{μ}) \frac{{\hat{x}}_{(k) n_{k}}^{μ}}{\sqrt{{({\hat{x}}_{(k) n_{k}}^{μ})}^{2} μ}} \end{matrix}) .$

因此，

$□$

4. 光滑化前后稳定点的一致性

使用光滑化方法求解非光滑优化问题的一个重要的问题是：随着光滑参数趋于零，光滑化问题的解能否趋向于原问题的解，即光滑化前后解的一致性问题。只有当解的一致性成立时，才能保证光滑化问题的解趋向于原问题的解。

下面的定理说明本文的光滑化方法能够保证光滑化问题(17)的稳定点与问题(2)的方向稳定点具有一致性。

定理4.1 (稳定点的一致性)设光滑化函数 ${\tilde{φ}}_{1 μ}$ 和 ${\tilde{φ}}_{2 μ}$ 均满足假设3.1，并设 ${\hat{x}}^{μ_{k}}$ 是光滑化问题(17)在光滑化参数 $μ = μ_{k}$ 时的稳定点，则当 $μ_{k} \to 0^{}$ 时， ${{\hat{x}}^{μ_{k}}}_{k = 1}^{\infty}$ 的任意聚点都是问题(2)的方向稳定点。

证明. 设 $\hat{x}$ 为 ${{\hat{x}}^{μ_{k}}}_{k = 1}^{\infty}$ 的任一聚点，不妨设

$\lim_{k \to \infty} {\hat{x}}^{μ_{k}} = \hat{x} .$

因 ${\hat{x}}^{μ_{k}}$ 是 ${\tilde{f}}_{μ_{k}} (x)$ 的稳定点，根据 ${\tilde{f}}_{μ_{k}} (x)$ 连续可微性和(18)和(19)可知， $\forall d \in ℝ^{n}$ ，有

$\begin{matrix} 0 = 〈 \nabla {\tilde{f}}_{μ_{k}} ({\hat{x}}^{μ_{k}}), d 〉 \\ = 〈 \nabla l ({\hat{x}}^{μ_{k}}), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ λ_{2} \sum_{j = 1}^{k} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \\ = 〈 \nabla l ({\hat{x}}^{μ_{k}}), d 〉 λ_{1} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ λ_{1} \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} λ_{2} \sum_{j \in j (\hat{x})} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \\ λ_{2} \sum_{j \notin j (\hat{x})} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 . \end{matrix}$ (20)

令 $k \to \infty$ ，则 $μ_{k} \to 0$ ， ${\hat{x}}^{μ_{k}} \to \hat{x}$ 。根据第三节中 ${\tilde{m}}_{μ} (x)$ 的一致和弱一致收敛性质以及假设3.1，可得下述极限：

$\begin{array}{l} \forall j \in j (\hat{x}), \forall i \in i_{j} (\hat{x}) : \lim_{k \to \infty} {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} = m' ({\hat{x}}_{(j) i}; d_{(j)}), \lim_{k \to \infty} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) = {φ^{'}}_{1} (| {\hat{x}}_{(j) i} |); \\ \forall j \in 1, \dots, k, \forall i \notin i_{j} (\hat{x}) : \underset{k \to \infty}{\lim \sup} {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} = m^{'} (0; d_{(j) i}) = | d_{(j) i} | \geq 0, \underset{k \to \infty}{\lim \sup} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) = {φ^{'}}_{1} (0) > 0; \\ \forall j \in j (\hat{x}) : \lim_{k \to \infty} 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 = m^{'} ({\hat{x}}_{(j)}; d_{(j)}), \lim_{k \to \infty} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) = {φ^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖); \\ \forall j \notin j (\hat{x}) : \underset{k \to \infty}{\lim \sup} 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 = m^{'} (0; d_{(j)}) = ‖ d_{(j)} ‖ \geq 0, \underset{k \to \infty}{\lim \sup} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) = {φ^{'}}_{2} (0) > 0. \end{array}$

在(20)中利用上述极限，根据定理2.1我们可以得到 $\forall d \in ℝ^{n}$

$\begin{matrix} 0 = \lim_{k \to \infty} 〈 \nabla {\tilde{f}}_{μ_{k}} ({\hat{x}}^{μ_{k}}), d 〉 \\ = \lim_{k \to \infty} 〈 \nabla l ({\hat{x}}^{μ_{k}}), d 〉 \lim_{k \to \infty} λ_{1} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ \lim_{k \to \infty} λ_{1} \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ \lim_{k \to \infty} λ_{2} \sum_{j \in j (\hat{x})} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \\ \lim_{k \to \infty} λ_{2} \sum_{j \notin j (\hat{x})} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \end{matrix}$

$\begin{matrix} \leq \lim_{k \to \infty} 〈 \nabla l ({\hat{x}}^{μ_{k}}), d 〉 \lim_{k \to \infty} λ_{1} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ λ_{1} \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} \lim_{k \to \infty} {\tilde{φ}}^{'}_{1 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) \cdot \lim \sup_{k \to \infty} {\tilde{m}}^{'}_{μ_{k}} ({\hat{x}}_{(j) i}^{μ_{k}}) d_{(j) i} \\ \lim_{k \to \infty} λ_{2} \sum_{j \in j (\hat{x})} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \\ λ_{2} \sum_{j \notin j (\hat{x})} \lim_{k \to \infty} {\tilde{φ}}^{'}_{2 μ_{k}} ° {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}) \cdot \lim \sup_{k \to \infty} 〈 \nabla {\tilde{m}}_{μ_{k}} ({\hat{x}}_{(j)}^{μ_{k}}), d_{(j)} 〉 \end{matrix}$

$\begin{matrix} = 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j \in j (\hat{x})} \sum_{i \in i_{j} (\hat{x})} {\tilde{φ}}^{'}_{1} ° m ({\hat{x}}_{(j) i}) \cdot m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) \\ λ_{1} \sum_{j = 1}^{k} \sum_{i \notin i_{j} (\hat{x})} {φ^{'}}_{1} ° m ({\hat{x}}_{(j) i}) \cdot m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) λ_{2} \sum_{j \in j (\hat{x})} {φ^{'}}_{2} ° m ({\hat{x}}_{(j)}) \cdot m^{'} ({\hat{x}}_{(j)}; d_{(j)}) \\ λ_{2} \sum_{j \in j (\hat{x})} {φ^{'}}_{2} ° m ({\hat{x}}_{(j)}) \cdot m^{'} ({\hat{x}}_{(j)}; d_{(j)}) \\ = 〈 \nabla l (\hat{x}), d 〉 λ_{1} \sum_{j = 1}^{k} \sum_{i = 1}^{n_{j}} {φ^{'}}_{1} (| {\hat{x}}_{(j) i} |) m^{'} ({\hat{x}}_{(j) i}; d_{(j) i}) λ_{2} \sum_{j = 1}^{k} {φ^{'}}_{2} (‖ {\hat{x}}_{(j)} ‖) m^{'} ({\hat{x}}_{(j)}; d_{(j)}) \\ = f^{'} (\hat{x}; d) \end{matrix}$

因此， $\hat{x}$ 是问题(2)的方向稳定点。 $□$

5. 总结

本文研究了稀疏加组稀疏优化问题的非凸松弛模型。给出了非凸松弛模型方向导数的刻画和方向稳定点，分析了方向稳定点的特征及其局部最优性质。进一步构造了松弛模型的光滑化逼近问题，并证明了光滑化问题的稳定点与松弛模型的方向稳定点具有一致性，为后续使用光滑方法计算模型的方向稳定点提供了理论保障。

基金项目

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

notes

^*通讯作者。

参考文献

[1]	bech, a. and hallak, n. (2019) optimization problems involving group sparsity terms. mathematical programming, 178, 39-67.
[2]	hu, y., li, c., meng, k., qin, j. and yang, x. (2017) group sparse optimization via lp,q regularization. journal of machine learning research, 18, 960-1011.
[3]	jiao, y., jin, b. and lv, x. (2017) group sparse recovery via the l0(l2) penalty: theory and algorithm. ieee transactions on signal processing, 65, 998-1012.
[4]	li, w., bian, w. and toh, k.-c. (2022) difference-of-convex algorithms for a class of sparse group l0 regularized optimization problems. siam journal on optimization, 32, 1614-1641.
[5]	pan, l. and chen, x. (2021) group sparse optimization for images recovery using capped folded concave functions. siam journal on imaging sciences, 14, 1-25.
[6]	natarajan, b.k. (1995) sparse approximate solu-tions to linear systems. siam journal on computing, 24, 227-234.
[7]	li, x., sun, d. and toh, k.-c. (2018) a highly efficient sem-ismooth newton augmented lagrangian method for solving lasso problems. siam journal on optimization, 28, 433-458.
[8]	lin, m., liu, y. j., sun, d. and toh, k.c. (2019) efficient sparse semismooth newton methods for the clustered lasso problem. siam journal on optimization, 29, 2026-2052.
[9]	zhang, y., zhang, n., sun, d. and toh, k.-c. (2020) an efficient hes-sian-based algorithm for solving large-scale sparse group lasso problems. mathematical programming, 179, 223-263.
[10]	candès, e.j., wakin, m.b. and boyd, s.p. (2008) en-hancing sparsity by reweighted l1 minimization. journal of fourier analysis and applications, 14, 877-905.
[11]	fan, j. and li, r. (2001) variable selection via nonconvave pe-nalized likelihood and its oracle properties. journal of the american statistical association, 96, 1348-1360.
[12]	fan, j. and li, r. (2006) statistical challenges with high di-mensionality: feature selection in knowledge discovery. proceedings of the international congress of mathematicians, 3, 595-622.
[13]	zhang, c.-h. (2010) nearly unbiased variable selection under minimax concave penalty. annals of statistics, 38, 894-942.
[14]	thi, l.e. and cheng, s.o. (2013) learning sparse classifiers with difference of convex functions algorithms. optimization methods and software, 28, 830-854.
[15]	tong, z. (2010) analy-sis of multi-stage convex relaxation for sparse regularization. journal of machine learning research, 11, 1081-1107.
[16]	nikolova, m., ng, m.-k., zhang, s. and ching, w.-k. (2008) efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. siam journal on imaging sciences, 1, 2-25.
[17]	bruckstein, a.m., donoho, d.l. and elad, m. (2009) from sparse solu-tions of systems of equations to sparse modeling of signals and images. siam review, 51, 34-81.
[18]	knight, k. and fu, w. (2000) asymptotics for lasso-type estimators. annals of statistics, 28, 1356-1378.
[19]	huang, j., ma, s., xie, h. and zhang, c.h. (2009) a group bridge approach for variable selection. biometrika, 96, 339-355.
[20]	ahn, m., pang, j.-s. and xin, j. (2017) difference-of-convex learning: directional stationarity, optimality, and sparsity. siam journal on optimization, 27, 1637-1665.
[21]	chang, t.h., hong, m. and pang, j.-s. (2017) local minimizers and second-order conditions in composite piecewise programming via directional derivatives.
[22]	pang, j.-s., razaviyayn, m. and alvarado, a. (2017) computing b-stationary points of nonsmooth dc programs. mathematics of operations research, 42, 95-118.
[23]	rochafellar, r.t. and wets, r.j.-b. (2009) variational analysis. 3rd edition, springer-verlag, berlin.
[24]	peng, d. and chen, x. (2020) computation of second-order directional station-ary points for group sparse optimization. optimization methods and software, 35, 348-376.
[25]	chen, x. (2012) smoothing methods for nonsmooth, no-vonvex minimization. mathematical programming, 134, 71-99.
[26]	chen, x., niu, l. and yuan, y. (2013) optimality conditions and a smoothing trust region newton method for non- lipschitz optimization. siam journal on optimization, 23, 1528-1552.
[27]	chen, x., xu, f. and ye, y. (2010) lower bound theory of nonzero entries in solutions of l2-lp minimization. siam journal on computing, 32, 2832-2852.

为你推荐

凯发娱乐官网的友情链接