Systems Optimization Laboratory
Stanford, CA 94305-4121 USA
|
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.
|
