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

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

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

Semi-definite Programming mirror-prox method, saddle point problem, semidefinite programming

Arkadi Nemirovski

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

A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

Published: 2004/10/06

Arkadi Nemirovski

Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming condition number, conjugate gradient method, convergence rate, ellipsoid method, linear systems of equations, polynomial algorithms, steepest descent algorithm

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

A modified nearly exact method for solving low-rank trust region subproblem

Published: 2004/05/31, Updated: 2004/12/12

Nonlinear Optimization large-scale optimization, limited memory bfgs method, nearly exact method, sherman-morrison-woodbury formula, trust-region methods

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

An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex QP

Published: 2004/05/04

Linear, Cone and Semidefinite Programming, Quadratic Programming convex quadratic programming, inexact search directions, iterative solver, polynomial convergence

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

Dual Convergence of the Proximal Point Method with Bregman Distances for Linear Programming

Published: 2004/03/13

João Xavier da Cruz Neto

Orizon Pereira Ferreira

Convex and Nonsmooth Optimization, Convex Optimization, Linear Programming barrier function, bregman distances, convergence of dual, dual convergence rate, dual path, generalized proximal point methods, primal convergence rate, primal path

A. N. Iusem

In this paper we consider the proximal point method with Bregman distance applied to linear programming problems, and study the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. We establish the convergence of this dual sequence, as well as convergence rate results for the primal sequence, for a suitable … Read more

Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

Published: 2003/10/31, Updated: 2003/11/03

Linear Programming, Network Optimization condition number, interior point methods, iterative methods for linear equations, linear programming, network flow problems, normal matrix, polynomial bound, preconditioning

In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more

Local Minima and Convergence in Low-Rank Semidefinite Programming

Published: 2003/09/29

Samuel Burer

Combinatorial Optimization, Semi-definite Programming

The low-rank semidefinite programming problem (LRSDP_r) is a restriction of the semidefinite programming problem (SDP) in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and … Read more

Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

Published: 2003/07/23, Updated: 2004/12/12