How to approximate convex separable non-linear problem as LP using interp1 ?

[JackJack]

Dear Professor Johan Lofberg,

I am trying to solve this convex separable optimization problem (toy example) by approximating it as a linear programming problem





The linear programming approximation (approximation with x_i in the close segment [0 8]) would look like


Is is possible to construct this formulation using YALMIP interp1 ?

https://yalmip.github.io/command/interp1/

The documentation above  said that yalmip will "creating mixed-integer sos2-based approximation". What worry me is that I dont want mixed integer problem. I just want to construct this optimization problem and solve it naturally.

Is is possible to do so using YALMIP interp1 ?

Thank you for your enthusiasm !

Best regard

Tuong

[Johan Löfberg]

If you approximate a convex function and know this, you can explicitly use 'graph'. If you're not sure, use 'lp' and yalmip will use 'sos2' or 'graph' depending on what is possible. It is all described in the page

[JackJack]

Dear Professor Johan,

I am so sorry that I do not understand your idea 😢 .

I have search for the command 'graph' and 'lp' at this page https://yalmip.github.io/allcommands but I could not find any use of them.

 Could you elaborate more on your idea ?

Thank you and best regard,

Tường

[Johan Löfberg]

they are options to the interp1 command

[JackJack]

Dear Professor Johan,

Thank you so much for your guidance. 

If I understand it correctly, do you mean that if I am trying to approximate (using linear segment) a function that is already convex then I should you the 'graph' option of the interp function right ?

[Johan Löfberg]

xdata = (-1:0.01:1);
f1data = xdata.^2
f2data = xdata.^3
sdpvar x

% Ok, leads to graph representation since f1 is convex
y = interp1(xdata,f1data,x,'lp')

optimize([],y,sdpsettings('solver','linprog'))

% ok as f1 is convex

y = interp1(xdata,f1data,x,'graph')

optimize([],y,sdpsettings('solver','linprog'))

% Fails as linprog doesn't support sos2

y = interp1(xdata,f1data,x,'sos2')

optimize([],y,sdpsettings('solver','linprog'))

% Fails as f2 nonconvex and thus cannot use graph

y = interp1(xdata,f2data,x,'graph')

optimize([],y,sdpsettings('solver','linprog'))

% Fails as f2 nonconvex and 'lp' thus leads to sos2

y = interp1(xdata,f2data,x,'lp')

optimize([],y,sdpsettings('solver','linprog'))