Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
You may want to start here and here. –  cardinal Oct 3 '11 at 22:08
1  
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
show 2 more comments

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
I believe $u^Tw=0$ is wrong. –  Wok Oct 26 '12 at 9:06
    
@Wok Why is that? It's the standard complementarity condition. –  Dominique Dec 27 '13 at 0:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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