First-Stage PhD Comprehensive Examination
in
CONTINUOUS OPTIMIZATION
Department of Combinatorics and Optimization, Faculty of Mathematics,
University of Waterloo
MC 5479, Thursday, June 13, 2019, 1pm – 4pm (3 hours)
Examiners: Levent Tunçel and Stephen A. Vavasis
1. Consider the univariate function
ex for x < 0,
f (x) :=
x + 1 for x ≥ 0.
(a) Show that this function is convex. Any standard theorem that characterizes con-
vexity of functions may be used.
(b) Show that the gradient of this function is Lipschitz continuous, and find L, the
Lipschitz constant of the gradient.
(c) Since f 0 is Lipschitz continuous, Zoutendijk’s theorem for minimizing f using steep-
est descent is applicable. State Zoutendijk’s theorem and the conclusion as it applies
to this function f .
(d) Suppose that xk = 0 on the kth iteration of the steepest descent method. Identify
an interval of positive width of choices for xk+1 that satisfy the Wolfe conditions.
(Select any reasonable values for the constants appearing in Wolfe’s conditions, and
state what values you used.)
1
2. Let n be a positive integer.
(a) Assume f : Rn → (−∞, +∞] is positively 1-homogeneous. Show that it is subad-
ditive if and only if it is convex.
(b) Recall, if f : Rn → R satisfies
(i) f (x) > 0, ∀x ∈ Rn \ {0},
(ii) f (u + v) ≤ f (u) + f (v), ∀u, v ∈ Rn ,
(iii) f (λx) = |λ|f (x), ∀x ∈ Rn , ∀λ ∈ R,
then f is a norm on Rn . Let
F := {f : f is a norm on Rn } ,
and
C := {C ⊂ Rn : C is compact, convex, 0 ∈ int (C) and C = −C} .
Prove that (with γ being the gauge function)
f (·) := γ(C; ·) and C := {x ∈ Rn : f (x) ≤ 1}
define a one-to-one correspondence between F and C.
2
3. Let n be a positive integer and f : Rn → (−∞, +∞] be convex.
(a) Define the notion of subgradient of f at x̄ ∈ Rn .
(b) Define the notion of subdifferential of f at x̄ ∈ Rn .
(c) Let f (x) := ||x||∞ . What is the subdifferential of f at a given x̄ ∈ Rn ? Prove your
claims.
For the remaining parts of this question, let m and n be positive integers such that
n ≥ m + 1, and consider linear programming problems in the form
p∗ := min c> x
s.t. Ax = 0
(P)
e> x = n
x ∈ Rn+ ,
where A is a given full row rank m-by-n matrix, c ∈ Rn is also given. e ∈ Rn is
the vector of all ones. Assume that Ae = 0, p∗ = 0 and c> e > 0. In your answers,
you may use the Fundamental Theorem of LP, provided you state it clearly and
correctly. For every q ∈ R++ , define
(q + 1) ln c> x − ln (minj {xj }) , if x ∈ Rn++
φq (x) :=
+∞, otherwise,
and consider the optimization problem
v(Pq ) := inf φq (x)
(Pq ) s.t. Ax = 0
e> x = n.
(d) Prove that for every q ∈ R++ , v(Pq ) = −∞ (i.e., (Pq ) is unbounded). Further
prove that for every q ∈ R++ , (P) and (Pq ) are equivalent (by stating a suitable
definition of equivalence and proving it).
Hint:
• (P) has optimal solution(s),
• (Pq ) has feasible sequences in the domain of φq which certify unboundedness
of (Pq ).
(e) Let f : Rn++ → R be defined by f (x) := − ln (minj {xj }). What is the subdifferen-
tial of f at a given x̄ ∈ Rn++ ? Prove your claims.
3
4. Let a1 , . . . , an ∈ Rd be given, and consider the following optimization problem in which
x1 , . . . , xn ∈ Rd are the unknowns (i.e., nd total variables), λ > 0 is a fixed parameter,
and all norms are Euclidean:
n
1X X
min f (x) := kxi − ai k2 + λ kxi − xj k.
x1 ,...,xn 2 i=1 1≤i<j≤n
(Note: This formulation arises in “sum-of-norms” clustering.)
(a) What is the definition of “strongly convex”? Suppose g, h : Rn → R are two convex
functions such that g is strongly convex. Prove that g + h is also strongly convex.
(b) Apply the result in (a) to the function at hand to conclude that f is strongly
convex. Justify your answer.
(c) By introducing auxiliary variables, rewrite the problem of minimizing f as a con-
strained optimization in standard conic form min cT x subject to Ax = b, x ∈ K (not
necessarily the same x), where the convex cone K is a Cartesian product of second-
order cones. The following standard trick may help: the convex quadratic constraint
s ≥ kxk2 /2 may be expressed in second-order cone form:
1 1
(s + 1) ≥ x; √ (s − 1) ,
2 2
where the notation on the right-hand side indicates concatenation of a vector and
scalar.
