稀疏优化是指决策变量具有稀疏性的一类优化问题. 一些学者基于信号稀疏性建立了压缩感知理论^[1-3] 引发关注并迅速发展. 经过近二十年的探索, 稀疏优化已取得许多突破性成果. 然而, 实际问题中的数据除具有整体稀疏性之外, 常常存在组稀疏性. 组稀疏结构将向量分组, 每组分量全为零或全部非零, 以更少的测量数据实现更准确的恢复效果. 这一性质已被成功应用于机器学习^[4,5]、 生物信息学^[6]、 回归分析^[7]和人脸识别^[8]等领域.

本文考虑具有非线性约束的组稀疏优化问题 (Nonlinear Group Sparsity Constrained Optimization, NL-GSCO)

其中, $f(\mathbf x):\mathbb R^n \to \mathbb R,g(\mathbf{x})=(g_1(\mathbf x),g_2(\mathbf x),\cdots,g_m(\mathbf x))^{\rm T}:\mathbb R^n \to \mathbb R^m,h(\mathbf x)=(h_1(\mathbf x),h_2(\mathbf x),\cdots, h_l(\mathbf x))^{\rm T}:\mathbb R^n \to \mathbb R^l$ 是连续可微函数. 问题 (1.1) 将变量 $\mathbf x$ 分为 $s$ 个不相交的组

每个组有 $n_i$ 个元素: $\sum_{i=1}^s n_i=n,n_i \ge 1$. {$\|\mathbf x\|_{2,0}=\sum_{i=1}^s(\|\mathbf x_i\|_{2})^0$} 表示 $\mathbf x$ 非零组的个数, 方便刻画组稀疏性, $p\le s\le n$. 记 $P:=\left\{\mathbf x:\|\mathbf x\|_{2,0} \le p\right\}, S:=\left\{\mathbf x \in \mathbb R^n:g(\mathbf x) \le 0,h(\mathbf x) = 0\right\},$ 则 NL-GSCO 的可行域为 $S \cap P.$

目前, 一般的单稀疏优化问题已有丰富的理论成果和算法设计. Beck-Eldar^[9] 提出了三类一阶必要最优性条件; Pan-Xiu 在文献[10] 中建立了单稀疏集的 Bouligand、Clarke 和 Mordukhovich 切锥及法锥的等价定义, 给出 N-稳定点、T-稳定点及相关最优性条件, 并将结果推广至带有非负性的稀疏约束优化. 文献[11] 从拓扑角度引入非退化的 M- 稳定点并讨论与基本可行性、CW 最优性等稳定点的关系, 描述了全局性质. 针对带有对称集约束的单稀疏优化问题, Beck-Eldar 对文献[9] 中最优性条件在文献[12] 中进行了推广; Lu 进一步提出强 L-稳定点概念 ^[13]. Chen 等重点刻画三类稀疏优化于多元回归领域应用的问题的解, 并研究了它们的关系^[14]. 对于带有等式和不等式约束的稀疏优化问题, Lu 将稀疏集分解成数个子空间的并, 在每个子空间利用 Robinson 约束规范建立一阶必要最优性条件, 提出惩罚分解算法^[15]; Pan 等在两种新约束规范之上建立了可行集的三种法锥分解, 进一步提出三类 KKT 点及最优性条件^[16]. Zhao 和 Luo 提出等式约束的稀疏优化问题的一类强 $\beta$-拉格朗日稳定点及一阶最优性条件, 设计与该稳定性一致的拉格朗日方程, 讨论相应雅可比矩阵的非奇异性^[17]. 这将为后续提出拉格朗日牛顿算法 (Lagrange-Newton Algorithm, LNA) 提供理论支撑.

对于问题 (1.1), 没有等式和不等式约束时, Beck 和 Hallak 研究了一种广义组稀疏模型 ^[18], 推广了下降引理、L-稳定点等概念. 文献[19] 中, Wu 和 Peng 基于组稀疏集的不同切锥和法锥的表达式建立了一阶和二阶最优性条件. 在文献[20] 中作者考虑非负条件的限制, 研究非负组稀疏约束优化问题的最优性理论. 最近, Yi 和 Shou等在文献[21]中对文献[16] 进行推广, 在法锥分解的基础上分析问题 (1.1) 的三类 KKT 点及最优性条件.

在现有研究中, 利用组稀疏性质对 NL-GSCO 进行深入分析的理论成果仍然较少, 但又有着重要的现实意义. 因此受到 Zhao^[17] 等工作的启发, 本文研究问题 (1.1) 的最优性理论. 本文剩余部分的框架如下: 第 2 节利用投影给出问题 (1.1) 的强 $\gamma$-{Lagrange} 稳定点及其一阶最优性条件, 分析该稳定点与 F-KKT 点等稳定点的关系;第 3 节定义等式约束下的组稀疏优化问题的拉格朗日方程, 证明其与强 $\gamma$-{Lagrange} 稳定点的等价性质; 第 4 节分析了第 3 节中拉格朗日方程中函数的雅可比矩阵的非奇异性; 第 5 节针对等式约束下组稀疏优化问题, 利用组稀疏 GPNP 算法进行了数值实验. 最后一节对本文简要总结.

在文中, 我们定义 $I(\mathbf x)=\left\{i\in ({1,2,\cdots,s}):\mathbf x_i\neq \mathbf 0\right\}$ 为向量 $\mathbf x$ 的组支撑集, $\tilde I=I(\tilde {\mathbf x})=\left\{i\in ({1,2,\cdots,s}):\tilde{\mathbf x}_i\neq \mathbf 0\right\}$; 则 $I(\mathbf x)$ 的基数 $|I(\mathbf x)|=\|\mathbf x\|_{2,0}.\, \tilde I^c$ 是 $\tilde I$ 在 $\left\{1,\cdots,n\right\}$ 中的补集. 定义 $\Lambda=\left\{J\subset ({1,2,\cdots,s}):|J|=p\right\}$, $\Lambda(\mathbf x)=\{J\subseteq\{1,\cdots,s\}:|J|=p, J\supseteq I(\mathbf x)\}$, 其中 $J$ 为 $I$ 的扩展支撑集. 记

其中 $e_{ij^{'}}$ 表示分组后第 $i$ 组的第 $j'$ 个元素为 1, 其余元素为 0 的 $n$ 维向量. 则组稀疏集 $P=\bigcup_{J\in \Lambda(\mathbf x)}\mathbb R_J^n=\bigcup_{J\in \Lambda(\mathbf x)}\text{span}\left\{e_{ij^{'}},i\in J,j^{'}=1,\cdots,n_i\right\}$. 定义问题 (1.1) 的不等式约束积极集

对于连续可微函数 $f:\mathbb R^n\rightarrow\mathbb R$, 有

类似地, 对 $\nabla g_{m^*}(\mathbf x)({m^*}=1,\cdots,m),\nabla h_{l^*}(\mathbf x)(l^*=1,\cdots,l)$ 有同样分组方式. 研究问题 (1.1) 的最优性理论需要利用组稀疏集的法锥、投影等概念. 集合 $P$ 在点 $\mathbf x$ 处的 {Fr$\acute{\rm e}$chet} 法锥 $\hat{N}_P({\mathbf{x}})$、{Mordukhovich} 法锥 ${N}_P^M({\mathbf{x}})$ 及 {Clarke} 法锥 ${N}_P^C({\mathbf{x}})$ 表达式如下

定理 2.1(1)^[19]

(2)^[21] $N_P^M(\mathbf x){=}\left\{\mathbf u\in \mathbb R^n|\|\mathbf u\|_{2,0}\le n-p\right\}\cap\text{span}\left\{e_{ij^{'}},i\notin I(\mathbf x),j^{'}=1,\cdots,n_i\right\}{=}\bigcup_{J\in \Lambda}\mathbb R_{J^c}^n,$

当 $\|\mathbf x\|_{2,0}=p$ 时, $N_P^M(\mathbf x)=\text{span}\left\{e_{ij^{'}},i\in I(\mathbf x),j^{'}=1,\cdots,n_i\right\}=\mathbb R_{I^c}^n.$

(3)^[19] $N_P^C(\mathbf x)= \left\{\mathbf u\in \mathbb R^n:\mathbf u_i=\mathbf 0,i\in I\right\}=\text{span}\left\{e_{ij^{'}},i\notin I,j^{'}=1,\cdots,n_i\right\}.$

推论 2.1^[21] 上述三类法锥成立包含关系 $\hat{N}_P(\tilde{\mathbf x})\subseteq N_P^M(\tilde{\mathbf x})\subseteq N_P^C(\tilde{\mathbf x}).$

由文献[10] 中对单稀疏集支撑投影的讨论, 考虑点到组稀疏集 $P$ 的投影 $\Pi_P(\mathbf x)$. 设 $ I_p(\mathbf x) \triangleq \{k_1, k_2, \cdots, k_p\} \subseteq \{1, 2, \dots, s\} $ 满足 $ \min_{i \in I_p(\mathbf x)} \|\mathbf x_i\| \geq \max_{i \notin I_p(\mathbf x)} \|\mathbf x_i\|, \|\mathbf x_i\|=(\sum_{j^{'}=1}^{n_i}\mathbf x_{ij^{'}}^2)^{\frac{1}{2}}. $ 则组支撑投影 $\Pi_P(\mathbf x) = \left\{ \mathbf z \in \mathbb{R}^n : \mathbf z_i = \mathbf x_i,\, i \in I_p(\mathbf x);\ \mathbf z_i = \mathbf 0,\, i \notin I_p(\mathbf x) \right\}. $ 由于 $P$ 非凸, 则 $\Pi_P(\mathbf x)$ 是非单值映射.

定理 2.2(组稀疏投影的单值性条件) 记$\|\mathbf x\|=(\|\mathbf x_1\|,\|\mathbf x_2\|,\dots,\|\mathbf x_s\|)^{\rm T}$, 设 $\mathcal M_i(\mathbf x)$ 表示 {$\|\mathbf x\|$} 中第 $i$ 大的组, 也就是说 $ {\mathcal M}_1(\|\mathbf x\|) \geq {\mathcal M}_2(\|\mathbf x\|) \geq \cdots \geq {\mathcal M}_s(\|\mathbf x\|). $ 若满足 ${\mathcal M}_p(\|\mathbf x\|) = 0$ 或 ${\mathcal M}_p(\|\mathbf x\|) > {\mathcal M}_{p+1}(\|\mathbf x\|)$, 则 $\Pi_P(\mathbf x)$ 是单点集, 此时

否则, 投影非单值, 需按如下规则处理

若存在多个 $\|\mathbf x_i\| = {\mathcal M}_p(\|\mathbf x\|)$ 的项, 任选其中一组或按某种预定规则保留, 其余置为零组.

利用支撑投影可以建立等式约束的单稀疏优化问题的稳定点和最优性条件^[17]. 那么基于组支撑投影, 我们首先定义问题 (1.1) 的强 $\gamma$-{Lagrange} 稳定点.

定义 3.1(强 $\gamma$-{Lagrange} 稳定点) 对于点 $\tilde{\mathbf x}\in \mathbb R^n,\gamma>0,\tilde{\mathbf x}$ 是问题 (1.1) 的强 $\gamma$-{Lagrange} 稳定点, 如果存在拉格朗日乘子 $\boldsymbol{\xi}\in \mathbb R^m,\boldsymbol\eta\in \mathbb R^l$, 使得

其中

$\gamma$ 是组支撑投影中的步长参数,调节梯度信息在投影步中的权重. 容易看出, (3.1) 式要求组稀疏投影集的单值性, 这也正是定义 "强" 的由来.根据定理 2.2, 能够给出强 $\gamma$-{Lagrange} 稳定点的等价定义.

定理 3.1 $\tilde{\mathbf x}\in \mathbb R^n$ 是以 $\boldsymbol\xi\in {\mathbb R^m},\boldsymbol\eta \in \mathbb R^l$ 为乘子的强 $\gamma$-{Lagrange} 稳定点当且仅当 $\tilde{\mathbf x}$ 满足 $\|\tilde{\mathbf x}\|_{2,0}\leq p, {\xi _{m^*}\geq 0, g_{m^*}(\tilde{\mathbf x})\leq 0, \xi_{m^*}g_{m^*}(\tilde{\mathbf x})=0 ({m^*}=1,\cdots,m), h_{l^*}(\tilde{\mathbf x})=0 ({l^*}=1,\cdots,l)}$ 时, 有

证 先证必要性. 当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, 有 ${\mathcal M}_p(\|\tilde{\mathbf x}\|)>0$. 又

则 $(\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta))_i=\boldsymbol0,\forall i\in \tilde{I}.$ 对任意的 $i\in \tilde{I}^c,\tilde{\mathbf x}_i=\mathbf 0,$ 因此

当 $\|\tilde{\mathbf x}\|_{2,0}<p$ 时, 有 $\tilde{\mathbf x}=\tilde{\mathbf x}-\gamma\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta)$, 则 $\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta)=\boldsymbol0.$

下证充分性. 当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, 由已知, 对于任意的 $ i\in \tilde{ I},\gamma\|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta))_i\|<{\mathcal M}_p(\|\tilde{\mathbf x}\|),$$(\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta))_i=\boldsymbol0.$ 则 $\|(\tilde{\mathbf x}-\gamma \nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta))_i\|=\|\tilde{\mathbf x}_i\|\geq {\mathcal M}_p(\tilde{\mathbf x}).$ 同时, 对于所有 $i\in \tilde{I}^c$,

因此成立

当 $\|\tilde{\mathbf x}\|_{2,0}<p$ 时, $\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta)=\boldsymbol0,$ 则 $\Pi_P(\tilde{\mathbf x}-\gamma \nabla _{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta))=\tilde{\mathbf x}.$

在三类法锥定义 2.1 和组支撑投影定义 2.2 的基础上, 我们给出四种拉格朗日乘子集

由推论 2.1 及定理 3.1, 当拉格朗日乘子 $(\boldsymbol\xi,\boldsymbol\eta)\in \Omega _{\gamma}(\tilde{\mathbf x})$ 时, 可得

因此成立

给定 $\tilde{\mathbf x}\in S\cap P,(\boldsymbol\xi,\boldsymbol\eta)\in\mathbb R^m\times\mathbb R^l,$ 下面定义

我们将在文献 [21,定义 2.9] 中的约束规格 GR-LICQ (Group Restricted-Linear Independence Constraint Qualification) 下研究问题 (1.1) 的一阶最优必要条件.

假设 3.1^[21] (GR-LICQ) 在点 $\tilde{\mathbf x}\in S\cap P$ 处, ${\nabla_{\tilde{I}}g_{m^*}(\tilde{\mathbf x}),\nabla_{\tilde{I}}h_{l^*}(\tilde{\mathbf x}),{m^*}\in \Gamma,{l^*}=1,\dots,l}$ 线性无关. 其中 $\nabla_{\tilde{I}}g_{m^*}(\tilde{\mathbf x})$ 是由 $\tilde{I}$ 确定的 $\nabla g_{m^*}(\tilde{\mathbf x})$ 的子向量, $\Gamma$ 如 (2.1) 式中定义.

基于上述假设, 问题 (1.1) 的一阶最优必要性条件如下.

定理 3.2(一阶必要条件) 假设 $\tilde{\mathbf x}\in S\cap P$ 是问题 (1.1) 的局部最优解, 并且 GR-LICQ 在 $\tilde{\mathbf x}$ 处成立, 则

(i) $\Omega^C(\tilde{\mathbf x})$是一个非空紧凸集;

(ii) ${\text{存在}}(\boldsymbol\xi,\boldsymbol\eta)\in \mathbb R^m\times\mathbb R^l,\,{\text{使得}}\,\forall\gamma\in (0,\gamma^{\ast}),\,\Omega^F(\tilde{\mathbf x})=\Omega_{\gamma}(\tilde{\mathbf x})=\left\{(\boldsymbol\xi,\boldsymbol\eta)\right\}.$

证 对于问题 (1.1) 的可行解 $\tilde{\mathbf x}$ 来说, GR-LICQ 的成立保证了文献[22] CC-LICQ (Cardinality Constraints Linear Independence Constraint Qualification)及文献[23] RRCQ (Restricted Robinson Constraint Qualification) 的成立, 且文献 [21,定理 2.10]yi2025optimality 给出的 Fr$\acute{\rm e}$chet 法锥的分解性质

成立. 因此由文献 [23,定理 4.1] 可得 (i) 及 $\Omega^F(\tilde{\mathbf x})$ 是单点集的结论. 下证 $\Omega^F(\tilde{\mathbf x})=\Omega_{\gamma}(\tilde{\mathbf x}),\,\forall \gamma\in (0,\gamma^{\ast}).$ 由于 $\tilde{\mathbf x}$ 是问题 (1.1) 的局部最优解, 则由文献 [24,定理 6.12] 中最优性条件,

那么存在向量 ${{\boldsymbol\alpha^{(1)}}}\in \hat{N}_S(\tilde{\mathbf x}),{\boldsymbol\alpha^{(2)}}\in \hat{N}_P(\tilde{\mathbf x}),$ 使得

又根据文献 2.1, 有 $\hat{N}_S(\tilde{\mathbf x})=\left\{\langle \nabla_{\Gamma}g(\tilde{\mathbf x}),\boldsymbol\xi\rangle+\langle \nabla h(\tilde{\mathbf x}),\boldsymbol\eta\rangle:{\xi_{m^*}\geq 0,\eta_{l^*}\in \mathbb R}\right\},$ 不妨设

由定理 2.1, 可令

其中 ${\boldsymbol\alpha}^{(2)}_i$ 是将 ${\boldsymbol\alpha^{(2)}}$ 进行与 $\tilde{\mathbf x}$ 同样的分组后 $i\in \tilde{I}^c$ 时的组分量, ${\boldsymbol\alpha}_i^{(2)}\in \mathbb R^{n_i}.$ 因此

另, 在 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, 对于任意的 $i\in \tilde{I}^c,\gamma\in(0,\gamma^\ast)$, 成立 $\gamma\|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta)_i\|<{\mathcal M}_p(\|\tilde{\mathbf x}\|)$. 由定理 3.1, $(\boldsymbol\xi,\boldsymbol\eta)\in \Omega_{\gamma}(\tilde{\mathbf x})$; 根据 (3.4) 式以及 $\Omega^F(\tilde{\mathbf x})$ 是单点集, 可得结论.

接下来, 我们研究问题 (1.1) 的一阶充分条件.

定理 3.3 设 $f,g$ 均为凸函数, $h$ 为一仿射函数, $\gamma>0.$ 若 $\tilde{\mathbf x}$ 是问题 (1.1) 的以 $(\boldsymbol\xi,\boldsymbol\eta)\in \mathbb R^m\times \mathbb R^l$ 为拉格朗日乘子的强 $\gamma$-{Lagrange} 稳定点, 则当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, $\tilde{\mathbf x}$ 是原问题的一个局部最优解; 若 $\|\tilde{\mathbf x}\|_{2,0}<p$, $\tilde{\mathbf x}$ 是全局最优解.

证 由 $f,{g_{m^*}({m^*}=1,2,\cdots,m)}$ 的凸性以及 ${h_{l^*}({l^*}=1,2,\cdots,l)}$ 是仿射函数可知拉格朗日函数 $L({\mathbf x},\boldsymbol\xi,\boldsymbol\eta)$ 关于 $\mathbf x$ 是凸的, 则对任意的 $\mathbf x\in S\cap P,$

而 $L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta)=f(\tilde{\mathbf x})+{\sum_{{m^*}=1}^m\xi_{m^*}g_{m^*}(\tilde{\mathbf x})+\sum_{{l^*}=1}^l\eta_{l^*}h_{l^*}(\tilde{\mathbf x})}=f(\tilde{\mathbf x}).$ 另一方面, 对任意的 $\mathbf x\in S\cap P,$ 由 $\xi_{m^*}\geq0({m^*}=1,2,\cdots,m),$ 可推知

当 $0<\|\tilde{\mathbf x}\|_{2,0}<p$ 时, 有 $\langle\nabla_{\mathbf x}L(\tilde{\mathbf x},\boldsymbol\xi,\boldsymbol\eta),\mathbf x-\tilde{\mathbf x}\rangle\overset{(3.2)}{=}0$, 因此

当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, 存在足够小的 $\epsilon>0$ 及邻域 $U(\tilde{\mathbf x},\epsilon)=\left\{\mathbf x\in \mathbb R^n:\|\mathbf x-\tilde{\mathbf x}\|\leq \epsilon\right\}$ 使得 $U(\tilde{\mathbf x},\epsilon)\cap (S\cap P)=U(\tilde{\mathbf x},\epsilon)\cap (S\cap \mathbb R_{\tilde{I}}^n).$ 则

即此时 $\tilde{\mathbf x}$ 是一个局部最优解.

强 $\gamma$-{Lagrange} 稳定点的建立基于组支撑投影, 当组内元素为 1($s=n$) 时退化为单稀疏约束下的稳定点. 问题 (1.1) 的不同法锥及其分解、拉格朗日乘子集均依赖于组结构, 因此其一阶最优性条件与单稀疏约束的最优性条件有着本质区别.} 本节的最后, 讨论强 $\gamma$-{Lagrange} 稳定点与其它稳定点的关系. 首先, 问题 (1.1) 的 $\alpha-$稳定点 $\tilde{\mathbf x}$ 需要满足对于 $\alpha>0,$

由文献[12] 可知, 如果存在常数 $L_f$ 满足 $0<\alpha<L_f$, 使得目标函数 $f$ 是 $L_f$ 梯度 Lipschitz 连续的, 那么 $\alpha$- 稳定点是 NL-GSCO 的局部最优解, {同时是其基本可行点}. 又因为点 $\tilde{\mathbf x}\in S\cap P$ 是 NL-GSCO 的 $\alpha$-稳定点当且仅当 $\tilde{\mathbf{x}}$ 是下列问题的全局最优解

显然 $\nabla \phi(\tilde{\mathbf x})=\alpha\nabla f(\tilde{\mathbf x})$. 根据文献[21], GR-LICQ 成立时 $\alpha-$稳定点是 F-KKT 点, 且 F-KKT 点强于 M-KKT 点, M-KKT 点强于 C-KKT 点. 由定理 3.2, 当 GR-LICQ 成立时三种乘子集非空, 则 NL-GSCO 的局部最优解必是强 $\gamma$-{Lagrange} 稳定点, 也是 F-KKT 点. 依文献 [备注 1] 的稳定性关系, 可得 NL-GSCO 的一阶最优性关系.

定理 3.4 假设目标函数关于 $L_f>0$ 梯度 Lipschitz 连续, 则 NL-GSCO 稳定点有如下关系成立

上述有关强 $\gamma$-{Lagrange} 稳定点的优化理论是解决问题 NL-GSCO 的一条研究路径. 由于强 $\gamma$-{Lagrange} 稳定点的求解涉及组稀疏投影算子 $\Pi_P(\cdot)$ 的不可微性质, 一阶最优性条件难以直接运用至算法设计中, 因此要通过构建拉格朗日方程, 将强 $\gamma$-Lagrange 稳定点等价地转化为一个可微方程组, 以避免后续直接处理非光滑项.

受互补松弛条件复杂度影响, 我们研究等式约束 ${h_{l^*}(\mathbf x)=0({l^*}=1,2,\cdots,l)}$ 下组稀疏优化问题 (Equality Constraints-Group Sparsity Constrained Optimization, EC-GSCO)

其强 $\gamma$-{Lagrange} 稳定点及一阶最优性条件等结论可由上节直接给出, 这里不再赘述.

定义 4.1 对于点 $\mathbf x\in P,$ 拉格朗日乘子 $\boldsymbol\eta\in \mathbb R^l,\gamma >0$, 设 $\boldsymbol\nu\triangleq \mathbf x-\gamma\nabla_{\mathbf x}L(\mathbf x,\boldsymbol\eta).$ 定义 $\boldsymbol{\nu}$ 的组稀疏投影指标集为

简便起见, 我们记 $\mathcal{A}=\mathcal{A}(\mathbf x,\boldsymbol{\eta};\gamma)$. 对于任意 $A\in \mathcal{A}$, 相应的拉格朗日方程为

其中 $\mathbf x_j=(x_1,\cdots,x_{n_j})^{\rm T}.$

定理 4.1 设 $\gamma>0.$ 则 $\tilde{\mathbf x}\in P$ 是问题 (4.1) 的关于拉格朗日乘子 $\tilde{\boldsymbol{\eta}}\in \mathbb R^l$ 的强 $\gamma$-{Lagrange} 稳定点的充要条件是对任意的 $A\in \mathcal{A}(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};\gamma),$ 拉格朗日方程 $G(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};A)=\mathbf 0.$ 下记 $\tilde{\mathcal{A}}=\mathcal{A}(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};\gamma).$

证 先证必要性. 由定义 3.1 可知 $\tilde{\mathbf x}=\Pi_P(\tilde{\mathbf x}-\gamma\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))=\Pi_P(\tilde{\boldsymbol{\nu}}),h(\tilde{\mathbf x})=0.$ 对于所有 $ A\in \tilde{\mathcal{A}},$ 由定义 4.1

上式成立当且仅当 $(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_i=\mathbf 0.$ 又 $\tilde{\mathbf x}_j=\mathbf 0,\forall j\in A^c$. 则必要性成立, 下证充分性.

令 $\tilde {\boldsymbol{\nu}}=\tilde{\mathbf x}-\gamma\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}).$ 设拉格朗日方程 $G(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};A)={\bf 0}$ 对于任意的 $A\in \tilde{\mathcal{A}}$ 成立. 当 $\tilde{\mathcal{A}}$ 有且仅有一个元素 $A$, 那么

投影结果唯一. 当 $\tilde{\mathcal{A}}$ 中元素不唯一, 对于任意的 $A\in \tilde{\mathcal{A}},G(\tilde{\mathbf{x}},\tilde{\boldsymbol{\eta}};A)={\bf 0}.$ 下面先证 ${\mathcal M}_p(\|\tilde{\boldsymbol{\nu} }\|)=0$. 不妨假设 ${\mathcal M}_p(\|\tilde{\boldsymbol{\nu}}\|)={\mathcal M}_{p+1}(\|\tilde{\boldsymbol{\nu}}\|)>0$, 那么

记 $A^{(1)}=\left\{1,2,\cdots,p\right\},A^{(2)}=\left\{1,2,\cdots,p-1,p+1\right\},$ 又

则 $(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_p=\mathbf 0,\tilde{\mathbf x}_p=\mathbf 0.$ 这意味着 $\tilde{\boldsymbol{\nu}}_p=\mathbf 0,$ 矛盾. 因此 ${\mathcal M}_p(\|\tilde{\boldsymbol{\nu}}\|)=0.$ 结合定义 4.1 可得

这说明 $(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_{A^c}=\mathbf 0$, 从而 $\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}})=\mathbf 0$.

推论 4.1 若 $\tilde{\mathbf x}$ 是问题 (4.1) 的强 $\gamma$-{Lagrange} 稳定点, 拉格朗日乘子为 $\tilde{\boldsymbol{\eta}},$ 则

证 先证 $\tilde{\mathcal{A}}\subseteq\tilde{\Lambda}$}, 即 $\forall A\in \tilde{\mathcal{A}},\tilde{I}\subseteq A.$ 根据定理4.1, $\tilde{\mathcal{A}}$ 中任意支撑集 $A$ 满足 (4.3) 式, 那么

由 $A$ 的任意性, 可知 $\tilde{\mathcal{A}}\subseteq\tilde{\Lambda}.$ {下证 $\tilde{\mathcal{A}}\supseteq\tilde{\Lambda}$}. 当 $0<\|\tilde{\mathbf x}\|_{2,0}<p$ 时, 对于任意的$ J\in \tilde{\Lambda},$ 有

由定义 4.1, $J\in \tilde{\mathcal{A}},$ 也就是说$\tilde{\Lambda}\subseteq\tilde{\mathcal{A}}.$ 当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, ${\mathcal M}_p(\|\tilde{\mathbf x}\|)>0,$ 唯一包含 $\tilde{\mathbf x}$ 组支撑集的基数为 $p$ 的指标集是其自身, 即 $\tilde{\Lambda}=\left\{\tilde{I}\right\}.$ 此时 $\tilde{\mathcal A}$ 是单点集. 由 (3.2) 式可知

那么对任意的 $i\in \tilde{I},j\in \tilde{I}^c$,

因此 $\tilde{I}\in \tilde{\mathcal{A}}$ 即 $\tilde{\Lambda}\subseteq \tilde{\mathcal{A}}.$ 综上可得 $\tilde{\mathcal{A}}=\tilde{\Lambda}$.

当拉格朗日乘子 $\tilde{\boldsymbol{\eta}}\in \Omega_{\gamma}(\tilde{\mathbf x})$ 时, $\tilde{\mathcal{A}}$ 只与 $\tilde{\mathbf x}$ 有关. 若 $\|\tilde{\mathbf x}\|_{2,0}=p_1<p$, $\tilde{\mathcal{A}}=\tilde{\Lambda}$ 中包含 $C(s-p_1,p-p_1)$ 个大小为 $p$ 且覆盖 $\tilde{I}$ 的指标集, 由定理 4.1, 需要检查 $C(s-p_1,p-p_1)$ 个拉格朗日方程才能确定 $\tilde{\mathbf x}$ 是否符合强 $\gamma$-{Lagrange} 稳定点条件.那么当问题高维且 $p_1<p\ll s$ 时可解性大大降低. 下述定理表明只需检查一个 $\tilde{\mathcal{A}}$ 的指标集即可.

定理 4.2 设 $\tilde{\mathbf x}\in P,\tilde{\boldsymbol \eta}\in \mathbb R^l,\gamma>0$, 则对于任意的 $\hat {\gamma}\in(0,\gamma),\tilde{\mathbf x}$ 是以 $\tilde{\boldsymbol{\eta}}$ 为乘子的强 $\hat \gamma$-{Lagrange} 稳定点的充要条件是

证 先证必要性. 由已知,

当 $\|\tilde{\mathbf x}\|_{2,0}<p$ 时, ${\mathcal M}_p(\|\tilde{\mathbf x}\|)=0.$ 由 (3.2) 式,

当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, $\tilde{\Lambda}=\left\{J\right\}=\left\{\tilde{I}\right\}$ 是单点集. 同样根据 (3.2) 式, 有

令 $\hat{\gamma}\rightarrow\gamma,$ 那么就有 $\max_{j\in {J^c}}\|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_j\|\leq \frac{1}{\gamma}{\mathcal M}_p(\|\tilde{\mathbf x}\|).$ 此外, 有 $ (\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_{\tilde{I}}=(\nabla_{\mathbf x}L(\tilde{\mathbf x},$$\tilde{\boldsymbol{\eta}}))_J=\mathbf 0,$ 又由于 $\|\tilde{\boldsymbol{\nu}}_i\|=\|\tilde{\mathbf x}_i\|\geq {\mathcal M}_p(\|\tilde{\mathbf x}\|)\geq \gamma\cdot \|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_j\|=\|\tilde{\boldsymbol{\nu}}_j\|,\forall i\in J,j\in J^c,$ 那么 $J\in \tilde{\mathcal{A}}.$ 由 $\tilde{\Lambda}$ 的单值性, 令 $A=J$. 同时 (4.4) 成立, 因此 $G(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};A)={\bf 0}.$

现在证明充分性. 设存在满足 $\max_{j\in A^c}\|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_j\|\leq \frac{1}{\gamma}\cdot {\mathcal M}_p(\|\tilde{\mathbf x}\|)$ 的指标集 $A\in \tilde{\mathcal{A}}$ 使得拉格朗日方程 (4.3) 成立. 当 $\|\tilde{\mathbf x}\|_{2,0}=p$, ${\mathcal M}_p(\|\tilde{\mathbf x}\|)>0.$ 对于所有$\hat{\gamma}\in(0,\gamma),j\in A^c$, 有

当 $\|\tilde{\mathbf x}\|_{2,0}<p$, 只需证 $(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_{A^c}=\mathbf 0.$ 由 $\gamma\cdot \max_{j\in A^c}\|(\nabla_{\mathbf x}L(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}))_j\|\leq {\mathcal M}_p(\|\tilde{\mathbf x}\|)=0$ 知显然成立.

本节分析 $G(\mathbf x,\boldsymbol{\eta};A)$ 所对应的雅可比矩阵的结构, 证明其在稳定点附近的非奇异性. 这将为日后的二阶算法设计及其收敛性的证明奠定基础. 对于指标集 $A\in \mathcal{A},|A|=p.\,G(\mathbf x,\boldsymbol{\eta};A)$ 关于变量 $(\mathbf x,\boldsymbol{\eta})\in \mathbb R^n\times \mathbb R^l$ 的雅可比矩阵如下

其中 $\nabla_{\mathbf x\mathbf x}^2L(\mathbf x,\boldsymbol{\eta})=\nabla^2f(\mathbf x)-{\sum_{{l^*}=1}^l{\eta}_{l^*}\nabla^2h_{l^*}(\mathbf x)}$ 是关于 $\mathbf x$ 的二阶 Hessian 矩阵, $E_{A^c}$ 是 $n-\sum_{i=1}^pn_i$ 阶的单位矩阵. 我们讨论上述矩阵的非奇异性. 设 $\tilde{\mathbf x}$ 是强 $\gamma$-{Lagrange} 稳定点, 其拉格朗日乘子 $\tilde{\boldsymbol{\eta}}\in \Omega_\gamma(\tilde{\mathbf x}).$ 首先需要给出较 GR-LICQ 更弱的假设

假设 5.1(弱 GR-LICQ) 对任意 $J\in\tilde{\Lambda},{\nabla_Jh_{l^*}(\tilde{\mathbf x}),{l^*}=1,\cdots,l}$ 线性无关.

另外, 还需要两个辅助性假设作为支撑

假设 5.2 对任意 $J\in\tilde{\Lambda}$, 满足 $\langle\mathbf q,(\nabla_{\mathbf x\mathbf x}^2L(\tilde{\mathbf{x}},\tilde{\boldsymbol{\eta}})_{J,J})\mathbf q\rangle>0$. 其中

假设 5.3 $\nabla ^2f(\mathbf x)$ 和 ${\nabla h_{l^*}(\mathbf x)({l^*}=1,\cdots,l)}$ 的二阶 Hessian 矩阵在 $\tilde{\mathbf x}$ 的某个 $\kappa$ 邻域 $U(\tilde{\mathbf x},\kappa)=\left\{\mathbf x\in \mathbb R^n\mid \|\mathbf x-\tilde{\mathbf x}\|_2<\kappa\right\}$ 内 Lipschitz 连续.

结合定理 3.4 可得问题 (4.1) 的二阶最优性充分条件.

定理 5.1(二阶充分性条件) 设问题 (4.1) 中的函数 $f,h$ 二阶连续可微. 当 $\tilde{\mathbf x}\in\mathbb R^n$ 是以 $\tilde{\boldsymbol{\eta}}\in \mathbb R^l$ 为乘子的强 $\gamma$-{Lagrange} 稳定点且假设 5.2 成立时, $\tilde{\mathbf x}$ 是问题 (4.1) 的严格局部最优解.

基于上述假设, 下面讨论组稀疏约束下的雅可比矩阵的非奇异性.

定理 5.2 设 $\tilde{\mathbf x}$ 是问题 (4.1) 的强 $\gamma$-{Lagrange} 稳定点, 拉格朗日乘子为 $\tilde{\boldsymbol{\eta}}\in \Omega_\gamma(\tilde{\mathbf x}),$ 弱 GR-LICQ 以及假设 5.2 在 $\tilde{\mathbf x}$ 处成立. 则矩阵 $\tilde{\mathcal{X}}\triangleq\nabla_{(\mathbf x,\boldsymbol{\eta})}G(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}};A)\in \mathbb R^{(n+l)\times(n+l)},\forall A\in \tilde{\mathcal{A}}$ 非奇异.

证 下证 $\tilde{\mathcal{X}}$ 是满秩矩阵, 即方程组 $\tilde{\mathcal{X}}(\boldsymbol{\mu}^{\rm T};\boldsymbol{\omega}^{\rm T})^{\rm T}=\mathbf 0$ 有唯一零解, 其中 $\boldsymbol{\mu}=(\boldsymbol \mu_A^{\rm T},\boldsymbol{\mu}_{A^c}^{\rm T})^{\rm T}.$ 将 (5.1) 式代入, 齐次方程组化简为

则

由此可知 $\boldsymbol{ \mu_A}\in \mathcal{K}(\nabla_Ah(\tilde{\mathbf x})), \mathcal{K}$ 为假设 5.2 中定义的集合. 对 (5.3) 式中第一个等式左乘 $\boldsymbol{\mu}_A^{\rm T},$

那么 $(\nabla_Ah(\tilde{\mathbf x}))^{\rm T}\boldsymbol{\omega}=\mathbf 0$. 由弱 GR-LICQ, 对于任意 $A\in\tilde{\mathcal{A}}=\tilde{\Lambda},{\nabla_Ah_{l^*}(\tilde{\mathbf x})({l^*}=1,\cdots,l)}$ 线性无关, $(\nabla _Ah(\tilde{\mathbf x}))^{\rm T}$ 满秩, 因此 $\boldsymbol{\omega}=\mathbf 0$, 齐次方程组 (5.3) 有且仅有零解.

记矩阵

由上述证明过程知 $\mathcal{X}$ 与 $\mathcal{X}^\ast$ 的非奇异性一致, 因此只需求解 ${(\sum_{i=1}^{p}n_i+l)\times(\sum_{i=1}^{p}n_i+l)}$ 阶雅可比矩阵相关的线性系统.有鉴于此, 我们在本节的最后探讨拉格朗日方程 (4.3) 所对应的 $\mathcal{X}^\ast$ 在何时是非奇异的. 首先需要陈述几个关键引理.

引理 5.1 给定 $ \tilde{\mathbf x} $ 是问题 (4.1) 的以 $ \tilde{\boldsymbol{\eta}} \in \Omega_\gamma(\tilde{\mathbf x}) $ 为拉格朗日乘子的强 $\gamma$-{Lagrange} 稳定点, 且假设 5.3 成立, 记 $ \tilde{\mathbf y} \triangleq (\tilde{\mathbf x}, \tilde{\boldsymbol{\eta}}) $. 则

(i) 存在 $\kappa_1,L,\ell_i(i=1,\cdots, l)>0,\text{使得对所有} \mathbf {x},\mathbf{x'}\in U(\tilde{\mathbf x},\kappa_1),$ 成立

(ii)^[17] $\nabla_\mathbf x L(\mathbf x,\boldsymbol{\eta})$ 在 $\tilde{\mathbf y}$ 局部 Lipschitz 连续, 即存在 $L^{(1)}>0$, 使得

(iii)^[17] $\nabla^2 L(\mathbf x,\boldsymbol{\eta})$ 在 $\tilde{\mathbf y}$ 局部 Lipschitz 连续, 即存在 $L^{(2)}>0$, 使得

令

出于现实意义, 忽略 $\tilde{\mathbf x}=\mathbf 0$ 的情况. 记 $ \tilde{\kappa}\triangleq \min\left\{\kappa_1,\kappa_2\right\}, $$\kappa_1$ 是 (5.5) 式中的邻域半径. 定义 $\tilde{\mathbf y}$ 的邻域

引理 5.2 设 $\tilde{\mathbf x}$ 是问题 (4.1) 的以 $\tilde{\boldsymbol{\eta}}$ 为乘子的强 $\gamma$-{Lagrange} 稳定点, $\tilde{\mathbf y}=(\tilde{\mathbf x},\tilde{\boldsymbol{\eta}}).$ 如果假设5.3 成立, 则对任意 $\mathbf y\in {U}_P(\tilde{\mathbf y};\tilde{\kappa})$, 成立

当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, $\left\{I\right\}=\mathcal{A}=\tilde{\mathcal{A}}=\left\{\tilde{I}\right\}.$

证 根据引理 3.1 可知 $(\nabla_\mathbf xL(\tilde{\mathbf{x}},\tilde{\boldsymbol{ \eta}}))_{\tilde{I}} =\mathbf 0,\forall \mathbf x\in P\cap S.$ 对于任意的 $\mathbf y\in U_P(\tilde{\mathbf y};\tilde{\kappa}),i\in \tilde{I},j\in \tilde{I}^c$ 有

又由 $(\|\mathbf x_i-\tilde{\mathbf x}_i\|+\|\mathbf x_j-\tilde{\mathbf x}_j\|)^2\leq \|\mathbf x-\tilde{\mathbf x}\|^2+2\|\mathbf x_i-\tilde{\mathbf x}_i\|\cdot \|\mathbf x_j-\tilde{\mathbf x}_j\|\leq 2\|\mathbf x-\tilde{\mathbf x}\|^2, $ 可知 $\|\mathbf x_i-\tilde{\mathbf x}_i\|+\|\mathbf x_j-\tilde{\mathbf x}_j\|\leq \sqrt{2}\|\mathbf x-\tilde{\mathbf x}\|,$ 因此

则任意的 $i\in\tilde{I},j\in\tilde{I}^c,$ 满足 $\|\boldsymbol{\nu}_i\|\geq\|\boldsymbol{\nu}_j\|,$ 即 $\tilde{I}\subseteq A,\forall A\in{\mathcal{A}}.$ 那么一定存在 $J\in\tilde{\Lambda},$ 使得 $A\subseteq J.$ 由推论 4.1,$\mathcal{A}\subseteq\tilde{\Lambda}=\tilde{\mathcal{A.}}$ 当 $\|\tilde{\mathbf x}\|_{2,0}=p$ 时, $\tilde{\mathcal{A}}$ 是单点集 $\left\{\tilde{I}\right\}$, 不难推知

证毕.

现在, 就可以得到简化的雅可比矩阵 $\mathcal{X}^\ast$ 的非奇异性质.

定理 5.3 设 $\tilde{\mathbf x}$ 为问题 (4.1) 的以 $\tilde{\boldsymbol{\eta}}$ 为拉格朗日乘子的强 $\gamma$-{Lagrange} 稳定点且满足弱 GR-LICQ. 如果假设 5.2 和假设 5.3 均成立, 则存在 $\kappa'\in(0,\tilde{\kappa}],\beta>0,$ 使得对任意 $\mathbf y \in U_P(\tilde{\mathbf y},\kappa'),\mathcal{X}^{\ast}$ 非奇异且逆矩阵的矩阵范数一致有界, 即

证 记 $\tilde{\mathcal{X}}^\ast$ 是在 $\tilde{\mathbf y}$ 处的简化雅可比矩阵. 若弱 GR-LICQ 和假设 5.2 成立, 由定理 5.2 可知任意 $A\in\tilde{\mathcal{A}},\tilde{\mathcal{X}}^\ast$ 是可逆的, 那么 $\tilde{\mathcal{X}}^*$ 可逆对于所有 $ A\in \mathcal{A}$ 同样成立, 因此

即 $\mathcal{X}^*$ 在 $\tilde{\mathbf y}$ 局部 Lipschitz 连续. 那么存在 $\kappa_A,\beta_A>0,$ 使得对 $\forall \mathbf y\in U_P(\tilde{\mathbf{y}},\kappa_A),\mathcal{X}^*$ 保持非奇异性, 即其逆矩阵存在, 且矩阵范数一致有界 $ \|(\mathcal{X}^*)^{-1}\|\leq \beta_A.$ 对于每个 $A\in\mathcal{A}\subseteq\tilde{\mathcal{A}}=\tilde{\Lambda},$ 不妨设 $\kappa'=\min\left\{\kappa,\left\{\kappa_A\right\}\right\},~ \beta=\max\left\{\beta_A\right\},$ 则对任意 $\mathbf y\in U_P(\tilde{\mathbf{y}};\kappa'),\mathcal{X}^*$ 非奇异且逆矩阵满足 (5.11) 式.

鉴于应用上述理论成果的 EC-GSCO 求解算法仍需深入研究, 本文将文献[25] 中求解单稀疏优化问题的梯度投影牛顿追踪算法 (GPNP) 改进应用于组稀疏优化问题. GPNP 算法核心在于计算梯度投影, 当支撑集满足一定条件时执行牛顿追踪步. 我们的本质创新在于组支撑投影的计算. 由文献 [25,引理 3.1], 算法全局收敛于 $\alpha$-稳定点. 那么当 GR-LICQ^[21] 成立时, $\alpha$-稳定点即为强 $\gamma$-Lagrange 稳定点. 为检验等式约束下组稀疏 GPNP 的数值表现, 进行随机生成实验和稀疏信号恢复实验, 均在 16GB 内存, AMD Ryzen 5 4600U with Radeon Graphics 2.10 GHz CPU 的笔记本电脑上采用 MATLAB (R2022a) 上实现.

例 数值实验中, 考虑组稀疏等式约束优化问题

我们采用二次罚函数法加入等式约束, 罚因子 $\bar{\lambda}=5$. 高斯矩阵 $A\in\mathbb{R}^{\overline{m}\times n}$, 观测向量 $\textbf{b}\in \mathbb R^{\overline{m}}$, 原始组稀疏信号 $\bar{\textbf{x}}$. 约束矩阵 $C\in\mathbb R^{l\times n},\textbf{d}=C*\bar{\textbf{x}},l$ 代表等式约束数量. 生成观测值

其中 $\iota$ 为噪声. 选择 $p$ 个组非零, 组内生成正态分布随机数. 算法运行迭代次数为 $\rm iter$. 类似文献[25] 中定义, 当 $\pi_{k'}$ 小于收敛容差 $\epsilon_1$ 时算法终止, 其中

$std (\textbf{x} )$ 代表 $\textbf{x}$ 的标准差, $\textbf{x}^{k'}$ 为第 ${k'}$ 次迭代点.

随机模拟 1 随机生成 ${\overline{m}}=1500$, $n=3000$ 的高斯矩阵 $A,$ 等式约束数量 $l=50,$ 组稀疏度 $p=50,$ 每组元素个数为 6. 实验中设置参数最大迭代次数 $\rm Maxiter=10^4,$ 收敛容差 $\epsilon_1=10^{-6}.$图 2(a) 和图 2(b)分别为零噪声和噪声为 0.1$\%$ 时的稀疏信号恢复情况.

可以观察到, 原始信号 $\bar{\textbf{x}}$ 与恢复信号 $\textbf{x}^*$ 几乎重合. 因此算法可以在有效满足等式约束的同时, 当噪声 $\iota=0$ 和噪声 $\iota=0.1\%$ 时都有优秀的高维稀疏信号恢复能力.

随机模拟 2 取 ${\overline{m}}=800,n=2000,l=20,$ 将组稀疏解 $\bar{\textbf{x}}$ 分为 400 组, 每组对应元素数量为 5, 其余参数与随机模拟 1 相同. 我们在两种噪声情况下测试成功率、相对误差、计算时间和约束违反随组稀疏度的变化情况, 图 2 展示了不同噪声下每个稀疏度进行 100 次随机试验取平均值的实验结果. $relerr=\frac{\|\bar{\textbf{x}}-\textbf{x}^*\|}{\|\bar{\textbf{x}}\|}$ 为相对误差的计算公式, 约束违反度 $viol=\|C*\bar{\textbf{x}}-d\|.$ 当 $relerr<10^{-4}$ 且 $viol<10^{-3}$ 时被视作一次成功实验.

可以看出, 当罚因子 $\bar{\lambda}=5$, 噪声 $\iota=0$ 时, 成功率在组稀疏度 $p\leq20$ 的情况下表现出色, 且相对误差保持在 $2.2\times10^{-6}$ 以内, 约束违反度在 $3\times10^{-5}$ 以内, 说明算法此时可以精确恢复. 当噪声水平增加到 $\iota=0.1\%$ 时, 成功率随组稀疏度增加呈下降趋势. 当 $p\leq 6,$ 成功率保持在 100$\%$, 恢复较易; 当 $p>6$ 时成功率逐渐开始有显著下降, 相对误差在 $3.4\times10^{-5}$ 附近波动, 约束违反有所增加, 即噪声 $\iota=0.1\%$ 情况下的组稀疏 GPNP 算法精度低于零噪声情况下的精度.

在两种噪声条件下, 计算时间均很短且 $\rm Iter\ll \rm Maxiter$, 这意味着算法在收敛条件下有效近似计算了 $\alpha$-稳定点, 满足 GR-LICQ 时即为强$\gamma$-Lagrange 稳定点. 同时, 等式约束的加入使罚参数的选择也成为关键, 不同问题规模 (约束数量、求解维度等) 可能需要不同的选择策略, 罚参数与问题特性的定量关系仍需深入研究. 此外, 考虑到本文给出的强 $\gamma$-Lagrange 稳定点与拉格朗日方程的关系, 未来可能考虑使用牛顿法求解组稀疏拉格朗日方程, 从而直接求解问题 (4.1) 的强 $\gamma$-Lagrange 稳定点. 数值实验中, 组大小的不同可能会影响计算结果, 或导致实际求解的线性系统规模没有明显缩小, 维度仍然较高; 需注意更为复杂的收敛情况, 如组间有重叠, 算法可能陷入非期望的局部极小点; 组投影、组范数计算、组间比较等操作可能引入数值误差.

针对问题 NL-GSCO, 本文建立了强 $\gamma$-{Lagrange} 稳定点, 给出一阶最优性条件, 并系统分析了不同稳定点之间的强弱关系. 囿于不等式约束互补松弛条件的复杂情况, 设计了等式约束的组稀疏优化问题 (EC-GSCO) 的拉格朗日方程, 严格证明了相应雅可比矩阵在强 $\gamma$-{Lagrange} 稳定点邻域内的非奇异性. 本文将单稀疏优化算法延申至组稀疏领域, 应用组稀疏 GPNP 算法于 EC-GSCO 问题中, 展现出较高的计算效率和良好的性能. 文中理论成果为等式约束和不等式约束下组稀疏优化问题的分析和求解奠定了基础, 也为其算法设计提供了重要思路.后续研究将基于所获得的最优性条件和雅可比矩阵性质, 开发专门针对 EC-GSCO 问题的高效求解算法.