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
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
examples/unconstrained/nonconvex_qp
This example solves the nonconvex quadratic programming problem
where \(\Delta^n\) is the unit simplex given by
examples/unconstrained/nonconvex_qsdp.m
This example solves the nonconvex quadratic semidefinite programming problem
where \(\mathbb{S}^{n}_{+}\) is the collection of positive semidefinite matrices and \(P^n\) is the unit spectrahedron given by
examples/unconstrained/nonconvex_svm.m
This example solves the nonconvex support vector machine problem
9.2. Nonconvex-Concave Min-Max Problems¶
This subsection considers nonconvex-concave min-max composite optimization problems of the form
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
examples/minmax/nonconvex_minmax_qp.m
This example solves the nonconvex minmax quadratic programming problem
where \(\Delta^n\) is the unit simplex given by
examples/minmax/nonconvex_power_control.m
This example solves the nonconvex power control problem
where \(f_{k,n}\), \(B_x\), and \(B_y\) are given by
examples/minmax/nonconvex_robust_regression.m
This example solves the robust regression problem
where \(\phi_\alpha\) and \(\ell_j\) are given by
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
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
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
where \(\Delta^n\) is the unit simplex given by
examples/constrained/nonconvex_lin_constr_qsdp.m
This example solves the linearly-constrained nonconvex quadratic semidefinite programming problem
where \(\mathbb{S}^{n}_{+}\) is the collection of positive semidefinite matrices and \(P^n\) is the unit spectrahedron given by
examples/constrained/nonconvex_sparse_pca.m
This example solves the nonconvex sparse principal component analysis problem
where \({\cal F}^k\) is the \(k\)-Fantope given by
examples/constrained.nonconvex_bounded_mc.m
This example solves the nonconvex bounded matrix completion problem
where \({\cal R}_\mu\) is a nonconvex regularization function and \(B_{[l,u]}\) is the box given by