Renato D.C. Monteiro – Page 6 – Optimization Online

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming augmented lagrangian method, convex optimization, first-order methods, lagrange multiplier, penalty

This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means … Read more

On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean

Published: 2009/03/17, Updated: 2010/10/17

Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming complementarity problems, complexity, extragradient, maximal monotone operator, variational inequality

Benar Fux Svaiter

In this paper we analyze the iteration-complexity of the hybrid proximal extragradient (HPE) method for finding a zero of a maximal monotone operator recently proposed by Solodov and Svaiter. One of the key points of our analysis is the use of new termination criteria based on the $\varepsilon$-enlargement of a maximal monotone operator. The advantage … Read more

Iteration-complexity of first-order penalty methods

Published: 2008/07/24

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization convex optimization, exact penalty functions, lagrange multiplier, quadratic penalty method

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

Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

Published: 2008/01/10

Convex Optimization, Nonsmooth Optimization, Statistics cone programming, dimension reduction, first-order methods, interior point methods, multivariate linear regression, smooth saddle point problem, trace norm

Ming Yuan

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

A polynomial predictor-corrector trust-region algorithm for linear programming

Published: 2007/06/01

Linear Programming, Nonlinear Optimization interior point methods, linear programming, primal-dual algorithms, strongly polynomial, trust-region methods

Takashi Tsuchiya

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

Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

Published: 2006/12/05, Updated: 2006/12/26

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming cone programming, linear programming, non-smooth method, primal-dual first-order methods, prox-method, semidefinite programming, smooth optimal method

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

A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

Published: 2005/09/30

Linear Programming, Linear, Cone and Semidefinite Programming affine-scaling, central path, condition number, crossover events, curvature, interior point methods, layered least squares steps, linear programming, path following, polynomial complexity, predictor-corrector, primal-dual algorithms, scale-invariance, strongly polynomial

Takashi Tsuchiya

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

An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

Published: 2005/06/29

Linear, Cone and Semidefinite Programming convex quadratic programming, hybrid augmented normal equation, inexact search directions, interior point methods, iterative linear solver, polynomial convergence, primal-dual path-following methods

Jerome W. O'Neal

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

Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

Published: 2004/11/12