Dual-Scaling Algorithm

This chapter summarizes the dual-scaling algorithm for conic optimization for solving (P) and (D). It assumes that both of these programs bounded and feasible. Note that (PP) and (DD) are bounded and feasible, and they can be expressed in that form. For simplicity, the notation will refer to semidefinite programming, but the algorithm can be generalized to other cones.

Let $K$ be the cone of positive semidefinite matrices. The data $C, A_i \in \mathbb{R}^{n \times n}$ are given symmetric matrices, $b \in \mathbb{R}^m$ is a given vector, and the variables $X, S \succeq 0$. The symbol $\succ (\succeq)$ means the matrix is positive (semi)definite. Following conventional notation, let

$${\cal A} X = \left[ \begin{array}{ccc} \langle A_{1} , X \ran... ...ght]^T \quad\mbox{and}\quad {\cal A}^Ty = \sum_{i=1}^m A_i y_i,$$

For feasible $(y,S)$, let $\bar z= \langle C, X \rangle$ for some feasible $X$ and consider the dual potential function

$$\psi(y, \bar{z}) = \rho\ln(\bar{z} - b^Ty) - \ln \det S.$$ (1)

The dual-scaling algorithm reduces this function, whose the first term decreases the duality gap and second term keeps $S$ in the interior of the positive semidefinite matrix cone. The gradient of this potential function is

$$\nabla \psi ( y, \bar{z} ) = -\frac{\rho}{\bar{z} - b^Ty}b +{\cal A}(S^{-1}).$$ (2)

Beginning with a strictly feasible point $(y^k,S^k)$ and upper bound $\bar z^k$, each iteration solves the following problem.

$$\begin{array}{lllll} \mbox{Minimize} & \nabla \psi^T(y^k, \b... ...al A}^T(y - y^k) (S^k)^{-.5}\Vert \leq \alpha, \\ \end{array}$$ (3)

where $\alpha$ is a positive constant. Denoting $S=S^k$, the step direction $\Delta y$ solves the linear system

$$\left( \begin{array}{ccc} \langle {A}_1, S^{-1} {A}_1 S^{-1}... ...) \Delta y = \frac{\rho}{\bar{z} - b^Ty}b - {\cal A}(S^{-1}).$$ (4)

The left-hand side of this linear system is a Gram matrix and is positive definite when $S \succ 0$ and the $A_i$s are linearly independent. In this manuscript, it will sometimes be referred to as $M$.

Using the ellipsoidal constraint, the minimal solution, $y^{k+1}$, of (3) is given by

$$\begin{array}{lll} y^{k+1} - y^k = \beta^k \Delta y & \mbox... ...} {\sqrt{-\nabla \psi^T(y^k,\bar{z}^k ) \Delta y}}. \end{array}$$

Practically, the algorithm then selects a step size $\beta_{k}\in (0,1]$ such that $S^{k+1} = S^k + \beta^{k} \Delta S$ is positive definite and the potential function $\psi (y,\bar{z} )$ is reduced.

To find a feasible point $X$, we solve the least squares problem

$$\begin{array}{llll} \mbox{minimize} & \Vert S^{.5} X S^{.5}... ...{\rho}I \Vert & \mbox{subject to} & {\cal A} X = b. \end{array}$$ (5)

The answer to (5) is given explicitly by

$$X(\bar z^k) = \frac{\bar z - b^T y}{\rho} S^{-1} \left({\cal A}^T \Delta y +S \right) S^{-1}.$$ (6)

Computing this matrix at each iteration is expensive and unnecessary. The next step direction only requires a new upper bound $\bar z^{k+1}$, which can be set to

$$\bar z^{k+1} := C \bullet X(\bar z^k) = b^Ty^k + X(\bar z^k)... ...k }{\rho} \left( \Delta y^T {\cal A}( {S^k})^{-1} + n \right).$$

if ${\cal A}^T \Delta y +S \succeq 0$.

Alternatively, consider $\mu > 0$ and

$$\begin{array}{llll} \mbox{maximize} & \phi(y) := b^Ty + \mu \ln \det S & \mbox{subject to} & {\cal A}^Ty +S = C. \end{array}$$ (7)

The first-order KKT conditions are ${\cal A}X = b$, ${\cal A}^Ty +S = C$, $\mu S^{-1} = X$, and the corresponding Newton equations are

$${\cal A}(X + \Delta X) = b \hspace{0.5in} {\cal A}^T(\Delta... ....5in} \mu S^{-1} \Delta S S^{-1} + \Delta X = \mu S^{-1} - X.$$ (8)

The Schur complement of these equations is (4) if we set $\mu = \frac{\bar z - b^Ty}{\rho}$, and $X(\bar z^k) = \mu S^{-1} - \mu S^{-1} \Delta S S^{-1}$ satisfies the constraints ${\cal A} X(S,\mu) =b$.

Given a feasible starting point and appropriate choices for step-length and $\mu$, convergence results in [6] show that either the new point $(y,S)$ or the new point $X$ is feasible and reduces the Tanabe-Todd-Ye primal-dual potential function

$$\Psi(X,S) = \rho \ln(X \bullet S) - \ln \det X - \ln \det S$$

enough to achieve linear convergence. When $\rho > n$, the infimum of the potential function occurs at an optimal solution. A more thorough explanation of the the dual-scaling algorithm and its convergence properties, can be found in [6].