Reducing a quadratic program to standard form

Question

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem:

Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to
$e^Tw = 1$ and $w \geq 0$

using a solver I want a re-parametrization of the problem to the form:

$\min(-d^T b + 1/2 b^T D b)$ with the constraints $A^T b \geq b_0$

so that I can use a general-purpose optimization software for quadratic programming.

Question: So now, what would $d,b,D,A,b_0$ be?

Secondly, how is this re-parametrization done (is there a well-known procedural, aspect to this, or is it just algebra)? I ask because I would want to use this general-purpose solver for various quadratic minimization programs.

I can see that $b$ is $w$ and I am guessing that $A$ is an identity matrix and $b_0$ is a vector of zeros. What is $D$?

Answer 1

To transform your original program into the form you specified, use the following mappings:

• First, $D = 2S'S$, and $D$ is positive semidefinite.
• $b = w$, as you pointed out
• $d = 0$, as Nico notes
• $A$ takes the following form:

\begin{align} A = \left[\begin{array}{c} I \\ e^{T} \\ -e^{T}\end{array}\right] \end{align}

• $b_0$ takes the following form:

\begin{align} b_{0} = \left[ \begin{array}{c} 0 \\ 1 \\ -1\end{array} \right] \end{align}

where $0$ is a vector of zeros, but $1$ and $-1$ are scalars.

The values of $A$ and $b_{0}$ are the tricky part. The rows of $A$ and $b_{0}$ can be partitioned into three sets:

• the rows of $A$ and $b_{0}$ corresponding to the pair $(I, 0)$ map to $w \geq 0$
• the row of $A$ and $b_{0}$ corresponding to the pair $(e^{T}, 1)$ map to $e^{T}w \geq 1$
• the row of $A$ and $b_{0}$ corresponding to the pair $(-e^{T}, -1)$ map to $-e^{T}w \geq -1$, which is equivalent to $e^{T}w \leq 1$

The pair $e^{T}w \geq 1$ and $e^{T}w \leq 1$ is equivalent to $e^{T}w = 1$.

Answer 2

Here's another approach: subdivide $w$ and $S$ as follows: $$w=\begin{bmatrix}\bar{w} \\ w_n \end{bmatrix} \quad S=\begin{bmatrix}\bar{S} & s \end{bmatrix}$$ Specifically, $w_n$ is the very last element of $w\in\mathbb{R}^n$, and $\bar{w}\in\mathbb{R}^{n-1}$ is a vector containing every element but that last one. Now we have $$e^Tw = e^T\bar{w} + w_n = 1 \quad\Longrightarrow\quad w_n=1-e^T\bar{w}$$ and $$Sw=\bar{S}\bar{w} + s w_n = \bar{S} \bar{w} + s ( 1 - e^T\bar{w} ) = (\bar{S}-se^T)\bar{w}+s$$ and the problem becomes $$ \begin{array}{ll} \text{minimize} & \| (\bar{S}-se^T) \bar{w} + s \|^2 \\ \text{subject to} & \bar{w} \geq 0 \\ & e^T \bar{w} \leq 1 \end{array} $$ Now you've eliminated the equality constraint and constructing the standard form should be straightforward.