Tutorial 6

Lecturer: N. Monshizadeh

14 March 2025

Question 1 Consider the constrained minimization problem

2 4
Minimizex∈R3 2x21 + 4x22 + x1 + x2 + 5x23
3 3
subject to the budget constraint

2x1 + 4x2 = 5,
x1 + x3 = 4

Design a primal-dual algorithm whose solutions converge to the global minimizer of the optimization
problem above.

Define
2 4
L(x, λ) := f (x) + λT (Ax − b) = 2x21 + 4x22 + x1 + x2 + 5x23 + λ1 (2x1 + 4x2 − 5) + λ2 (x1 + x3 − 4)
3 3
∂L ∂L
By using ẋ = − (x, λ), λ̇ = + (x, λ), we get
∂x ∂λ
∂L 2
ẋ1 = − (x, λ) = −(4x1 + + 2λ1 + λ2 )
∂x1 3
∂L 4
ẋ2 =− (x, λ) = −(8x2 + + 4λ1 )
∂x2 3
∂L
ẋ3 =− (x, λ) = −(10x3 + λ2 )
∂x3
∂L
λ̇1 =+ (x, λ) = +(2x1 + 4x2 − 5)
∂λ1
∂L
λ̇2 =+ (x, λ) = +(x1 + x3 − 4)
∂λ2

Question 2 Consider the constrained minimization problem

2 4
Minimizex∈R2 2x21 + 4x22 + x1 + x2
3 3
subject to the budget constraint

2x1 + 4x2 = 5

i) Design a primal-dual algorithm with augmented Lagrangian whose solutions converge to the global mini-
mizer of the optimization problem above.
ii) Prove convergence of the algorithm in part i with a quadratic Lyapunov function.

1
  
a b
Hint: a 2 × 2 matrix is positive definite if and only if a > 0 and its determinant is positive.
c d
i) Define augmented Lagrangian function
ρ 2 4 ρ
LAug (x, λ) := f (x)+λT (Ax−b)+ (Ax−b)T (Ax−b) = 2x21 +4x22 + x1 + x2 +λ(2x1 +4x2 −5)+ (2x1 +4x2 −5)2
2 3 3 2
∂LAug ∂LAug
Now, by using ẋ = − (x, λ), λ̇ = + (x, λ), we have
∂x ∂λ
2
ẋ1 = −(4x1 + + 2λ + 2ρ(2x1 + 4x2 − 5))
3
4
ẋ2 = −(8x2 + + 4λ + 4ρ(2x1 + 4x2 − 5))
3
λ̇ = +(2x1 + 4x2 − 5)

ii) We have       2 
ẋ1 −(4 + 4ρ) −8ρ −2 x1 − 3 + 10ρ
ẋ2  =  −8ρ −(8 + 16ρ) −4 x2  + − 43 + 20ρ
λ̇ 2 4 0 λ −5
We have a system of the form ẋ = Ax + b; thus, we consider 0 = Ax∗ + b and subtract it from the original
system to get ẋ = A(x − x∗ ) which results in

−2 x1 − x∗1
    
ẋ1 −(4 + 4ρ) −8ρ
ẋ2  =  −8ρ −(8 + 16ρ) −4 x2 − x∗2  (1)
λ̇ 2 4 0 λ − λ∗

To investigate convergence, let V = 21 (x1 − x∗1 )2 + 21 (x2 − x∗2 )2 + 12 (λ − λ∗ )2 ; therefore, we get

V̇ = −(4 + 4ρ)(x1 − x∗1 )2 − 16ρ(x1 − x∗1 )(x2 − x∗2 ) − (8 + 16ρ)(x2 − x∗2 )2

x1 − x∗1
  
 (1 + ρ) 2ρ
= −4 x1 − x∗1 x2 − x∗2

2ρ 2(1 + 2ρ) x2 − x∗2

To prove that V̇ ≤ 0, we need to show that the matrix

 
(1 + ρ) 2ρ
(2)
2ρ 2(1 + 2ρ)

is positive definite (or at least positive semi-definite). By using the “Hint”, and ρ > 0, we have (1 + ρ) > 0
and 2(1 + ρ)(1 + 2ρ) − 4ρ2 = 2 + 6ρ > 0, which means that (2) is positive definite; therefore, we get

x1 − x∗1
  
 (1 + ρ) 2ρ
V̇ = −4 x1 − x∗1 x2 − x∗2

≤0
2ρ 2(1 + 2ρ) x2 − x∗2

We need to resort to LaSalle’s invariance principle since V̇ is negative semi-definite. Since

 
(1 + ρ) 2ρ
> 0,
2ρ 2(1 + 2ρ)

we conclude that V̇ = 0 ⇐⇒ x1 − x∗1 = 0, x2 − x∗2 = 0 on the invariant set.

From the first or second equation of (1), we can get

x1 − x∗1 = 0, x2 − x∗2 = 0 =⇒ λ − λ∗ = 0

Therefore, the origin is asymptotically stable and the convergence is proved.

Page 2
Question 3 Let q ∈ R. Consider the constrained minimization problem

Minimizex∈R2 2x21 + 4x22 + qx1 + (2 − q)x2

subject to the budget constraint

2x1 + 4x2 = b, b > 0.

i) Write a dual ascent algorithm using the Lagrangian.

ii) Obtain the result of part i) using the duality theory.
Hint: Formulate the dual problem as indicated in the slide “Duality: Primal vs. Dual”. Change maximiza-
tion to minimization. Then, write a gradient descent algorithm for the obtained minimization problem.

iii) Set q = 1, b = 1. Write a dual ascent algorithm using the augmented Lagrangian (set ρ = 1)

i) The Lagrangian function is given by

L(x, λ) = 2x21 + 4x22 + qx1 + (2 − q)x2 + λ(2x1 + 4x2 − b)

For obtaining a dual ascent algorithm, we use the primal-dual algorithm

∂L
0=− (x, λ)
∂x (3)
∂L
Kλ λ̇ = + (x, λ)
∂λ
For simplicity, we set Kλ = I in the above. From the first equation, we obtain x as a function of λ, i.e.,
x = h(λ), and substitute that into the second equation. In this regard, one has
∂L 1
(x, λ) = 4x1 + q + 2λ = 0 =⇒ x1 = − (q + 2λ) (4)
∂x1 4
∂L 1
(x, λ) = 8x2 + 2 − q + 4λ = 0 =⇒ x2 = − (2 − q + 4λ) (5)
∂x2 8
Now, we can substitute the preceding equation into (3) and get

λ̇ = −3λ − 1 − b (6)

The dual ascent algorithm is given by (6) together with (4) and (5).
ii) To formulate the dual problem, we need to get g(λ) := inf x∈Rn L(x, λ). For that, we need to find x
such that L(x, λ) is minimized with respect to the decision variable x. As a result,

∂L x1 = − 41 (q + 2λ)
(x, λ) = 0 =⇒
∂x x2 = − 18 (2 − q + 4λ)

By substituting the obtained questions into L(x, λ), we get

3 3q 2 q 1
g(λ) = − λ2 − (b + 1)λ − + −
2 16 4 4
The parameter λ should maximize g(λ), which is equivalent to minimization of −g(λ); hence

3 3q 2 q 1
Minimizeλ∈R −g(λ) = Minimizeλ∈R λ2 + (b + 1)λ + − +
2 16 4 4
For this minimization, by using the gradient descent method, we get
∂(−g)
λ̇ = − (λ) = −3λ − (b + 1)
∂λ

Page 3
iii) Define
1
LAug (x, λ) = 2x21 + 4x22 + x1 + x2 + λ(2x1 + 4x2 − 1) + (2x1 + 4x2 − 1)2
2
∂LAug
First, we need to obtain x = h(λ) from (x, λ) = 0; thus,
∂x
∂LAug
(x, λ) = 0 =⇒ 4x1 + 1 + 2λ + 2(2x1 + 4x2 − 1) = 0
∂x1
∂LAug
(x, λ) = 0 =⇒ 8x2 + 1 + 4λ + 4(2x1 + 4x2 − 1) = 0
∂x2
We can rewrite the preceding equation as follows

− λ8
        
8 8 x1 1 − 2λ x1
= =⇒ = (7)
8 24 x2 3 − 4λ x2 − λ8 + 18

On the other hand, for the Lagrange multiplier, we have

∂LAug
λ̇ = + (x, λ) = 2x1 + 4x2 − 1
∂λ
By using (7), one has
3 1
λ̇ = − λ −
4 2
λ
x1 = − (8)
8
λ 1
x2 = − +
8 8

Page 4