Description
1 Convex Sets
1. Prove that if sets S1 and S2 are convex sets in R
n
, then their intersection S1 ∩ S2 is a convex
set, using the definition of convex sets.
Hint: This should be an easy argument following from the definition. Also, we always take an
empty set as a convex set.
Remark: This exercise tells us an important property that the intersection of two convex sets
is a convex set, in short we say, intersection preserves convexity.
2. Extend the above result to argue that S1 ∩ S2 ∩ … ∩ Sm is convex if all S1, . . . , Sm are convex
sets in R
n
for any m ≥ 1.
3. Show that a halfspace H+ = {x ∈ R
n
: a
>x ≥ b} is a convex set using the definition of a
convex set.
4. Show that a hyperplane H = {x ∈ R
n
: a
>x = b} is a convex set by using the conclusion of
questions 1 and 3.
5. Argue that a polyhedron is always a convex set by using the results from questions 2 and 3.
6. Show that the convex hull S of a finite number of points x
1
, . . . , x
m in R
n
is a convex set.
Hint: Use the definition of a convex set.
7. Give an example to show that a nonempty convex set may not be the convex hull of a finite
number of points.
8. Draw the following sets by hands using ruler and pencil (your circles do not have to be perfect).
State if each set is a convex set, and list all the extreme points of each set. If a set does not have
an extreme point, just say so. Hint: The definition of an extreme point applies to nonconvex
sets.
(a) T1 = {x ∈ R
2
: x1 + x2 ≤ 1}.
(b) T2 = conv −1
1
,
−2
0
,
−1
−1
,
1
−1
,
2
0
,
1
1
,
0
0
.
(c) T3 = {x ∈ R
2
: |x1| + |x2| ≤ 1}.
(d) T4 = {x ∈ R
3
: |x1| + |x2| + |x3| ≤ 1}.
(e) T5 = {x ∈ R
2
: 1 ≤ x
2
1 + x
2
2 ≤ 4}.
(f) T6 = {0, 1, 2, 3, 4} ⊂ R.
1
2 Convex Functions
1. Give an example of a function f : R → R that is both convex and concave.
2. Let f1 : R
n → R and f2 : R
n → R be two convex functions. Prove that the sum f = f1 + f2
is always a convex function. What about af1 + bf2 for any nonnegative constants a, b? Hint:
This should be a straightforward argument from the Jensen’s inequality, and this shows linear
combination of convex functions with nonnegative weights is again a convex function.
3. Let f1 = |x| and f2 = |x+1|. Notice that both f1 and f2 are convex functions. Let f = f1−f2.
Draw f1(x), f2(x), and f(x) for x ∈ [−2, 2] on the same plot by hand, i.e. using ruler and
pencil on a piece of paper by hand. Is f a convex function on [−2, 2]? Hint: Your answer
should show that the difference of two convex functions may not be a convex function any
more. Contrast this with the previous question.
4. Let f0 = x
2
, f1 = (x − 1)2
, …, fk = (x − k)
2
for all x ∈ R. Let gk(x) = max{f1(x), …, fk(x)}
for all x ∈ R. Draw f0, f1, f2, and g1(x) and g2(x) on two separate plots. Are they convex
sets?
5. Let f1(x), …, fk(x) be convex functions on R. Prove g(x) = max{f1(x), . . . , fk(x)} is a convex
function. Hint: Use the Jensen’s inequality and a similar argument that you used in Homework
1 for proving a similar result. This exercise shows that the pointwise max operation preserves
convexity of functions.
6. Define a set S = {(x, y) ∈ R
2
: y = sin(x)}, i.e. S is the graph of the sine function on the
entire real axis. Draw S. Is S a convex set in R
2
? Find the convex hull of S by drawing
it. Write down the inequalities that define the convex hull of S. Hint: This exercise requires
you to find the convex hull of an infinite number of points. Your intuition of how to form the
convex hull of a finite number of points should suffice to guide you.
3 LP geometry and the simplex method
1. Consider the following linear program:
min −2×1 − 3×2
s.t. x1 + x2 ≤ 4
−x1 + x2 ≤ 2
x1 − x2 ≤ 2
x1 ≥ 0, x2 ≥ 0.
Draw the feasible region of this linear program.
2. To solve this problem using the simplex method, first transform it into a standard form LP.
Denote x = [x1, x2, x3, x4, x5]
> as the vector of variables, and use the standard form notation:
min c
>x
s.t. Ax = b, x ≥ 0,
specify c, A, b for the above problem.
2
3. Now we want to solve the above standard-form linear program by the simplex method. If in
an iteration of the Simplex method, there is any ambiguity about which nonbasic variable to
enter the basis or which basic variable to exit the basis, use the Bland’s rule.
(a) For each iteration of the simplex method, write down the following information in the
format given below:
• Iteration k = numerical value, e.g. 1, 2, …;
• Basis B = [Ai
, Aj , Ak] = numerical value (i.e. you need to specify i, j, k as well as
the numerical values of the columns);
• Basis inverse B−1 = numerical value;
• Basic variable xB = [xi
, xj , xk] = numerical value (you need to specify i, j, k and
numerical values of xi
, xj , xk);
• Nonbasic variable xN = [xp, xq] = numerical value (you need to specify p, q and
numerical values of xp, xq);
• Reduced cost for each nonbasic variable ¯cp = cp − c
>
BB−1A? = numerical values;
Same for ¯cq; (you need to the index “?” for A?);
• Is the current solution optimal? If not, which nonbasic variable to enter the basis?
• Direction dB = −B−1A? = numerical value. Does the simplex method terminate
with an unbounded optimum?
• Min-ratio test θ
∗ = mini:dB(i)<0
{xB(i)/(−dB(i)
)} = min{numerical values of the ratios} =
numerical value of θ
∗
.
• Which basic variable to exit the basis?
Start at iteration k = 1 with the basis B1 = [A3, A4, A5]. Solve the above linear program
with simplex method and write down all the information required above for each iteration.
Also indicate the basic feasible solution at each step on the picture in (x1, x2). What is
the optimal solution of the above LP in (x1, . . . , x5)? What is the optimal cost?
From this exercise, you can see how the simplex method works and geometrically what each
step is doing.
4 Modeling exercise: least squares and robust regressions
Given a set of training data {xi
, yi}i=1,…,N , where xi
is an n-dimensional feature vector and yi
is a
label of value either 0 or 1. Think about each xi represents a vector of lab test data of a patient i
and yi
labels if this person has a certain disease. We want to build a linear classifier, i.e. a linear
function f(x) = β0 +
Pn
j=1 βjxj , so that for a given feature vector x, if f(x) ≥ 0.5, then x is
classified as y = 1, otherwise classified as y = 0.
There are many ways to build this linear classifier. Most of them try to find the coefficients of
the linear function by minimizing certain distance metric over the training data. A very popular
method is called the absolute deviation regression (ADR). ADR is also called robust regression.
The optimization model of ADR is described below.
(ADR) min
β0,…,βn
X
N
i=1
yi − β0 −
Xn
j=1
βjxij
,
3
where xij is the jth component of vector xi and both xij ’s and yi
’s are the given data, while βi
’s are
the decision variables. Note that the (ADR) model in the above form is a nonlinear optimization
problem, which cannot be directly solved by Xpress.
Answer the following questions.
1. Is the objective function of (ADR) a convex function in β0, . . . , βn? (The answer should be
yes.) But explain why, using the conclusion of question 2.2.
2. Write down a linear programming reformulation of (ADR).
3. Code your LP reformulation of (ADR) in Xpress, using the data file and the partial mos file
provided. Pay attention to the format of the data file and how it is handled in the mos file.
Submit your mos code in t-square. And write down your solution in the hardcopy of your
homework.
4. Use the MATLAB code to plot the hyperplane obtained from (ADR). Submit a hard copy of
the plot.
