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.
Best Answer
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.