Can fmincon find corner solutions?

I found a problem I could not really understand with fmincon. When the optimal solution is x=0 for a function under a contraint that x>=0, fmincon returns 2.0000e-08. It does not equal 0, though very close to. I wondered why it happenend and how I can get the correct result which is 0 instead of 2.0000e-08.

The example below is simple, but it shows the problem.

-------------script1: set up function

function cor = corners(ivm);

cor=ivm

end

-------------script2: use fmincon

fun = @(ivm)corners(ivm);

problem = createOptimProblem('fmincon','x0',0,...

'objective',fun,'lb',0,'ub',[]);

[cx,fval,exitflag,output,lambda,grad,hessian] = fmincon(problem)

-------------the results I get:

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in

feasible directions, to within the default value of the optimality tolerance,

and constraints are satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

cx =

2.0000e-08

fval =

2.0000e-08

exitflag =

1

output =

struct with fields:

iterations: 7

funcCount: 17

constrviolation: 0

stepsize: 1.9739e-06

algorithm: 'interior-point'

firstorderopt: 2.0000e-08

cgiterations: 0

message: 'Local minimum found that satisfies the constraints.↵↵Optimization completed because the objective function is non-decreasing in ↵feasible directions, to within the default value of the optimality tolerance,↵and constraints are satisfied to within the default value of the constraint tolerance.↵↵Stopping criteria details:↵↵Optimization completed: The relative first-order optimality measure, 1.999988e-08,↵is less than options.OptimalityTolerance = 1.000000e-06, and the relative maximum constraint↵violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-06.↵↵Optimization Metric Options↵relative first-order optimality = 2.00e-08 OptimalityTolerance = 1e-06 (default)↵relative max(constraint violation) = 0.00e+00 ConstraintTolerance = 1e-06 (default)'

lambda =

struct with fields:

eqlin: [0×1 double]

eqnonlin: [0×1 double]

ineqlin: [0×1 double]

lower: 1.0000

upper: 0

ineqnonlin: [0×1 double]

grad =

1

hessian =

6.4000e-05

-------------when I clicked "stopping criteria details", I get:

Optimization completed: The relative first-order optimality measure, 1.999988e-08,

is less than options.OptimalityTolerance = 1.000000e-06, and the relative maximum constraint

violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-06.

Optimization Metric Options

relative first-order optimality = 2.00e-08 OptimalityTolerance = 1e-06 (default)

relative max(constraint violation) = 0.00e+00 ConstraintTolerance = 1e-06 (default)

-------------possible reasons I am thinking of:

1. fmincon can't identify corner solutions properly
2. something to do with one of the tolerances
3. the gradient at x=0 is not 0.

It looks like the reasons are shown in the command window, but I couldn't really understand it. I would appreciate your help and detailed explanations. Thanks!

[John D'Errico]

Numerical optimization tools like fmincon or fminunc, fminsearch, etc., don't return exact solutions. They cannot do so, since they are iterative schemes. They stop when they think they are sufficiently close, based on convergence tests. That does not mean you can reduce the tolerances to zero though.

Remember that in floating point arithetic, you should NEVER assume those last few digits are correct anyway.

[Kailin]

Thanks a lot John!

I wondered whether there is any other algorithm that can generate the exact solution 0 instead of 2e-08. Any comments would be appreciated.

[Matt J]

Only a symbolic solver could do that, if there even is such a thing out there.

[John D'Errico]

Yes. You absolutely NEED a symbolic tool to find an exact solution. What is not clear is if your problem has an analytical solution, since we do not see the problem itself.

[Kailin]

Thank you very much John and Matt! I find that my problem actually has a analytical solution. I worked it out and the program is much faster (because I don't need to use fmincon)! Really appreciate your help and inspiration.