Optimization Online


Nonsymmetric potential-reduction methods for general cones

Yurii Nesterov (nesterov***at***core.ucl.ac.be)

Abstract: In this paper we propose two new nonsymmetric primal-dual potential-reduction methods for conic problems. Both methods are based on {\em primal-dual lifting}. This procedure allows to construct a strictly feasible primal-dual pair linked by an exact {\em scaling} relation even if the cones are not symmetric. It is important that all necessary elements of our methods can be obtained from the standard solvers for {\em primal} Newton system. The first of the proposed schemes is based on the usual affine-scaling direction. For the second one, we apply a new {\em first-order} affine-scaling direction, which incorporates in a symmetric way the gradients of primal and dual barriers. For both methods we prove the standard $O(\sqrt{\nu} \ln {1 \over \epsilon})$ complexity estimate, where $\nu$ is the parameter of the barrier and $\epsilon$ is the required accuracy.

Keywords: Interior-point methods, potential-reduction methods, self-concordant barriers, self-scaled barriers, affine-scaling direction

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: CORE Discussion Paper 2006/34, March 2006

Download: [PDF]

Entry Submitted: 04/11/2006
Entry Accepted: 04/11/2006
Entry Last Modified: 04/11/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society