Effective methods to minimize a convex smooth energy with nonlinear smooth equality constraints

Question

I have a convex and smooth function $f(x_1, \dots, x_n)$ which I would like to minimize subject to a set of nonlinear equality constraints $g_i (x_1, \dots, x_n)=0$ for $i = 1, \dots, m$.

The $g_i$'s are smooth functions but since they are not affine, i.e., the entire problem is nonconvex and relatively hard to solve. There are no inequality constraints.

I am trying to figure out the best alternative for a numerical optimization method for such a problem.

I can think of several alternatives. I would be happy to hear pros and cons as well as better alternatives before I try all these.

1. Use sequential convex programming. That is, solve a convex problem iteratively till convergence. In each iteration the nonlinear constraints can be linearized and the Jacobian of the constraints can be added to the system as linear constraints. Each such convex problem in each iteration can be solved with Newton's method with line search. The expression of the Hessian is relatively simple.

2. A similar approach but instead of computing the global minimizer of the convex problem in each iteration (with the linearized constraints) do a single Newton iteration. In other words, have one loop only and in each iteration update the Hessian of the energy, the gradient and the Jacobian of the constraints.

3. Instead of linearizing the constraints, use the Lagrange multipliers method. In this way we get rid of the constraints and convert the problem into an unconstrained method. In this case the energy (Lagrangian) is a sum of convex and nonconvex functions. I can use the Newton's method to minimize this nonconvex function but for that I will need the Hessian of the Lagrangian (which is harder to obtain than the Jacobian of the constraints). It wasn't clear to me whether I need to modify the Hessian of the Lagrangian such that it becomes positive definite or not. This method seems to be the most difficult to implement so I wonder if there is a benefit over the others.

Any other suggestion are welcome.

Answer 1

If you use Lagrange multipliers, you will obtain an unconstrained problem in which the objective function is the sum of a convex and a nonlinear differentiable function. You can exploit this structure, for example, with this method.

Disclaimer: The paper was found after a quick search. I am not sure if this is the state of the art, but at least can be a starting point for you.

Hope this helps