基于huber损失和capped-凯发国际一触即发

期刊菜单

基于huber损失和capped-l1正则的线性不等式约束稀疏优化问题研究
on sparse optimization problems with linear inequality constraints based on huber loss and capped-l1 regularization

doi: , , html, , 国家自然科学基金支持
作者: 田梦达, 彭定涛^*, 张弦：贵州大学数学与统计学院，贵州贵阳
关键词: ；；；；；；；；；

摘要: 对多元线性回归中回归系数的估计问题，本文考虑了基于huber损失和线性不等式约束的稀疏优化模型。首先，给出了稀疏优化的原问题、基于capped-l1正则的松弛问题和基于约束惩罚的无约束问题三种模型。其次，借助惩罚模型方向稳定点的下界性质，在一定条件下分析了三种模型全局最优解的等价性。最后，提出了光滑化惩罚算法，并证明了该算法的收敛性。本文为求解线性不等式约束稀疏优化问题提供了理论和方法基础。

abstract: for the estimation of regression coefficients in multivariate linear regression, a sparse optimization model based on huber loss and linear inequality constraints is considered in this paper. firstly, three models of the original sparse optimization problem, the relaxation problem based on capped-l1 regularization and the unconstrained problem based on the penalty of constraint are given. secondly, by use of the lower bound property of the directional stationary point of the pe-nalized model, the equivalence of the global optimal solutions of the three models is analyzed under certain conditions. finally, a smoothing penalty algorithm is proposed and its convergence is proved. this paper provides a theoretical and methodological basis for solving sparse optimization problems with linear inequality constraints.

文章引用：田梦达, 彭定涛, 张弦. 基于huber损失和capped-l1正则的线性不等式约束稀疏优化问题研究[j]. 理论数学, 2022, 12(11): 2021-2032.

1. 引言

在多元线性回归中，常用的最小二乘法是通过极小化残差平方和来估计回归系数，即：

$\min_{x \in ℝ^{n}} f (x) : = {‖ a x - b ‖}_{2}^{2},$

其中， $a \in ℝ^{m \times n}$ ， $b \in ℝ^{m}$ 。最小二乘法也常用于曲线拟合。为避免数据的多重共线性和可能出现的欠定和过拟合现象，并实现变量选择，研究者引入了 $l_{0}$ 正则的稀疏优化模型：

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

其中 ${‖ x ‖}_{0}$ 表示向量x非零分量的个数， $λ > 0$ 是正则化参数。

由于 $l_{0}$ 正则是非凸、非光滑甚至是不连续的。因此，求解问题(1)是np难的 [1]。于是一些研究学者考虑用 $l_{1}$ 正则来松弛 $l_{0}$ 正则 [2] [3] [4]，即lasso回归模型：

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

其中 ${‖ x ‖}_{1} = \sum_{i = 1}^{n} | x_{i} |$ 。lasso回归模型具有子集选择和岭回归的一些优点，它能够产生可解释的模型并且具

有岭回归的稳定性。但是fan和li证明了lasso回归模型得到的解是有偏估计 [5]，并指出一个好的正则函数应当使得产生的估计量具有下述四个性质：1) 无偏性，2) 稀疏性，3) 连续性，4) oracle性质：所得估计量与oracle解具有相同的渐进分布，其中oracle解定义为：

$x^{oracle} \in \arg \min_{x : supp (x) \subset supp (x^{*})} l (x),$

$l (x)$ 是损失函数， $supp (x^{*})$ 是真实解 $x^{*}$ 的支撑集。研究表明，scad [5]，mcp [6] 和capped-l1等几类折叠凹正则函数 [7] [8] [9] [10] 可产生满足无偏性、稀疏性、连续性和oracle性质的估计量 [11] [12] [13]。因此研究者们考虑用折叠凹函数来松弛 $l_{0}$ 正则，即考虑以下折叠凹正则模型：

$\min_{x \in ℝ^{n}} f (x) : = {‖ a x - b ‖}_{2}^{2} φ (x),$ (2)

其中 $φ (x) = \sum_{i = 1}^{n} φ (x_{i})$ 是折叠凹函数， $φ (t)$ 可取如下几类函数：

i) capped-l1： $φ (t) = λ \cdot \min {1, \frac{| t |}{γ}}, λ > 0, γ > 0$

ii) mcp： $φ (t) = {\begin{array}{l} λ | t | - \frac{t^{2}}{2 γ}, & if 0 \leq | t | \leq γ λ, \\ \frac{γ λ^{2}}{2}, & if | t | > γ λ, \end{array}, λ > 0, γ > 1;$

iii) scad： $φ (t) = {\begin{array}{l} λ | t |, & if 0 \leq | t | \leq λ, \\ λ | t | - \frac{{(| t | - λ)}^{2}}{2 (γ - 1)}, & if λ < | t | \leq γ λ, \\ \frac{(γ 1) λ^{2}}{2}, & if | t | > γ λ, \end{array}, λ > 0, γ > 2.$

因为 $φ (x)$ 是非凸正则函数，所以问题(2)是非凸优化。研究者们已经发展了多种有效算法，例如：凸差算法 [9] [14] [15] [16]，信赖域算法 [17]，迭代重加权算法 [18] 等。

文献 [19] 研究了capped-l1正则模型(2)与原 $l_{0}$ 正则模型(1)解的关系，在一定条件下证明了capped-l1正则模型与原 $l_{0}$ 模型全局解的等价性和局部解的包含关系，并给出了邻近梯度算法。文献 [20] 研究了损失函数为最小一乘时，mcp正则模型与原 $l_{0}$ 正则模型解的关系，证明了两模型全局解的等价性。文献 [21] 对损失函数为一般凸函数的组稀疏优化问题，研究了组capped-l1正则模型与 $l_{2, 0}$ 正则模型解的关系，证明了两模型全局解的等价性和局部解的包含关系。文献 [22] 研究了带线性约束的组稀疏优化问题及其折叠凹松弛问题解的等价性和求解算法。文献 [23] 进一步对带一般凸约束的组稀疏优化问题，研究了组capped-l1正则模型与 $l_{2, 0}$ 正则模型解的关系，并利用组capped-l1正则模型给出了组光滑化邻近梯度算法。

由于模型(1)中的最小二乘损失缺乏鲁棒性，对异常值的容忍度不高 [3]，而huber函数不仅对异常值具有鲁棒性，而且结合了最小一乘和最小二乘的优点，既光滑又不会放大误差，因此，将huber函数作为损失函数具有非常大的优点。另一方面，模型(1)没有考虑约束条件，这也在很大程度上限制了它的应用范围。

基于上述分析，本文考虑如下带huber损失和线性不等式约束的稀疏优化模型：

$\begin{array}{l} \min_{x \in ℝ^{n}} \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i}) λ {‖ x ‖}_{0} \\ s .t . b x \leq h, \end{array}$ (3)

其中

$h (t) = {\begin{array}{l} \frac{1}{2} t^{2}, & | t | \leq δ, \\ δ (| t | - \frac{1}{2} δ), & 其他, \end{array}$

是huber函数， $a \in ℝ^{m \times n}$ ， $a_{i}^{⊤}$ 是a的第i个行向量， $i = 1, \dots, m$ ， $b \in ℝ^{q \times n}$ ， $h \in ℝ^{q}$ ， $δ > 0$ 。不等式约束 $b x \leq h$ 可以刻画真实解(信号)的某些先验信息，如非负性 [22]、有界性 [19] 等，但增加了约束使得问题的分析和求解变得更加复杂。

为便于分析和求解，本文将模型(3)松弛为如下capped-l1正则模型：

$\begin{array}{l} \min_{x \in ℝ^{n}} \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i}) φ (x) \\ s .t . b x \leq h . \end{array}$ (4)

其中 $φ (x) = \sum_{i = 1}^{n} φ (x_{i})$ ，而 $φ (t) = λ \cdot \min {1, \frac{| t |}{γ}}$ 是capped-l1函数。

模型(4)是约束优化，为方便研究，将其不等式约束作为惩罚项加罚到目标函数上去，从而转化为如下无约束优化：

$\min_{x \in ℝ^{n}} \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i}) φ (x) α {‖ {(b x - h)}_{} ‖}_{1},$ (5)

其中 $z_{} \in ℝ^{n}$ ，其定义为 ${(z_{})}_{i} : = \max {0, z_{i}}$ ， $α > 0$ 为惩罚因子。

这里重要且有趣的问题是，模型(3)、模型(4)和模型(5)之间解的关系如何，特别是它们的解是否具有某种等价性，以及如何对其求解的问题。

本文主要工作如下：

i) 定义了问题(5)的方向稳定点(d-稳定点)，分析了问题(5)的一阶最优性条件，并探讨了问题(3)，(4)与(5)之间解的关系，证明了等价性。

ii) 因为问题(4)是非光滑优化问题，本文使用光滑化惩罚方法来计算其d-稳定点。通过对约束惩罚函数的光滑化逼近来得到近似问题，并证明了该算法产生的任意聚点都是松弛问题的d-稳定点，为使用光滑化方法求解该问题提供了理论和方法保证。

在接下来的讨论中，为了简便，记：

$\begin{array}{l} f (x) = \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i}) φ (x) α {‖ {(b x - h)}_{} ‖}_{1} \\ f (x) = \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i}), \\ q (x) = {‖ {(b x - h)}_{} ‖}_{1}, \\ ω = {x \in ℝ^{n} : b x \leq h} . \end{array}$

对任意闭集 $ω \in ℝ^{n}$ ， $dist (x, ω) = \inf_{y \in ω} ‖ x - y ‖$ 表示x到闭集 $ω$ 的距离， $p_{ω} (x)$ 表示 $x \in ℝ^{n}$ 在 $ω$ 上投影点的集合。

记向量x的支撑集为：

$γ (x) = {i \in {1, \dots, n} : x_{i} \neq 0} = γ_{1} (x) \cup γ_{2} (x),$

其中 $γ > 0$ ，

$γ_{1} (x) = {i : 0 < | x_{i} | < γ}, γ_{2} (x) = {i : | x_{i} | \geq γ} .$

符号函数 $sgn (t)$ 定义为：

$sgn (t) : = {\begin{matrix} 1, & t > 0, \\ 0, & t = 0, \\ - 1, & t < 0. \end{matrix}$

本文结构如下：第二节首先借助方向导数给出问题(5) d-稳定点的定义，然后得出其d-稳定点的下界性质。第三节探讨问题(3)，问题(4)与问题(5)解的等价性。第四节给出求解问题(5) d-稳定点的光滑化惩罚方法，并证明该算法的收敛性。

2. 最优性条件

2.1. 问题(5)的d-稳定点

首先给出问题(5)的d-稳定点的定义 [16] [24]。

定义2.1：设 $f : ℝ^{n} \to ℝ$ 在点 $x \in ℝ^{n}$ 处方向可微，则函数f在点x处沿方向 $w \in ℝ^{n}$ 的方向导数定义为：

$f^{'} (x; w) : = \lim_{τ ↓ 0} \frac{f (x τ w) - f (x)}{τ} .$

定义2.2：称 $x^{*} \in ℝ^{n}$ 是问题(5)的d-稳定点，如果：

$f^{'} (x^{*}; x - x^{*}) = f^{'} (x^{*}; x - x^{*}) φ^{'} (x^{*}; x - x^{*}) α q^{'} (x^{*}; x - x^{*}) \geq 0, \forall x \in ℝ^{n} .$

peng和chen [24] [25] 证明了当目标函数局部lipschitz连续且方向可微时，d-稳定点具有如下最优性质：

定理2.1：设函数 $f : ℝ^{n} \to ℝ$ 在点 $\hat{x} \in ℝ^{n}$ 处是局部lipschitz连续且方向可微的，则有如下性质：

i) 若 $\hat{x}$ 是函数f的局部最优值点，那么 $\hat{x}$ 是函数f的d-稳定点。

ii) $\hat{x}$ 是函数f的严格局部最优值点并满足一阶增长性条件，即存在 $\hat{x}$ 的领域 $w$ 和 $δ > 0$ 使得：

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

当且仅当 $\hat{x}$ 满足：

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

2.2. 问题(5) d-稳定点的下界性质

下述定理表明问题(5)的d-稳定点的非零分量具有一致的下界。

定理2.2：设 $\frac{λ}{γ} > \frac{δ}{m} ‖ \sum_{i = 1}^{m} a_{i} ‖ α \sqrt{q} {‖ b ‖}_{f}$ ，若 $x^{*} \in ℝ^{n}$ 是问题(5)的d-稳定点，那么或者 $| x_{i}^{*} | \geq γ$ ，或者 $| x_{i}^{*} | = 0$ ， $\forall i = 1, \dots, n$ 。

证明：根据记号，要证明本定理，只需证明 $γ_{1} (x^{*}) = \emptyset$ 。因 $x^{*}$ 是d-稳定点，由定义2.2：

$f^{'} (x^{*}; x - x^{*}) φ^{'} (x^{*}; x - x^{*}) α q^{'} (x^{*}; x - x^{*}) \geq 0, \forall x \in ℝ^{n}$

其中：

i) 因为huber损失函数 $f (x) = \frac{1}{m} \sum_{i = 1}^{m} h (a_{i}^{t} x - b_{i})$ 是可微的，故

$f^{'} (x^{*}; x - x^{*}) = \nabla f {(x^{*})}^{⊤} (x - x^{*}) = \frac{1}{m} \sum_{i = 1}^{m} h^{'} (a_{i}^{⊤} x^{*} - b_{i}) a_{i}^{⊤} (x - x^{*}),$

这里

$h^{'} (a_{i}^{⊤} x^{*} - b_{i}) = {\begin{array}{l} a_{i}^{⊤} x^{*} - b_{i}, & | a_{i}^{⊤} x^{*} - b_{i} | \leq δ, \\ δ \cdot sgn (a_{i}^{⊤} x^{*} - b_{i}), & 其他 . \end{array}$

ii) $φ^{'} (x^{*}; x - x^{*}) = \sum_{i = 1}^{n} φ^{'} (x_{i}^{*}; x_{i} - x_{i}^{*})$ ，且由 $φ (t) = λ \cdot \min {1, \frac{| t |}{γ}}$ ，得：

$φ^{'} (x_{i}^{*}; x_{i} - x_{i}^{*}) = {\begin{array}{l} \frac{λ | x_{i} |}{γ}, & x_{i}^{*} = 0, \\ \frac{λ (x_{i} - x_{i}^{*}) sgn (x_{i}^{*})}{γ}, & | x_{i}^{*} | \in (0, γ), \\ \min {0, \frac{λ (x_{i} - x_{i}^{*}) sgn (x_{i}^{*})}{γ}}, & | x_{i}^{*} | = γ, \\ 0, & 其他 . \end{array}$

iii) 根据文献 [25]，得 $q^{'} (x^{*}; x - x^{*}) = δ : = \sum_{j = 1}^{q} δ_{j}$ ，其中

$δ_{j} = {\begin{array}{l} 0, & 如果 〈 b_{j}, x^{*} 〉 < h_{j}, \\ \max {0, 〈 b_{j}, x - x^{*} 〉}, & 如果 〈 b_{j}, x^{*} 〉 = h_{j}, \\ 〈 b_{j}, x - x^{*} 〉, & 其他, \end{array}$

此处， $b_{j}^{⊤}$ 是矩阵b的第j个行向量。

下面用反证法证明。假设 $γ_{1} (x^{*}) \neq \emptyset$ 。对每个 $i_{0} \in γ_{1} (x^{*})$ ，定义 ${\hat{x}}^{1}, {\hat{x}}^{2} \in ℝ^{n}$ 如下：

${\hat{x}}_{i}^{1} = {\begin{array}{l} 2 x_{i_{0}}^{*}, & 如果 i = i_{0}, \\ x_{i}^{*}, & 其他, \end{array} {\hat{x}}_{i}^{2} = {\begin{array}{l} 0, & 如果 i = i_{0}, \\ x_{i}^{*}, & 其他, \end{array} i = 1, \dots, n .$

则 $f^{'} (x^{*}, {\hat{x}}^{η} - x^{*}) \geq 0, η = 1, 2$ 。由上述(i) (ii) (iii)，得：

$\begin{array}{l} f^{'} (x^{*}, {\hat{x}}^{1} - x^{*}) = {[\nabla f (x^{*})]}_{i_{0}} x_{i_{0}}^{*} \frac{λ x_{i_{0}}^{*} sgn (x_{i_{0}}^{*})}{γ} δ_{i_{0}} \geq 0, \\ f^{'} (x^{*}, {\hat{x}}^{2} - x^{*}) = {[\nabla f (x^{*})]}_{i_{0}} x_{i_{0}}^{*} - \frac{λ x_{i_{0}}^{*} sgn (x_{i_{0}}^{*})}{γ} - δ_{i_{0}} \geq 0. \end{array}$

于是

$\begin{matrix} \frac{λ | x_{i_{0}}^{*} |}{γ} \leq | {[\nabla f (x^{*})]}_{i_{0}} | | δ_{i_{0}} | \leq ‖ \frac{1}{m} \sum_{i = 1}^{m} h^{'} (a_{i}^{⊤} x^{*} - b_{i}) a_{i} ‖ | x_{i_{0}}^{*} | ‖ b^{i_{0}} ‖ | x_{i_{0}}^{*} | \\ \leq (\frac{δ}{m} ‖ \sum_{i = 1}^{m} a_{i} ‖ α \sqrt{q} {‖ b ‖}_{f}) | x_{i_{0}}^{*} | . \end{matrix}$

由 $| x_{i_{0}}^{*} | > 0$ ，得 $\frac{λ}{γ} \leq \frac{δ}{m} ‖ \sum_{i = 1}^{m} a_{i} ‖ α \sqrt{q} {‖ b ‖}_{f}$ ，这与已知条件 $\frac{λ}{γ} > \frac{δ}{m} ‖ \sum_{i = 1}^{m} a_{i} ‖ α \sqrt{q} {‖ b ‖}_{f}$ 矛盾，所以 $γ_{1} (x^{*}) = \emptyset$ 。

注：定理2.2表明问题(5)的d-稳定点的非零分量的绝对值具有正下界 $γ$ 。这种解的下界性质在理论上反映了解的稀疏性，在数值计算中，如果数值解的某些分量小于下界，则可以直接将这些分量取为0，这样可以提高解的稀疏度。类似研究可参见文献 [11] [19] [22] [24]。

3. 解的等价性

3.1. 问题(3)和问题(4)解的等价性

定理3.1：若 $\bar{x} \in ω$ ，那么 $\bar{x}$ 是问题(4)的全局最优解当且仅当 $\bar{x}$ 是问题(3)的全局最优解，且问题(3)和问题(4)具有相同的全局最优值。

证明：

i) 设 $\bar{x} \in ω$ 是问题(4)的全局最优解，则

$f (\bar{x}) λ {‖ \bar{x} ‖}_{0} = f (\bar{x}) φ (\bar{x}) \leq f (x) φ (x) \leq f (x) λ {‖ x ‖}_{0}, \forall x \in ω,$

其中第一个等式由 [19] 中引理2.3可得，而最后一个不等式由 $φ (x) \leq λ {‖ x ‖}_{0}$ 对任何 $x \in ℝ^{n}$ 均成立可得。故 $\bar{x}$ 是问题(3)全局最优解。

ii) 设 $\bar{x} \in ω$ 是问题(3)全局最优解，但不是问题(4)的全局最优解，则问题(4)存在一个全局最优解 $\hat{x}$ ，使得

$f (\hat{x}) φ (\hat{x}) < f (\bar{x}) φ (\bar{x}) .$

由(i)知 $\hat{x}$ 也是问题(3)全局最优解，因此

$f (\hat{x}) λ {‖ \hat{x} ‖}_{0} < f (\bar{x}) λ {‖ \bar{x} ‖}_{0},$

这与 $\bar{x}$ 是问题(3)全局最优解相矛盾。所以问题(3)的任何全局最优解都是问题(4)的全局最优解。

3.2. 问题(4)和问题(5)解的等价性

假设3.1：矩阵b和向量h满足如下条件：存在一些正数 $τ$ ，使得 $dist (x, ω) \leq τ {‖ {(b x - h)}_{} ‖}_{1}$ [26]。

定理3.2：设假设3。1成立，则问题(4)的全局最优解都是问题(5)的全局最优解。

证明：因为 $f (x) φ (x)$ 是lipschitz连续的，设其lipschitz常数为 $l_{f}$ 。对所有的 $α > τ l_{f}$ ，有

$f (x) φ (x) \frac{α}{τ} dist (x, ω) \geq f (y) φ (y), \forall x \in ℝ^{n}, \forall y \in p_{ω} (x) .$ (6)

由假设3.1和(6)，可得：

$\begin{matrix} \inf_{x \in ℝ^{n}} f (x) φ (x) α {‖ {(b x - h)}_{} ‖}_{1} \geq \inf_{x \in ℝ^{n}} f (x) φ (x) \frac{α}{τ} dist (x, ω) \\ \geq \inf_{x \in ℝ^{n}, y \in p_{ω} (x)} f (y) φ (y) \\ = \inf_{x \in ω} f (x) φ (x) \\ = \inf_{x \in ω} f (x) φ (x) α {‖ {(b x - h)}_{} ‖}_{1} \\ \geq \inf_{x \in ℝ^{n}} f (x) φ (x) α {‖ {(b x - h)}_{} ‖}_{1} . \end{matrix}$

因此， $x^{*}$ 是问题(5)的全局最优解。

定理3.3：设假设3.1成立，且 $α > τ l_{f}$ ，其中 $l_{f}$ 是 $f (x) φ (x)$ 的lipschitz常数。若 $x^{*}$ 是问题(5)的全局最优解，那么 $x^{*}$ 是问题(4)的全局最优解。

证明： $x^{*} \in ℝ^{n}$ 是问题(5)的全局最优解，则

$\begin{matrix} f (x^{*}) φ (x^{*}) α {‖ {(b x^{*} - h)}_{} ‖}_{1} = \inf_{x \in ℝ^{n}} f (x) φ (x) α {‖ {(b x - h)}_{} ‖}_{1} \\ \leq \inf_{x \in ω} f (x) φ (x) \\ \leq f (x) φ (x), \forall x \in ω . \end{matrix}$ (7)

由假设3.1，对任意 $x \in p_{ω} (x^{*})$ ，有

$f (x^{*}) φ (x^{*}) \frac{α}{τ} dist (x^{*}, ω) \leq f (x) φ (x) .$

考虑到 $f (x) φ (x)$ 是lipschitz连续的，对任意 $x \in p_{ω} (x^{*})$ ，由上式得

$\begin{matrix} dist (x^{*}, ω) \leq \frac{τ}{α} [f (x) φ (x) - f (x^{*}) - φ (x^{*})] \\ \leq \frac{τ l_{f}}{α} ‖ x - x^{*} ‖ = \frac{τ l_{f}}{α} dist (x^{*}, ω) . \end{matrix}$

因为 $α > τ l_{f}$ ，故 $dist (x^{*}, ω) = 0$ ，因此 $x^{*} \in ω$ 。再由 $α {‖ {(b x^{*} - h)}_{} ‖}_{1} \geq 0$ 和(7)式，可得 $f (x) φ (x) \geq f (x^{*}) φ (x^{*})$ ， $\forall x \in ω$ 。故 $x^{*}$ 是问题(4)的全局最优解。

3.3. 问题(3)和问题(5)解的等价性

由定理3.1、定理3.2和定理3.3可得问题(3)与问题(4)之间解的等价性。

定理：设 $\frac{λ}{γ} > \frac{δ}{m} ‖ \sum_{i = 1}^{m} a_{i} ‖ α \sqrt{q} {‖ b ‖}_{f}$ ， $α > τ l_{f}$ 且 $dist (x, ω) \leq τ {‖ {(b x - h)}_{} ‖}_{1}$ ，则 $x^{*} \in ℝ^{n}$ 是问题(5)的全局最优解当且仅当它是问题(3)的全局最优解。

4. 光滑化惩罚算法

由定理2.1可知，d-稳定点具有非常好的局部最优性。如何计算d-稳定点是一个有趣且具有挑战性的问题。光滑逼近方法是一种求解非光滑问题非常有效且被广泛使用的方法，参见 [19] [22] [23] [24] [26]。受上述文献启发，本节我们使用光滑化惩罚算法来求解问题(4)。

对于 $t_{} = \max {t, 0}$ 函数，将采用下述光滑化函数

$h_{μ} (t) : = {\begin{array}{l} t - \frac{μ}{2}, & t \geq μ, \\ \frac{t^{2}}{2 μ}, & 0 < t < μ, \\ 0, & t \leq 0, \end{array}$

其中 $μ > 0$ 为光滑化参数。因此， $q (x)$ 具有如下光滑化函数

$q_{μ} (x) : = \sum_{j = 1}^{q} h_{μ} (b_{j}^{⊤} x - h_{j}) .$

因 $0 \leq t_{} - h_{μ} (t) \leq \frac{μ}{2}$ ，故对任意的 $x \in ℝ^{n}$ ，可得

$0 \leq q_{μ} (x) \leq q (x) \leq q_{μ} (x) \frac{q}{2} μ .$

此外，注意到 ${h^{'}}_{μ} (t) = \min {{(\frac{t}{μ})}_{}, 1}$ ，

$\nabla q_{μ} (x) = \sum_{j = 1}^{q} {h^{'}}_{μ} (b_{j}^{⊤} x - h_{j}) b_{j} .$

容易证明，光滑函数 $q_{μ} (x)$ 具有下述性质。

i) $\lim_{z \to x, μ ↓ 0} q_{μ} (z, μ) = q (x)$ ；

ii) 对每个固定的 $μ > 0$ ， $q_{μ} (x)$ 是x的凸函数；

iii) 对每个固定的 $μ > 0$ ， $q_{μ} (x)$ 关于x是lipschitz连续的，即

$| q_{μ} (x_{1}) - q_{μ} (x_{2}) | \leq κ ‖ x_{1} - x_{2} ‖;$

iv) 对每个固定的 $x \in ℝ^{n}$ ， $q_{μ} (x)$ 关于 $μ$ 是lipschitz连续的，即

$| q_{μ} (x_{1}) - q_{μ} (x_{2}) | \leq κ^{'} | μ_{1} - μ_{2} | .$

下面给出求解问题(4)的光滑化惩罚算法的框架。

算法4.1. 光滑化惩罚算法

在算法4.1中，

$\begin{array}{l} \nabla f (x^{k}) = \frac{1}{m} \sum_{i = 1}^{m} h^{'} (a_{i}^{⊤} x^{k} - b_{i}) a_{i}, \\ φ^{'} (x^{k}; x - x^{k}) = \sum_{i = 1}^{m} φ^{'} (x_{i}^{k}; x_{i} - x_{i}^{k}), \\ \nabla q_{μ} (x^{k}) = \sum_{j = 1}^{q} {h^{'}}_{μ} (b_{j}^{⊤} x^{k} - h_{j}) b_{j}, \end{array}$

其中，

$h^{'} (a_{i}^{⊤} x^{k} - b_{i}) = {\begin{array}{l} a_{i}^{⊤} x^{k} - b_{i}, & | a_{i}^{⊤} x^{k} - b_{i} | \leq δ, \\ δ \cdot sgn (a_{i}^{⊤} x^{k} - b_{i}), & 其他, \end{array}$

$φ^{'} (x_{i}^{k}; x_{i} - x_{i}^{k}) = {\begin{array}{l} \frac{λ | x_{i} |}{γ}, & x_{i}^{k} = 0, \\ \frac{λ (x_{i} - x_{i}^{k}) sgn (x_{i}^{k})}{γ}, & | x_{i}^{k} | \in (0, γ), \\ \min {0, \frac{λ (x_{i} - x_{i}^{k}) sgn (x_{i}^{k})}{γ}}, & | x_{i}^{k} | = γ, \\ 0, & 其他, \end{array}$

${h^{'}}_{μ} (b_{j}^{⊤} x^{k} - h_{j}) = \min {{(\frac{b_{j}^{⊤} x^{k} - h_{j}}{μ})}_{}, 1} .$

由上述表达式可知 $| h^{'} (a_{i}^{⊤} x^{k} - b_{i}) | \leq δ (i = 1, \dots, n), ‖ \nabla f (x^{k}) ‖ \leq \frac{δ}{m} {‖ a ‖}_{f}$ 和 $0 \leq {h^{'}}_{μ} (b_{j}^{⊤} x^{k} - h_{j}) \leq 1 (j = 1, \dots, q)$ 。

注意，这里只是对非光滑项 $q (x) = {‖ {(b x - h)}_{} ‖}_{1}$ 进行了光滑化，并未对非光滑项 $φ (x)$ 进行光滑化。因此，如何求解迭代步中步1的子问题 $\min_{x \in ℝ^{n}} g_{λ_{k}, μ_{k}} (x)$ 是非常关键的。该子问题仍是一个非光滑优化，但 $φ (x)$ 的邻近函数具有解析表达式 [19]，因此，本文建议采用文献 [26] 中的非单调邻近梯度(npg)算法对其进行求解。

定理4.1：设 $x_{k}$ 是算法4.1生成的序列，则 ${x_{k}}$ 的任何聚点 $x^{*}$ 都是问题(4)的d-稳定点，即

$x^{*} \in ω 且 f^{'} (x^{*}; x - x^{*}) φ^{'} (x^{*}; x - x^{*}) \geq 0, \forall x \in ω .$

证明：设 ${x^{k}}$ 的收敛子列 ${x^{k}}_{k}$ ，使得当 $k \in k$ ， $k \to \infty$ 时， $x^{k} \to x^{*}$ 。

1) 首先证明 $x^{*}$ 是问题(4)的可行点：

$\begin{matrix} {‖ {(b x^{k} - h)}_{} ‖}_{1} \leq q_{μ_{k}} (x^{k}) \frac{q}{2} μ_{k} \\ \leq \frac{1}{α_{k}} g_{λ_{k}, μ_{k}} (x^{k}) \frac{q}{2} μ_{k} \\ \leq \frac{1}{α_{k}} g_{λ_{k}, μ_{k}} (x^{feas}) \frac{q}{2} μ_{k} \\ = \frac{1}{α_{k}} f (x^{feas}) \frac{1}{α_{k}} φ (x^{feas}) \frac{q}{2} μ_{k}, \end{matrix}$

故当 $k \in k$ ， $k \to \infty$ 时，有 ${‖ {(b x^{k} - h)}_{} ‖}_{1} \leq 0$ ，即 $x^{*} \in ω$ 。

2) 其次证明 $x^{*}$ 是问题(4)的d-稳定点。定义

$w_{j}^{k} : = {h^{'}}_{μ_{k}} (b_{j}^{⊤} x^{k} - h_{j}), \forall j = 1, \dots, p$

和

$i^{*} : = {j \in {1, \dots, p} : b_{j}^{⊤} x^{*} - h_{j} = 0},$

则 $0 \leq w_{j}^{k} \leq 1, \forall j = 1, \dots, p$ ；当 $j \notin i^{*}$ 时， $b_{j}^{⊤} x^{*} - h_{j} < 0$ ，且当k充分大时，有 $b_{j}^{⊤} x^{k} - h_{j} < 0$ ，此时也有 $w_{j}^{k} = 0$ ；当 $j \in i^{*}$ 时， $b_{j}^{⊤} x^{k} - h_{j} \to b_{j}^{⊤} x^{*} - h_{j} = 0$ ， $w_{j}^{k} = {h^{'}}_{μ_{k}} (b_{j}^{⊤} x^{k} - h_{j}) \to 0$ 。因

$\min_{x \in ℝ^{n}} {〈 \nabla f (x^{k}), x - x^{k} 〉 φ^{'} (x^{k}, x - x^{k}) α_{k} 〈 \nabla q_{μ_{k}} (x^{k}), x - x^{k} 〉} \geq - ϵ_{k}, \forall x \in ℝ^{n} .$

再由方向导数的表示，存在 $ζ^{k} : = {(ζ_{1}^{k}, \dots, ζ_{n}^{k})}^{⊤}$ 且 $ζ_{i}^{k} \in \partial ϕ (x_{i}^{k}), i = 1, \dots, n$ ，使得

$〈 \nabla f (x^{k}) ζ^{k} α_{k} \sum_{j \in i^{*}} w_{j}^{k} b_{j}, x - x^{k} 〉 \geq - ϵ_{k}, \forall x \in ℝ^{n} .$ (8)

因 $φ (x)$ 是全局lipschitz的，故 ${ζ^{k}}$ 都是有界的。由上式及 ${\nabla f (x^{k})}$ 和 ${ζ^{k}}$ 的有界性，对每个 $j \in i^{*}$ ， ${α_{k} w_{j}^{k}}$ 都是有界的，否则可取 $\hat{x} = x^{k} - [\nabla f (x^{k}) ζ^{k} α_{k} \sum_{j \in i^{*}} w_{j}^{k} b_{j}]$ ，使得

$〈 \nabla f (x^{k}) ζ^{k} α_{k} \sum_{j \in i^{*}} w_{j}^{k} b_{j}, \hat{x} - x^{k} 〉 = - {‖ \nabla f (x^{k}) ζ^{k} α_{k} \sum_{j \in i^{*}} w_{j}^{k} b_{j} ‖}^{2} \to - \infty,$

与(8)矛盾。因此，不妨设

${ζ^{k}}_{k} \to ζ^{*} = {(ζ_{1}^{*}, \dots, ζ_{n}^{*})}^{⊤} \in \partial φ (x^{*}), {α_{k} w_{j}^{k}}_{k} \to y_{j} \in [0, c], j \in i^{*},$

其中 $c > 0$ 为某一常数。在(8)中，由 $ϵ_{k} \to 0$ ，得

$〈 \nabla f (x^{*}) ζ^{*} \sum_{i \in i^{*}} y_{i} b_{j}, x - x^{*} 〉 \geq 0, \forall x \in ℝ^{n} .$

取 $x = x^{*} - [\nabla f (x^{*}) ζ^{*} \sum_{i \in i^{*}} y_{i} b_{j}]$ ，由上式得 $- {‖ \nabla f (x^{*}) ζ^{*} \sum_{i \in i^{*}} y_{i} b_{j} ‖}^{2} \geq 0$ ，故

$\nabla f (x^{*}) ζ^{*} \sum_{i \in i^{*}} y_{i} b_{j} = 0.$

由 $x^{*} \in ω = {x : b x \leq h}$ ，知 $\sum_{i \in i^{*}} y_{i} b_{j} \in n_{ω} (x^{*})$ ，故 $- [\nabla f (x^{*}) ζ^{*}] \in n_{ω} (x^{*})$ 。注意到， $\forall x \in ω$ ，有 $x - x^{*} \in t_{ω} (x^{*})$ 。因此，

$〈 \nabla f (x^{*}) ζ^{*}, x - x^{*} 〉 \geq 0, \forall x \in ω .$

进而， $\forall x \in ω$ ，有

$\begin{matrix} 0 \leq 〈 \nabla f (x^{*}) ζ^{*}, x - x^{*} 〉 \\ \leq 〈 \nabla f (x^{*}), x - x^{*} 〉 \max_{ζ \in \partial φ (x^{*})} 〈 ζ, x - x^{*} 〉 \\ = f^{'} (x^{*}; x - x^{*}) φ^{'} (x^{*}; x - x^{*}) . \end{matrix}$

上式表明， $x^{*}$ 是问题(4)的d-稳定点。

5. 总结

本文研究了基于huber损失的线性不等式约束稀疏优化问题。我们给出了稀疏优化的原问题、松弛问题和惩罚问题等三种模型，在一定条件下分析了三种模型全局最优解的等价性，提出了求解该问题的光滑化惩罚算法，并证明了该算法的收敛性。本文为求解线性不等式约束稀疏优化问题提供了理论和方法基础。下一步将通过数值实验和算例进一步检验算法的实际效果。

基金项目

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

notes

^*通讯作者。

参考文献

[1]	natarajan, b. (1995) sparse approximate solutions to linear systems. siam journal on computing, 24, 227-234.
[2]	donoho, d. (2006) compressed sensing. ieee transactions on information theory, 52, 1289-1306.
[3]	candès, e., romberg, j. and tao, t. (2006) robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. ieee transactions on infor-mation theory, 52, 489-509.
[4]	tibshirani, r. (1996) regression shrinkage and selection via the lasso. journal of the royal statistical society: series b (methodological), 58, 267-288.
[5]	fan, j. and li, r. (2001) variable selection via nonconcave penalized likelihood and its oracle properties. journal of the american statistical association, 96, 1348-1360.
[6]	zhang, c. (2010) nearly unbiased variable se-lection under minimax concave penalty. annals of statistics, 38, 894-942.
[7]	ong, c. and an, l. (2013) learning sparse classifiers with difference of convex functions algorithms. optimization methods and software, 28, 830-854.
[8]	peleg, d. and meir, r. (2008) a bilinear formulation for vector sparsity optimization. signal processing, 88, 375-389.
[9]	thi, h., dinh, t., le, h. and vo, x. (2015) dc approximation approaches for sparse optimization. european journal of operational research, 244, 26-46.
[10]	zhang, t. (2013) multi-stage convex relaxation for feature se-lection. bernoulli, 19, 2277-2293.
[11]	bian, w. and chen, x. (2017) optimality and complexity for constrained optimization problems with nonconvex regularization. mathematics of operations research, 42, 1063-1084.
[12]	chartrand, r. and staneva, v. (2008) restricted isometry properties and nonconvex compressive sensing. inverse problems, 24, 1-14.
[13]	huang, j., horowitz, j. and ma. s. (2008) asymptotic properties of bridge estimators in sparse high-dimensional regression models. annals of statistics, 36, 587-613.
[14]	ahn, m., pang, j. and xin, j. (2017) difference-of-convex learning: directional stationarity, optimality, and sparsity. siam journal on optimization, 27, 1637-1655.
[15]	an, l. and tao, p. (2005) the dc (difference of convex functions) programming and dca revisited with dc models of real world nonconvex optimization problems. annals of op-erations research, 133, 23-46.
[16]	pang, j., razaviyayn, m. and alvarado, a. (2017) computing b-stationary points of nonsmooth dc programs. mathematics of operations research, 42, 95-118.
[17]	chen, x., niu, l. and yuan, y. (2013) optimality conditions and smoothing trust region newton method for non-lipschitz optimization. siam journal on optimization, 23, 1528-1552.
[18]	candès, e., walkin, m. and boyd, s. (2008) enhancing sparsity by reweighted minimization. journal of fourier analysis and applications, 14, 877-905.
[19]	bian, w. and chen, x. (2020) a smoothing proximal gradient algorithm for non-smooth convex regression with cardinality penalty. siam journal on numerical analysis, 58, 858-883.
[20]	罗孝敏, 彭定涛, 张弦. 基于mcp正则的最小一乘回归问题研究[j]. 系统科学与数学, 2021, 41(8): 2327-2337.
[21]	彭定涛, 唐琦, 张弦. 组稀疏优化问题精确连续capped-l1松弛[j]. 数学学报, 2022, 65(2): 243-262.
[22]	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.
[23]	zhang, x. and peng, d. (2022) solving constrained nonsmooth group sparse optimization via group capped- relaxation and group smoothing proximal gradient algorithm. computa-tional optimization and applications, 83, 801-804.
[24]	peng, d. and chen, x. (2020) computation of second-order directional stationary points for group sparse optimization. op-timization methods and software, 35, 348-376.
[25]	rockafellar, r. and wets, r. (2009) variational analysis. 3rd edition, springer-verlag, berlin.
[26]	chen, x., lu, z. and pong, t. (2016) penalty methods for a class of non-lipschitz optimization problems. siam journal on optimization, 26, 1465-1492.

为你推荐

凯发国际一触即发的友情链接