1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Rahul Aug 12 '17 at 21:55
  • $\begingroup$ Not easy. There is no method that guarantees finding a feasible point. $\endgroup$ – Wazowski Aug 13 '17 at 5:45
  • $\begingroup$ Each nonlinear constraint is a sum of 6 terms like this: $arcos((a+b-c)/(2 sqrt(a b)))$ $\endgroup$ – Wazowski Aug 13 '17 at 14:00
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In my case the convex part is also differentiable and I would like to take advantage of that. Also, do I really need to minimize the Lagrangian like you suggest or just find a saddle point? $\endgroup$ – Wazowski Aug 13 '17 at 14:03
  • $\begingroup$ In the augmented lagrangian\penalty function method, you will iteratively find a stationary point of an unconstrained problem. You could use the method I suggest you to do that. So, you would be implementing the augmented lagrangian\penalty function method and as a subroutine computing stationary points with the proposed method; therefore exploiting the convexity assumption $\endgroup$ – John D Aug 13 '17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.