(Solved)DATA130026 Optimization Assignment 4

Description

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 x²₁ + 2x₁x₂ + 2x²₂ + x²₃ + 3x₁ − 4x₂

_{s.t. 2x}2 _{+ x1x2 + 4x}2 _{+ 4 +} ^{(x1 − x2 + x3 + 1)2} _{≤ 6}

^{1 2} x₁ + x₂

x ≥ 1

2.

min x₁ + x₂ + x₃ + x₄

s.t. (x₁ − x₂)² + (x₃ + 2x₄)⁴ ≤ 5

x₁ + 2x₂ + 3x₃ + 4x₄ ≤ 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

x²₁ + x²₂ + 4x²₃ + 2x₁x₂ + 2x₁x₃ + 2x₂x₃ ≤ 10

|x₁ + x₂ − x₃|² ≤ 20

x ≥ 0.

5.

	x4	x4
min	1	+	2	+ 2x1x2 + |x1 + 5| + |x2 + 5| + |x3 + 5|
	x2		x2
	2	1

s.t. ((x²₁ + x²₂ + x²₃ + 1)² + 1)² + x⁴₁ + x⁴₂ + x⁴₃ ≤ 200 max{x²₁ + 4x₁x₂ + 9x²₂, x₁, x₂} ≤ 40

x₁ ≥ 1

x₂ ≥ 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 A₁ ∈ R^19×2 are the 19 points of class 1 and the rows of A₂ ∈ R^21×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