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

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.

• How easy is it to project on to the constraints? That is, given a vector $(x_1,\dots,x_n)$, can you easily find a "nearby" vector $(y_1,\dots,y_n)$ such that $g_i(y_1,\dots,y_n)=0$ for a chosen constraint $g_i$? What about simultaneously for all constraints? – Rahul Aug 12 '17 at 21:55
• Not easy. There is no method that guarantees finding a feasible point. – Wazowski Aug 13 '17 at 5:45
• Each nonlinear constraint is a sum of 6 terms like this: $arcos((a+b-c)/(2 sqrt(a b)))$ – Wazowski Aug 13 '17 at 14:00