5
$\begingroup$

I have a nonlinear inequality constrained optimization problem of the form $$\begin{array}{cc} \min & f(x) \\ \textrm{s.t.} & g(x) \ge 0 \end{array}$$ where $x \in \mathbb{R}^n$, $f : \mathbb{R}^n \to \mathbb{R}$, $g : \mathbb{R}^n \to \mathbb{R}^m$. I am currently solving this system with pseudotransient continuation (3) applied to a semismooth Newton's method (1,2). The semismooth Newton's method encodes the KKT conditions for a local solution to the constrained optimization into a single semismooth equation. Pseudotransient continuation is an unnecessarily fancy name for adding a diagonal term to the gradient of this equation (which includes the Hessian of the energy $f$) and running Newton's method.

Unfortunately, pseudotransient continuation globally convergent only for sufficiently large diagonal adjustments, and my current problem is converging only down to a nasty period two oscillation between two states. Without the constraints, global convergence could be enforced using line search using the original energy function $f$. However, the KKT conditions depend only on the gradient of $f$, not its value, and the original energy is somewhat obscured in the passage to the semismooth equation.

Question: Are there natural ways to perform line search in the context of constrained optimization? Note that it is not sufficient to apply line search to the residual norm, as described by Jed Brown here.

References:

  1. T. De Luca, F. Facchinei, and C. Kanzow (1996), A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical programming, 75(3), 407-439.

  2. F. Facchinei, A. Fischer, and C. Kanzow, A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience.

  3. Kelley, C., Keyes, D. E. (1998). Convergence analysis of pseudo-transient continuation. SIAM Journal on Numerical Analysis, 508–523.

$\endgroup$
  • $\begingroup$ It would help if you added whatever you know about the structure of $f(x), g(x)$: are they linear, polynomial, convex, etc., is there a unique minimum to the problem? $\endgroup$ – Wolfgang Bangerth Jul 10 '13 at 12:47
  • $\begingroup$ Unfortunately the problem is highly nonlinear and nonconvex: it's membrane energy plus self collisions between different triangles. $\endgroup$ – Geoffrey Irving Jul 10 '13 at 16:43
3
$\begingroup$

Yes. Constrained optimization algorithms update their iterates in the same basic fashion as unconstrained optimization algorithms, using updates of the form $x_{k + 1} = x_{k} + \alpha_{k}d_{k} \in \mathbb{R}^{n}$, where $d_{k} \in \mathbb{R}^{n}$ is the direction of the update, $x_{k} + d_{k}$ is feasible, and $\alpha_{k} \in [0, 1]$ is chosen such that $f(x_{k} + \alpha_{k}d_{k}) < f(x_{k})$ using a line search algorithm. (Some variants will set $\alpha_{k} = 1$, and force the direction-finding algorithm to choose and scale $d_{k}$ appropriately in order to achieve convergence.)

Examples of algorithms of this form include feasible direction, conditional gradient, and gradient projection algorithms.

$\endgroup$
  • $\begingroup$ This is the perfect answer for feasible methods. However, at least in some cases the initial guess will be infeasible (generally only for a subset of constraints which are reasonably well behaved), and the semismooth method I'm currently using is infeasible. Is there a natural way to incorporate line search into an infeasible method? $\endgroup$ – Geoffrey Irving Jul 10 '13 at 16:46
  • 1
    $\begingroup$ It's possible. There are some methods that will incorporate line searches into methods whose iterates are not necessarily primal feasible. See, for instance, line search filter methods of the type proposed by Andreas W\"{a}chter and Lorenz Biegler, "Line search filter methods for nonlinear programming: local convergence", SIAM J. Optim., Vol. 16, No. 1, p. 32-48. I'd have to poke around in the literature a bit more to see what other methods are available, because some methods do not employ line searches (and don't update iterates as above). $\endgroup$ – Geoff Oxberry Jul 10 '13 at 21:39
  • $\begingroup$ There are also the methods based on merit functions, though then you must beware the Maratos effect, as well as exact penalty methods. Though I'm unsure how developer either approach is for semismooth methods. $\endgroup$ – cjordan1 Jul 11 '13 at 6:16

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.