MATH4816/7050 HOMEWORK 1 (2024-2025 SEMESTER 1)
• Due: 10:00AM, September 28th (Saturday).
• No late submission and no exception.
• You are allowed to discuss with others but you must finish all questions by yourself. We have a zero tolerance for abnormal similarities.
• RPg students are highly recommended to use LaTeX.
• You must include your name and student ID in your submission.
• Submit your work in one single PDF on Moodle. All submissions via email will be intentionally ignored.
• For undergraduate students, finishing questions marked with “not required for MATH4816 students” may earn you extra credits, but it will not exceed the designed full score for this homework.
1. Let x ∈ Rn. Show the following inequalities:
(1) ∥x∥1 ≥ ∥x∥2 ≥ ∥x∥∞.
(2) ∥x∥1 ≤ √n∥x∥2 ≤ n∥x∥∞.
Hint: use the arithmetic and geometric means (AM-GM) inequality: for positive real numbers a1, . . . , ak, it holds
k/a1 + · · · + ak ≥ k√a1a2 · · · ak.
2. Let A ∈ R
m×n. Show the following inequalities:
(1) √n/1∥A∥∞ ≤ ∥A∥2 ≤
√n∥A∥1.
(2) √m/1 ∥A∥1 ≤ ∥A∥2 ≤ √m∥A∥∞.
Hint: use the definition of induced matrix norms and the inequalities you showed in Q1. Also, remark that if f and g are functions such that f(x) ≤ g(x) for all x ∈ D, then minx∈D f(x) ≤ minx∈D g(x).
3. (not required for MATH4816 students) Let A ∈ R
m×n. Using the definition of induced norms, show that:
(1) ∥A∥∞ := max∥x∥∞ =1
∥Ax∥∞ = max 1≤i≤m P
nj =1 |Aij |.
(2) ∥A∥1 := max∥x∥1 =1
∥Ax∥1 = max1≤j≤n Pni =1 |Aij |.
(3) ∥A∥2 := max∥x∥2 =1
∥Ax∥2 = σ1(A), where σ1(A) is the largest singular value of A.
4. Denote by ∥ · ∥ be a norm of Rn as well as its induced matrix norm in Rn×n. Consider the system Ax = b for A ∈ Rn×n with the solution x
∗ and suppose A is invertible. Let ∆A ∈ Rn×n be a perturbation and let ∆x* be the solution to the perturbed system, i.e., (A + ∆A)(x* + ∆x) = b. Show
∥∆x + x
∗∥/∥∆x∥ ≤ ∥A∥∥A
−1
∥
∥A∥/∥∆A∥.
5. Let A ∈ S
n
+ and let x ∈ R
n. Show that
(1) If x
T Ax = 0, then Ax = 0.
(2) (not required for MATH4816 students) If A ∈ S
n
++, then the function ∥ · ∥A : R
n 7→ R such that ∥x∥A =
√
x
T Ax for all x ∈ Rn gives a norm.
Hint: use the Cauchy-Schwartz inequality: (xTy)2 ≤ ∥x∥
2 2 ∥y∥
2 2 for all x, y ∈ Rn.
6. Let f(x1, x2) = x
4 1 x
2 2 +x
2 1 x
4 2 −3x
2 1 x
2 2 + 1. Show that f ∈ C
2
( R2) and write down the gradient, the directional derivative in the direction [1, −1], and the Hessian matrix of f (the polynomial f is called the Motzkin polynomial). Is f a convex function?
7. Show that any vector norm ∥ · ∥ is a convex function on R
n, then show that for g(t): R 7→ R
m and a < b, we have
Z
a
b g(t)dt ≤
Z
a
b ∥g(t)∥ dt.
Hint: you may try Jensen’s inequality. But this is not the only approach...
8. Show Lemma 11 in Lecture 2: Let f : R
n 7→ R be twice continuously differen-tiable on an open set D, and suppose its Hessian ∇2f is Lipschitz continuous at x in its neighborhood with the Lipschitz constant equal to γ. Then for any x+v ∈ D, it holds
∥f(x + v) − f(x) − ∇f(x)
T
v − 2/1v
T ∇2
f(x)v∥ ≤ 6/γ ∥v∥
3
.
Hint: To derive the second order Taylor expansion of f with integral reminder, you may find considering the second order expansion for the univariate function ϕ(t) := f(x + tv) every useful, that by Taylor’s theorem, we have
ϕ(1) = ϕ(0) + ϕ
′
(0) + Z
0
1 (1 − t)ϕ
′′(t)dt.
9. (1) Let f(x) := −e
x
. Show that the sublevel set Cα of f(x) is convex for all x ∈ R, but f(x) is strictly concave.
(2) Show Lemma 18 in Lecture 2: A function f : X 7→ R is convex iff its epigraph
epi(f) := {(x, t) ∈ X × R : f(x) ≤ t}
is convex.
10. (1) Let f(x1, x2) = x
4 1 x
2 2 + x
2 1 x
4 2 − 3x
2 1 x
2 2 + 1 be the Motzkin polynomial. Show that ∇f(1, 0) = 0 but (x1, x2) = (1, 0) is not a global minimizer.
(2) Let D:= {(x1, x2) ∈ R
2
: 3x1 > 2x2, x1x2 > 0}, and let f : D 7→ R be such that f(x1, x2) = x 3 1 + x 1 x 2 show that they do not exist.
− 4x1 − 2x2. Find all global minimizers of f on D or