Homework 5
Important submission instructions:
• All explanations and answers must be clearly and neatly written. Explain each step
in your solution. Your solutions should make very clear to the instructor that you
understand all of the steps and the logic behind the steps.
You are allowed to discuss the homework problems with other students (in particular
via Canvas discussion board). However, what you hand in should reflect your own
understanding of the material. You are NOT allowed to copy solutions from other
students or other sources. Also, please list at the end of the problem set the sources
you consulted and people you worked with on this assignment.
• The final document should be saved and submitted as a single .pdf file, and please
be sure all problem solutions are presented starting from the first to the last (that
is, the first solution must correspond to problem 1 and the second to problem 2 and
so on).
• Typed submissions (for example in LaTeX) will be positively considered in the
grade. Overleaf is an easy avenue to start learning LaTeX. See the tutorials at
https://www.overleaf.com/learn
• Very important: Honor code applies fully. You must submit your own work only.
In particular, it is prohibited to post the following problems on any website/forum
or any other virtual means (for example Chegg).
Problem 0
Which of the following sets are convex? Justify either by definition or some other formal
way.
1. The set {x E R³ : ai ≤ xi ≤ bi, i
2. The set {x R²0 : x1×2 ≥ 1}.
== 1,
, n}, for ai, bi Є R.
3. The set of points closer to a given point than a given set:
where SCR”.
{x € R” : ||x − x0||2 ≤ ||x − y||2 for all y € S},
4. The set {x ЄR" : x + S₂ ≤ S₁}, where S1, S2 CR" with S₁ convex. Problem 1
Consider the following sets:
(a) A = {(x1, x2) ЄR²: |x1|+|x2| ≤ 1};
(b) B = {x € R³ : 0 ≤ x1 ≤ x2 ≤ x3}; Hint: Recall {x: Ax ≤ 0} is a convex cone;
(c) C = {x R2 x2 ≤ x}};
:
(d) D = {(x1, x2, x3) Є R³ : √√√x² + x ≤ x3};
For each set:
1. Prove or disprove it is convex.
2. Prove or disprove it is a cone.
3. Determine the extreme points (if convex).
4. Determine the recession cone (if convex).
Problem 2
Consider the set of all non-decreasing functions ƒ : R → R. Prove or disprove it is a
convex cone.
Problem 3
Let be a set of n elements.
1. Describe the set P of all probability distributions (probability mass functions) sup-
ported on .
2. Show that P is convex.
3. Determine the extreme points of P.
Problem 4
K = {x R 0 ≤ x ≤ x2 < ... < xn}
Compute the polar cone K°. Problem 5
Consider the following optimization problem:
minimize -10x1 - 2x2 + x3 + 5x4
s.t.
2x1x3x4 = −5
4x1 x22x4 = 3
x > 0
1. List all basic solutions indicating which ones are feasible.
2. What is the solution of the problem?
Problem 6
Consider the optimization problem:
maximize (2xy)² + ( y − z)² + ( − 1)2
s.t. x+2y+ 3z = 1
x, y, z≥ 0
1. What is the solution of the problem?
2. What is the solution of the probem if the objective function is f(x) = z +1?
3. What is the solution of the probem if the objective function is f(x) = x+z+1?
Problem 7
Consider the following problem
minimize log(y2 — x²)
-
s.t. x² + y ≤1
2x - y ≤0
y ≥ 1/2
x ≥ 0
What is the solution of the problem?
Problem 8
Consider P
=
{x = R^ : Ax = b,x > 0} where A = Rmxn. Assume the rows are l.2.
For each one of the following assertions, state whether it is true or false. If true,
provide a proof, else, provide a counterexample. 1. If n = m + 1, then P has at most two basic feasible solutions.
2. The set of all optimal solutions is bounded.
3. At every optimal solution, no more than m variables can be positive.
4. If there is more than one optimal solution, then there are uncountably many optimal
solutions.
5. If there are several optimal solutions, then there exist at least two basic feasible
solutions that are optimal.
6. Consider the problem of minimizing max{c¹x, d³ x} over the set P. If this problem
has an optimal solution, it must have an optimal solution which is an extreme point
of P.
Problem 9
Implementing and Applying Support Vector Machines (SVM)
Part 1: Implementing SVM with Synthetic Data
• Implement a linear SVM classifier using CVXpy.
Create a synthetic dataset with two features and a binary target variable. En-
sure that the data is linearly separable. Visualize the dataset using a scatter plot,
distinguishing the two classes with different colors.
Your implementation should include the formulation of the hard and soft SVM
optimization problem. Apply the SVM model to the synthetic data and find the
optimal hyperplane.
Visualize the optimal hyperplane along with the margin and support vectors on the
scatter plot of the synthetic dataset. Discuss the role of support vectors in SVM.
Calibrate the parameter (soft formulation).
Part 2 (bonus credit): Applying SVM to a Real-World Dataset
• Choose a well-known dataset that is suitable for binary classification. Examples
include the Iris dataset (selecting two of the three species) or the Breast Cancer
Wisconsin (Diagnostic) dataset.
• Preprocess the dataset as necessary.
• Apply the SVM model implemented in Part 1 to the selected dataset.
• Evaluate the model's performance using appropriate metrics such as accuracy, pre-
cision, and recall. Compare these results with a baseline model, such as logistic
regression. • Discuss how well the SVM model generalized from the synthetic data to the real-
world data.
• Reflect on the strengths and limitations of SVMs based on your observations.
• Reflect on the difference in results between synthetic and real-world data and what
this implies for the application of SVM in practical scenarios.
