APM236 HW1
Due date: Sat Jan 18 before 9pm on Crowdmark
Note: In each homework 3-4 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.
Please submit the following 6 problems on Crowdmark.
(1) (a) 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
3x + 2y ≥ 12
x − 2y ≥ 0
(b) Sketch the set of solutions to the following set of inequalities. Here a is a non-negative number. Is it a convex set? Is it a bounded set? Explain.
x − y + a ≤ 10
3x + 2y − a ≥ 12
x − 2y − a ≥ 0
Note that when a = 0 you get the set in part (a). Also note that when a is large enough the set becomes empty.
(c) Sketch the set of solutions to the following set of equations/inequalities and label the extreme points.
x + y + z ≤ 10
x + 2y ≥ 6
x, y, z ≥ 0
(2) Let w0, w1, w2, . . . be a sequence of points in R
n
. Now define MS(0) := w0, and for every k ≥ 1, define MS(k) := 0.9MS(k−1)+0.1wk. So for example MS(1) := 0.9MS(0)+0.1w1, and MS(2) := 0.9MS(1)+0.1w2. Prove that for all k ≥ 0, MS(k) ∈ convex hull{w0, w1, . . . , wk}. Hint: start by proving this for k = 0, 1, 2 and once you see the pattern use induction. Note that the expression 0.9MS(k − 1) + 0.1wk is a convex combination of MS(k − 1) and wk.
Remark: this question is related to an optimization technique called rmsprop use in Ma-chine Learning to train neural networks. You do not need to know anything about neural netwroks to solve this problen, but if you are interested in some context you can watch the video Hinton 6.5.
(3) In this question you will show that the composition of affine functions is an affine function. One place this fact comes up is in neural networks where each neuron in a layer of neurons is an affine function of the neurons in the previous layer. You do not need to know anything about neural netwroks to solve this problen, but if you are interested in more details you can watch the video Hinton 2.1.
(a) Suppose y is an affine function of the zi
’s: y = a +
P i
vizi
. And suppose each zi
is an affine function of the xj ’s: zi =
P j
(wijxj + bj ). Show that y is an affine function of the xj ’s. Here a, vi
, wij , bj are all fixed numbers. Hint: composition of functions.
(b) Show the same thing as in part (a) but now use vector notation. That is, show that if y(z) = v
T
z + a is an affine function of z and z(x) = W x + b is an affine of x then the composition y(z(x)) is an affine function of x. Here v, b are fixed vectors, W is a fixed matrix, and a a fixed scalar.
(c) Show that if y(z) = v
T
z is a linear function of z and z(x) = W x a linear function of x then the composition y(z(x)) is a linear function of x. Hint: this is easy once you recall that a linear function is a special case of an affine function and so can use part (a) or part (b) as you prefer.
(4) (a) Let f : R
n → R
1 be a function and let C := {(x, y) ∈ R
n × R
1
| y ≥ f(x)} be the set of points above the graph of f. Prove that f is a convex function iff C is a convex set. Hint: use the definitions of convex functions and convex sets. It may be useful to draw a picture in the case when n = 1.
(b) Show that the function f : R
n → R given by f(x) = ||x|| is a convex function. Here ||x|| := p x
2
1 + · · · + x
2
n =
√
x · x is the norm of the vector x. Hint: use the triangle inequality: ||a + b|| ≤ ||a|| + ||b|| for all a, b ∈ R
n and then apply part (b).
(c) Let f1, f2 : R
n → R be two convex functions. Use part (a) to show that the function f(x) := max{f1(x), f2(x)} is convex. Note: the value of f at x is the maximum of the two numbers f1(x) and f2(x). For example max{x, −x} is the absolute value |x| of x.
(d) Use parts (b)-(c) above to show that the function max{|x|, 1} is a convex function. Here x ∈ R
1
.
(5) (a) Prove that a convex polytope has finitely many extreme points. Hint: KB Theorem 1.5 and Theorem 1.6.
(b) Suppose you are given the following fact: the set of extreme points of a disc {x ∈ R
2
| x
2
1 + x
2
2 ≤ r
2} is its boundary, i.e. the set {x ∈ R
2
| x
2
1 + x
2
2 = r
2}. Now consider the intersection of two discs S := {x ∈ R
2
| (x1 + 1)2 +x
2
2 ≤ 2} ∩ {x ∈ R
2
| (x1 −1)2 +x
2
2 ≤ 2} (see diagram at top). Show that the set of extreme point of S is its boundary {x ∈ R
2
| (x1 + 1)2 + x
2
2 = 2, x1 ≤ 0} ∪ {x ∈ R
2
| (x1 − 1)2 + x
2
2 = 2, x1 ≥ 0}. Hint: draw a picture and use the fact above.
(c) Prove that the set S is not a convex polytope.
(6) In this question you will classify all polyhedrons in R
1
. Recall that any polyhedron in R
1
is of the form. P := {x ∈ R
1
| aix ≤ bi for i = 1, ..., k} where the ai
’s and the bi
’s are numbers.
(a) Show that any (non-empty) polyhedron in R
1 has one of 4 types: (a) a single point, (b) a closed interval, (c) a half closed infinite interval (i.e. of the form. (−∞, a] or [a, ∞)) or (d) all of R
1
.
(b) What do polytopes in R
1
look like? Explain.
(c) Try to classify polyhedrons in R
2 by making a list of as many types of polyhedrons you can think of. Hint: you should contemplate what the word “type” could possibly mean in this context.
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