# How to test convergence of an algorithm for constrained optimization

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!

• If your gradient norm isn't shrinking, or staying fixed at a single value, then the algorithm is definitely not converging. Maybe a bug in how you are calculating iterations? – Jeff-Inventor ChromeOS Aug 5 '14 at 8:41

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$

• Thank you so much for your help! I think there is something wrong with my Hessian, because the finite difference error || Hessian(x)*v - (gradient(x + h*v) - gradient(x))/h ||, where h is a scalar, x and v are vectors, increases as h decreases and decreases as h increases. I tested the same thing with the gradient and the function and the results look fine, though (so I don't think my test is wrong). I have checked my Hessian computation multiple times but still cannot find any errors. Could you give me some hints what I should do in this case? – Mathematics Curious Jul 30 '14 at 10:15
• I have a separate code that computes the Hessian-times-vector and another code that computes that gradient. My PDE constraint for this problem is linear. For the nonlinear PDE case, the Hessian finite difference test looks fine (the error decreases as h decreases and vice versa), but the Hessian is not positive definite at x = zeros(n,1) and the method/code only works for certain sets of parameters. – Mathematics Curious Jul 30 '14 at 10:18
• If the Hessian is not positive definite, then Newton's method will fail, and you would be better off with a quasi-Newton or trust-region method (such as Steihaug's). I'm not sure if your test for the Hessian is sufficient; you want to check directly whether it's a second derivative for the functional. I'll edit my answer. – Christian Clason Jul 30 '14 at 12:29