- Nonsymmetric potential-reduction methods for general cones Yurii Nesterov (nesterovcore.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/2006Entry Accepted: 04/11/2006Entry Last Modified: 04/11/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.