# 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

 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.

 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.

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

 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 . 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\}.$