Nonsymmetric potential-reduction methods for general cones

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.


CORE Discussion Paper 2006/34, March 2006



View Nonsymmetric potential-reduction methods for general cones