Discussion on Nonlinear Solvers

[Aras]

I know this is not related to YALMIP even though I use YALMIP. Just a friendly discussion is what I am looking for.

1) I solve something like the following many times:

Objective = -(d'*u + d'*V*w - (1+d'*r)*sum(w.*log(w))); 

optimize(Constraints,Objective,sdpsettings('solver','ipopt'));

This is clearly convex, but a hard objective of entropy form. The thing is, ipopt is very slow and most of the times it can not solve the problem / or gives 'Restoration Failed!'

When I instead use knitro, it solves very fast without any errors. 

I believe it is due to the fact that ipopt uses interior points, and the barrier methods suffer w*log(w) when w is almost 0. Am I correct?

2) This is directly related to Ipopt. I think IPOPT is a general purpose local optimality solver. Am I wrong?

However, when I run a problem of form:

x = sdpvar(n,1);

Constraints = [D*x <= d, x>=0 ];

Obj = log(sum(exp(A*x)));

tic

optimize(Constraints, -Obj, sdpsettings('solver', 'ipopt','ipopt.max_iter',999999));

toc

value(Obj)

Ipopt eiher returns "EXIT: Optimal Solution Found", and I am sure that in all my examples these are global optimum; or does not return anything and exceeds the max cpu time etc. Do you have any idea about this behavior?

Thank you for your time :)

Best regards,

[Johan Löfberg]

First, you should use high-level operators when possible, as this will improve derivative computations etc, and avoid various iintroduction of internal normalizing variables etc (and the issues at 0 as you note)

In your case

w = sdpvar(10,1);
% Elementwise blind definition
optimize(0 <= w <= 1,sum(w.*log(w)),sdpsettings('debug',1,'solver','ipopt'))

% Let YALMIP know what you are doing, and derivatives will be computed quicker and better
optimize(0 <= w <= 1,-entropy(w),sdpsettings('debug',1,'solver','ipopt'))

Same thing with the logsumexp opeartor (although you maximize the expression, and logsumexp is convex, so one might argue your use of the log operator. Perhaps the objective is nicer than without it, but you still have nonconvexity)

The reason ipopt performs badly is because ipopt is extremely sensitive to Hessian computations of objective in my experience, and YALMIP does not deliver any Hessian so it has to realy on its quasi-Newton stuff. Sometimes it helps by simply moving the objective to the constraints

[Aras]

That's very good to know. I didn't know about the entropy command (also logsumexp)! I can try taking the log after the solution arrives. 

However, I am still not sure about the second issue I mention. Why do you think if ipopt returns it is global optimum? Can ipopt understand global optimality? If not, why doesn't it return any local solution (it is very fast in my setting)? 

Thank you!

[Johan Löfberg]

ipopt simply isn't good at estimating hessians / has an algorithm which is sensitive to hessian estimate (in its default setting)

The following trivial QP with a reasonable but non-trivial conditioned hessian fails miserably in naive implementation using ipopt, but is solved without issues when the curvature is moved away from objective

n = 3;

x = sdpvar(n,1);

R = randn(n);

S = diag(linspace(1,1000,n))

Q = R'*S'*S*R;

optimize([],(x-1)'*Q*(x-1),sdpsettings('solver','ipopt'))

e = sdpvar(n,1);

optimize([e == S*R*(x-1)],e'*e,sdpsettings('solver','ipopt'))

In more general setting, replacing objective f(x) with t and minimizing t with added constraint t>= f(x) can be a trick in some cases. Another trick is to use another solver and/or not use YALMIP has an interface to ipopt when hessian is crucial

if you solve a nonconvex problem using a local solver such as ipopt, you have no guarantee that the globally optimal solution has been found (it might very well be, but you have no certificate of this)

[Aras]

That is pretty clear. Thank you!