上海理工大学学报  2022, Vol. 44 Issue (4): 373-380 PDF

A sequential active set algorithm for nonsmooth composite functions with polyhedral constraints
SHI Shanshan, YU Zhensheng
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: The solution of nonsmooth composite function problem with polyhedral constraints was studied. For the problem of nonsmooth composite function, a smooth function was firstly constructed to approximate the nonsmooth objective function, and the purpose of solving the original problem was then achieved by handling the smooth approximation problem. On this basis, considering the special structure of polyhedral constraints, the idea of sequential quadratic programming algorithm was adopted. A quadratic programming subproblem was solved to obtain the search direction. The active set strategy was adopted by the solution of quadratic programming to approach the optimal solution of the search direction by solving a series of quadratic programming problems with equality constraints step by step. After that, the step size was obtained by line search. The next iteration point was then obtained. Finally, the global convergence of the algorithm was proved theoretically. A preliminary numerical experiment was carried out to compare the algorithm with the smoothed sequential projection shrinkage algorithm. The results show that the algorithm has certain advantages not only in iteration times but also in computing time.
Key words: smooth approximation     polyhedral constraint     composite function     sequential quadratic programing     active set
1 问题的提出

 $\left\{ \begin{array}{*{20}{l}} \mathop {\min }\limits_x \quad \phi \left( {\boldsymbol{x}} \right): = f\left( {\boldsymbol{x}} \right) + g\left( {\boldsymbol{x}} \right) \\ {\text{s}}{\text{.t}}{\text{.}}\quad \;\;{\boldsymbol{x}} \in \varOmega \\ \end{array} \right.$ (1)

 $\left\{ \begin{array}{*{20}{l}} \mathop {\min }\limits_x \quad \phi \left( {\boldsymbol{x}} \right): = f\left( {\boldsymbol{x}} \right) + \left\| {\boldsymbol{x}} \right\|_q^q \\ {\text{s}}{\text{.t}}{\text{.}}\quad \;\;{\boldsymbol{x}} \in \varOmega \\ \end{array} \right.$ (2)

 $\left\{ \begin{array}{*{20}{l}} \mathop {\min }\limits_x \quad \phi \left( {\boldsymbol{x}} \right): = f\left( {\boldsymbol{x}} \right) + \left\| {{\boldsymbol{b}} - {\boldsymbol{Ax}}} \right\|_q^q \\ {\bf{s}}{\bf{.t.}}\quad \;\;{\boldsymbol{x}} \in \varOmega \\ \end{array} \right.$ (3)

2 光滑近似

 $\theta \left( t \right) = \left| t \right|$

 ${\theta _\mu }\left( {t, \mu } \right) = \left\{ \begin{array}{*{20}{l}} t,& t > \dfrac{\mu }{2} \\ \dfrac{{{t^2}}}{\mu } + \dfrac{\mu }{4}, &- \dfrac{\mu }{2} \leqslant t \leqslant \dfrac{\mu }{2} \\ - t, & t < - \dfrac{\mu }{2} \end{array} \right.$ (4)

 $\left\{ \begin{array}{*{20}{l}} \mathop {\min }\limits_x \;{\text{ }}\tilde \phi ({\boldsymbol{x}},\mu ): = f\left( {\boldsymbol{x}} \right) + \tilde g\left( {{\boldsymbol{x}},\mu } \right) \\ {\text{s}}{\text{.t}}{\text{.}}\;\;\;\,{\boldsymbol{x}} \in \varOmega \\ \end{array} \right.$ (5)

 ${\theta _\mu }(t,\mu ) = \theta (t),\;\forall t \geqslant \mu$

 $\theta (t,\mu ) \geqslant \dfrac{\mu }{4},\;\,\forall t$

 ${\left[ {{\theta ^q}(t,\mu )} \right]^\prime } = \left\{ {\begin{array}{*{20}{l}} {q{t^{q - 1}},{\text{ }}\quad \quad \quad \quad \;t > \dfrac{\mu }{2}} \\ {2q{\theta ^{q - 1}}\left( {t,\mu } \right)\dfrac{t}{\mu },{\text{ }} - \dfrac{\mu }{2} \leqslant t \leqslant \dfrac{\mu }{2}} \\ { - q{t^{q - 1}},\quad \quad \quad \quad \;t < - \dfrac{\mu }{2}} \end{array}} \right.\quad$
 ${\left[ {{\theta ^q}(t,\mu )} \right]^{\prime \prime }} = \left\{ {\begin{array}{*{20}{l}} {q\left( {q - 1} \right){t^{q - 2}},\qquad \qquad t > \dfrac{\mu }{2}}\\ \begin{array}{l} q{\theta ^{q - 1}}\left( {t,\mu } \right)\dfrac{2}{\mu } + q\left( {q - 1} \right)\cdot \\\quad {\theta ^{q - 2}}(t,\mu )\dfrac{{2{t^2}}}{{{\mu ^2}}},\qquad - \dfrac{\mu }{2} \leqslant t \leqslant \dfrac{\mu }{2} \end{array}\\ { - q\left( {q - 1} \right){t^{q - 2}}, \qquad \qquad t < - \dfrac{\mu }{2}} \end{array}} \right.$

a. $0 \leqslant {\theta ^q}\left( {t,\mu } \right) - {\theta ^q}\left( t \right) \leqslant {\left( {\dfrac{\mu }{4}} \right)^q},\forall t \leqslant \dfrac{\mu }{2}$ ，且有 ${\left[ {{\theta ^q}(t,\mu )} \right]^{\prime \prime }} \leqslant 16q{\mu ^{q - 2}}$ $\forall t \notin \left\{ - \dfrac{\mu }{2},\dfrac{\mu }{2}\right\}$

b. 定义

 $\kappa (t,\mu )\left\{\begin{array}{l}16q{\mu }^{q-2},\text{ }0\leqslant t\leqslant \mu \\ 0,\text{ }其他 \end{array}\right.$

$\forall t$ $\hat t$ ，如果 $\hat t > \mu$ 使得 $t - \hat t \geqslant - \dfrac{{\hat t}}{2}$ ，或者 $0 \leqslant t \leqslant \mu$ 时， $t \in ( - \infty ,\infty )$ ，或者 $\hat t < 0$ 时， $t - \hat t \leqslant 0$ ，有

 ${\theta ^q}\left( {t,\mu } \right) \leqslant {\theta ^q}\left( {\hat t,\mu } \right) + {\left[ {{\theta ^q}(\hat t,\mu )} \right]^\prime }(t - \hat t) + \frac{{\kappa (\hat t,\mu )}}{2}{(t - \hat t)^2}$

3 算　法

 \begin{aligned} {Q_1}\left( {{\boldsymbol{x}},{{\boldsymbol{x}}_k},\mu } \right) =& \tilde g\left( {{{\boldsymbol{x}}_k},\mu } \right) + \nabla \tilde g{\left( {{{\boldsymbol{x}}_k},\mu } \right)^{\text{T}}}\left( {{\boldsymbol{x}} - {{\boldsymbol{x}}_k}} \right) + \\&\frac{1}{2}{({\boldsymbol{x}} - {{\boldsymbol{x}}_k})^{\text{T}}}\tilde B({{\boldsymbol{x}}_k},\mu )({\boldsymbol{x}} - {{\boldsymbol{x}}_k}) \end{aligned}

 ${Q_2}({\boldsymbol{x}},{{\boldsymbol{x}}_k}) = f({{\boldsymbol{x}}_k}) + \nabla f{({{\boldsymbol{x}}_k})^{\rm{T}}}({\boldsymbol{x}} - {{\boldsymbol{x}}_k}) + \frac{1}{2}{L_k}{\left\| {{\boldsymbol{x}} - {{\boldsymbol{x}}_k}} \right\|^2}$

 ${\left\| {\nabla f({\boldsymbol{x}}) - \nabla f({\boldsymbol{y}})} \right\|_2} \leqslant L{\left\| {{\boldsymbol{x}} - {\boldsymbol{y}}} \right\|_2},\;\forall {\boldsymbol{x}},{\boldsymbol{y}} \in \varOmega$

 $Q({\boldsymbol{x}},{{\boldsymbol{x}}_k},\mu ) = {Q_1}({\boldsymbol{x}},{{\boldsymbol{x}}_k},\mu ) + {Q_2}({\boldsymbol{x}},{{\boldsymbol{x}}_k})$ (6)

 $\begin{gathered} {\left( {{{\boldsymbol{x}}_k} - {\boldsymbol{x}}} \right)_e} \leqslant 0,\,\;e \in \mathcal{I}_{{{\boldsymbol{x}}_k}}^\mu \\ {\left( {{{\boldsymbol{x}}_k} - {\boldsymbol{x}}} \right)_e} \geqslant - \dfrac{{{{({{\boldsymbol{x}}_k})}_e}}}{2},\;e \in \mathcal{J}_{{{\boldsymbol{x}}_k}}^\mu \\ \end{gathered}$

 $\begin{gathered} \mathcal{I}_{{{\boldsymbol{x}}_k}}^\mu = \left\{ {e|{{({{\boldsymbol{x}}_k})}_e} < 0} \right\} \\ \mathcal{J}_{{{\boldsymbol{x}}_k}}^\mu = \left\{ {e|{{({{\boldsymbol{x}}_k})}_e} > \mu } \right\} \\ \end{gathered}$

 $\left\{\begin{gathered} \mathop {\min }\limits_x \quad {\mkern 1mu} \tilde \phi ({\boldsymbol{x}},\mu ): = f({\boldsymbol{x}}) + \tilde g({\boldsymbol{x}},\mu ) \\ {\text{s}}{\text{.t}}{\text{.}}\quad \;\; {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_E} \\ {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} \geqslant {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_I} \end{gathered}\right.$ (7)

 $\left\{\begin{array}{l} \min \quad {\mkern 1mu} Q\left( {{\boldsymbol{x}},{{\boldsymbol{x}}_k},\mu } \right) \\ {\text{s}}{\text{.t}}{\text{.}}\quad \;\; {{{\left( {{{\boldsymbol{x}}_k} - {\boldsymbol{x}}} \right)}_e} \leqslant 0,\;e \in \mathcal{I}_{{{\boldsymbol{x}}_k}}^\mu } \\ \quad\quad\;\;\;{{{\left( {{{\boldsymbol{x}}_k} - {\boldsymbol{x}}} \right)}_e} \geqslant - \dfrac{{{{({{\boldsymbol{x}}_k})}_e}}}{2},\;e \in \mathcal{J}_{{{\boldsymbol{x}}_k}}^\mu } \\ \quad\quad\;\;\; {{\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} = {b_i},\;i \in {\mathcal{M}_E}} \\ \quad\quad\;\;\; {{\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} \geqslant {b_i},\;i \in {\mathcal{M}_I}} \end{array}\right.$ (8)

${{\boldsymbol{d}}_k} = {\boldsymbol{x}} - {{\boldsymbol{x}}_k}$ ${{\boldsymbol{H}}_k} = {L_k}{{\boldsymbol{I}}_n} + \tilde {\boldsymbol{B}}({{\boldsymbol{x}}_k},\mu )$ ，则 $Q\left( {{\boldsymbol{x}},{{\boldsymbol{x}}_k},\mu } \right) = \nabla \tilde \phi {({{\boldsymbol{x}}_k},\mu )^{\text{T}}}{{\boldsymbol{d}}_k} + \dfrac{1}{2}{\boldsymbol{d}}_k^{\text{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k}$

${r_k} = \dfrac{{f({{\boldsymbol{x}}_{k + 1}}) - f({{\boldsymbol{x}}_k}) - \nabla f{{({{\boldsymbol{x}}_k})}^{\text{T}}}({{\boldsymbol{x}}_{k + 1}} - {{\boldsymbol{x}}_k})}}{{\dfrac{1}{2}{L_k}{{\left\| {{{\boldsymbol{x}}_{k + 1}} - {{\boldsymbol{x}}_k}} \right\|}^2}}}$

${\boldsymbol{x}} - {{\boldsymbol{x}}_k} = {\boldsymbol{d}}$ ，则可将QP子问题（8）转化与 ${\boldsymbol{d}}$ 有关的子问题求解。通过积极集策略，会有越来越多的 ${{\boldsymbol{x}}_k}$ 逐渐满足 ${\boldsymbol{a}}_i^{\rm{T}}{{\boldsymbol{x}}_k} = {{\boldsymbol{b}}_i},\;i \in {{{\mathcal{S}}}_k}$ 。这样问题就转化为了等式约束优化问题，再利用拉格朗日乘子算法对其进行求解。因此，本文的算法可以在大大减少问题维数的同时提高计算的效率。

 $\begin{gathered} \min \quad {\mkern 1mu} {q_k}\left( {\boldsymbol{t}} \right) = \frac{1}{2}{{\boldsymbol{t}}^{\text{T}}}{{\boldsymbol{H}}_k}{\boldsymbol{t}} + {\boldsymbol{C}}_k^{\text{T}}{\boldsymbol{t}} \\ {\text{s}}{\text{.t}}{\text{.}}\quad \;{\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{t}} = 0,\;i \in {\mathcal{S}_k} \\ \end{gathered}$

${\bar \alpha _k} = \mathop {\min }\limits_{i \in {\mathcal{S}_k}} \left\{ {\dfrac{{{c_i} - {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{d}}_k}}}{{{\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{t}}_k}}}\Bigg| {{\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{t}}_k} < 0} } \right\}$

${{\boldsymbol{d}}_{k + 1}}: = {{\boldsymbol{d}}_k} + {\alpha _k}{{\boldsymbol{t}}_k}$ ，其中 ${c_i} = {{\boldsymbol{b}}_i} - {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_0}$

4 收敛性分析

${{\boldsymbol{H}}_k}$ 的构造可知， ${{\boldsymbol{H}}_k}$ 一定是对称正定的。本文提出的SQP-ASA算法通过求解如下形式的二次规划问题

 $\left\{ \begin{gathered} \min \quad \nabla \tilde \phi {({{\boldsymbol{x}}_k},\mu )^{\text{T}}}{\boldsymbol{d}} + \frac{1}{2}{{\boldsymbol{d}}^{\rm{T}}}{{\boldsymbol{H}}_k}{\boldsymbol{d}} \\ {\text{s}}{\text{.t}}{\text{.}}\quad \; {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{d}} + {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_E} \\ \quad\quad {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{d}} + {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} \geqslant {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_I} \end{gathered}\right.$ (9)

 \begin{aligned} {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_{k + 1}} =& {\boldsymbol{a}}_i^{\text{T}}({{\boldsymbol{x}}_k} + {\beta _k}{{\boldsymbol{d}}_k}) = {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} + {\beta _k}{\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{d}}_k} =\\& {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} + 0 = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_E} \end{aligned}
 $\begin{gathered} {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_{k + 1}} = {\boldsymbol{a}}_i^{\text{T}}({{\boldsymbol{x}}_k} + {\beta _k}{{\boldsymbol{d}}_k}) = {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} + {\beta _k}{{\boldsymbol{a}}_i}{{\boldsymbol{d}}_k} \geqslant \\ {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} + {\beta _k}({{\boldsymbol{b}}_i} - {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k}) \geqslant (1 - {\beta _k}){\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} + \\ {\beta _k}{{\boldsymbol{b}}_i} \geqslant (1 - {\beta _k}){{\boldsymbol{b}}_i} + {\beta _k}{{\boldsymbol{b}}_i} = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_I} \\ \end{gathered}$

 $\left\{ \begin{gathered} \nabla \tilde \phi ({{\boldsymbol{x}}_k},\mu ) + {{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k} = \mathop \sum \limits_{i \in {\mathcal{M}_I}} {\lambda _i}{{\boldsymbol{a}}_i} + \mathop \sum \limits_{i \in {\mathcal{M}_E}} {\lambda _i}{{\boldsymbol{a}}_i} \\ {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{d}}_k} = 0,\;i \in {\mathcal{M}_E} \\ {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{d}}_k} \geqslant {c_i},\;{c_i} = {{\boldsymbol{b}}_i} - {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k},\;i \in {\mathcal{M}_I} \\ {\lambda _i} \geqslant 0,\;i \in {\mathcal{M}_I};{\lambda _i} = 0,\;i \in \mathcal{M}\backslash {\mathcal{S}_k} \\ \end{gathered} \right.$ (10)

 \begin{aligned} \nabla \tilde \phi ({{\boldsymbol{x}}_k},\mu ){{\boldsymbol{d}}_k} =& - {\boldsymbol{d}}_k^{\text{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k} - \mathop \sum \limits_{i \in {\mathcal{M}_I}} {\lambda _i}({\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i}) - \\ &\mathop \sum \limits_{i \in {\mathcal{M}_E}} {\lambda _i}({\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i}) = - {\boldsymbol{d}}_k^{\rm{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k} -\\ & \mathop \sum \limits_{i \in {\mathcal{S}_k}} {\lambda _i}({\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i}) - \mathop \sum \limits_{i \in \mathcal{M}\backslash {\mathcal{S}_k}} {\lambda _i}({\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i}) \\ \end{aligned}

$i \in {\mathcal{S}_k}$ 时， ${\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i} = 0$ ；当 $i \in \mathcal{M}\backslash {\mathcal{S}_k}$ 时， ${\lambda _i} = 0$ ，从而 $\displaystyle \mathop \sum \limits_{i \in \mathcal{M}} {\lambda _i}({\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}_k} - {{\boldsymbol{b}}_i}) = 0$ ，即 $\nabla \tilde \phi ({{\boldsymbol{x}}_k},\mu ){{\boldsymbol{d}}_k} = - {\boldsymbol{d}}_k^{\text{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k}$ 。又因为 ${{\boldsymbol{H}}_k}$ 是对称正定矩阵，所以对任何非负向量 ${{\boldsymbol{d}}_k}$ 都有 ${\boldsymbol{d}}_k^{\text{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k} > 0$ ，故 $\nabla \tilde \phi ({{\boldsymbol{x}}_k},\mu ){{\boldsymbol{d}}_k} < 0$

 $\lambda ({\boldsymbol{x}}) = \left( {{\lambda _i}({\boldsymbol{x}}),i \in \mathcal{M}} \right) \text{，} {\lambda _i}({\boldsymbol{x}}) = \left\{ \begin{gathered} {{\tilde \lambda }_i}({\boldsymbol{x}}),\;i \in \mathcal{S}({\boldsymbol{x}}) \\ 0,\;\;\quad \;i \in \mathcal{M}\backslash {\mathcal{S}}({\boldsymbol{x}}) \\ \end{gathered} \right.$

 $\left\{ \begin{gathered} \nabla \tilde \phi ({\boldsymbol{x}},\mu ) = \mathop \sum \limits_{i \in {\mathcal{M}_I}} {\lambda _i}{{\boldsymbol{a}}_i} + \mathop \sum \limits_{i \in {\mathcal{M}_E}} {\lambda _i}{{\boldsymbol{a}}_i} \\ {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_E} \\ {\boldsymbol{a}}_i^{\text{T}}{\boldsymbol{x}} \geqslant {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_I} \\ {\lambda _i} \geqslant 0,\;i \in {\mathcal{M}_I};{\lambda _i} = 0,\;i \in \mathcal{M}\backslash \mathcal{S}(x) \\ \end{gathered} \right.$

 \begin{aligned} 0 = &\mathop {\lim }\limits_{k \in K} \;(\tilde \phi ({{\boldsymbol{x}}_{k + 1}},\mu ) - \tilde \phi ({{\boldsymbol{x}}_k},\mu )) \leqslant \mathop {\lim }\limits_{k \in K} \,\,\beta \,\nabla \tilde \phi {({{\boldsymbol{x}}_k},\mu )^{\text{T}}}{{\boldsymbol{d}}_k} \leqslant \\& \mathop {\lim }\limits_{k \in K} \,\,\beta \,( - {\boldsymbol{d}}_k^{\text{T}}{{\boldsymbol{H}}_k}{{\boldsymbol{d}}_k}) \leqslant 0 \end{aligned}

 $\left\{ \begin{gathered} \nabla \tilde \phi ({{\boldsymbol{x}}^ * },\mu ) = \mathop \sum \limits_{i \in {\mathcal{M}_I}} \lambda _i^ * {{\boldsymbol{a}}_i} + \mathop \sum \limits_{i \in {\mathcal{M}_E}} \lambda _i^ * {{\boldsymbol{a}}_i} \\ {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}^ * } = {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_E} \\ {\boldsymbol{a}}_i^{\text{T}}{{\boldsymbol{x}}^ * } \geqslant {{\boldsymbol{b}}_i},\;i \in {\mathcal{M}_I} \\ \lambda _i^ * \geqslant 0,\;i \in {\mathcal{M}_I};\lambda _i^ * = 0,\;i \in \mathcal{M}\backslash \mathcal{S} \\ \end{gathered} \right.$

5 数值计算

 \begin{aligned} \mathop {\min }\limits_{\boldsymbol{x}}& \;\;\phi (x) = \left\| {{\boldsymbol{A}}x - {\boldsymbol{b}}} \right\|_2^2 \\& {\text{s}}{\text{.t}}{\text{.}}\quad 0 \leqslant {\boldsymbol{x}} \leqslant 255 \\ \end{aligned}

 \begin{aligned} \mathop {\min }\limits_x & \;\;\phi ({\boldsymbol{x}}) = \left\| {{\boldsymbol{A}}{\boldsymbol{x}} - {\boldsymbol{b}}} \right\|_2^2 + \left\| {\boldsymbol{x}} \right\|_q^q \\ & {\text{s}}{\text{.t}}{\text{.}}\quad 0 \leqslant {\boldsymbol{x}} \leqslant 255 \\ \end{aligned}

 图 1 迭代次数比较 Fig. 1 Comparison of iteration times

 \begin{aligned} \mathop {\min }\limits_x &\;\;\phi ({\boldsymbol{x}}) = f({\boldsymbol{x}}) \\& {\text{s}}{\text{.t}}{\text{.}}\;\;\;{\boldsymbol{x}} \in \varOmega \\ \end{aligned}

 \begin{aligned} \mathop {\min }\limits_x & \;\;\phi ({\boldsymbol{x}}) = f({\boldsymbol{x}}) + \left\| {\boldsymbol{x}} \right\|_q^q \\& {\text{s}}{\text{.t}}{\text{.}}\;\;\;{\boldsymbol{x}} \in \varOmega \\ \end{aligned}

 $\varOmega = \left\{ \begin{gathered} - 2{x_1} - {x_2} + 3 \geqslant 0 \\ {x_1} - {x_2} + 1 \geqslant 0 \\ - {x_1} - 2{x_2} + 2 \geqslant 0 \\ {x_1},{x_2} \geqslant 0 \\ \end{gathered} \right.$

 图 2 迭代次数比较 Fig. 2 Comparison of iteration times

 $\varOmega = \left\{ \begin{gathered} - 3{x_1} - 2{x_2} + 6 \geqslant 0 \\ {x_1},{x_2} \geqslant 0 \\ \end{gathered} \right.$

 图 3 迭代次数比较 Fig. 3 Comparison of iteration times

6 结　论

 [1] ZHANG C, CHEN X J. A smoothing active set method for linearly constrained non-lipschitz nonconvex optimization[J]. SIAM Journal on Optimization, 2020, 13(1): 1-30. [2] COMBETTES P L, PESQUET J C. Proximal splitting methods in signal processing[M]//BAUSCHKE H H, BURACHIK R S, COMBETTES P L, et al. Fixed-point Algorithms for Inverse Problems in Science and Engineering. New York: Springer, 2011. [3] LIU Y F, DAI Y H, LUO Z Q. Joint power and admission control via linear programming deflation[J]. IEEE Transactions on Signal Processing, 2013, 61(6): 1327-1338. DOI:10.1109/TSP.2012.2236319 [4] LIU Y F, MA S Q, DAI Y H, et al. A smoothing SQP framework for a class of composite Lq minimization over polyhedron [J]. Mathematical Programming, 2016, 158(1/2): 467-500. [5] NESTEROV Y. Gradient methods for minimizing composite functions[J]. Mathematical Programming, 2013, 140(1): 125-161. DOI:10.1007/s10107-012-0629-5 [6] BIAN W, CHEN X J. Worst-case complexity of smoothing quadratic regularization methods for non-lipschitzian optimization[J]. SIAM Journal on Optimization, 2013, 23(3): 1718-1741. DOI:10.1137/120864908 [7] WANG W N, WU C L, TAI X C. A globally convergent algorithm for a constrained non-lipschitz image restoration model[J]. Journal of Scientific Computing, 2020, 83(1): 14. DOI:10.1007/s10915-020-01190-4 [8] HUANG Y K, LIU H W. A Barzilai-borwein type method for minimizing composite functions[J]. Numerical Algorithms, 2015, 69(4): 819-838. DOI:10.1007/s11075-014-9927-8 [9] MANJU V N, FRED A L. Sparse decomposition technique for segmentation and compression of compound images[J]. Journal of Intelligent Systems, 2019, 29(1): 515-528. [10] HU J H, JIAN H, FENG Q. A group adaptive elastic-net approach for variable selection in high-dimensional linear regression[J]. Science China Mathematics, 2018, 61(1): 173-188. DOI:10.1007/s11425-016-0071-x [11] SARABI M E. Primal superlinear convergence of SQP methods in piecewise linear-quadratic composite optimization[J]. Set-Valued and Variational Analysis, 2022, 30(1): 1-37. DOI:10.1007/s11228-021-00580-6 [12] BECH A, TEBOULLE M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal of Imaging Sciences, 2009, 2(1): 183-202. DOI:10.1137/080716542 [13] 李启朋. 非光滑凸优化问题的快速迭代收缩阈值算法研究[D]. 西安: 西安电子科技大学, 2018. [14] KANZOW C, LECHNER T. Globalized inexact proximal newton-type methods for nonconvex composite functions[J]. Computational Optimization and Applications, 2021, 78(2): 377-410. DOI:10.1007/s10589-020-00243-6 [15] CRUZ J Y B. On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions[J]. Set-Valued and Variational Analysis, 2017, 25(2): 245-263. DOI:10.1007/s11228-016-0376-5 [16] PATRASCU A, IROFTI P. Stochastic proximal splitting algorithm for composite minimization[J]. Optimization Letters, 2021, 15(6): 2255-2273. DOI:10.1007/s11590-021-01702-7 [17] ZHANG X Y, BARRIO R, MARTÍNEZ M A, et al. Bregman proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems[J]. IEEE Access, 2019, 7: 126515-126529. DOI:10.1109/ACCESS.2019.2937005 [18] NECOARA I. General convergence analysis of stochastic first-order methods for composite optimization[J]. Journal of Optimization Theory and applications, 2021, 189(1): 66-95. DOI:10.1007/s10957-021-01821-2 [19] 张涛. 一种针对盒子约束优化问题带有新积极集策略的信赖域算法[D]. 北京: 北京交通大学, 2016. [20] HAGER W W W, ZHANG H C. An active set algorithm for nonlinear optimization with polyhedral constraints[J]. Science China Mathematics, 2016, 59(8): 89-106. [21] FLETCHER R . Practical methods of optimization[J]. SIAM Review, 1984, 26(1):143–144. [22] EVTUŠENKO J G. Numerical methods for nonlinear programming[J]. Doklady Akademii Nauk SSSR, 1975, 221(5): 1016-1019. [23] WEI B, CHEN X J, YE Y Y. Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization[J]. Mathematical Programming, 2014, 149(1/2): 301-327. [24] NESTEROV Y. Smooth minimization of non-smooth functions[J]. Mathematical Programming, 2005, 103(1): 127-152. DOI:10.1007/s10107-004-0552-5 [25] 王传芳. 解非光滑优化问题的光滑技术及理论[D]. 南京: 南京航空航天大学, 2003. [26] 马昌凤. 最优化方法及其Matlab程序设计[M]. 北京: 科学出版社, 2010.