3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I doesn't look like you can translate your problem into that form. With $D=S'S$, $d=0$, $A=I$, $b_0=0$, you've set all parameters, but you can't capture $e^Tw=1$. $\endgroup$ – Nico Schlömer May 11 '13 at 12:19
3
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ It turns out that $e^Tw\leq 1$ is unnecessary in this case! The objective guarantees that the $\geq$ inequality must be active. This simplifies the results here and pretty much makes my approach worthless, especially if $S$ is sparse. $\endgroup$ – Michael Grant May 12 '13 at 18:52
  • $\begingroup$ @MichaelC.Grant and Geoff I implemented the approach and $D$ is not p.s.d in my case and I am getting an error from the solver. I checked the internal functions, where a cholesky decomposition of $D$ is being computed and then the inverse of the result is being computed. The error is occuring within these two steps, saying that $D$ is not p.s.d. What would be a turnaround? Note that $S$ is a real-rectangular matrix. Can I replace $D$ by adding a non-negative scalar to the diagonal of $D$? I also thought that this problem is convex. Am i missing something? $\endgroup$ – hearse May 12 '13 at 20:46
  • $\begingroup$ $D=2S^TS$ is PSD by construction. It is simply impossible for it not to be the case. There is almost certainly an error in your code. It might be possible for the Cholesky of $D$ to fail because $D$ is only semidefinite, not strictly positive definite. This can happen if $S$ has more columns than rows, for instance. But a good QP solver is supposed to be able to handle the semidefinite case. As a check, what are the eigenvalues of $D$? $\endgroup$ – Michael Grant May 12 '13 at 21:55
  • $\begingroup$ @MichaelC.Grant, Geoff, I am getting a 'constraints are inconsistent, no solution!' error with this proposed formulation. These are the dimensions that I have: $b$ is 15 by 1, $A^T$ is 17 by 15 with the two extra rows due to $e,-e^T$. $S$ is 5000 by 15. Have I made an error in the construction of the block matrix form $A$ or is there an error in the proposed answer? That said, I have resolved the psd part. u are right, as D is a gram matrix and hence a psd. But where is the inconsistency in the constraints error coming from? $\endgroup$ – hearse May 13 '13 at 6:06
  • $\begingroup$ Delete the $-e$ constraint and see what happens. $\endgroup$ – Michael Grant May 13 '13 at 11:30
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is $w_n$ and $\bar{w}$? $\endgroup$ – hearse May 12 '13 at 17:57
  • $\begingroup$ Sorry I was not clear. What I am saying is that you break apart $w\in\mathbb{R}^n$ into two pieces: $\bar{w}$ is a vector containing the first $n-1$ elements, and $w_n$ is just the last element. I've edited the answer to make this more clear. $\endgroup$ – Michael Grant May 12 '13 at 17:58
  • $\begingroup$ So, the corresponding colums in $S$ are separated as well..right? Thanks for this answer and formulation! $\endgroup$ – hearse May 12 '13 at 18:20
  • $\begingroup$ Yes, that's right. But I just thought of a modification to Geoff's answer that I think renders mine obsolete ;) $\endgroup$ – Michael Grant May 12 '13 at 18:50
  • $\begingroup$ Well that is fine. i do happen to catch on to some basics of optimization, based on different view points. This is surely not my subject of training, but do put forth the modification if you would think it improves the answer. $\endgroup$ – hearse May 12 '13 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.