An Augmented Primal-Dual Method for Linear Conic Programs

Florian Jarre (jarreopt.uni-duesseldorf.de)
Franz Rendl (franz.rendluni-klu.ac.at)

Abstract: We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This ``agumented primal-dual function'' or ``apd-function'' is restricted to an affine set in the primal-dual space. The evaluation of the function and its derivative is cheap if the projection of a given point onto the cone %and its dual can be computed cheaply, and if the projection of a given point onto the affine subspace defining the primal problem can be computed cheaply. For the special case of a semidefinite program, a certain regularization of the apd-function is analyzed. Numerical examples minimizing the apd-function with a conjugate gradient method illustrate the potential of the approach.

Keywords: Conic program, linear convergence, augmented primal-dual function.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Report, Institut f\"ur Mathematik, Universit\"at D\"usseldorf, April 2007.

Download: [PDF]

Entry Submitted: 04/01/2007
Entry Accepted: 04/01/2007
Entry Last Modified: 04/11/2007

Modify/Update this entry