# Line search for constrained optimization

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:

• 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? – Wolfgang Bangerth Jul 10 '13 at 12:47
• Unfortunately the problem is highly nonlinear and nonconvex: it's membrane energy plus self collisions between different triangles. – Geoffrey Irving Jul 10 '13 at 16:43

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.)