Search

In this paper, we focus on using the low-rank factorization approach to solve the SDP relaxation of a graph equipartition problem, which involves an additional spectral upper bound over the traditional linear SDP. We discuss the equivalence between the decomposed problem and the original SDP problem. We also derive a sufficient condition, under which a second order stationary point of the non-convex problem is also a global minimum. Moreover, the constraints of the non-convex problem involve an algebraic variety with conducive geometric properties which we analyse. We also develop a method to escape from a non-optimal singular point on this variety. This allows us to use Riemannian optimization techniques to solve the SDP problem very efficiently with certified global optimality. [ABSTRACT FROM AUTHOR]

We consider the problem of learning a graph under the Laplacian constraint with a non-convex penalty: minimax concave penalty (MCP). For solving the MCP penalized graphical model, we design an inexact proximal difference-of-convex algorithm (DCA) and prove its convergence to critical points. We note that each subproblem of the proximal DCA enjoys the nice property that the objective function in its dual problem is continuously differentiable with a semismooth gradient. Therefore, we apply an efficient semismooth Newton method to subproblems of the proximal DCA. Numerical experiments on various synthetic and real data sets demonstrate the effectiveness of the non-convex penalty MCP in promoting sparsity. Compared with the existing state-of-the-art method, our method is demonstrated to be more efficient and reliable for learning graph Laplacian with MCP. [ABSTRACT FROM AUTHOR]

The discrete optimal transport (OT) problem, which offers an effective computational tool for comparing two discrete probability distributions, has recently attracted much attention and played essential roles in many modern applications. This paper proposes to solve the discrete OT problem by applying a squared smoothing Newton method via the Huber smoothing function for solving the corresponding KKT system directly. The proposed algorithm admits appealing convergence properties and is able to take advantage of the solution sparsity to greatly reduce computational costs. Moreover, the algorithm can be extended to solve problems with similar structures, including the Wasserstein barycenter (WB) problem with fixed supports. To verify the practical performance of the proposed method, we conduct extensive numerical experiments to solve a large set of discrete OT and WB benchmark problems. Our numerical results show that the proposed method is efficient compared to state-of-the-art linear programming (LP) solvers. Moreover, the proposed method consumes less memory than existing LP solvers, which demonstrates the potential usage of our algorithm for solving large-scale OT and WB problems. [ABSTRACT FROM AUTHOR]

Sdpnal+ is a MATLAB software package that implements an augmented Lagrangian based method to solve large scale semidefinite programming problems with bound constraints. The implementation was initially based on a majorized semismooth Newton-CG augmented Lagrangian method, here we designed it within an inexact symmetric Gauss-Seidel based semi-proximal ADMM/ALM (alternating direction method of multipliers/augmented Lagrangian method) framework for the purpose of deriving simpler stopping conditions and closing the gap between the practical implementation of the algorithm and the theoretical algorithm. The basic code is written in MATLAB, but some subroutines in C language are incorporated via Mex files. We also design a convenient interface for users to input their SDP models into the solver. Numerous problems arising from combinatorial optimization and binary integer quadratic programming problems have been tested to evaluate the performance of the solver. Extensive numerical experiments conducted in [L.Q. Yang, D.F. Sun, and K.C. Toh, SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput. 7 (2015), pp. 331–366] show that the proposed method is quite efficient and robust, in that it is able to solve 98.9% of the 745 test instances of SDP problems arising from various applications to the accuracy of 10 − 6 in the relative KKT residual. [ABSTRACT FROM AUTHOR]

The article presents the study on large-scale matrix optimization problems dealing with linear constraints and convex cost functions. It discusses how the study was conducted which involved convex matrix cone programming, a class of semidefinite programming. The results reportedly revealed that some large-scale dense linear equation systems from the Newton proximal-point and Lagrangian algorithms will be moderately well-conditioned if certain constraint nondegeneracy conditions hold.

In this paper, the formulation of a lower-bound limit analysis for axisymmetric problems by means of finite elements leads to an optimization problem with a large number of variables and constraints. For the Mohr-Coulomb criterion, it is shown that these axisymmetric problems can be solved by second-order cone programming (SOCP). First, a brief introduction to SOCP is given and how axisymmetric lower-bound limit analysis can be formulated in this way is described. Through the use of an efficient toolbox ( MOSEK or SDPT3), large-scale SOCP problems can be solved in minutes on a desktop computer. The method is then applied to estimate the collapse load of circular footings and uplift capacity of single or multiplate circular anchors. By comparing the present analysis with the results reported in the literature, it is shown that the results obtained from the proposed method are accurate and computationally more efficient than the numerical lower-bound limit analysis incorporated with linear programming. [ABSTRACT FROM AUTHOR]

Abstract: A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1–24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method. [Copyright &y& Elsevier]

We present the computation of the condition numbers for linear programming (LP) problems from the NETLIB suite. The method of Peña [Peña, J., 1998, {Computing the distance to infeasibility: theoretical and practical issues}. Technical report, Center for Applied Mathematics, Cornell University.] was used to compute the bounds on the distance to ill-posedness ?( d ) of a given problem instance with data d , and the condition number was computed as C ( d )?=?? d ?/?( d ). We discuss the efficient implementation of Peña’s method and compare the tightness of the estimates on C ( d ) computed by Peña’s method to that computed by the method employed by Ordóñez and Freund [Ordóñez, F. and Freund, R.M., 2003, {Computational experience and the explanatory value of condition measures for linear optimization}. SIAM Journal on Optimization, 14, 307–333.]. While Peña’s method is generally much cheaper, the bounds provided are generally not as tight as those computed by Ordóñez and Freund. As a by-product, we use the computational results to study the correlation between log C ( d ) and the number of interior-point method iterations taken to solve a LP problem instance. Our computational findings on the preprocessed problem instances from NETLIB suite are consistent with those reported by Ordóñez and Freund. [ABSTRACT FROM AUTHOR]

Focuses on the fundamental phenomena which governs convergence of Krylov subspace matrix iterations for solving systems of equations. Examination of six approximations for solving systems of equations; Information on large-scale matrix problems of computational science and engineering.

We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted to the intersection of the positive semidefinite cone and a polyhedral cone representing the algebraic properties of binary and box constraints as well as the sparsity structure of the objective polynomial. Our DNN relaxation serves as a variant of the Lasserre moment-SOS hierarchy of relaxations for binary and box constrained POPs when the size of the cones is gradually increased to compute tighter lower bounds for their optimal values. A significant part of the paper is devoted to deriving and analyzing a class of polyhedral cones to strengthen the DNN relaxation, and the design of efficient computation of the metric projections onto these cones in the accelerated BP algorithm. Numerical results on various POPs are available in Ito et al. (ACM Trans Math Softw 45, Article 34, 2019). [ABSTRACT FROM AUTHOR]

Rank regularized minimization problem is an ideal model for the low-rank matrix completion/recovery problem. The matrix factorization approach can transform the high-dimensional rank regularized problem to a low-dimensional factorized column-sparse regularized problem. The latter can greatly facilitate fast computations in applicable algorithms, but needs to overcome the simultaneous non-convexity of the loss and regularization functions. In this paper, we consider the factorized column-sparse regularized model. Firstly, we optimize this model with bound constraints, and establish a certain equivalence between the optimized factorization problem and rank regularized problem. Further, we strengthen the optimality condition for stationary points of the factorization problem and define the notion of strong stationary point. Moreover, we establish the equivalence between the factorization problem and its nonconvex relaxation in the sense of global minimizers and strong stationary points. To solve the factorization problem, we design two types of algorithms and give an adaptive method to reduce their computation. The first algorithm is from the relaxation point of view and its iterates own some properties from global minimizers of the factorization problem after finite iterations. We give some analysis on the convergence of its iterates to a strong stationary point. The second algorithm is designed for directly solving the factorization problem. We improve the PALM algorithm introduced by Bolte et al. (Math Program Ser A 146:459–494, 2014) for the factorization problem and give its improved convergence results. Finally, we conduct numerical experiments to show the promising performance of the proposed model and algorithms for low-rank matrix completion. [ABSTRACT FROM AUTHOR]

For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method implemented in BBCPOP [ACM Tran. Softw., 45(3):34 (2019)]. The relaxation problem is converted into the problem of finding the largest zero y ∗ of a continuously differentiable (except at y ∗ ) convex function g : R → R such that g (y) = 0 if y ≤ y ∗ and g (y) > 0 otherwise. In theory, the method generates lower and upper bounds of y ∗ both converging to y ∗ . Their convergence is quadratic if the right derivative of g at y ∗ is positive. Accurate computation of g ′ (y) is necessary for the robustness of the method, but it is difficult to achieve in practice. As an alternative, we present a secant-bracketing method. We demonstrate that the method improves the quality of the lower bounds obtained by BBCPOP and SDPNAL+ for binary QOP instances from BIQMAC. Moreover, new lower bounds for the unknown optimal values of large scale QAP instances from QAPLIB are reported. [ABSTRACT FROM AUTHOR]

We derive an explicit formula, as well as an efficient procedure, for constructing a generalized Jacobian for the projector of a given square matrix onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To guarantee the high efficiency of our procedure, a semismooth Newton method for solving the dual of the projection problem is proposed and efficiently implemented. Extensive numerical experiments are presented to demonstrate the merits and effectiveness of our method by comparing its performance against other powerful solvers such as the commercial software Gurobi and the academic code PPROJ (Hager and Zhang in SIAM J Optim 26:1773–1798, 2016). In particular, our algorithm is able to solve the projection problem with over one billion variables and nonnegative constraints to a very high accuracy in less than 15 min on a modest desktop computer. More importantly, based on our efficient computation of the projections and their generalized Jacobians, we can design a highly efficient augmented Lagrangian method (ALM) for solving a class of convex quadratic programming (QP) problems constrained by the Birkhoff polytope. The resulted ALM is demonstrated to be much more efficient than Gurobi in solving a collection of QP problems arising from the relaxation of quadratic assignment problems. [ABSTRACT FROM AUTHOR]

Due to the possible lack of primal-dual-type error bounds, it was not clear whether the Karush–Kuhn–Tucker (KKT) residuals of the sequence generated by the augmented Lagrangian method (ALM) for solving convex composite conic programming (CCCP) problems converge superlinearly. In this paper, we resolve this issue by establishing the R-superlinear convergence of the KKT residuals generated by the ALM under only a mild quadratic growth condition on the dual of CCCP, with easy-to-implement stopping criteria for the augmented Lagrangian subproblems. This discovery may help to explain the good numerical performance of several recently developed semismooth Newton-CG based ALM solvers for linear and convex quadratic semidefinite programming. [ABSTRACT FROM AUTHOR]

For a symmetric positive semidefinite linear system of equations Q x = b , where x = (x 1 , ... , x s) is partitioned into s blocks, with s ≥ 2 , we show that each cycle of the classical block symmetric Gauss–Seidel (sGS) method exactly solves the associated quadratic programming (QP) problem but added with an extra proximal term of the form 1 2 ‖ x - x k ‖ T 2 , where T is a symmetric positive semidefinite matrix related to the sGS decomposition of Q and x k is the previous iterate. By leveraging on such a connection to optimization, we are able to extend the result (which we name as the block sGS decomposition theorem) for solving convex composite QP (CCQP) with an additional possibly nonsmooth term in x 1 , i.e., min { p (x 1) + 1 2 ⟨ x , Q x ⟩ - ⟨ b , x ⟩ } , where p (·) is a proper closed convex function. Based on the block sGS decomposition theorem, we extend the classical block sGS method to solve CCQP. In addition, our extended block sGS method has the flexibility of allowing for inexact computation in each step of the block sGS cycle. At the same time, we can also accelerate the inexact block sGS method to achieve an iteration complexity of O (1 / k 2) after performing k cycles. As a fundamental building block, the block sGS decomposition theorem has played a key role in various recently developed algorithms such as the inexact semiproximal ALM/ADMM for linearly constrained multi-block convex composite conic programming (CCCP), and the accelerated block coordinate descent method for multi-block CCCP. [ABSTRACT FROM AUTHOR]

The exclusive lasso (also known as elitist lasso) regularizer has become popular recently due to its superior performance on intra-group feature selection. Its complex nature poses difficulties for the computation of high-dimensional machine learning models involving such a regularizer. In this paper, we propose a highly efficient dual Newton method based proximal point algorithm (PPDNA) for solving large-scale exclusive lasso models. 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 more practical. Extensive numerical results are presented to demonstrate the superior performance of the PPDNA against other popular numerical algorithms for solving the exclusive lasso problems. [ABSTRACT FROM AUTHOR]

We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss–Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate SDPs to high accuracy, even in the presence of millions of equality constraints. [ABSTRACT FROM AUTHOR]

This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets. [ABSTRACT FROM AUTHOR]

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-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. [ABSTRACT FROM AUTHOR]

We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-completely positive programming (CPP) relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem with a single Lagrangian parameter in a CPP matrix variable with its upper-left element fixed to 1. Replacing the CPP matrix variable by a DNN matrix variable, we derive the Lagrangian-DNN relaxation, and establish the equivalence between the optimal value of the DNN relaxation of the original QOP and that of the Lagrangian-DNN relaxation. We then propose an efficient numerical method for the Lagrangian-DNN relaxation using a bisection method combined with the proximal alternating direction multiplier and the accelerated proximal gradient methods. Numerical results on binary QOPs, quadratic multiple knapsack problems, maximum stable set problems, and quadratic assignment problems illustrate the superior performance of the proposed method for attaining tight lower bounds in shorter computational time. [ABSTRACT FROM AUTHOR]

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 et al. (, ). 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. [ABSTRACT FROM AUTHOR]

In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently been found to have many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to make the defined MCP tractable and meaningful, we must first understand the structure of these epigraphs. So far, only the epigraph of the Frobenius matrix norm, which can be regarded as a second order cone, has been well studied. Here, we take an initial step to study several important properties, including its closed form solution, calm Bouligand-differentiability and strong semismoothness, of the metric projection operator over the epigraph of the $$l_1,\,l_\infty $$, spectral or operator, and nuclear matrix norm, respectively. These properties make it possible to apply augmented Lagrangian methods, which have recently received a great deal of interests due to their high efficiency in solving large scale semidefinite programming, to this class of MCP problems. The work done in this paper is far from comprehensive. Rather it is intended as a starting point to call for more insightful research on MCP so that it can serve as a basic tool to solve more challenging convex matrix optimization problems in years to come. [ABSTRACT FROM AUTHOR]

For a long period of time, scientists studied genomes while assuming they are linear. Recently, chromosome conformation capture (3C)-based technologies, such as Hi-C, have been developed that provide the loci contact frequencies among loci pairs in a genome-wide scale. The technology unveiled that two far-apart loci can interact in the tested genome. It indicated that the tested genome forms a three-dimensional (3D) chromosomal structure within the nucleus. With the available Hi-C data, our next challenge is to model the 3D chromosomal structure from the 3C-derived data computationally. This article presents a deterministic method called ChromSDE, which applies semi-definite programming techniques to find the best structure fitting the observed data and uses golden section search to find the correct parameter for converting the contact frequency to spatial distance. Further, we develop a measure called consensus index to indicate if the Hi-C data corresponds to a single structure or a mixture of structures. To the best of our knowledge, ChromSDE is the only method that can guarantee recovering the correct structure in the noise-free case. In addition, we prove that the parameter of conversion from contact frequency to spatial distance will change under different resolutions theoretically and empirically. Using simulation data and real Hi-C data, we showed that ChromSDE is much more accurate and robust than existing methods. Finally, we demonstrated that interesting biological findings can be uncovered from our predicted 3D structure. [ABSTRACT FROM AUTHOR]

Finite-element analysis of many soil-structure interaction problems involves material zones of widely differing stiffnesses. The large relative differences in material stiffnesses usually result in an ill-conditioned system for which practical preconditioners become ineffective for the iterative solution of such systems. The study suggests that a block diagonal preconditioner can exploit such differences. However, the theoretical preconditioner is expensive for practical use. Less costly block diagonal preconditioners are numerically evaluated for various inexact forms of the blocks in conjunction with conjugate gradient solver. The study includes analysis of two representative soil-structure interaction problems and proposes two simplified block diagonal preconditioners that effectively mitigate such material ill conditionings. [ABSTRACT FROM AUTHOR]

Biot's symmetric indefinite linear systems of equations are commonly encountered in finite-element computations of geotechnical problems. The development of efficient solution methods for Biot's linear systems of equations is of practical importance to geotechnical software packages. In conjunction with the Krylov-subspace iterative method symmetric quasi-minimal residual (SQMR), some zero-level fill-in incomplete factorization preconditioning techniques including a symmetric successive overrelaxation (SSOR) type method and several zero-level incomplete LU [ILU(0)] methods are investigated and compared for Biot's symmetric indefinite linear systems of equations. Numerical experiments are carried out based on three practical geotechnical problems. Numerical results indicate that ILU(0) preconditioners are classical and generally efficient when adequately stabilized. However, the tunnel problem provides a counterexample demonstrating that ILU(0) preconditioners cannot be fully stabilized by preliminary scaling, reordering, making use of perturbed matrices, or dynamically selecting pivots. Compared with the investigated ILU(0) preconditioners, the recently proposed modified SSOR preconditioner is less efficient but is robust over the range of problems studied. [ABSTRACT FROM AUTHOR]

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature. [ABSTRACT FROM AUTHOR]

We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension n up to 4, 110 and the number of equality constraints m up to 2, 156, 544 show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with n = 4, 110 and m = 1, 154, 467) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts. [ABSTRACT FROM AUTHOR]

In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss–Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an inexact proximal augmented Lagrangian method. This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Even for the two-block case, a by-product of this equivalence is the convergence of the whole sequence generated by the classic ADMM with a step-length that exceeds the conventional upper bound of (1 + 5) / 2 , if one part of the objective is linear. This is exactly the problem setting in which the very first convergence analysis of ADMM was conducted by Gabay and Mercier (Comput Math Appl 2(1):17–40, 1976), but, even under notably stronger assumptions, only the convergence of the primal sequence was known. A collection of illustrative examples are provided to demonstrate the breadth of applications for which our results can be used. Numerical experiments on solving a large number of linear and convex quadratic semidefinite programming problems are conducted to illustrate how the theoretical results established here can lead to improvements on the corresponding practical implementations. [ABSTRACT FROM AUTHOR]

The sparse group Lasso is a widely used statistical model which encourages the sparsity both on a group and within the group level. In this paper, we develop an efficient augmented Lagrangian method for large-scale non-overlapping sparse group Lasso problems with each subproblem being solved by a superlinearly convergent inexact semismooth Newton method. Theoretically, we prove that, if the penalty parameter is chosen sufficiently large, the augmented Lagrangian method converges globally at an arbitrarily fast linear rate for the primal iterative sequence, the dual infeasibility, and the duality gap of the primal and dual objective functions. Computationally, we derive explicitly the generalized Jacobian of the proximal mapping associated with the sparse group Lasso regularizer and exploit fully the underlying second order sparsity through the semismooth Newton method. The efficiency and robustness of our proposed algorithm are demonstrated by numerical experiments on both the synthetic and real data sets. [ABSTRACT FROM AUTHOR]

The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box, and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a doubly nonnegative relaxation of the POP, and then solves the COP by applying the bisection and projection method. The COP is expressed with a linear objective function and constraints described as a single hyperplane and two cones, which are the Cartesian product of positive semidefinite cones and a polyhedral cone induced from the BBC constraints. BBCPOP aims to compute a tight lower bound for the optimal value of a large-scale POP in the class that is beyond the comfort zone of existing software packages. The robustness, reliability, and efficiency of BBCPOP are demonstrated in comparison to the state-of-the-art software SDP package SDPNAL+ on randomly generated sparse POPs of degree 2 and 3 with up to a few thousands variables, and ones of degree from 5 to 8 with up to a few hundred variables. Numerical results on BBC-constrained POPs that arise from quadratic assignment problems are also reported. The software package BBCPOP is available at https://sites.google.com/site/bbcpop1/. [ABSTRACT FROM AUTHOR]

While clustering has been well studied in the past decade, model selection has drawn much less attention due to the difficulty of the problem. In this paper, we address both problems in a joint manner by recovering an ideal affinity tensor from an imperfect input. By taking into account the relationship of the affinities induced by the cluster structures, we are able to significantly improve the affinity input, such as repairing those entries corrupted by gross outliers. More importantly, the recovered ideal affinity tensor also directly indicates the number of clusters and their membership, thus solving the model selection and clustering jointly. To enforce the requisite global consistency in the affinities demanded by the cluster structure, we impose a number of constraints, specifically, among others, the tensor should be low rank and sparse, and it should obey what we call the rank-1 sum constraint. To solve this highly non-smooth and non-convex problem, we exploit the mathematical structures, and express the original problem in an equivalent form amenable for numerical optimization and convergence analysis. To scale to large problem sizes, we also propose an alternative formulation, so that those problems can be efficiently solved via stochastic optimization in an online fashion. We evaluate our algorithm with different applications to demonstrate its superiority, and show it can adapt to a large variety of settings. [ABSTRACT FROM AUTHOR]

High-dimension-low-sample size statistical analysis is important in a wide range of applications. In such situations, the highly appealing discrimination method, support vector machine, can be improved to alleviate data piling at the margin. This leads naturally to the development of distance weighted discrimination (DWD), which can be modeled as a second-order cone programming problem and solved by interior-point methods when the scale (in sample size and feature dimension) of the data is moderate. Here, we design a scalable and robust algorithm for solving large-scale generalized DWD problems. Numerical experiments on real datasets from the UCI repository demonstrate that our algorithm is highly efficient in solving large-scale problems, and sometimes even more efficient than the highly optimized LIBLINEAR and LIBSVM for solving the corresponding SVM problems. Supplementary material for this article is available online. [ABSTRACT FROM AUTHOR]

The class of matrix optimization problems (MOPs) has been recognized in recent years to be a powerful tool to model many important applications involving structured low rank matrices within and beyond the optimization community. This trend can be credited to some extent to the exciting developments in emerging fields such as compressed sensing. The Löwner operator, which generates a matrix valued function via 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 the Löwner operator has become inadequate in these recent applications. The main objective of this paper is to provide necessary theoretical foundations from the perspectives of designing efficient numerical methods for solving MOPs. We achieve this goal 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 and Fréchet-differentiability are systematically studied. [ABSTRACT FROM AUTHOR]

In this paper, we establish the convergence properties for a majorized alternating direction method of multipliers for linearly constrained convex optimization problems, whose objectives contain coupled functions. Our convergence analysis relies on the generalized Mean-Value Theorem, which plays an important role to properly control the cross terms due to the presence of coupled objective functions. Our results, in particular, show that directly applying two-block alternating direction method of multipliers with a large step length of the golden ratio to the linearly constrained convex optimization problem with a quadratically coupled objective function is convergent under mild conditions. We also provide several iteration complexity results for the algorithm. [ABSTRACT FROM AUTHOR]

We consider a class of matrix spectral norm approximation problems for finding an affine combination of given matrices having the minimal spectral norm subject to some prescribed linear equality and inequality constraints. These problems arise often in numerical algebra, engineering and other areas, such as finding Chebyshev polynomials of matrices and fastest mixing Markov chain models. Based on classical analysis of proximal point algorithms (PPAs) and recent developments on semismooth analysis of nonseparable spectral operators, we propose a semismooth Newton-CG based dual PPA for solving the matrix norm approximation problems. Furthermore, when the primal constraint nondegeneracy condition holds for the subproblems, our semismooth Newton-CG method is proven to have at least a superlinear convergence rate. We also design efficient implementations for our proposed algorithm to solve a variety of instances and compare its performance with the nowadays popular first order alternating direction method of multipliers (ADMM). The results show that our algorithm, which is warm-started with an initial point obtained from the ADMM, substantially outperforms the pure ADMM, especially for the constrained cases and it is able to solve the problems robustly and efficiently to a relatively high accuracy. [ABSTRACT FROM AUTHOR]

Low-rank matrix completion is a problem of immense practical importance. Recent works on the subject often use nuclear norm as a convex surrogate of the rank function. Despite its solid theoretical foundation, the convex version of the problem often fails to work satisfactorily in real-life applications. Real data often suffer from very few observations, with support not meeting the randomness requirements, ubiquitous presence of noise and potentially gross corruptions, sometimes with these simultaneously occurring. This paper proposes a Proximal Alternating Robust Subspace Minimization method to tackle the three problems. The proximal alternating scheme explicitly exploits the rank constraint on the completed matrix and uses the $$\ell _0$$ pseudo-norm directly in the corruption recovery step. We show that the proposed method for the non-convex and non-smooth model converges to a stationary point. Although it is not guaranteed to find the global optimal solution, in practice we find that our algorithm can typically arrive at a good local minimizer when it is supplied with a reasonably good starting point based on convex optimization. Extensive experiments with challenging synthetic and real data demonstrate that our algorithm succeeds in a much larger range of practical problems where convex optimization fails, and it also outperforms various state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]