APM462: Homework 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
APM462: Homework 2
Due: Sat Feb 4, before 9pm.
(1) Let g : Rn → R be the quadratic function g(x) = 
xT Qx _ bT x where Q is (symmetric) positive definite and such that the minimum value g(Q-1 b) < 0. Let Ω = (x e Rn | g(x) < 0} and suppose x0 is a point where g(x0 ) = 0. Note: for this question it is useful to recall the 1st order Taylor approximation.
(a) Suppose n = 3 and that Q is a diagonal matrix. Show that the level sets of g are
ellipsoids. Hint: by completing the square you can find the centre of the ellipsoid. Remark: the level sets of g are also ellipsoids for any n.
(b) Let v be a feasible direction for Ω at x0 . Prove that Vg(x0 ) . v < 0.
(c) Suppose that Vg(x0 ) . v < 0. Prove that v is a feasible direction for Ω at x0 .
(d) Suppose that Vg(x0 ) . v = 0. Is v a feasible direction for Ω at x0 ?
(e) Let Ω = (x e R2 | g(x) = x1(2) + x2(2) _ 1 < 0} be the unit disc and x0 a point on the unit circle, i.e g(x0) = 0. Find the feasible directions for Ω at x0 . Note: compare your answer to what we did in lecture.
(2) Assume that g is a convex function on Rn , that f is a linear function of a single variable, and in addition that f is a nondecreasing function (which means that f (r) 2 f (s) whenever r 2 s).
(a) Show that F := f 。g is convex by directly verifying the convexity inequality F (θx + (1 _ θ)y) < θF (x) + (1 _ θ)F (y).
Explain where each hypothesis (convexity of g, linearity of f , and the fact that f is nondecreasing) is used in your reasoning. (The notation F = f o g means that F (x) = f(g(x)).)
(b) Now assume that f and g are both C2 . Express the matrix of second derivatives V2 F (x) in terms of f and g . Prove directly (without using part (a)) that V2 F (x) is positive semidefinite at every x. Hint: see HW1 suggested problem I.
Discussion: Expressing V2 F in terms of f and g is basically an exercise in using the chain rule for functions of several variables. If you find it at all difficult, then review the chain rule until you have completely mastered it! When showing that V2 F is positive semidefinite, please explain again, as you did in part (a), where each hypothesis is used in your reasoning.
(3) Let C c Rn be a nonempty convex set and a e Rn a point outside C . Let ||y|| denote the norm of y e Rn . Suppose x0 e C is the closest point in C to a, that is ||x0 _ a|| < ||x _ a|| for all x e C . Prove that x0 is unique. Hint: try a proof by contradiction. You may want to use the triangle inequality: ||X + Y || < ||X|| + ||Y || (with = iff one of the vectors is a non-negative multiple of the other).
(4) Consider the convex set C = ((x, y) e R2 | max(|x|, |y|} < 1} in R2 . Solve the following minimization problem by finding a candidate for minimizer (1st order necessary condition) and then showing this candidate is in fact a global minimizer.
minimize: f (x, y) = 
(x _ 2)2 + 
(y _ 3)2
(x, y) e C
Hint: start by drawing a picture in R2 .
(5) Let f (x) = x . Qx + x . (x + a) + 1990, where Q is positive semidefinite 3 × 3 symmetric matrix and x, a e R3 . You can think of the vector x as having coordinates x = (x, y, z).
(a) Prove that f (x) is a convex function.
(b) For which b e R is gb(x, y, z) = bx2 _ 3xz + 2by2 + z2 + 2000, where (x, y, z) e R3, a convex function? Explain your answer.
(6) We are to minimize the the affine function f (x) = aT x +b over the convex set C c Rn . Sup- pose x0 e C satisfies the first order necessary condition for a local minimum: Vf (x0 )T v 2 0 for all feasible directions v at x0 . Prove that x0 is in fact a global minimizer. Hint: start with any y e C and use Taylor approximation to show f (y) 2 f (x0 ).
The following three problems are for practice only and are not to be turned in.
I. Let Q be a symmetric n × n-matrix (not necessarily positive definite) and let λ 1 < . . . < λn be its eigenvalues. Consider the problem
minimize: f (x) = 
xT Qx _ bT x
subject to: g(x) = |x|2 _ 1 = 0
Assuming the minimizer x0 is an eigenvector of Q, express the minimum value of this prob- lem in terms of the eigenvalues of Q. You should not use the method of Lagrange multipliers.
II. Consider the function f (x, y) = |x2 _ y| where x, y e R1 . Is f convex? Explain.
III. Consider the function f (x, y) = ||x|| _ ||y|| where x, y e Rn . Is f convex? Explain. Hint: sublevel sets of a convex function are convex sets.
IV. Let Q = ┌c(a) d(b)┐ be a 2 × 2 (not necessarily symmetric) matrix, where a, b, c, d e R. Consider the function f (x, y) = 
┌ ┐y(x) T Q ┌ ┐y(x) . Find the most general conditions on a, b, c, d which guarantee that f (x) is convex. Hint: see practice problem II(b) on HW1.
V. Let f : Rn+m → R be defined as f (x, y) = ||Ax + y||2 , where A is an m × n matrix, x e Rn and y e Rm .
(a) Find Vf (x, y) and V2f (x, y). Hint: you may want to expand the expression for f (x, y) and compute the partial derivatives with respect to x and y .
(b) Describe the points (x0 , y0 ) satisfying the necessary first and second order conditions for a minimizer of f (x, y) on Ω = Rn+m .
2023-02-06