9. Examples

This section documents the examples solved by NC-OPT. For brevity, only the optimization model is given. Moreover, to avoid repetition, we will also define

\[\begin{split}\delta_{C}(x) = \begin{cases} 0, & x \in C, \\ \infty, & x\notin C, \end{cases}\end{split}\]

for any closed convex set \(C\) and any point \(x\).

Note

Additional details about these problems can be found in the papers:

[1] Kong, W., Melo, J. G., & Monteiro, R. D. (2019). Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization, 29(4), 2566-2593.

[2] Kong, W., Melo, J. G., & Monteiro, R. D. (2020). An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems. Computational Optimization and Applications, 76(2), 305-346.

[3] Kong, W., & Monteiro, R. D. (2019). An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. arXiv preprint arXiv:1905.13433.

[4] Kong, W., & Monteiro, R. D. (2020). Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems. arXiv preprint arXiv:2007.11772.

9.1. Unconstrained Problems

This subsection considers unconstrained composite optimization problems.

examples/unconstrained/basic_convex_qp.m

This example solves the convex univariate optimization problem

\[\begin{split}\underset{x}{\text{minimize}}\quad & \frac{1}{2}x^{2}-x+\frac{1}{2} \\ \text{subject to}\quad & x\in\mathbb{R}.\end{split}\]

examples/unconstrained/nonconvex_qp

This example solves the nonconvex quadratic programming problem

\[\begin{split}\underset{x}{\text{minimize}}\quad & -\frac{\xi}{2}\|DBx\|^{2}+\frac{\tau}{2}\|Ax-b\|^{2}+\delta_{\Delta^{n}}(x) \\ \text{subject to}\quad & x\in\mathbb{R}^{n},\end{split}\]

where \(\Delta^n\) is the unit simplex given by

\[\Delta^{n}:=\left\{ x\in\mathbb{R}^{n}:\sum_{i=1}^{n}x_{i}=1,0\leq x\leq1\right\}.\]

examples/unconstrained/nonconvex_qsdp.m

This example solves the nonconvex quadratic semidefinite programming problem

\[\begin{split}\underset{X}{\text{minimize}}\quad & -\frac{\xi}{2}\|DB(X)\|_{F}^{2}+\frac{\tau}{2}\|A(X)-b\|^{2}_{F}+\delta_{P^{n}}(X) \\ \text{subject to}\quad & X\in\mathbb{S}^{n}_{+},\end{split}\]

where \(\mathbb{S}^{n}_{+}\) is the collection of positive semidefinite matrices and \(P^n\) is the unit spectrahedron given by

\[P^{n}:=\left\{ X\in\mathbb{S}^{n}_{+}: {\rm tr}\, X = 1\right\}.\]

examples/unconstrained/nonconvex_svm.m

This example solves the nonconvex support vector machine problem

\[\begin{split}\underset{x}{\text{minimize}}\quad & \frac{1}{n}\sum_{i=1}^{n}\left[1-\tanh\left(v_{i}\langle u_{i},x\rangle\right)\right]+\frac{1}{2n}\|x\|^{2} \\ \text{subject to}\quad & x\in\mathbb{R}^{n}.\end{split}\]

9.2. Nonconvex-Concave Min-Max Problems

This subsection considers nonconvex-concave min-max composite optimization problems of the form

\[\begin{split}\underset{x}{\text{minimize}} \quad & \left[\underset{y}{\text{max}} \,\, \Phi(x,y) + h(x) \right] \\ \text{subject to}\quad & x\in\mathbb{R}^{n}, \quad y \in \mathbb{R}^{m}\end{split}\]

under a saddle-point termination criterion based on the one given in [3]. More specifically, given a tolerance pair \((\rho_x, \rho_y) \in \mathbb{R}_{++}^2\), the goal is to find a quadruple \((x,y,v,w)\) satisfying the conditions

\[\begin{split}\left(\begin{array}{c} v\\ w \end{array}\right)\in\left(\begin{array}{c} \nabla_{x}\Phi(x,y)\\ 0 \end{array}\right)+\left(\begin{array}{c} \partial h(x)\\ \partial\left[-\Phi(x,\cdot)\right](y) \end{array}\right),\quad\|v\|\leq\rho_{x},\quad\|w\|\leq\rho_{y}.\end{split}\]

examples/minmax/nonconvex_minmax_qp.m

This example solves the nonconvex minmax quadratic programming problem

\[\begin{split}\underset{x}{\text{minimize}} \quad & \left[ \underset{i\in\{1,...,k\}}{\text{max}} \,\, -\frac{ \xi_i}{2}\|D_i B_i x\|^{2}+\frac{\tau_i}{2}\|A_i x-b\|^{2} +\delta_{\Delta^{n}}(x) \right] \\ \text{subject to}\quad & x\in\mathbb{R}^{n},\end{split}\]

where \(\Delta^n\) is the unit simplex given by

\[\Delta^{n}:=\left\{ x\in\mathbb{R}^{n}:\sum_{i=1}^{n}x_{i}=1,0\leq x\leq1\right\}.\]

examples/minmax/nonconvex_power_control.m

This example solves the nonconvex power control problem

\[\begin{split}\underset{x}{\text{minimize}} \quad & \left[\max_{y} \,\, \sum_{k=1}^{K}\sum_{n=1}^{N} f_{k,n}(X,y) + \delta_{B_x}(x) + \delta_{B_y}(y) \right] \\ \text{subject to}\quad & x\in\mathbb{R}^{K\times N}, \quad y\in\mathbb{R}^{N},\end{split}\]

where \(f_{k,n}\), \(B_x\), and \(B_y\) are given by

\[\begin{split}f_{k,n}(X,y) & := -\log\left(1+\frac{{\cal A}_{k,k,n}X_{k,n}}{\sigma^{2}+B_{k,n}y_{n}+\sum_{j=1,j\neq k}^{K}{\cal A}_{j,k,n}X_{j,n}}\right), \\ B_x & := \left\{X\in \mathbb{R}^{K\times N} : 0 \leq X \leq R \right\}, \\ B_y & := \left\{y\in \mathbb{R}^{N} : 0 \leq y \leq \frac{N}{2} \right\}.\end{split}\]

examples/minmax/nonconvex_robust_regression.m

This example solves the robust regression problem

\[\begin{split}\underset{x}{\text{minimize}} \quad & \left[ \underset{i\in\{1,...,n\}}{\text{max}} \,\, \phi_\alpha \circ \ell_i(x) \right] \\ \text{subject to}\quad & x\in\mathbb{R}^{k},\end{split}\]

where \(\phi_\alpha\) and \(\ell_j\) are given by

\[\phi_\alpha(t) := \alpha \log \left(1 + \frac{t}{\alpha} \right), \quad \ell_j := \log \left(1 + e^{-b_j \langle a_j, x \rangle}\right).\]

9.3. Spectral Problems

This subsection considers spectral optimization problems where \(f_s = f_{1,s} + f_{2,s}^{\cal V} \circ \sigma\) and \(f_n = f_{n}^{\cal V} \circ \sigma\) for absolutely symmetric functions \(f_{2,s}^{\cal V}\) and \(f_{n}^{\cal V}\).

examples/spectral/nonconvex_spectral_mc.m

This example solves the spectral matrix completion problem

\[\begin{split}\underset{X}{\text{minimize}}\quad & \frac{1}{2}\|{\rm Proj}_{\Omega}(X-A)\|^{2}_{F}+{\cal R}_{\mu}\circ\sigma(X) + \delta_{B_R}(X) \\ \text{subject to}\quad & X \in \mathbb{R}^{p\times q},\end{split}\]

where \({\cal R}_{\mu}\) is an absolutely symmetric regularization function, \(\sigma(\cdot)\) is the function that maps a matrix to its vector of singular values, and \(B_R\) is the Euclidean ball of radius \(R\), i.e., \(B_R := \{X \in \mathbb{R}^{p\times q} : \|X\|_F \leq R\}\).

examples/spectral/nonconvex_spectral_bmc.m

This example solves the spectral blockwise matrix completion problem

\[\begin{split}\underset{X}{\text{minimize}}\quad & \frac{1}{2}\|{\rm Proj}_{\Omega}(X-A)\|^{2}_{F}+{\cal R}_{\mu}\circ\sigma(X_i) + \delta_{B_R}(X) \\ \text{subject to}\quad & X \in \mathbb{R}^{p\times q},\end{split}\]

where \(\{X_i\}_{i=1}^k\) are block components of the matrix \(X\), \({\cal R}_{\mu}\) is an absolutely symmetric regularization function, \(\sigma(\cdot)\) is the function that maps a matrix to its vector of singular values, and \(B_R\) is the Euclidean ball of radius \(R\), i.e., \(B_R := \{X \in \mathbb{R}^{p\times q} : \|X\|_F \leq R\}\).

9.4. Linearly-Set Constrained Problems

This subsection considers linearly-set constrained composite optimization problems where \(g(x)=Ax\) for a linear operator \(A\) and \(S\) is a closed convex set.

examples/constrained/lin_constr_nonconvex_qp.m

This example solves the linearly-constrained nonconvex quadratic programming problem

\[\begin{split}\underset{x}{\text{minimize}}\quad & -\frac{ \xi}{2}\|DBx\|^{2}+\frac{\tau}{2}\|Ax-b\|^{2}+\delta_{\Delta^{n}}(x) \\ \text{subject to}\quad & C x = d,\quad x\in\mathbb{R}^{n},\end{split}\]

where \(\Delta^n\) is the unit simplex given by

\[\Delta^{n}:=\left\{ x\in\mathbb{R}^{n}:\sum_{i=1}^{n}x_{i}=1,0\leq x\leq1\right\}.\]

examples/constrained/nonconvex_lin_constr_qsdp.m

This example solves the linearly-constrained nonconvex quadratic semidefinite programming problem

\[\begin{split}\underset{X}{\text{minimize}}\quad & -\frac{\xi}{2}\|DB(X)\|_{F}^{2}+\frac{\tau}{2}\|A(X)-b\|^{2}_{F}+\delta_{P^{n}}(X) \\ \text{subject to}\quad & C(X)=d, \quad X\in\mathbb{S}^{n}_{+},\end{split}\]

where \(\mathbb{S}^{n}_{+}\) is the collection of positive semidefinite matrices and \(P^n\) is the unit spectrahedron given by

\[P^{n}:=\left\{ X\in\mathbb{S}^{n}_{+}: {\rm tr}\, X = 1\right\}.\]

examples/constrained/nonconvex_sparse_pca.m

This example solves the nonconvex sparse principal component analysis problem

\[\begin{split}\underset{\Pi,\Phi}{\text{minimize}}\quad & \langle\Sigma,\Pi\rangle+\sum_{i,j=1}^{n}q_{\nu}(\Phi_{ij})+\nu\sum_{i,j=1}^{n}|\Phi_{ij}|+\delta_{{\cal F}^{k}}(\Pi) \\ \text{subject to}\quad & \Pi-\Phi=0, \quad(\Pi, \Phi)\in \mathbb{R}^{n\times n}\times\mathbb{R}^{n\times n},\end{split}\]

where \({\cal F}^k\) is the \(k\)-Fantope given by

\[{\cal F}^k:=\left\{ X\in\mathbb{S}^{n}_{+}: 0 \preceq X \preceq I, {\rm tr}\, X = k\right\}.\]

examples/constrained.nonconvex_bounded_mc.m

This example solves the nonconvex bounded matrix completion problem

\[\begin{split}\underset{X}{\text{minimize}}\quad & \frac{1}{2}\|{\rm Proj}_{\Omega}(X-A)\|^{2}_{F}+{\cal R}_{\mu}(X) \\ \text{subject to}\quad & X \in B_{[l,u]},\end{split}\]

where \({\cal R}_\mu\) is a nonconvex regularization function and \(B_{[l,u]}\) is the box given by

\[B_{[l,u]}:=\left\{ X\in\mathbb{R}^{p\times q}:l\leq X_{ij}\leq u,(i,j)\in\{1,...,p\}\times\{1,...,q\}\right\}.\]