How to test convergence of an algorithm for constrained optimization

Question

I am applying an iterative method (projected newton) to an optimization problem. Theoretically, the method should converge linearly. I would greatly appreciate it if you could share how should I test the convergence and which stopping criteria should I use?

I used the gradient norm (gradient of the objective function) as the stopping criteria but the results look weird. The norm only decreases from 1e-01 to 1e-02 and then stays at 1e-02 forever--the gradient norm does not decrease any more.

However, the first order necessary condition for the optimization problem says that the gradient should be zero at the solution --> which means we expect to see really small gradient norm, right? --> **Is the gradient norm of order 1e-02 small enough or still big?**

Thank you so much!

Answer 1

The first order necessary optimality conditions for a minimization problem with inequality constraints are not that the gradient vanishes, since the minimum can be attained at the boundary of the feasible set (where only the directional derivatives into the interior of the set have to be non-negative, i.e., going away from the boundary leads to an increase in function value).

Specifically, for a problem of the form $$ \min_{x\in C} f(x)$$ for a convex set $C$, the necessary optimality conditions for a minimizer $\bar x \in C$ are $$ \langle \nabla f(\bar x), \bar x-x \rangle \leq 0\qquad \text{for all }x\in C.$$ For this condition, there is no sensible way to define a residual. But one way to reformulate this condition is using the metric projection $P_C$ onto $C$ as $$ \bar x = P_C(\bar x - \nabla f(\bar x)),$$ so you could monitor $$ r(x^k) := \| x^k - P_C(x^k - \nabla f(x^k))\|,$$ which should go to zero.

That being said, if your minimizer $\bar x$ lies in the interior of $C$, either of these conditions can only hold if the gradient vanishes. If this is the case in your problem, your gradient norm should go to zero -- and $10^{-2}$ is definitely not zero. If your derivatives are correct, then the norm should go to zero up to machine precision (say, $10^{-16}$). Otherwise the method is limited by the accuracy of your gradient and Hessian evaluation, so I'd suspect that there's an error there (which you can check by comparing directional derivatives via inner products of the gradient with a direction and via finite difference approximations).

EDIT: To test whether your gradient and Hessian are suitably accurate approximations of derivatives of your functional, you can do the following:

1. Gradient: Pick $x$ and direction $h$ (e.g., $h=x$ or $h$ random -- always test multiple vectors!) and compare for $\varepsilon \to 0$

   a) $(f(x+\varepsilon h)-f(x))/\varepsilon$

   b) $\langle \nabla f(x),h\rangle$

2. Action of Hessian: $x,h$ as above and compare for $\varepsilon \to 0$

   a) $(f(x+\varepsilon h)-2f(x) +f(x-\varepsilon h))/\varepsilon^2$

   b) $\langle [\nabla^2 f(x)h],h\rangle$