Refine
Document Type
- Article (9)
Language
- English (9)
Has Fulltext
- yes (9)
Keywords
- Software (5)
- Theoretical Computer Science (5)
QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
(2018)
In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) https://doi.org/10.5281/zenodo.1206980.
Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
(2017)
We provide a sparse version of the bounded degree SOS hierarchy BSOS (Lasserre et al. in EURO J Comp Optim:87–117, 2017) for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem.Moreover, for the class of SOS-convex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version.
Sparse covariance selection problems can be formulated as logdeterminant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.
In this paper, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL+, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL+ is a much enhanced version of SDPNAL introduced by Zhao et al. (SIAM J Optim 20:1737–1765, 2010) for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton- CG augmented Lagrangian method coupled with a convergent 3-block alternating direction method of multipliers introduced recently by Sun et al. (SIAM J Optim, to appear). Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Wen et al. (Math Program Comput 2:203– 230, 2010) and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro et al. (Math Program Comput 1–48, 2014). In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of 10?6 efficiently, while SDPAD and 2EBD-HPE successfully solve 30 and 16 problems, respectively. In addition, SDPNAL+ appears to be the only viable method currently available to solve large scale SDPs arising from rank-1 tensor approximation problems constructed by Nie and Wang (SIAM J Matrix Anal Appl 35:1155–1179, 2014). The largest rank-1 tensor approximation problem we solved (in about 14.5 h) is nonsym(21,4), in which its resulting SDP problem has matrix dimension n = 9261 and the number of equality constraints m = 12,326,390.
A partial proximal point algorithm for nuclear norm regularized matrix least squares problems
(2014)
We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semismoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.
In this paper, we develop a self-adaptive ADMM that updates the penalty parame-
ter adaptively. When one part of the objective function is strongly convex i.e., the
problem is semi-strongly convex, our algorithm can update the penalty parameter
adaptively with guaranteed convergence. We establish various types of convergence
results including accelerated convergence rate of O(1/k2), linear convergence and
convergence of iteration points. This enhances various previous results because we
allow the penalty parameter to change adaptively. We also develop a partial proximal
point method with the subproblems being solved by our adaptive ADMM. This enables
us to solve problems without semi-strongly convex property. Numerical experiments
are conducted to demonstrate the high efficiency and robustness of our method.
Optimization over an embedded submanifold defined by equality constraints c(x) = 0
has attracted much interest over the past few decades due to its wide applications in var-
ious areas, including computer vision, signal processing, numerical linear algebra, and
deep learning. For solving such problems, many related optimization packages have
been developed based on Riemannian optimization approaches, which rely on some
basic geometrical materials of Riemannian manifolds, including Riemannian gradi-
ents, retractions, vector transports, etc. These geometrical materials can be challenging
to determine in general. In fact, existing packages only accommodate a few well-known
manifolds whose geometrical materials are more easily accessible. For other mani-
folds that are not contained in these packages, the users have to develop the geometric
materials by themselves. In addition, it is not always tractable to adapt the advanced fea-
tures from various state-of-the-art unconstrained optimization solvers to Riemannian
optimization approaches. Here we introduce a user-friendly Python package, CDOpt
(available at https://cdopt.github.io/ under BSD 3-clause license), for solving a class of
Riemannian optimization problems. CDOpt is designed to complement existing Riemannian optimization packages by transforming Riemannian optimization problems
into their unconstrained counterparts through the constraint dissolving approach. We
prove that the when the penalty parameter in the constraint dissolving approach is suffi-
ciently large, Riemannian optimization problems and their unconstrained counterparts
are equivalent. Therefore, solving Riemannian optimization problems through CDOpt
can directly benefit from various existing solvers and the rich expertise gained over
the past few decades for unconstrained optimization. Moreover, all the computations
in CDOpt related to any manifold in question are conducted through its constraints
expression, hence users can easily define new manifolds in CDOpt without any back-
ground on differential geometry. Furthermore, CDOpt extends the neural layers from
PyTorch and Flax, thus allowing users to train manifold constrained neural networks
directly by the solvers for unconstrained optimization. Extensive numerical experi-
ments demonstrate that CDOpt is highly efficient and robust in solving various classes
of Riemannian optimization problems.
In this paper, we propose an adaptive sieving (AS) strategy for solving general sparse machine learning models by effectively exploring the intrinsic sparsity of the solutions, wherein only a sequence of reduced problems with much smaller sizes need to be solved. We further apply the proposed AS strategy to generate solution paths for large-scale sparse optimization problems efficiently. We establish the theoretical guarantees for the proposed AS strategy including its finite termination property. Extensive numerical experiments are presented in this paper to demonstrate the effectiveness and flexibility of the AS strategy to solve large-scale machine learning models.