BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Defeng Sun

Defeng Sun appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCMachine LearningComputationNumerical AnalysisApplicationsInformation Theorymath.APmath.ITmath.NAmath.PR

Catalog footprint

What is connected

23works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

23 published item(s)

preprint2026arXiv

The global well-posedness for master equations of mean field games of controls

In this manuscript, we establish the global well-posedness for master equations of mean field games of controls, where the interaction is through the joint law of the state and control. Our results are proved under two different conditions: the Lasry-Lions monotonicity and the displacement $λ$-monotonicity, both considered in their integral forms. We provide a detailed analysis of both the differential and integral versions of these monotonicity conditions for the corresponding nonseparable Hamiltonian and examine their relation. The proof of global well-posedness relies on the propagation of these monotonicity conditions in their integral forms and a priori uniform Lipschitz continuity of the solution with respect to the measure variable.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Beyond ADMM: A Unified Client-variance-reduced Adaptive Federated Learning Framework

As a novel distributed learning paradigm, federated learning (FL) faces serious challenges in dealing with massive clients with heterogeneous data distribution and computation and communication resources. Various client-variance-reduction schemes and client sampling strategies have been respectively introduced to improve the robustness of FL. Among others, primal-dual algorithms such as the alternating direction of method multipliers (ADMM) have been found being resilient to data distribution and outperform most of the primal-only FL algorithms. However, the reason behind remains a mystery still. In this paper, we firstly reveal the fact that the federated ADMM is essentially a client-variance-reduced algorithm. While this explains the inherent robustness of federated ADMM, the vanilla version of it lacks the ability to be adaptive to the degree of client heterogeneity. Besides, the global model at the server under client sampling is biased which slows down the practical convergence. To go beyond ADMM, we propose a novel primal-dual FL algorithm, termed FedVRA, that allows one to adaptively control the variance-reduction level and biasness of the global model. In addition, FedVRA unifies several representative FL algorithms in the sense that they are either special instances of FedVRA or are close to it. Extensions of FedVRA to semi/un-supervised learning are also presented. Experiments based on (semi-)supervised image classification tasks demonstrate superiority of FedVRA over the existing schemes in learning scenarios with massive heterogeneous clients and client sampling.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

QPPAL: A two-phase proximal augmented Lagrangian method for high dimensional convex quadratic programming problems

In this paper, we aim to solve high dimensional convex quadratic programming (QP) problems with a large number of quadratic terms, linear equality and inequality constraints. In order to solve the targeted {\bf QP} problems to a desired accuracy efficiently, we develop a two-phase {\bf P}roximal {\bf A}ugmented {\bf L}agrangian method {(QPPAL)}, with Phase I to generate a reasonably good initial point to warm start Phase II to obtain an accurate solution efficiently. More specifically, in Phase I, based on the recently developed symmetric Gauss-Seidel (sGS) decomposition technique, we design a novel sGS based semi-proximal augmented Lagrangian method for the purpose of finding a solution of low to medium accuracy. Then, in Phase II, a proximal augmented Lagrangian algorithm is proposed to obtain a more accurate solution efficiently. Extensive numerical results evaluating the performance of {QPPAL} against {existing state-of-the-art solvers Gurobi, OSQP and QPALM} are presented to demonstrate the high efficiency and robustness of our proposed algorithm for solving various classes of large-scale convex QP problems. {The MATLAB implementation of the software package QPPAL is available at: \url{https://blog.nus.edu.sg/mattohkc/softwares/qppal/}.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A sparse semismooth Newton based proximal majorization-minimization algorithm for nonconvex square-root-loss regression problems

In this paper, we consider high-dimensional nonconvex square-root-loss regression problems and introduce a proximal majorization-minimization (PMM) algorithm for these problems. Our key idea for making the proposed PMM to be efficient is to develop a sparse semismooth Newton method to solve the corresponding subproblems. By using the Kurdyka-Łojasiewicz property exhibited in the underlining problems, we prove that the PMM algorithm converges to a d-stationary point. We also analyze the oracle property of the initial subproblem used in our algorithm. Extensive numerical experiments are presented to demonstrate the high efficiency of the proposed PMM algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Adaptive Sieving with PPDNA: Generating Solution Paths of Exclusive Lasso Models

The exclusive lasso (also known as elitist lasso) regularization has become popular recently due to its superior performance on structured sparsity. Its complex nature poses difficulties for the computation of high-dimensional machine learning models involving such a regularizer. In this paper, we propose an adaptive sieving (AS) strategy for generating solution paths of machine learning models with the exclusive lasso regularizer, wherein a sequence of reduced problems with much smaller sizes need to be solved. In order to solve these reduced problems, we propose a highly efficient dual Newton method based proximal point algorithm (PPDNA). As important ingredients, we systematically study the proximal mapping of the weighted exclusive lasso regularizer and the corresponding generalized Jacobian. These results also make popular first-order algorithms for solving exclusive lasso models practical. Various numerical experiments for the exclusive lasso models have demonstrated the effectiveness of the AS strategy for generating solution paths and the superior performance of the PPDNA.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming

Powerful interior-point methods (IPM) based commercial solvers, such as Gurobi and Mosek, have been hugely successful in solving large-scale linear programming (LP) problems. The high efficiency of these solvers depends critically on the sparsity of the problem data and advanced matrix factorization techniques. For a large scale LP problem with data matrix $A$ that is dense (possibly structured) or whose corresponding normal matrix $AA^T$ has a dense Cholesky factor (even with re-ordering), these solvers may require excessive computational cost and/or extremely heavy memory usage in each interior-point iteration. Unfortunately, the natural remedy, i.e., the use of iterative methods based IPM solvers, although can avoid the explicit computation of the coefficient matrix and its factorization, is not practically viable due to the inherent extreme ill-conditioning of the large scale normal equation arising in each interior-point iteration. To provide a better alternative choice for solving large scale LPs with dense data or requiring expensive factorization of its normal equation, we propose a semismooth Newton based inexact proximal augmented Lagrangian ({\sc Snipal}) method. Different from classical IPMs, in each iteration of {\sc Snipal}, iterative methods can efficiently be used to solve simpler yet better conditioned semismooth Newton linear systems. Moreover, {\sc Snipal} not only enjoys a fast asymptotic superlinear convergence but is also proven to enjoy a finite termination property. Numerical comparisons with Gurobi have demonstrated encouraging potential of {\sc Snipal} for handling large-scale LP problems where the constraint matrix $A$ has a dense representation or $AA^T$ has a dense factorization even with an appropriate re-ordering.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient algorithms for multivariate shape-constrained convex regression problems

Shape-constrained convex regression problem deals with fitting a convex function to the observed data, where additional constraints are imposed, such as component-wise monotonicity and uniform Lipschitz continuity. This paper provides a comprehensive mechanism for computing the least squares estimator of a multivariate shape-constrained convex regression function in $\mathbb{R}^d$. We prove that the least squares estimator is computable via solving a constrained convex quadratic programming (QP) problem with $(n+1)d$ variables and at least $n(n-1)$ linear inequality constraints, where $n$ is the number of data points. For solving the generally very large-scale convex QP, we design two efficient algorithms, one is the symmetric Gauss-Seidel based alternating direction method of multipliers ({\tt sGS-ADMM}), and the other is the proximal augmented Lagrangian method ({\tt pALM}) with the subproblems solved by the semismooth Newton method ({\tt SSN}). Comprehensive numerical experiments, including those in the pricing of basket options and estimation of production functions in economics, demonstrate that both of our proposed algorithms outperform the state-of-the-art algorithm. The {\tt pALM} is more efficient than the {\tt sGS-ADMM} but the latter has the advantage of being simpler to implement.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Estimation of sparse Gaussian graphical models with hidden clustering structure

Estimation of Gaussian graphical models is important in natural science when modeling the statistical relationships between variables in the form of a graph. The sparsity and clustering structure of the concentration matrix is enforced to reduce model complexity and describe inherent regularities. We propose a model to estimate the sparse Gaussian graphical models with hidden clustering structure, which also allows additional linear constraints to be imposed on the concentration matrix. We design an efficient two-phase algorithm for solving the proposed model. We develop a symmetric Gauss-Seidel based alternating direction method of the multipliers (sGS-ADMM) to generate an initial point to warm-start the second phase algorithm, which is a proximal augmented Lagrangian method (pALM), to get a solution with high accuracy. Numerical experiments on both synthetic data and real data demonstrate the good performance of our model, as well as the efficiency and robustness of our proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Mesh Independence of a Majorized ABCD Method for Sparse PDE-constrained Optimization Problems

A majorized accelerated block coordinate descent (mABCD) method in Hilbert space is analyzed to solve a sparse PDE-constrained optimization problem via its dual. The finite element approximation method is investigated. The attractive $O(1/k^2)$ iteration complexity of {the mABCD} method for the dual objective function values can be achieved. Based on the convergence result, we prove the robustness with respect to the mesh size $h$ for the mABCD method by establishing that asymptotically the infinite dimensional ABCD method and finite dimensional discretizations have the same convergence property, and the number of iterations of mABCD method remains almost constant as the discretization is refined.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

A Unified Algorithmic Framework of Symmetric Gauss-Seidel Decomposition based Proximal ADMMs for Convex Composite Programming

This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alternating direction methods of multipliers (ADMMs) for convex composite optimization problems. The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algorithms. Specifically, the majorized augmented Lagrangian functions, the indefinite proximal terms, the inexact symmetric Gauss-Seidel decomposition theorem, the tolerance criteria of approximately solving the subproblems, and the large dual step-lengths, are all incorporated in one algorithmic framework, which we named as sGS-imiPADMM. From the popularity of convergent variants of multi-block ADMMs in recent years, especially for high-dimensional multi-block convex composite conic programming problems, the unification presented in this paper, as well as the corresponding convergence results, may have the great potential of facilitating the implementation of many multi-block ADMMs in various problem settings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems

This note serves two purposes. Firstly, we construct a counterexample to show that the statement on the convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex optimization problems in a highly influential paper by Boyd et al. [Found. Trends Mach. Learn. 3(1) 1-122 (2011)] can be false if no prior condition on the existence of solutions to all the subproblems involved is assumed to hold. Secondly, we present fairly mild conditions to guarantee the existence of solutions to all the subproblems and provide a rigorous convergence analysis on the ADMM, under a more general and useful semi-proximal ADMM (sPADMM) setting considered by Fazel et al. [SIAM J. Matrix Anal. Appl. 34(3) 946-977 (2013)], with a computationally more attractive large step-length that can even exceed the practically much preferred golden ratio of $(1+\sqrt{5})/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming

In this paper, we propose an inexact multi-block ADMM-type first-order method for solving a class of high-dimensional convex composite conic optimization problems to moderate accuracy. The design of this method combines an inexact 2-block majorized semi-proximal ADMM and the recent advances in the inexact symmetric Gauss-Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block-variable. One distinctive feature of our proposed method (the sGS-imsPADMM) is that it only needs one cycle of an inexact sGS method, instead of an unknown number of cycles, to solve each of the subproblems involved.With some simple and implementable error tolerance criteria, the cost for solving the subproblems can be greatly reduced, and many steps in the forward sweep of each sGS cycle can often be skipped, which further contributes to the efficiency of the proposed method. Global convergence as well as the iteration complexity in the non-ergodic sense is established.Preliminary numerical experiments on some high-dimensional linear and convex quadratic SDP problems with a large number of linear equality and inequality constraints are also provided. The results show that for the vast majority of the tested problems, the sGS-imsPADMM is 2 to 3 times faster than the directly extended multi-block ADMM with the aggressive step-length of 1.618, which is currently the benchmark among first-order methods for solving multi-block linear and quadratic SDP problems though its convergence is not guaranteed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Characterization of the Robust Isolated Calmness for a Class of Conic Programming Problems

This paper is devoted to studying the robust isolated calmness of the Karush-Kuhn-Tucker (KKT) solution mapping for a large class of interesting conic programming problems (including most commonly known ones arising from applications) at a locally optimal solution. Under the Robinson constraint qualification, we show that the KKT solution mapping is robustly isolated calm if and only if both the strict Robinson constraint qualification and the second order sufficient condition hold. This implies, among others, that at a locally optimal solution the second order sufficient condition is needed for the KKT solution mapping to have the Aubin property.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming

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, 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) where 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization

This paper presents a majorized alternating direction method of multipliers (ADMM) with indefinite proximal terms for solving linearly constrained $2$-block convex composite optimization problems with each block in the objective being the sum of a non-smooth convex function and a smooth convex function, i.e., $\min_{x \in {\cal X}, \; y \in {\cal Y}}\{p(x)+f(x) + q(y)+g(y)\mid A^* x+B^* y = c\}$. By choosing the indefinite proximal terms properly, we establish the global convergence and $O(1/k)$ ergodic iteration-complexity of the proposed method for the step-length $τ\in (0, (1+\sqrt{5})/2)$. The computational benefit of using indefinite proximal terms within the ADMM framework instead of the current requirement of positive semidefinite ones is also demonstrated numerically. This opens up a new way to improve the practical performance of the ADMM and related methods.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients

For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the low-rank correlation matrix completion in various fields such as the financial market and the low-rank density matrix completion from the quantum state tomography. To seek a solution of high recovery quality beyond the reach of the nuclear norm, in this paper, we propose a rank-corrected procedure using a nuclear semi-norm to generate a new estimator. For this new estimator, we establish a non-asymptotic recovery error bound. More importantly, we quantify the reduction of the recovery error bound for this rank-corrected procedure. Compared with the one obtained for the nuclear norm penalized least squares estimator, this reduction can be substantial (around 50%). We also provide necessary and sufficient conditions for rank consistency in the sense of Bach (2008). Very interestingly, these conditions are highly related to the concept of constraint nondegeneracy in matrix optimization. As a byproduct, our results provide a theoretical foundation for the majorized penalty method of Gao and Sun (2010) and Gao (2010) for structured low-rank matrix optimization problems. Extensive numerical experiments demonstrate that our proposed rank-corrected procedure can simultaneously achieve a high recovery accuracy and capture the low-rank structure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming

We consider least squares semidefinite programming (LSSDP) where the primal matrix variable must satisfy given linear equality and inequality constraints, and must also lie in the intersection of the cone of symmetric positive semidefinite matrices and a simple polyhedral set. We propose an inexact accelerated block coordinate descent (ABCD) method for solving LSSDP via its dual, which can be reformulated as a convex composite minimization problem whose objective is the sum of a coupled quadratic function involving four blocks of variables and two separable non-smooth functions involving only the first and second block, respectively. Our inexact ABCD method has the attractive $O(1/k^2)$ iteration complexity if the subproblems are solved progressively more accurately. The design of our ABCD method relies on recent advances in the symmetric Gauss-Seidel technique for solving a convex minimization problem whose objective is the sum of a multi-block quadratic function and a non-smooth function involving only the first block. Extensive numerical experiments on various classes of over 600 large scale LSSDP problems demonstrate that our proposed ABCD method not only can solve the problems to high accuracy, but it is also far more efficient than (a) the well known BCD (block coordinate descent) method, (b) the eARBCG (an enhanced version of the accelerated randomized block coordinate gradient) method, and (c) the APG (accelerated proximal gradient) method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming

In this paper, we aim to provide a comprehensive analysis on the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a certain error bound condition, we establish the global linear rate of convergence for a more general semi-proximal ADMM with the dual steplength being restricted to be in the open interval $(0, (1+\sqrt{5})/2)$. In our analysis, we assume neither the strong convexity nor the strict complementarity except an error bound condition, which holds automatically for convex composite quadratic programming. This semi-proximal ADMM, which includes the classic ADMM, not only has the advantage to resolve the potentially non-solvability issue of the subproblems in the classic ADMM but also possesses the abilities of handling multi-block convex optimization problems efficiently. We shall use convex composite quadratic programming and quadratic semi-definite programming as important applications to demonstrate the significance of the obtained results. Of its own novelty in second-order variational analysis, a complete characterization is provided on the isolated calmness for the nonlinear convex semi-definite optimization problem in terms of its second order sufficient optimality condition and the strict Robinson constraint qualification for the purpose of proving the linear rate convergence of the semi-proximal ADMM when applied to two- and multi-block convex quadratic semi-definite programming.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block

In this paper, we present a semi-proximal alternating direction method of multipliers (ADMM) for solving $3$-block separable convex minimization problems with the second block in the objective being a strongly convex function and one coupled linear equation constraint. By choosing the semi-proximal terms properly, we establish the global convergence of the proposed semi-proximal ADMM for the step-length $τ\in (0, (1+\sqrt{5})/2)$ and the penalty parameter $σ\in (0, +\infty)$. In particular, if $σ>0$ is smaller than a certain threshold and the first and third linear operators in the linear equation constraint are injective, then all the three added semi-proximal terms can be dropped and consequently, the convergent $3$-block semi-proximal ADMM reduces to the directly extended $3$-block ADMM with $τ\in (0, (1+\sqrt{5})/2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints

The objective of this paper is to design an efficient and convergent alternating direction method of multipliers (ADMM) for finding a solution of medium accuracy to conic programming problems whose constraints consist of linear equalities, linear inequalities, a non-polyhedral cone and a polyhedral cone. For this class of problems, one may apply the directly extended ADMM to their dual, which can be written in the form of convex programming with four separable blocks in the objective function and a coupling linear equation constraint. Indeed, the directly extended ADMM, though may diverge in theory, often performs much better numerically than many of its variants with theoretical convergence guarantee. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semi-proximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order $1 \rightarrow 3 \rightarrow 2 \rightarrow 3$, instead of the usual $1 \rightarrow 2 \rightarrow 3$ Gauss-Seidel BCD cycle used in the non-convergent directly extended $3$-block ADMM, for updating the variable blocks. Our extensive numerical tests on the important class of doubly non-negative semidefinite programming (SDP) problems with linear equality and/or inequality constraints demonstrate that our convergent method is at least $20%$ faster than the directly extended ADMM with unit step-length for the vast majority of about $550$ large scale problems tested.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions

This paper is devoted to the design of an efficient and convergent {semi-proximal} alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SDPNAL$+$: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints

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, Sun and Toh [SIAM Journal on Optimization, 20 (2010), pp.~1737--1765] 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, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. 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, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010), pp.~203--230] and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro, Ortiz and Svaiter [Mathematical Programming Computation, (2013), pp.~1--48]. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Spectral Operators of Matrices

The class of matrix optimization problems (MOPs) has been recognized in recent years to be a powerful tool by researchers far beyond the optimization community to model many important applications involving structured low rank matrices. This trend can be credited to some extent to the exciting developments in the emerging field of compressed sensing. The Löwner operator, which generates a matrix valued function by applying a single-variable function to each of the singular values of a matrix, has played an important role for a long time in solving matrix optimization problems. However, the classical theory developed for Löwner operators has become inadequate in these recent applications. The main objective of this paper is to provide some necessary theoretical foundations for designing numerical methods for solving the MOP. This goal is achieved by introducing and conducting a thorough study on a new class of matrix valued functions, coined as spectral operators of matrices. Several fundamental properties of spectral operators, including the well-definedness, continuity, directional differentiability, Fréchet-differentiability, locally Lipschitzian continuity, $ρ$-order B(ouligand)-differentiability ($0<ρ\leq 1$), $ρ$-order G-semismooth ($0<ρ\leq 1$) and the characterization of Clarke's generalized Jacobian, are systematically studied.

0 citations0 reviewsNo code linkedOpen access