Hi, Johan Löfberg and other friends, I need help in piecewise approximation algorithm with Yalmip

[Yimiao,G]

Hi, Johan Löfberg and other friends,

Thanks for your instruction and help in advance. 

I am new in Yalmip and also a green hand in optimization. 

I used to use C++ console to call Cplex. I have spent so much time in coding and debugging in C++. 

Till some day, my friend told me to use Yalmip instead. 

I think Yalmip is an amazing tool for our researcher. 

Now, I need to use the "Piecewise approximation method " to optimize the convex curve. 

For example, divide the interval [Xmin, Xmax] into 10 sub intervals. Using these 10+1 points to get 11 tangent lines. 

Then using these 11 tangent lines to approximation the convex curve. 

And I don't know, how to code this in Yalmip.

[Johan Löfberg]

Is it in a convex optimization problem (being convex does not necessarily lead to a convex program)

If you have a convex operator in a convex optimization problem, you must derive tangents a_i^Tx + b_i and write as, e.g., minimize t subject to a_i x + b <= t

For instance, if your function is abs(x), the tangents are x and -x. Hence, you can write it as x<= t, -x <=t. Or here, approximating quadratic (the upper bound on t is used here only to obtain a bounded region to plot)

z = (-2:0.1:2)';

A = 2*z;

b = -z.^2;

x = sdpvar(1);

t = sdpvar(1);

plot([A*x+b <= t, t <= 4])

You can write the convex PWA approximation as max(A*x+b) and perhaps make it a bit easier to understand (the t is redundant here, used merely to get something to plot)

z = (-2:0.1:2)';

A = 2*z;

b = -z.^2;

x = sdpvar(1);

plot([max(A*x+b) <= t, t <= 4])

If you are to lazy to derive tangents, you can take a SOS2-style representation, and then simply skip the combinatorial SOS2 constraints. It will give you the same convex region, albeit using many more variables

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.SOS2

xi = (-2:0.1:2)';

fi = xi.^2;

sdpvar x t

lambda = sdpvar(length(fi),1)

F = [x == lambda'*xi, t >=  lambda'*fi,lambda>=0,sum(lambda)==1];

plot([F, t<=4],[x;t])

[Yimiao,G]

Dear Johan Löfberg ,

Thank you so much for your quick and helpful reply. 

I think this function is very powerful. 

The codes in SOS2 example have"F = [sos2(lambda1), sos2(lambda2)]". However, in your reply, you said skip this SOS2. I also want to know what does it do?

Another question is that why should the sum equals to 1, "sum(lambda1)==1"?

Many thanks:)

[Johan Löfberg]

SOS2 modelling is a general way to model nonconvex univariate functions (or convex functions used in a nonconvex setting) using combinatorial (binary variables) constraints. SOS2 essentially says that the linear interpolation only can use two consecutive data-points when interpolating, thus effectively modeling the function exactly between data points.

When you remove the combinatorial SOS2 constraints, you say that your approximation is allowed to take values from anywhere (as long as they some up to 1). This yields a relaxation in the general case but will work in convex models and effectively generate the tangent planes

If you don't force them to add up to one, you will have something very strange. Let us assume your function is y = f(x) = 1. You have two data points x1 = 1 and x2 = 2 and the two data points y1 = 1 and y2 = 1. Now you write x = lambda1*1+lambda2*2 and  y = lambda1*1+lambda2*1. If you use arbitrary lambda, you could for instance write x=1.5 as 1.5 = 0*1+0.75*2 and then you get your approximant y = 0*1+0.75*1, i.e. your interpolated value will be 0.75, which doesn't make sense.

Think of it this way. You interpolate the positions x1 and x2  with values y1 and y2. You can do this as x1*lambda + x2*(1-lambda) with values y1*lambda + y2*(1-lambda) where lambda is *one* scalar between 0 and 1. Generalizing this becomes tricky, so it is easier to use two lambdas x1*lambda1+x2*lambda2 where lambda1 and lambda 2 are positive and sum to 1.

[Yimiao,G]

Dear Johan Löfberg,

Thanks for your clear explanations and your hard work on YALMIP. Yalmip is very convenient. 

BTW, as a researcher, when I play to publish a paper, I should refer you in general way: (this conference paper?)

"YALMIP : A Toolbox for Modeling and Optimization in MATLAB. J. Löfberg. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004. (URL) (BIB)"

 

Am I right?

Thanks again!

[Johan Löfberg]

Correct.