An interpreter for optimisation problem

Specific domains Optimization
1

Hello,

Coming back to Scilab after a long time, I’ve started updating some old project. In particular, a tool aimed at simplifying the process of formulating optimisation problem.
It started from my curiosity concerning Yalmip on matlab and while it may not reach the same level, I still have good hopes to make it useful.

The code is available on github: GitHub - pivui/sopi: Scilab toolbox for parsing optimisation problem

For the time being, it is able to parse linear problems and solve them with a builtin simplex (that I would not fully trust) or scilab interior point karmakar. For instance,

sopi_begin;
// Declaration of optimisation variables 
x1          = sopi_var(1);                 
x2          = sopi_var(1);
x3          = sopi_var(1);
x4          = sopi_var(1);
// Objective function
fun         = x1  + 2*x2 + 3*x3 + 4*x4   
// Constraints
c1          = x1 + x2 + x3 + x4 == 1
c2          = x1 + x3 - 3*x4 == 1/2
c3          = x1 >= 0
c4          = x2 >= 0
c5          = x3 >= 0
c6          = x4 >= 0
// Problem formulation
p               = sopi_min(fun, list(c1, c2, c3, c4, c5, c6));
// Problem resolution
[xopt1, fopt1]    = sopi_solve(p,'sopilp');
[xopt2, fopt2]    = sopi_solve(p,'karmakar');

It is very early in (re)development and probably full of bugs but feedbacks are welcome.

1 Like
2

Hi all,

I have added some basic support for piecewise affine problems that can be converted to LP problems.

For instance:

sopi_begin;
n           = 3;
W           = rand(n,n);
d           = rand(n,1);
xMax        = 5*rand(n,1);
A           = rand(2,n);
b           = 20*rand(2,1);
// Problem formulation                                
x           = sopi_var(n);                 
LB          = x >= 0;                      
ci          = A*x <= b;
ce          = x(2) == xMax(2);
fun         = norm(W*(x - d),1);             
problem     = sopi_min(fun,list(LB,ce,ci));
// Problem resolution 
[xopt, fopt] = sopi_solve(problem,'sopilp');
[norm(W * (xopt.x - d),1), fopt]
3

Hello,

Welcome to Scilab’s Discourse and thanks for this initiative ! Could you quickly list the type of optimization problems that you currently consider and the Scilab solvers you plan to use ?

S.

4

Hello,

On the modelling side: Currently, the following problems should be correctly parsed:

  • linear problems,
  • convex piecewise affine problems, i.e. problems involving max/abs of linear elements.

In a somewhat short term, I will add support for

  • quadratic problems: quad. objective and linear constraints,
  • and everything that does not fit above will fall as general “non-linear” problem. Supported functions (scalar mainly) will be added incrementally. The idea is to generate scilab code for the associated non-linear functions/constraints (and their derivatives) to feed the solvers.

In the longer term, I may add support for:

  • shades of convex problems, e.g. : SOCP, SDP,
  • integer variables
  • extend the support for “exotic” matrix operations or functions

On the solver side: I only plan to interface with available solvers (and write some, but that is for fun) hence it is quite fast to do:

  • linear problems: karmarkar, linpro (from atoms, I have the interface but the install fails at the moment)
  • convex quadratic: qld, qp_solve, quapro (from atoms, same issue as above)
  • SDP: semidef
  • unconstrained NLP: optim_qn/gc/nd
  • box constrained NLP: opim_qn/gc
  • every NLP in general: sci-IPopt (from atoms)

Actually, I am not aware of the status of each optimisation package on atoms, so this may change. Since you are (or have been) involved in a number of those packages, you may have some insights on this point?

5

Hello,

Some updates:

  • quadratic element should be parsed correctly now,

  • qld and qpsolve have been interfaced to solve convex QP problems,

  • some demos files have been added, and in particular some “applications”:

    • demoPolyFit.sce: fit a polynomial with “noisy” data (as a LP)
    • demoLinearMPC1.sce: predictive control of a double integrator (as a convex QP)

→ suggestions for demos are welcome.

NLP are a bit more annoying to deal with that I initially thought but basic support is on its way.