# Systems Optimization Laboratory

## PDCO: Primal-Dual interior method for Convex Objectives

• AUTHOR: Michael Saunders
CONTRIBUTORS: Bunggyoo Kim, Chris Maes, Santiago Akle

• CONTENTS:
A primal-dual interior method for solving linearly constrained optimization problems with a convex objective function $$\phi(x)$$ (preferably separable): \begin{align*} \text{minimize } & \phi(x) + \frac12 \|D_1x\|^2 + \frac12 \|r\|^2 \\ \text{subject to } & Ax + D_2r = b \\ & l \le x \le u, \end{align*} where both $$x$$ and $$r$$ are variables. The $$m \times n$$ matrix $$A$$ may be sparse or represented by an M-file for computing $$Ax$$ and $$A^Ty$$. The positive-definite diagonal matrices $$D_1$$, $$D_2$$ provide primal and dual regularization. $$D_2$$ determines whether each row of $$Ax \approx b$$ should be satisfied accurately or in the least-squares sense. (Each element of $$D_2$$ is typically in the range $$[10^{-4},1]$$.)

• REFERENCES:
Documented in the MATLAB and LaTeX files below. Uses established primal-dual technology, with choice of direct or iterative method for computing search directions.
Special feature: Iterative (and inexact) computation of search directions using LSQR.

• RELEASE:
16 Oct 2002: First version, derived from PDSCO. $$D_1$$, $$D_2$$ and general bounds implemented.
23 Sep 2003: Revised. Maximum entropy test problems included (joint work with John Tomlin, IBM Almaden).
11 Feb 2005: Slight changes for MATLAB 7.0.
11 Feb 2005: Removed ENTROPY.big from zip file (too big for those who don't want it). Link is below.
03 Apr 2010: Nonseparable objectives; function handles; zero bounds treated directly.
19 Apr 2010: PDCO replaces PDSCO because zero bounds are treated properly.
02 Jun 2011: options.backtrack added (default = 0). The backtracking linesearch is now disabled by default because it seems to inhibit convergence.
28 Apr 2012: LSMR replaces LSQR (Method=3). MINRES is a new option (Method=4), although Method=3 should be somewhat better in general.