Geometric characterizations for strong minima with applications to nuclear norm minimization problems

Strong minima is an important property at a local minimizer of an optimization problem such that the difference between the cost value and the optimal value is bigger than a proportional of the norm square of the difference between the corresponding feasible solution and the minimizer. It is an error bound condition that has various applications to sensitivity analysis, robustness, and complexity of algorithms [4, 5, 7, 8, 18, 22, 23, 24, 29, 34, 42, 44]. Finding necessary and sufficient second order conditions for strong minima is a classical research area. For nonlinear programming, the first results in this direction were probably established in [22] under some restrictive conditions. Complete second order characterizations for nonlinear programming under mild conditions such as the Mangasarian-Fromovitz constraint qualification were obtained later in [4, 34]. For constrained (nonpolyhedral) optimization problems with smooth data, necessary and sufficient second order conditions for strong minima are much more involved. They often contain nontrivial “sigma terms”, which represent curvatures of some nonpolyhedral structures in the problem. Another important feature of these conditions is that they are usually formulated as “minimax” conditions such that Lagrange multipliers are dependent on the choice of vectors in the critical cone; see, e.g., [7, 8]. Although the aforementioned sigma terms are fully calculated for many seminal classes of optimization such as semi-infinite programming, semi-definite programming, and second order cone programming, their calculations are complicated in general. Moreover, checking the (minimax) sufficient second order conditions is quite a hard task numerically.

An important problem that motivates our study in this paper is the nuclear norm minimization problem

$$\min_{X\in\mathbb{R}^{n_{1}\times n_{2}}}\quad\|X\|_{*}\quad\mbox{subject to}\quad\Phi X=M_{0},$$

(1.1)

where $\|X\|_{*}$ is the nuclear norm of an $n_{1}\times n_{2}$ matrix $X$, $\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{m}$ is a linear operator, and $M_{0}$ is a known vector (observation) in $\mathbb{R}^{m}$. This problem is considered the tightest convex relaxation of the celebrated NP-hard affine rank minimization problem with various applications in computer vision, collaborative filtering, and data science; see, e.g., [1, 13, 15, 16, 40]. There are some essential reasons to study strong minima of this problem. First, strong minima of problem (1.1) guarantees the linear convergence of some proximal algorithms for solving problem (1.1) and related problems; see, e.g., [18, 29, 50]. Second, it is also sufficient for solution uniqueness and robustness of problem (1.1) [23, 24]. Solution uniqueness for problem (1.1) is a significant property in recovering the original low-rank solution $X_{0}\in\mathbb{R}^{n_{1}\times n_{2}}$ from observations $M_{0}=\Phi X_{0}$. In [15, 16], Candès and Recht introduced a nondegenerate condition sufficient for solution uniqueness of problem (1.1). It plays an important role in their results about finding a small bound for measurements $m$ such that solving problem (1.1) recovers exactly $X_{0}$ from observations $M_{0}$ over a Gaussian linear operator $\Phi$. Their condition is recently revealed in [24] to be a complete characterization for the so-called sharp minima introduced by Crome [12] and Polyak [39] independently. This special property of problem (1.1) at $X_{0}$ guarantees the robust recovery with a linear rate in the sense that any solutions of the following low-rank optimization problem

$$\frac{1}{2}\|\Phi X-M\|^{2}+\mu\|X\|_{*}$$

(1.2)

converge to $X_{0}$ with a linear rate as $\mu\downarrow 0$ provided that $\|M-M_{0}\|\leq c\mu$ for some constant $c>0$; see [14]. When strong minima occurs in problem (1.1), [24] shows that the convergence rate is Hölderian with order $\frac{1}{2}$. It is also worth noting that solution uniqueness of nuclear norm minimization problem (1.1) can be characterized geometrically via the descent cone [1, 13]. As the descent cone is not necessarily closed, using it to check solution uniqueness numerically is not ideal. Another geometric characterization for solution uniqueness of problem (1.1) is established recently in [28], but the set in their main condition is not closed too. As strong minima is necessary for sharp minima and sufficient for solution uniqueness, it is open to study the impact of strong minima to exact recovery.

Sufficient second order condition for strong minima of problem (1.1) can be obtained from [18, Theorem 12]. The approach in [18] is rewriting problem (1.1) as a composite optimization problem and applying the classical results in [7, 8]. Some second order analysis on spectral functions including the nuclear norm studied in [17, 18, 20, 37, 51] could be helpful in understanding this result, but these second order computations applied on the nuclear norm still look complicated. Most importantly, the sufficient second order condition obtained in [18, Theorem 12] is still in a minimax form, which makes it hard to check. Our main questions throughout the paper are: 1. Is it possible to obtain simple necessary and sufficient conditions for strong minima of problem (1.1)? 2. Can we avoid the minimax form usually presented in these kinds of second order sufficient conditions? and 3. Is there any efficient way to check strong minima of problem (1.1) numerically?

Our contribution. To highlight the new ideas and direct to the bigger picture, we study in Section 3 the following composite optimization problem

$$\min_{x\in\mathbb{X}}\quad f(x)+g(x),$$

(1.3)

where $\mathbb{X}$ is a finite dimensional space, $f:\mathbb{X}\to\mathbb{R}$ is a twice continuously differentiable function, and $g:\mathbb{X}\to\overline{\mathbb{R}}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\mathbb{R}\cup\{+\infty\}$ is a proper lower semi-continuous (nonsmooth) function. It covers problem (1.2) and many modern ones in optimization. One of the most popular ways to characterize strong minima of problem (1.3) is using the second subderivative [8, 42, 43]. As the function $g$ is nonsmooth, second subderivative of $g$ is hard to compute in general. To avoid this computation, we assume additionally that the function $g$ satisfies the classical quadratic growth condition [6, 49]. In the case of convex functions, it is shown in Section 3 that $\bar{x}$ is a strong solution of problem (1.3) if and only if $\bar{v}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}-\nabla f(\bar{x})\in\partial g(\bar{x})$ and the following geometric condition holds

$$\mbox{\rm Ker}\,\nabla^{2}f(\bar{x})\cap T_{(\partial g)^{-1}(\bar{v})}(\bar{x})=\{0\},$$

(1.4)

where $\partial g:\mathbb{X}\rightrightarrows\mathbb{X}^{*}$ is the subdifferential mapping of $g$, $\mbox{\rm Ker}\,\nabla^{2}f(\bar{x})$ is the nullspace of the Hessian matrix $\nabla^{2}f(\bar{x})$, and $T_{(\partial g)^{-1}(\bar{v})}(\bar{x})$ is the Bouligand contingent cone at $\bar{x}$ to $(\partial g)^{-1}(\bar{v})$. The action of the contingent cone to a first order structure in the above condition tells us that (1.4) is actually a second order condition. But it looks simpler for computation than the second subderivative; see, e.g., our Corollary 4.2 for the case of nuclear norm. Our results also work when $g$ is not convex; see Section 3 for more detailed analysis.

Another problem considered in Section 3 is the following convex optimization problem with linear constraints

$$\min_{x\in\mathbb{X}}\quad g(x)\quad\mbox{subject to}\quad\Phi x\in K,$$

(1.5)

where $g:\mathbb{X}\to\overline{\mathbb{R}}$ is a continuous (nonsmooth) convex function, $\Phi:\mathbb{X}\to\mathbb{Y}$ is a linear operator between two finite dimensional spaces, and $K$ is a closed polyhedral set of $\mathbb{Y}$. This problem covers the nuclear norm minimization problem (1.1) and a handful of other significant optimization problems [1, 3, 13]. When $g$ is twice continuously differentiable, characterizations for strong minima of problem (1.5) are simple; see, e.g., [8, Theorem 3.120]. But when $g$ is not differentiable, characterizing strong minima is much more involved. A standard approach is rewriting problem (1.5) as a composite problem, which can be represented by a constrained optimization problem with smooth data [7, 8, 35]. To obtain similar geometric characterization to (1.4) for problem (1.5), we additionally assume the function $g$ satisfies both quadratic growth condition and second order regularity. The latter condition was introduced by Bonnans, Cominetti, and Shapiro in [7] to close the gap between necessary and sufficient second order optimality conditions for constrained and composite optimization problems. But the extra assumption of quadratic growth condition on the function $g$ in this paper allows us to achieve geometric characterizations for strong minima of problem (1.5) in Theorem 3.5. Many vital classes of nonsmooth functions $g$ satisfy both the quadratic growth condition and second order regularity. To list a few, we have classes of piecewise linear-quadratic convex functions [43], spectral functions [18, 37], $\ell_{1}/\ell_{2}$ norms [50], and indicator functions to the set of positive semi-definite matrices [19]. Our results are applicable not only to nuclear norm minimization problem (1.1), but also other different problems in optimization.

As the nuclear norm satisfies both the quadratic growth condition and second order regularity, geometric characterizations for strong minima of low-rank problems (1.1) and (1.2) are foreseen. But our studies on problems (1.1) and (1.2) in Section 4 and 5 are not just straightforward applications. In Section 4, we derive simple calculation of the second order structure in (1.4) for the case of nuclear norm. Furthermore, some quantitative characterizations for strong minima of problem (1.2) are obtained via the so-called Strong Restricted Injectivity and Analysis Strong Source Condition that inherit the same terminologies introduced recently in [24] to characterize strong minima/solution uniqueness of group-sparsity optimization problems. These conditions are weaker than the well-known Restricted Injectivity and Nondegenerate Source Condition used in [15, 16] as sufficient conditions for solution uniqueness of nuclear norm minimization problem (1.1); see also [25] for the case of $\ell_{1}$-norm. Both conditions can be verified numerically. In Section 5, we obtain new characterizations for strong minima of problem (1.1). Our conditions are not in the form of minimax problems. Indeed, Theorem 5.2 shows that $X_{0}$ is a strong solution of problem (1.1) if and only if there exists a dual certificate $\overline{Y}\in\mbox{\rm Im}\,\Phi^{*}\cap\partial\|X_{0}\|_{*}$ such that

$$\mbox{\rm Ker}\,\Phi\cap T_{(\partial\|\cdot\|_{*})^{-1}(\overline{Y})}(X_{0})=\{0\},$$

which has some similarity with (1.4). Necessary and sufficient conditions for strong minima obtained in this section reveal some interesting facts about exact recovery for nuclear minimization problem (1.1). For example, one needs at least $\frac{1}{2}r(r+1)$ measurements for $M_{0}=\Phi X_{0}$ to recover exactly the matrix $X_{0}$ of rank $r$ as a strong solution of problem (1.1). This bound for $m$ is very small, but it is tight in the sense that we can construct infinitely many linear operators $\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{\frac{1}{2}r(r+1)}$ such that solving problem (1.1) recovers exactly $X_{0}$. Another compelling result in Section 5 shows that the low-rank representation problem [27, 33] always has strong minima, when the linear operator $\Phi$ in (1.1) is any $q\times n_{1}$ matrix.

Finally in this paper, we discuss numerical methods to check strong minima and compare the results with sharp minima and solution uniqueness. For example, with 100 nuclear norm minimization problems via standard Gaussian linear operators $\Phi$ and $460$ measurements $M_{0}\in\mathbb{R}^{460}$ observed from the original matrix $X_{0}\in\mathbb{R}^{40\times 40}$ of rank $3$, the case of exact recovery is about 80%, in which about 40% problems have sharp minima and the other 40% problems have strong minima. As the traditional approach for exact recovery in [1, 13, 16] is via sharp minima [24], seeing more unique (strong, non-sharp) solutions in these numerical experiments gives us a more complete picture about exact recovery when number of measurements $m$ is not big enough; see our Section 6 for further numerical experiments.

Throughout this paper, we suppose that $\mathbb{X}$ is an Euclidean space with norm $\|\cdot\|$ and $\mathbb{X}^{*}$ is its dual space endowed with the inner product $\langle v,x\rangle$ for any $v\in\mathbb{X}^{*}$ and $x\in\mathbb{X}$. $\mathbb{B}_{r}(\bar{x})$ is denoted by the closed ball with center $\bar{x}\in\mathbb{X}$ and radius $r>0$. Let $\varphi:\mathbb{X}\to\overline{\mathbb{R}}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\mathbb{R}\cup\{+\infty\}$ be a proper extended real-valued function with nonempty domain $\mbox{\rm dom}\,\varphi\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\{x\in\mathbb{X}|\;\varphi(x)<\infty\}\neq\emptyset$. A point $\bar{x}\in\mbox{\rm dom}\,\varphi$ is called a strong solution (or strong minimizer) of $\varphi$ if there exist $c,\varepsilon>0$ such that

$$\varphi(x)-\varphi(\bar{x})\geq c\|x-\bar{x}\|^{2}\quad\mbox{for all}\quad x\in\mathbb{B}_{\varepsilon}(\bar{x}).$$

(2.1)

In this case, we say that strong minima occurs at $\bar{x}$. The study of strong minima is usually based on second order theory, where the following structures of subderivatives play crucial roles; see, e.g., [5, 8, 35, 42, 43].

Parabolic subderivatives were introduced by Ben-Tal and Zowe in [5] to study strong minima; see also [43, Theorem 13.66]. Second subderivatives dated back to the seminal work of Rockafellar [42] with good calculus [35] for many important classes of functions. It is well known [43, Theorem 13.24] that $\bar{x}$ is a strong solution of $\varphi$ if and only if $0\in\partial\varphi(\bar{x})$ and

$$d^{2}\varphi(\bar{x}|0)(w)>0\quad\mbox{for all}\quad w\neq 0.$$

(2.5)

Here $\partial\varphi(\bar{x})$ stands for the Mordukhovich limiting subdifferential of $\varphi$ at $\bar{x}$ [36]:

$$\partial\varphi(\bar{x})=\left\{v\in\mathbb{X}^{*}|\;\exists(x_{k},v_{k})\stackrel{{\scriptstyle X\times\mathbb{X}^{*}}}{{\longrightarrow}}(\bar{x},v),\,\liminf_{x\to x_{k}}\dfrac{\varphi(x)-\varphi(x_{k})-\langle v_{k},x-x_{k}\rangle}{\|x-x_{k}\|}\geq 0\right\}.$$

(2.6)

When $\varphi$ is a proper l.s.c. convex function, this subdifferential coincides with the subdifferential in the classical convex analysis

$$\partial\varphi(\bar{x})=\left\{v\in\mathbb{X}^{*}|\;\varphi(x)-\varphi(\bar{x})\geq\langle v,x-\bar{x}\rangle,x\in\mathbb{X}\right\}.$$

(2.7)

We denote $\varphi^{*}:\mathbb{X}^{*}\to\overline{\mathbb{R}}$ by the Fenchel conjugate of $\varphi$:

$$\varphi^{*}(v)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\sup\{\langle v,x\rangle-\varphi(x)\rangle|\;x\in\mathbb{X}\}\quad\mbox{for}\quad v\in\mathbb{X}^{*}.$$

(2.8)

Next let us recall here some first and second order tangent structures [8, 43] on a nonempty closed set $K$ of $\mathbb{X}$ that widely used in this paper.

The contingent cone $T_{K}(\bar{x})$ is a closed set. It contains all $w\in\mathbb{X}$ such that there exists a sequence $\{t_{k}\}\downarrow 0$ such that ${\rm dist}\,(\bar{x}+t_{k}w;K)=o(t_{k})$, where ${\rm dist}\,(x;K)$ denotes the distance from $x\in\mathbb{X}$ to $K$:

$${\rm dist}\,(x;K)=\min\{\|x-u\||\;u\in K\}.$$

(2.11)

Similarly, the inner second order tangent set to $K$ at $\bar{y}$ is

$$T^{i,2}_{K}(\bar{x}|w)=\left\{z\in\mathbb{X}|\;{\rm dist}\,(x+tw+\frac{1}{2}t^{2}z;K)=o(t^{2}),t\geq 0\right\}.$$

(2.12)

When $K$ is convex, it is well-known that

$$T_{K}(\bar{x})=\{w\in\mathbb{X}|\;{\rm dist}\,(\bar{x}+tw;K)=o(t),t\geq 0\}.$$

Since the function ${\rm dist}\,(\cdot;K)$ is a convex function, $T_{K}(\bar{x})$ is a convex set. In this case, the inner second order tangent set $T^{i,2}_{K}(\bar{y}|w)$ is also convex due to the same reason and formula (2.12). Moreover, the dual of contingent cone is the normal cone to $K$ at $\bar{x}$:

$$N_{K}(\bar{x})\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}[T_{K}(\bar{x})]^{-}=\{v\in\mathbb{X}^{*}|\;\langle v,x-\bar{x}\rangle\leq 0\quad\mbox{for all}\quad x\in K\}.$$

(2.13)

It is also the subdifferential of the indicator function $\iota_{K}$ to the set $K$, which is defined by $\iota_{K}(x)=0$ if $x\in K$ and $+\infty$ otherwise. The normal cone can be characterized via the support function to $K$

$$\sigma_{K}(v)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\sup\{\langle v,x\rangle|\;x\in K\}\quad\mbox{for all}\quad v\in\mathbb{X}^{*}$$

(2.14)

with $N_{K}(\bar{x})=\{v\in\mathbb{X}^{*}|\;\sigma_{K}(v)\leq\langle v,\bar{x}\rangle\}$.

To characterize strong minima for constrained optimization problems, Bonnans, Cominetti, and Shapiro [7, Definition 3] introduced the following second order regular condition on $K$; see also [8, Definition 3.85].

The class of second order regular sets cover many important sets in optimization such as any polyhedral set and the set of positive semi-definite matrices and the second order ice cream cone; see, e.g., [8]. Piecewise linear quadratic convex functions are second order regular [7]. Recently, it is proved in [18] some special spectral functions are also second order regular.

When the function $\varphi:\mathbb{X}\to\overline{\mathbb{R}}$ is l.s.c. convex and second order regular at $\bar{x}\in\mbox{\rm dom}\,\varphi$, we note from [8, Proposition 3.41]

$$T^{i,2}_{{\rm epi}\,\varphi}((\bar{x},\varphi(\bar{x}))|(w,d\varphi(\bar{x})(w)))=\mbox{\rm epi}\,d^{2}\varphi(\bar{x})(w|\cdot)$$

(2.15)

for any $w\in\mbox{\rm dom}\,d\varphi(\bar{x})$. This is a convex set, which implies that $d^{2}\varphi(\bar{x})(w|\cdot)$ is a convex function. In this case, it is known from [8, Proposition 103] that $\varphi$ is parabolically regular at $\bar{x}$ in a direction $w\in\mathbb{X}$ for $v\in\mathbb{X}^{*}$ in the sense that

$$d^{2}\varphi(\bar{x}|v)(w)=-[d^{2}\varphi(\bar{x})(w|\cdot)]^{*}(v),$$

(2.16)

which is the Fenchel conjugate of the function $d^{2}\varphi(\bar{x})(w|\cdot)$ at $v$ provided that the pair $(w,v)\in\mathbb{X}\times\mathbb{X}^{*}$ satisfies the condition $\langle v,w\rangle=d\varphi(\bar{x})(w)$.

Next let us slightly modify [8, Theorem 3.108 and Theorem 3.109], which give necessary and sufficient conditions for strong solutions of the following composite problem

$$\min_{x\in\mathbb{X}}\quad g(F(x)),$$

(2.17)

where $F:\mathbb{X}\to\mathbb{Y}$ is a twice continuously differentiable mapping and $g:\mathbb{Y}\to\overline{\mathbb{R}}$ is a l.s.c. proper convex function. Suppose that $y_{0}=F(x_{0})\in\mbox{\rm dom}\,g$ with $x_{0}\in\mathbb{X}$. The Robinson’s constraint qualification at $x_{0}$ for this composite problem is known as

$$0\in{\rm int}\,(y_{0}+\nabla F(x_{0})\mathbb{X}-\mbox{\rm dom}\,g);$$

(2.18)

see, e.g., [7, 8]. The feasible point $x_{0}$ is a called a stationary point of problem (2.17) if there exists a Lagrange multiplier $\lambda\in\mathbb{Y}^{*}$ such that

$$\nabla F(\bar{x})^{*}\lambda=0\quad\mbox{and}\quad\lambda\in\partial g(y_{0}).$$

(2.19)

To prove the necessary part, we note again that the function $d^{2}g(y_{0})(\nabla F(x_{0})w|\cdot)$ is convex, then there is no gap between second order necessary and sufficient condition, i.e., condition (2.22) is also a necessary condition for strong solution $x_{0}$; see [7, Theorem 5.2] or [8, Theorem 3.108]. Due to the equivalence of (2.21) and (2.22) above, condition (2.21) is also necesary for the strong minima at $x_{0}$. $\hfill\Box$

As described in (2.21), the existence of Lagrange multiplier is dependent on the choice of each vector in the critical cone. Under the Robinson’s constraint qualification (2.18), (2.21) is a minimax condition in the sense that it is equivalent to

$$\min_{w\in C(x_{0}),\|w\|=1}\max_{\lambda\in\Lambda(x_{0})}\big{[}\langle\lambda,\nabla^{2}F(x_{0})(w,w)\rangle+d^{2}g(y_{0}|\lambda)(\nabla F(x_{0})w)\big{]}>0,$$

(2.23)

where $\Lambda(x_{0})$ is the set of all Lagrange multipliers satisfying (2.19). It is hard to check this condition numerically. On the other hand, its maximin version is more desirable, as it means that there may exist a Lagrange multiplier $\lambda$ such that inequality (2.21) is valid for any $w\in C(x_{0})\setminus\{0\}$. However, it is not clear how to close the gap between the minimax and maximin. For the case of (1.1), we will obtain some kind of maximin condition for strong minima in Theorem 5.2.