4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$
    – emrea
    Commented Sep 22, 2012 at 22:09

2 Answers 2

5
$\begingroup$

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)^T y = 0, \quad g(x) = 0, $$ (where $J$ is the Jacobian of $g$), apply Newton's method: $$ \begin{bmatrix} H(x,y) & J(x)^T \\ J(x) & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = - \begin{bmatrix} \nabla f(x) + J(x)^T 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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, that's exactly what I was looking for! $\endgroup$
    – Jules
    Commented May 7, 2014 at 23:55
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .