What is the proper solver for my global optimization problem inside YALMIP?

[Bardia Hassanzadeh]

Hi there,

I have an optimization problem which is subject to a nonlinear DAE system. I used a variant of implicit Runge-Kutta method to discretize my model and form a discrete time model that integrates the DAE system between to consecutive sampling times  'k' and 'k+1', e.g. x(k+1) = phi(x(k),u(k)).

Based on my understanding this would form an algebraic equation (  x(k+1) - phi(x(k),u(k)) =0 ) from my original DAE system. So my question is that: Is it OK to consider my converted system a convex equality constraint and solve my optimization problem using nonlinear solvers as IPOPT, or I have to acquire non-convex global solvers like BARON? (considering the rest of my constraints to be convex and I am seeking the global solution)

Thank you for your time and consideration. 

 

[Johan Löfberg]

An equality is only convex if it is affine, which I presume you don't have. Hence, you need a global approach such as bmibnb, scip or baron if you must have a global solution with globality certificate

[Bardia Hassanzadeh]

Thank you very much for your response. One fundamental question that comes to mind is that my discretized equality constraint is in the form of  (  x(k+1) - phi(x(k),u(k)) =0 ) as the output of ACADO, and I think BMIBNB is proper for twice continuously differentiable constraints; so do you think that BMIBMI is a good choice for my problem or I have to acquire BARON? 

[Johan Löfberg]

Do you mean that phi is not known but the output from a black-box function (the solver acado). Then basically no global solver will be suitable, it is a horribly hard problem. You will have to test different approaches and see. Baron will not solve that type of model (it is only applicable to a short list of explicit nonlinearities, same holds for scip.). bmibnb is applicable but will be insanely slow as it will have to sample the generator phi (through sdpfun) thousands of times per iteration to approiximate its convex bull. In short, deterministic guaranteed global solvers will not work.

[Bardia Hassanzadeh]

Well I don't think that phi is a black box function, because it is a c++ generated function that integrates a known DAE from time K to time K+1 using Implicit Runge Kutta. My concern is that even if I produce Phi by my own code (which will be explicit) and integrate my DAE, I will get a single-continuously differentiable equality constraint  and branch-n-bond methods like BMIBNB might require a twice-continuously differentiable function to guarantee the optimality of its solution. Please correct me if I'm wrong, but should I buy the BARON package for this reason (which does not require a  twice-continuously differentiable function)?

[Johan Löfberg]

A c++ file generating values for inputs would be the classical case of a black-box model.

Baron would definitely not work, since it only is applicable mto stuff modelled, in, e.g., gams or ampl models, with a limited set of nonlinear operators (polynomials, log,exp etc) (or interfaced via matlab, with the same limitations on nonlinear operators)

YALMIP does not assume twice differentiable (in fact, YALMIP does not have any notion of hessians and only works with first derivatives when performing automatic differentiation etc)

[Bardia Hassanzadeh]

I see. Regarding the twice differentiable constraints, Iwould appreciate it if could you refer me to a paper (or its author) on branch-n-bond methods that does not require the twice differentiablity on constraints? Because so far what I have seen from C.A. Floudas and similar authors, they require such a property on constraints. Or if it is not possible could you please refer me to the publications YALMIP implements its branch-n-bond method for global nonlinear optimization?

Thank you very much for your time and consideration.

[Johan Löfberg]

There is nothing in a vanilla LP-based b&b strategy which requires C2 (or even C1 for that matter). All you need is a strategy to generate outer polytopic approximations of the convex envelope (and a nonlinear solver to solve the problems locally of course)

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.BMIBNBTheory