5
$\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$
2
  • $\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$ May 11 '13 at 12:19
  • 1
    $\begingroup$ @NicoSchlömer The equality $e^{T}w=1$ is equivalent to the pair of inequalities $e^{T}w \leq 1$ and $-e^{T}w \leq -1$. $\endgroup$ Dec 28 '21 at 1:03
5
$\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$
8
  • 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$ 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$ 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$ May 13 '13 at 11:30
3
$\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$
0

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.