A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron

The composite \(L_q~(0<q<1)\) minimization problem over a general polyhedron has received various applications in machine learning, wireless communications, image restoration, signal reconstruction, etc. This paper aims to provide a theoretical study on this problem. First, we derive the Karush–Kuhn–Tucker (KKT) optimality conditions for local minimizers of the problem. Second, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires a (approximate) solution of a convex quadratic program at each iteration. Finally, we analyze the worst-case iteration complexity of the framework for returning an \(\epsilon \)-KKT point; i.e., a feasible point that satisfies a perturbed version of the derived KKT optimality conditions. To the best of our knowledge, the proposed framework is the first one with a worst-case iteration complexity guarantee for solving composite \(L_q\) minimization over a general polyhedron.

1. Here, the differences between two norms (\(\Vert \cdot \Vert _{\infty }\) in (5.40) and \(\Vert \cdot \Vert \) in (5.42)) are neglected.

We would like to thank Prof. Xiaojun Chen and Dr. Wei Bian for many insightful comments, which helped us in improving the results in this paper. We thank Dr. Qingna Li and Dr. Xin Liu for many useful discussions on an early version of this paper. We also thank Prof. Alexander Shapiro, the anonymous Associate Editor and referees for their constructive comments, which significantly improved the presentation of the paper.

Authors and Affiliations

1. LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China

   Ya-Feng Liu & Yu-Hong Dai

2. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong, China

   Shiqian Ma

3. Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN, 55455, USA

   Shuzhong Zhang

Corresponding author

Correspondence to Ya-Feng Liu.

Y.-F. Liu was partially supported by NSFC Grants 11331012 and 11301516. S. Ma was partially supported by the Hong Kong Research Grants Council General Research Fund Early Career Scheme (Project ID: CUHK 439513). Y.-H. Dai was partially supported by the China National Funds for Distinguished Young Scientists Grant 11125107, the Key Project of Chinese National Programs for Fundamental Research and Development Grant 2015CB856000, NSFC Grant 71331001, and the CAS Program for Cross & Cooperative Team of the Science & Technology Innovation. S. Zhang was partially supported by NSF Grant CMMI-1462408.

Appendix 1: Three motivating applications

Support Vector Machine [11, 28]. The support vector machine (SVM) is a state-of-the-art classification method introduced by Boser, Guyon, and Vapnik in 1992 in [11]. Given a database \(\left\{ s_m\in \mathbb {R}^{N-1},\,y_m\in \mathbb {R}\right\} _{m=1}^M,\) where \(s_m\) is called pattern or example and \(y_m\) is the label associated with \(s_m.\) For convenience, we assume the labels are \(+1\) for positive examples and \(-1\) for negative examples. If the data are linearly separable, the task of SVM is to find a linear discriminant function of the form \(\ell (s)=\hat{s}^Tx\) with \(\hat{s}=[s^T,1]^T\in \mathbb {R}^{N}\) such that all data are correctly classified and at the same time the margin of the hyperplane \(\ell \) that separates the two classes of examples is maximized. Mathematically, the above problem can be formulated as

In practice, data are often not linearly separable. In this case, problem (6.1) is not feasible, and the following problem can be solved instead:

where the constant \(\rho \ge 0\) balances the relative importance of minimizing the classification errors and maximizing the margin. Problem (6.2) with \(q=1\) is called the soft-margin SVM in [28]. It is clear that problem (6.2) is a special instance of (1.1) with

Here, e is the all-one vector of dimension M.

Joint Power and Admission Control [46, 49]. Consider a wireless network consisting of K interfering links (a link corresponds to a transmitter/receiver pair) with channel gains \(g_{kj}\ge 0\) (from the transmitter of link j to the receiver of link k), noise power \(\eta _k>0,\) signal-to-interference-plus-noise-ratio (SINR) target \(\gamma _k>0,\) and power budget \(\bar{p}_k>0\) for \(k, j=1,2,\ldots ,K.\) Denoting the transmission power of transmitter k by \(x_k\), the SINR at the kth receiver can be expressed as

Due to the existence of mutual interferences among different links [which correspond to the term \(\sum _{j\ne k}g_{kj}x_j\) in (6.3)], the linear system

may not be feasible. The joint power and admission control problem aims at supporting a maximum number of links at their specified SINR targets while using a minimum total transmission power. Assuming without loss of generality that \(g_{kk}=\gamma _k=\bar{p}_k=1\) for all \(k=1,2,\dots ,K,\) the joint power and admission control problem can be formulated as follows (see [46])

where \(\rho >0\) is a parameter, \(b=[\eta _1,\eta _2,\ldots ,\eta _K]^T,\) and \(A=[a_{kj}]\in \mathbb {R}^{K\times K}\) with

By utilizing the special structure of A,  i.e., all of its diagonal entries are positive and off-diagonal entries are nonpositive, it is shown in [47, Theorem 1] that the solution of problem (6.4) can maximize the number of supported links using a minimum total transmission power as long as q is chosen to be sufficiently small (but not necessarily to be zero). Clearly, (6.4) is a special case of (1.1) with

Linear Decoding Problem [13]. Given the coding matrix \(C\in \mathbb {R}^{K_1\times K_2}\) and corrupted measurement \(c=Cx+e_u\in \mathbb {R}^{K_1},\) where \(e_u\) is an unknown vector of errors, the linear decoding problem is to recover x from c. It is shown in [13] that, if C satisfies the restricted isometry property, x can be exactly recovered by solving the convex minimization problem

provided that \(e_u\) is sparse. By [33, Theorem 4.10], \(L_q\) (\(q\in (0,1)\)) minimization

has a better capability of recovering x than \(L_1\) minimization. By using the equation \(|a|=\max \left\{ a,0\right\} +\max \left\{ -a,0\right\} ,\) it is simple to see problem (6.5) is a special case of (1.1) with

Appendix 2: Proof of Lemma 3.2

Let \(\bar{x}\) be any local minimizer of problem (3.2) with \(\mathcal{I}_{\bar{x}},\,\mathcal{J}_{\bar{x}},\) and \(\mathcal{K}_{\bar{x}}\) given in (3.1). For convenience, we denote \(\mathcal{I}_{\bar{x}},\,\mathcal{J}_{\bar{x}},\,\mathcal{K}_{\bar{x}}\) as \(\mathcal{I},\,\mathcal{J},\,\mathcal{K}\) in this proof. We prove that \(\bar{x}\) is a local minimizer of problem (1.1) by dividing the proof into two parts. The first one is the easy case where \(\mathcal{K}=\emptyset \) and the second one deals with the complicated case where \(\mathcal{K}\ne \emptyset .\)

Part 1: \(\mathcal{K}=\emptyset .\) In this case, \(\bar{x}\) is a local minimizer of problem

By the definition, \(\bar{x}\) is a local minimizer of problem (1.1).

Part 2: \(\mathcal{K}\ne \emptyset .\) Consider the feasible direction cone \(\mathcal {D}_{\bar{x}}\) of problem (1.1) at point \(\bar{x},\) i.e.,

For simplicity, we use \(\mathcal {D}\) to denote \(\mathcal {D}_{\bar{x}}\) in the subsequent proof. For any subset \(\mathcal{K}_{p}\) of \(\mathcal{K}\) indexed by \(p=1,2,\ldots ,P:=2^{|\mathcal{K}|},\) let \(\mathcal{K}_{p}^{c}=\mathcal{K}\setminus \mathcal{K}_{p},\) and define

By the Minkowski–Weyl Theorem [5, Proposition 3.2.1], there exist \(d_p^1, d_p^2, \ldots , d_p^{g_p} \in \mathcal{D}_p\), such that

and thus

Without loss of generality, assume \(\Vert d_p^{j}\Vert =1\) for all \(j=1,2,\ldots ,g_p,~p=1,2,\ldots ,P.\) For any \(d\in \bigcup _{p=1}^P\left\{ d_p^{1},d_p^{2},\ldots ,d_p^{g_p}\right\} \subseteq \mathcal{D}\), define

Next, we consider the two cases where \(\overleftarrow{\mathcal{K}}^{d}\) is nonempty and empty, respectively. The former happens when d is not a feasible direction of problem (3.2) at point \(\bar{x};\) while the latter happens when d is a feasible direction of problem (3.2) at point \(\bar{x}.\)

Case 1: \(\overleftarrow{\mathcal{K}}^{d}\ne \emptyset .\) Since \(d\in \mathcal{D},\) there must exist \(\epsilon _0^d\) so that \(\bar{x}+\epsilon d\in \mathcal{X}\) holds for all \(0\le \epsilon \le \epsilon _0^d.\) Define

Choose \(\epsilon _1^d\) small enough such that

and

Therefore, for \(0\le \epsilon \le \min \left\{ \epsilon _0^d,\epsilon _1^d\right\} \), we obtain

where (6.10) is due to (3.1), (6.6), and (6.8); (6.11) is due to (6.7); (6.12) is due to the concavity of the function \(z^q\) with respect to \(z>0;\) (6.13) is due to (6.9) and the definition of \(\overrightarrow{\mathcal{J}}^{d}\) in (6.7). Moreover, by (1.3) and the Taylor’s expansion, for any \(0\le \epsilon \le 1\), there exists \(\xi \in (0,1)\) such that

Combining (6.13) with (6.14), for any \(0\le \epsilon \le \min \left\{ \epsilon _0^d,\epsilon _1^d,1\right\} ,\) we obtain

where

Define

and

From the above analysis, we can conclude that, for any \(d\in \bigcup _{p=1}^P\left\{ d_p^{1},d_p^{2},\ldots ,d_p^{g_p}\right\} \) with \(\overleftarrow{\mathcal{K}}^{d}\ne \emptyset ,\) \(F(\bar{x}+\epsilon d)\ge F(\bar{x})\) holds for all \(\epsilon \in [0,\bar{\epsilon }^d].\)

Case 2: \(\overleftarrow{\mathcal{K}}^{d}=\emptyset .\) Recall the definition of \(\overleftarrow{\mathcal{K}}^{d}\) (cf. (6.6)). \(\overleftarrow{\mathcal{K}}^{d}=\emptyset \) implies that d is a feasible direction of problem (3.2) at point \(\bar{x}.\) From the assumption that \(\bar{x}\) is a local minimizer of problem (3.2), we know that there exists an \(\tilde{\epsilon }>0\) such that for all \(d\in \bigcup _{p=1}^P\left\{ d_p^{1},d_p^{2},\ldots ,d_p^{g_p}\right\} \) with \(\overleftarrow{\mathcal{K}}^{d}=\emptyset ,\) there holds \(F(\bar{x}+\epsilon d)\ge F(\bar{x})\) for all \(\epsilon \in [0,\tilde{\epsilon }].\)

We now combine the above two cases: Case 1 and Case 2. Since there are finitely many directions \(\bigcup _{p=1}^P\left\{ d_p^{1},d_p^{2},\ldots ,d_p^{g_p}\right\} ,\) it follows that

and

hold true for all \(\epsilon \in [0, \bar{\epsilon }].\)

Let \({\text{ Conv }}_p(\bar{x},\bar{\epsilon })\) denote the convex hull spanned by points \(\bar{x}\) and \(\bar{x}+\bar{\epsilon }d_p^{j},~j=1,2,\ldots ,g_p.\) Then, for any \(x\in \bigcup _{p=1}^P{\text{ Conv }}_p(\bar{x},\bar{\epsilon }),\) we have \(F(x)\ge F(\bar{x})\) by (6.15) and the fact that f(x) is concave in \({\text{ Conv }}_p(\bar{x},\bar{\epsilon })\). Furthermore, one can always choose a sufficiently small but fixed \(\epsilon >0\) such that \(B(\bar{x},\epsilon )\bigcap \mathcal{X}\subseteq \bigcup _{p=1}^P{\text{ Conv }}_p(\bar{x},\bar{\epsilon }).\) Therefore, \(\bar{x}\) is a local minimizer of problem (1.1). \(\square \)

Appendix 3: Proof of Lemma 4.1

We show the three items of Lemma 4.1 separately.

1. (i)

   of Lemma 4.1: it follows directly from the inequality

   $$\begin{aligned} \theta ^q(t)\le \theta ^q(t,\mu )\le \left( \theta (t)+\frac{\mu }{2}\right) ^q\le \theta ^q(t)+\left( \frac{\mu }{2}\right) ^q,\quad \forall ~t\le \mu . \end{aligned}$$
2. (ii)

   of Lemma 4.1: When \(t\ne 0\) and \(t\ne \mu ,\) \(\theta ^q(t,\mu )\) is twice continuously differentiable with respect to t. Recall \(\theta ^q(t,\mu )\ge \left( \mu /2\right) ^q\) for all t (cf. (4.2)). Then it follows from (4.4) that

   $$\begin{aligned} \left| \left[ \theta ^q(t,\mu )\right] ''\right| \le 4q\mu ^{q-2},\quad \forall ~t\notin \left\{ 0,\mu \right\} . \end{aligned}$$

   This further implies (ii) of Lemma 4.1.

3. (iii)

   of Lemma 4.1: By the mean-value theorem [27, Theorem 2.3.7], we have

   $$\begin{aligned} \theta ^q(t,\mu )= \theta ^q(\hat{t},\mu )+\left[ \theta ^q(\hat{t},\mu )\right] '\left( t-\hat{t}\right) +\frac{\upsilon }{2}\left( t-\hat{t}\right) ^2,\end{aligned}$$

   (6.16)

   where \(\upsilon \in \partial _{t}\left( \left[ \theta ^q(\xi \hat{t}+(1-\xi )t,\mu )\right] '\right) \) and \(\xi \in [0,1].\) We consider the following three cases.

   • Case \(\hat{t}>2\mu :\) Since \(t-\hat{t}\ge {-\hat{t}}/{2},\) it follows for any \(\xi \in [0,1]\) that

     $$\begin{aligned} \xi t+(1-\xi )\hat{t}=\hat{t}+\xi (t-\hat{t})\ge \hat{t}/2>\mu . \end{aligned}$$

     This, together with (4.4) and (4.5), implies that the \(\upsilon \) in (6.16) satisfies

     $$\begin{aligned} \upsilon \le 0= \kappa (\hat{t},\mu ). \end{aligned}$$

     From this and (6.16), we obtain (4.6).

   • Case \(\hat{t}\in [-\mu , 2\mu ]:\) From (ii) of Lemma 4.1, \(|\upsilon |\) is uniformly bounded by \(\kappa (\hat{t},\mu )={{4q}\mu ^{q-2}}.\) Combining this with (6.16) yields (4.6).

   • Case \(\hat{t}<-\mu :\) Since \(t-\hat{t}\le \mu ,\) for any \(\xi \in [0,1],\) it follows

     $$\begin{aligned} \xi t+(1-\xi )\hat{t}=\hat{t}+\xi (t-\hat{t})< 0. \end{aligned}$$

     From this, (4.4), (4.5), and (6.16), we can obtain (4.6).

This completes the proof of Lemma 4.1. \(\square \)

Reprints and permissions