fmincon interior point stopping criteria

Greetings,

1. MY PROBLEM) I'm using fmincon's interior point algorithm. I want to stop the computation if the distance f(x_k) - f(x_opt) <= epsilon where x_opt is the optimum and x_k is the point generated by the algorithm at iteration k.
2. MY TRIALS) I'm seaching for an option to stop computation when the 'mu' of the problemmin f(x) - mu (sum BarrierFunctions(x))is less than a fixed parameter but I don't have found nothing.

I've read the documentation on the stopping criterias, TolFun doesn't seems to do what I want and the only things that refers to the 'mu' is the starting value. Thanks for your help.

[Devyani]

Also, can you tell what is the stopping criteria for fmincon: interior point methods? Like is it TolX or TolFun or first order optimality?

Answer 1

[Alan Weiss]

If somehow you know x_opt, then you can write an output function to do what you want.

But usually you don't know x_opt. I mean, if you did, then why are you running an optimization? And if you don't know x_opt, then how can you possibly write a stopping criterion that depends on x_opt?

Alan Weiss

MATLAB mathematical toolbox documentation

[R L]

It depends on the Algorithm and on the Hypothesis, the interior point (barrier method) or the Frank and Wolfe methods (i've said first two that come to my mind) offer this possibility.

In particular in the case of the barrier method (as the documentatio on the optimization tool saids) a sequence of problems in the form

min f(x) - mu (sum BarrierFunctions(x))

(where BarrierFunction(x) is a logaritmic term in the constraint) are solved. This implies that the solution found at each step is

(constraints number)*mu suboptimal.

Knowing the number of constraints and the mu at iteration k a stopping criteria could be written. Obviously modulo programming interface.

In addition, another possibility for convex functions is to imposing a stopping criteria on the complementary slackness condition. This term is considered by the 'First Order Optimality Condition' as said in the TolFun option documentation. Unfortunately, also the Lagrangian Stationarity condition is taken into account (complementary slackness furnish the bound if the Lagrangian Stationarity is achieved not if it is approximated*) and therefore TolFun hasn't enought expressivity.

*In some case (bounded convex feasible region, convex function) this could be bypassed but the bound would result less significative.

Answer 2

[Matt J]

(1) For each x_k, you will need to find a minorizing surrogate function Q(x;x_k), i.e., it satisfies Q(y;x_k)<=f(y) for all y with equality at y=x_k. You must find such a function that is easy to minimize analytically over the feasible set. Then,

     f(x_k) - f(x_opt)<=f(x_k)- min_y Q(y;x_k)

For a good choice of Q(), the right hand side will --->0 as x_k-->x_opt and you can monitor when it falls below your desired epsilon.

For example, in unconstrained problems in which a global lower bound on the Hessian eigenvalues L is known, you could construct the quadratic surrogate

     Q(y;x_k)= f(x_k)+ dot(grad(x_k),y-x_k)+ L/2*norm(y-x_k)^2

whose minimum is f(x_k)-grad(x_k)/(2*L). This leads to the upper bound

   f(x_k) - f(x_opt) <= grad(x_k)/(2*L)

so you would stop when grad(x_k)<= 2*L*epsilon.

(2) You should be able to reverse engineer mu from the Lagrange Multiplier equations for sub-problem (6-51) in the interior point algorithm documentation. Note that in addition to knowing the minimizing x, you also know the minimizing slacks s_i from the constraint g(x)+s=0.