APM236 HW11
Due date: Sat Jan 20 before 9pm on Crowdmark
Note: In each homework 2-3 questions will be selected for grading.
“The work is quite feasible, and is the only thing in our power... Let go of the past. We must only
begin. Believe me and you will see.”
Epictetus talking about the work of learning.
The questions from our textbook below can be found here: Kolman and Beck (2nd edition).
(1) (a) Sketch the set of solutions to the following set of inequalities. Is it a convex set? Is it
a bounded set? Explain.
2x− y ≤ 10
3x+ 2y ≥ 5
x+ y ≥ 0
(b) Sketch the set of solutions to the following set of inequalities. Is it a convex set? Is it
a bounded set? Explain.
|x|+ |y| ≤ 10
x ≤ 0
(2) Sketch the set of solutions to the following set of equations/inequalities and label the extreme
points.
x+ y + z ≥ 1
3x+ 2y + z = 10
x ≥ 0
(3) Textbook (Kolman and Beck) section 1.3: # 32.
(4) Textbook (Kolman and Beck) section 1.4: # 14. Hint: be clear about what you need to
prove.
(5) (a) Let f : Rn → R be a convex function and let c ∈ R be a fixed number. Show that the
set {x ∈ Rn | f(x) ≤ c} is a convex set. Hint: use the definitions of convex functions
and convex sets.
(b) Show that the function f : R1 → R given by f(x) = |x| is a convex function. Hint:
this is an algebraic calculation.
(c) Show that the function f : Rn → R given by f(x) = |x| is a convex function. Here
|x| :=
√
x21 + · · ·+ x2n =
√
x · x is the norm of the vector x. Hint: use the triangle
inequality: |a+ b| ≤ |a|+ |b| for all a, b ∈ Rn and then apply part (b).
(d) Use parts (a) and (c) above to show that the unit ball {x ∈ Rn | |x| ≤ 1} in Rn is a
convex set.
(6) (a) Prove that a convex polytope has finitely many extreme points. Hint: KB Theorem
1.5 and Theorem 1.6.
(b) Prove that the set of extreme points of the ellipse S := {x ∈ R2 | x21 + 3x22 ≤ 1} is its
boundary, i.e. the set {x ∈ R2 | x21 + 3x22 = 1}. Hint: Try to show that points which
1Copyright ©2024 J. Korman. Sharing or selling this material without permission of author is a copyright
violation.
1
are not extreme points cannot be on the boundary: that is take a point λx+ (1− λ)y
where x, y ∈ S and λ ∈ (0, 1) and show that λx+ (1− λ)y /∈ ∂S. For that you can use
the triangle inequality or alternalively the Cauchy-Schwarz inequality: |uT v| ≤ |u||v|
for all vectors u, v ∈ Rn, with equality if and only if u and v are linearly dependent.
Note: this is requires some attention.
(c) Prove that the ellipse S := {x ∈ R2 | x21 + 3x22 ≤ 1} is not a convex polytope.
The following problems are for practice only and are not to be turned in.
(7) Give an example to demonstrate that Theorem 1.7(2) as stated in KB p.87 is incorrect.
Suggest a way of correcting it.
(8) Textbook (Kolman and Beck) section 1.3: # 26
(9) Textbook (Kolman and Beck) section 1.3: # 37