Linear Least Squares with Linear Inequality Constraints

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.

• Try to make the question a little more self-contained. We are minimizing with respect to $x$? $x$ is a vector? G is square? – leonbloy Oct 3 '11 at 20:51
• $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$ – Jay Lemmon Oct 3 '11 at 21:59
• You may want to start here and here. – cardinal Oct 3 '11 at 22:08
• And also the dual problem... – user13838 Oct 3 '11 at 22:26
• 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... – 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.
• I believe $u^Tw=0$ is wrong. – Wok Oct 26 '12 at 9:06