Renato D.C. Monteiro This paper considers a special but broad class of convex programing (CP) problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. We study two first-order penalty methods for solving the above class of problems, namely: the quadratic penalty method and … Read more
In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more
In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more
In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more
The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more
In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more
In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more
The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more
In this paper we present a modified nearly exact (MNE) method for solving low-rank trust region (LRTR) subproblem. The LRTR subproblem is to minimize a quadratic function, whose Hessian is a positive diagonal matrix plus explicit low-rank update, subject to a Dikin-type ellipsoidal constraint, whose scaling matrix is positive definite and has the similar structure … Read more
In this paper we develop an interior-point primal-dual long-step path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of an iterative (linear system) solver. We propose a new linear system, which we refer to as the \emph{augmented normal equation} (ANE), to determine the primal-dual search directions. Since the condition number … Read more