CS407T - Mathematics for Data Science

Instructors: Dileep A. D. and Vandana Bharti

Class Tutorial 02 - Optimization Techniques

Deadline: 11:00 PM, October 28, 2025 Max. marks: 25

1. Given v = (3, −4, 12)T , compute: (5)

∥v∥1 , ∥v∥2 , ∥v∥∞

and their dual norms; verify the dual relationship.

Solution: Step 1: Compute the norms of v

∥v∥1 = |3| + | − 4| + |12| = 3 + 4 + 12 = 19,

p √ √
∥v∥2 = 32 + (−4)2 + 122 = 9 + 16 + 144 = 169 = 13,
∥v∥∞ = max{|3|, |−4|, |12|} = 12.

Step 2: Dual norms (general facts) For vector norms on Rn :

• The dual of the ℓ1 -norm is the ℓ∞ -norm: ∥v∥∗1 = sup u⊤ v = ∥v∥∞ .

∥u∥1 ≤1

• The dual of the ℓ2 -norm is the ℓ2 -norm: ∥v∥∗2 = sup u⊤ v = ∥v∥2 .

∥u∥2 ≤1

• The dual of the ℓ∞ -norm is the ℓ1 -norm: ∥v∥∗∞ = sup u⊤ v = ∥v∥1 .

∥u∥∞ ≤1

Thus for our vector v we expect

(∥v∥1 )∗ = ∥v∥∞ = 12,

(∥v∥2 )∗ = ∥v∥2 = 13,
(∥v∥∞ )∗ = ∥v∥1 = 19.

Step 3: Verify the dual relationships by constructing maximizers

Dual of ℓ1 (i.e. supremum over ∥u∥1 ≤ 1). Choose u = (0, 0, 1). Then ∥u∥1 = 1
and
u⊤ v = 0 · 3 + 0 · (−4) + 1 · 12 = 12 = ∥v∥∞ .
Hence sup∥u∥1 ≤1 u⊤ v ≥ 12. By Hölder’s inequality (or standard duality) the supremum
cannot exceed ∥v∥∞ . Therefore

sup u⊤ v = ∥v∥∞ = 12.

∥u∥1 ≤1

1
Dual of ℓ2 (Cauchy–Schwarz). Take u = v/∥v∥2 = 13 (3, −4, 12). Then ∥u∥2 = 1
and
1 ⊤ 1 1
u⊤ v = v v = ∥v∥22 = · 132 = 13 = ∥v∥2 .
13 13 13
By Cauchy–Schwarz the maximum over ∥u∥2 ≤ 1 is ∥v∥2 , so

sup u⊤ v = ∥v∥2 = 13.

∥u∥2 ≤1
 Dual of ℓ∞ (supremum over ∥u∥∞ ≤ 1). Take u = sign(v) = (1, −1, 1). Then
∥u∥∞ = 1 and

u⊤ v = 1 · 3 + (−1) · (−4) + 1 · 12 = 3 + 4 + 12 = 19 = ∥v∥1 .

By the general duality result the supremum cannot exceed ∥v∥1 , hence

sup u⊤ v = ∥v∥1 = 19.

∥u∥∞ ≤1

Finally,
∥v∥1 = 19, ∥v∥2 = 13, ∥v∥∞ = 12
and the dual norms satisfy

(∥ · ∥1 )∗ = ∥ · ∥∞ , (∥ · ∥2 )∗ = ∥ · ∥2 , (∥ · ∥∞ )∗ = ∥ · ∥1

with the numerical equalities

sup u⊤ v = 12, sup u⊤ v = 13, sup u⊤ v = 19.

∥u∥1 ≤1 ∥u∥2 ≤1 ∥u∥∞ ≤1

2. (a) State the First Order Necessary Condition (FONC) for optimality and interpret
it geometrically.
(b) State and explain the Second Order Necessary Condition (SONC) for a mini-
mization problem.
(c) Given f (x, y) = x2 + xy + y 2 , check whether the point (0,0) satisfies the FONC
and SONC.
(8)

Solution:

(a) First Order Necessary Condition (FONC) for optimality.

Statement. For an unconstrained minimization problem of a twice differentiable
function f : Rn → R, a necessary condition for x⋆ to be a local minimizer is

∇f (x⋆ ) = 0.

Geometric interpretation. The gradient vector ∇f (x) points in the direction

of steepest ascent of f . If ∇f (x⋆ ) ̸= 0 then moving a small amount in the
direction −∇f (x⋆ ) decreases f (first-order decrease), so x⋆ cannot be a local
minimizer. Hence at a local minimizer the first-order term vanishes and the linear
approximation gives no decrease: the gradient is orthogonal to every feasible
(infinitesimal) direction, i.e. orthogonal to the tangent space.

(b) Second Order Necessary Condition (SONC) for minimization.

Statement. Let f ∈ C 2 . If x⋆ is a local minimizer and ∇f (x⋆ ) = 0, then the
Hessian H(x⋆ ) = ∇2 f (x⋆ ) must be positive semidefinite:

d⊤ H(x⋆ )d ≥ 0 for all d ∈ Rn .

This is a necessary condition.

Remarks.
• If H(x⋆ ) is positive definite (i.e. d⊤ Hd > 0 for all nonzero d), then x⋆ is a
strict local minimum (this is a sufficient condition — often called the second-
order sufficient condition).
 • If H has a negative direction (some d with d⊤ Hd < 0), then x⋆ cannot be a
local minimizer (it would be a saddle or a maximum).

(c) Check FONC and SONC for f (x, y) = x2 + xy + y 2 at (0, 0).

Step 1: Gradient. ! !
∂f
∂x 2x + y
∇f (x, y) = ∂f = .
∂y
x + 2y
At (0, 0), !
0
∇f (0, 0) = ,
0
so the FONC is satisfied.
Step 2: Hessian.
 
∂2f ∂2f
!
2 ∂x2 ∂x∂y 2 1
H(x, y) = ∇ f (x, y) =  = ,
∂2f ∂2f 1 2
∂y∂x ∂y 2

which is constant (independent of (x, y)). Evaluate at (0, 0) (same matrix):

!
2 1
H(0, 0) = .
1 2

Step 3: Check definiteness. Compute eigenvalues of H. Solve det(H − λI) = 0:

!
2−λ 1
det = (2 − λ)2 − 1 = 0.
1 2−λ

Hence
(2 − λ)2 = 1 ⇒ 2 − λ = ±1.
Thus eigenvalues are

λ1 = 2 − 1 = 1, λ2 = 2 + 1 = 3.

Both eigenvalues are strictly positive, so H(0, 0) is positive definite.

Conclusion:
• The point (0, 0) satisfies the FONC since ∇f (0, 0) = 0.
• The Hessian at (0, 0) is positive definite (eigenvalues 1 and 3), so the SONC
(necessary condition) holds and in fact the second-order sufficient condition
also holds: (0, 0) is a strict local minimum.
 
1 µ
3. For A(µ) = , compute eigenvalues for µ ∈ [−1, 1] and find range of µ for which
µ 1
f (x) = 12 xT A(µ)x is strongly convex. (5)

Solution: The eigenvalues of a 2 × 2 matrix A are roots of the characteristic polyno-

mial
det(A − λI) = 0.
For A(µ) we have
!
1−λ µ
= (1 − λ)2 − µ2 .


det A(µ) − λI = det
µ 1−λ
 Set this equal to zero:
(1 − λ)2 − µ2 = 0 =⇒ (1 − λ) = ±µ.
Hence the two eigenvalues are
λ1 = 1 + µ, λ2 = 1 − µ.

For µ ∈ [−1, 1] these are real and satisfy

λ1 ∈ [0, 2], λ2 ∈ [0, 2].
The quadratic form f (x) = 12 x⊤ A(µ)x is (strictly) strongly convex if and only if A(µ)
is positive definite, i.e. its smallest eigenvalue satisfies
λmin = min(1 + µ, 1 − µ) > 0.
Note that min(1 + µ, 1 − µ) = 1 − |µ|. Therefore the strong convexity condition reads
1 − |µ| > 0 ⇐⇒ |µ| < 1.

Thus:
• For |µ| < 1 : λmin = 1 − |µ| > 0 so A(µ) is positive definite and f is strongly
convex. The strong convexity constant may be taken as
m = 1 − |µ|.
The smoothness (largest eigenvalue) is
L = λmax = 1 + |µ|.

• For |µ| = 1 (i.e. µ = ±1): one eigenvalue is zero (specifically when µ = 1,

λ2 = 0; when µ = −1, λ1 = 0), so A(µ) is positive semidefinite but not positive
definite. Hence f is convex but not strongly convex.
• For |µ| > 1 (outside the given interval) one eigenvalue becomes negative and
A(µ) is indefinite.

Condition number (optional). For |µ| < 1, the condition number of A(µ) (w.r.t.
Euclidean norm) is
λmax 1 + |µ|
κ(A(µ)) = = .
λmin 1 − |µ|

4. Let
f (x, y) = 4x3 − 6x2 y + 2xy 2 + y 3 .
(7)
(a) find all critical points of f (x, y).
(b) Compute the Hessian at each critical point/s and classify them.
Solution:
f (x, y) = 4x3 − 6x2 y + 2xy 2 + y 3 .

(a) Gradient and critical points Compute the partial derivatives:

∂f
fx (x, y) = = 12x2 − 12xy + 2y 2 ,
∂x
∂f
fy (x, y) = = −6x2 + 4xy + 3y 2 .
∂y
Critical points satisfy
fx = 0, fy = 0.
From fx = 0 (divide by 2):
6x2 − 6xy + y 2 = 0. (1)
From fy = 0:
−6x2 + 4xy + 3y 2 = 0. (2)
Case 1: x = 0. Substitute into (1): y 2 = 0, hence y = 0. So (0, 0) is a critical point.
Case 2: x ̸= 0. Set y = kx with k ∈ R. Dividing (1) and (2) by x2 gives
k 2 − 6k + 6 = 0, (3)

3k 2 + 4k − 6 = 0. (4)
If a common root k exists it must satisfy both (3) and (4). Multiply (3) by 3 and
subtract (4):
3(k 2 − 6k + 6) − (3k 2 + 4k − 6) = −22k + 24 = 0,
so any common root would satisfy
24 12
k= = .
22 11
12
But substituting k = 11
into (3) yields
 2  
12 12 78
−6 +6= ̸= 0,
11 11 121
so there is no common root. Thus no solution exists with x ̸= 0.
Therefore the only critical point is
(x, y) = (0, 0).

(b) Hessian and classification Compute second partial derivatives:

fxx (x, y) = 24x − 12y,
fxy (x, y) = −12x + 4y,
fyy (x, y) = 4x + 6y.
So the Hessian matrix is
!
24x − 12y −12x + 4y
H(x, y) = .
−12x + 4y 4x + 6y

At the critical point (0, 0): !

0 0
H(0, 0) = ,
0 0
which is the zero matrix (both eigenvalues 0). The second-derivative test is inconclu-
sive (degenerate Hessian).
To classify the critical point, inspect the function along lines through the origin. Along
the x-axis (y = 0),
f (x, 0) = 4x3 .
For small x > 0, f (x, 0) > 0, and for small x < 0, f (x, 0) < 0. Therefore f takes
both positive and negative values arbitrarily close to the origin and (0, 0) is not a local
minimum or maximum. Hence (0, 0) is a saddle point.

The only critical point is (0, 0), and it is a saddle point.