For each of the following optimization problems (i) show that it is convex, (ii) write a CVX code that solves it, and (iii) write down the optimal solution and optimal value (by running CVX). You need to write all the above step and publish your codes (using “publish” in MATLAB) in a PDF file. You should upload an electronic version on elearning.
1.
min x21 + 2x1x2 + 2x22 + x23 + 3x1 − 4x2
s.t. 2x2 + x1x2 + 4x2 + 4 + (x1 − x2 + x3 + 1)2 ≤ 6
1 2 x1 + x2
x ≥ 1
2.
min x1 + x2 + x3 + x4
s.t. (x1 − x2)2 + (x3 + 2x4)4 ≤ 5
x1 + 2x2 + 3x3 + 4x4 ≤ 6
x ≥ 0
3.
min |2x1 + 3x2 + x3| + ∥x∥2 +
2x12 + 4x1x2 + 7x22 + 10x2 + 6
x2
+ 1
2
2
2
1
+ 4x1x2 + 2x1x3 + 2x2x3 ≤ 7
s.t.
+ 2x1
+ 5x2
+ 10x3
x2
max{x1 + x2, x3, x1 − x3} ≤ 19
x1
≥ 0
x2
≥ 1.
4.
min
2x12 + 3x22 + x32 + 4x1x2 + 7 + (x12 + x22 + x32 + 1)2
s.t.
(x1 + x2)2
+ x18 ≤ 7
x3 + 1
x21 + x22 + 4x23 + 2x1x2 + 2x1x3 + 2x2x3 ≤ 10
|x1 + x2 − x3|2 ≤ 20
x ≥ 0.
1
5.
x4
x4
min
1
+
2
+ 2x1x2 + |x1 + 5| + |x2 + 5| + |x3 + 5|
x2
x2
2
1
s.t. ((x21 + x22 + x23 + 1)2 + 1)2 + x41 + x42 + x43 ≤ 200 max{x21 + 4x1x2 + 9x22, x1, x2} ≤ 40
x1 ≥ 1
x2 ≥ 1.
6. Suppose that we are given 40 points in the plane. Each of these points belongs to one of two classes. Specifically, there are 19 points of class 1 and 21 points of class 2. The points are generated and plotted by the MATLAB commands
rand(’seed’,id);
x=rand(40,1);
y=rand(40,1);
class=[2*x<y+0.5]+1;
A1=[x(find(class==1)),y(find(class==1))];
A2=[x(find(class==2)),y(find(class==2))];
plot(A1(:,1),A1(:,2),’*’,’MarkerSize’,6) hold on plot(A2(:,1),A2(:,2),’d’,’MarkerSize’,6) hold off
where id should be your student id number. Note that the rows of A1 ∈ R19×2 are the 19 points of class 1 and the rows of A2 ∈ R21×2 are the 21 points of class 2. Write a CVX-based code for finding the maximum-margin line separating the two classes of points.
2
