I'm trying to follow this older paper, page 19.

The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$

By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. $z \ge 0, w \ge 0, z \perp w$

To do this, they form a single large equation: $f(r,w,x,y,z) = \frac{1}{2} r^Tr - y^T(r+Ax-b) - z^T(Gx-w-h)$

And take the partial derivatives with respect to each variable to construct a large system of equations and work from there. I'm fine with their math once the above equation is constructed, but I'm confused where some of the new variables come from.

$r = Ax - b$, so $r$ is just the residual vector that we want to minimize (ideally it's $0$), and they state that at the top of the section. Presumably $y$ and $z$ are something similar, but where they come from seems less clear to me.

I looked in earlier sections in the paper but I don't see anything that explains it.

  • $\begingroup$ Try to make the question a little more self-contained. We are minimizing with respect to $x$? $x$ is a vector? G is square? $\endgroup$ – leonbloy Oct 3 '11 at 20:51
  • $\begingroup$ $G$ isn't square necessarily. We're minimizing w.r.t. $Ax - b$, where $x$ is unknown and $b$ is known apriori (which alone is a classic "least squares" problem) subject to additional hard constraints ($Gx \ge h$), where $h$ is also known apriori. $G$ has size $pxn$ and $A$ has size $mxn$, and $m \ge n$ $\endgroup$ – Jay Lemmon Oct 3 '11 at 21:59
  • 1
    $\begingroup$ You may want to start here and here. $\endgroup$ – cardinal Oct 3 '11 at 22:08
  • 1
    $\begingroup$ And also the dual problem... $\endgroup$ – user13838 Oct 3 '11 at 22:26
  • $\begingroup$ Perhaps I'm wrong, but it would seem that the mininum should occur either in the unconstrained minimum (classical least squares) or in the boundary of the constraint (Gx = h) , in which case Lagrange multipliers should work... $\endgroup$ – leonbloy Oct 3 '11 at 22:27

By defining $r := b - Ax$, you simply restate the objective of the problem as $\|r\|^2$ (in fact, your function $f$ states it as $\tfrac{1}{2} \|r\|^2$, which is an equivalent objective to minimize; the $\tfrac{1}{2}$ neatly cancels out the $2$ that appears when you differentiate). But now you must include this definition of $r$ as a constraint of the problem: $Ax + r = b$. Next, they don't want linear inequality constraint, they only want simple bounds. So they introduce a slack variable $w \geq 0$ such that $Gx - w = h$. Now you're left with the problem $$ \begin{aligned} \min_{x,r,w} & \tfrac{1}{2} \|r\|^2 \\ \text{s.t.} & Ax + r = b, \\ & Gx - w = h, \\ & w \geq 0. \end{aligned} $$ The Lagrangian of this problem is $$ L(x,r,w,y,z,u) = \tfrac{1}{2} \|r\|^2 - y^T (Ax + r - b) - z^T (Gx - w - h) - u^T w. $$ The vectors $y$, $z$ and $u$ are called vectors of Lagrange multipliers (or sometimes, dual variables). The first-order optimality conditions (which are necessary and sufficient here) require that the partial derivatives of $L$ with respect to $x$, $r$, $y$ and $z$ vanish and that $$ u \geq 0, \quad w \geq 0, \quad u^T w = 0. $$ Now the partial derivative of $L$ w.r.t $w$ is $z -u$. Since it must vanish, we must have $z=u$ and we recover the formulation of Golub and Saunders.

If you don't know about Lagrange multipliers, grab the book "Numerical Optimization" by Nocedal and Wright (Springer) and look up the chapter on first-order optimality conditions (also called KKT conditions).

  • $\begingroup$ I believe $u^Tw=0$ is wrong. $\endgroup$ – Wok Oct 26 '12 at 9:06
  • $\begingroup$ @Wok Why is that? It's the standard complementarity condition. $\endgroup$ – Dominique Dec 27 '13 at 0:16
  • $\begingroup$ I don't understand, what's the advantage of this form over this form: math.stackexchange.com/questions/73712/… $\endgroup$ – Royi Feb 21 '17 at 14:03
  • 1
    $\begingroup$ @Royi Do you mean the advantage of adding slack variables? On paper, there isn't much difference, but depending on which method you use to solve the problem, it can make all the difference. $\endgroup$ – Dominique Mar 13 '17 at 15:19

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.