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.

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there are well known algorithms to solve this. In many cases however, $g$ is not affine. For general $g$ this problem is hopelessly hard to solve, but what if the constraint is easy to solve on its own? In particular, suppose that if we are given $x_1,\ldots,x_{n-1}$, then Newtons method on the constraint $g(x_1,\ldots,x_n)=0$ can easily find $x_n$. Are there effective algorithms to solve the constrained optimization problem in that case?

To solve these kinds of problems I have tried to use Lagrange multipliers, and directly apply Newtons method to solve those (nonlinear) equations, but this does not converge. Something that does work is to add a penalty term for violating the constraint to the objective function, similar to how the barrier method handles inequalities. Unfortunately (but as expected) this is not very fast at getting an accurate answer.

share|improve this question
1  
The fact that it is easy to solve for $x_n$ given all other variables reminds me of coordinate descent method. You can write the full cost function (including the constraint) and then apply coordinate descent. Doesn't it work? –  emrea Sep 22 '12 at 22:09
add comment

2 Answers 2

up vote 1 down vote accepted

Newton's method applied directly on the optimality conditions may not converge because you need a merit function and a globalization mechanism (a line search or trust regions), but it's the right approach. Look up SQP methods in any good optimization textbook. In essence, what you'll do is write the KKT conditions $$ \nabla f(x) + J(x) y = 0, \quad g(x) = 0, $$ (where $J$ is the Jacobian of $g$), apply Newton's method: $$ \begin{bmatrix} H(x,y) & J(x) \\ J(x) & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = - \begin{bmatrix} \nabla f(x) + J(x) y \\ g(x) \end{bmatrix}, $$ and perform, say, a line search for a specific merit function. There are a few tricks, but this is the heart of the method and it's often very successful. You could implement your own toy version of this, but I'd recommend using a solid implementation. For instance, IPOPT will reduce to the above if your problem only has equality constraints.

share|improve this answer
    
Thanks, that's exactly what I was looking for! –  Jules May 7 at 23:55
add comment

If you have a single equality constraint you might try to rewrite your constraint $g(x_1,...,x_n)$ as:

$x_i = h(x_1,...x_{i-1},x_{i+1},...x_n)$

and then substitute for the $i$th variable in your objective function and solve the problem as an unconstraint optimiation problem.

share|improve this answer
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.