Tutorial 4

Lecturer: N. Monshizadeh

28 February 2025

Question 1 Consider a producer with the linear cost function C(x1 , x2 ) = x1 + x2 . Suppose that the
decision variables must lie in a circle of radius 2, i.e, x21 + x22 ≤ 4. Notice that if the constraint was linear,
we could have solved the problem using linear programming, however this is not the case here.

Part i): Use the Lagrangian method and KKT conditions to find the optimal value of the decision variables
x1 and x2 .

Part ii): : Suppose we add the constraint that x2 cannot take negative values. Obtain the optimal values
of x1 and x2 in this case.
Part i): The problem to be solved is
Minimizex∈R2 C(x1 , x2 )
subject to x21 + x22 ≤ 4,
where C(x1 , x2 ) = x1 + x2 . Rewrite this into the standard form to get
Minimizex∈R2 C(x1 , x2 )
subject to x21 + x22 − 4 ≤ 0.
Define the Lagrangian function
L(x, ν) := C(x1 , x2 ) + ν(x21 + x22 − 4) = x1 + x2 + ν(x21 + x22 − 4).
Thus, the KKT conditions are
(
∂L ∗ ∗ 1 + 2ν ∗ x∗1 = 0
0= (x , ν ) =⇒ (1)
∂x 1 + 2ν ∗ x∗2 = 0
x∗2 ∗2
1 + x2 − 4 ≤ 0 (2)
∗
ν (x∗2
1 + x∗2
2 − 4) = 0, ∗
ν ≥ 0. (3)
To find the solution, we check ν ∗ ≥ 0. If ν ∗ = 0, we reach a contradiction since from (1), we get 1 = 0.
Thus, we have ν ∗ > 0. Then we use (3) to obtain
x∗2 ∗2
1 + x2 − 4 = 0.
−1
√
From (1), we have x∗1 = x∗2 = 2ν ∗ ∗
∗ . Thus, it follows from the above relation x1 = x2 is either equal to 2 or
√ ∗ ∗ −1 ∗ ∗ ∗
− 2. Note from x1 = x2 = 2ν ∗ and ν > 0 that x1 , x2 < 0. Hence, the solution is
√ √
(x∗1 , x∗2 ) = (− 2, − 2).
Part ii): The new constraint is x2 ≥ 0. Thus the optimization problem is
Minimizex∈R2 C(x1 , x2 )
subject to x21 + x22 − 4 ≤ 0
−x2 ≤ 0

1
Define the Lagrangian function
L(x, ν) := C(x1 , x2 ) + ν1 (x21 + x22 − 4) + ν2 (−x2 ) = x1 + x2 + ν1 (x21 + x22 − 4) + ν2 (−x2 ).
Thus, the KKT conditions are
(
∂L ∗ ∗ 1 + 2ν1∗ x∗1 = 0
0= (x , ν ) =⇒ (4)
∂x 1 + 2ν1∗ x∗2 − ν2∗ = 0
x∗2 ∗2
1 + x2 − 4 ≤ 0 (5)
− x∗2 ≤ 0 (6)
ν1∗ (x∗2 ∗2
1 + x2 − 4) = 0, ν1∗ ≥ 0, (7)
ν2 x2 = 0, ν2∗ ≥ 0.
∗ ∗
(8)
We now check ν1∗
≥ 0. If ν1∗
= 0, we reach a contradiction since from (4), we get 1 = 0. Thus, we have
ν1∗ > 0. Hence from (7) we get
x∗2 ∗2
1 + x2 = 4. (9)
−1
We also check ν2∗ ≥ 0. If ν2∗ = 0, we see from (4) that x∗2 = 2ν ∗ ∗
∗ . This means that x2 < 0 since ν1 > 0, which
1
is in contradiction with (6). Thus, we should have ν2∗ > 0, and from (8), we get
x∗2 = 0.
−1
Using (4), we see that x∗1 = 2ν ∗ ∗
∗ , which together with ν1 > 0 means that x1 < 0. Using this with (9) and
1
∗ ∗
x2 = 0, we get x1 = −2. Consequently, the solution is
(x∗1 , x∗2 ) = (−2, 0).

Question 2 Consider the convex optimization problem

n
X
Maximizex∈Rn ln(αi + xi )
i=1
n
X
subject to x ≥ 0 and xi = 1.
i=1

In this problem, a sender aims to allocate power to receiving channels. The variable xi denotes the
transmitter power to the ith channel, and ln(αi +xi ) indicates the communication rate of the channel. Hence,
the goal of the optimization is to maximize the aggregated communication rate in the power allocation. 1
Use the Lagrangian method to solve this power allocation problem for the case where
n = 2, α1 = 4, , α2 = 1.
We first change maximization to minimization. Then, we define the Lagrangian function
L(x, λ, ν) := − ln(4 + x1 ) − ln(1 + x2 ) + λ(x1 + x2 − 1) − ν1 x1 − ν2 x2 .
Thus, the KKT conditions are
(
1 ∗ ∗
∂L ∗ ∗ ∗ − 4+x ∗ + λ − ν1 = 0
0= (x , λ , ν ) =⇒ 1
1
∗ ∗
∂x − 1+x ∗ + λ − ν2 = 0
2

x∗1 + x∗2 = 1
x∗1 ≥ 0, x∗2 ≥ 0
ν1∗ x∗1 = 0, ν2∗ x2 = 0
ν1∗ ≥ 0, ν2∗ ≥ 0.
1 Ex. 5.2, Boyd, S., Boyd, S.P. and Vandenberghe, L., 2004. Convex optimization. Cambridge university press.

Page 2
 We put aside the equality x∗1 + x∗2 = 1 for a moment.2 Then, the equations and inequalities for Channel
1 and Channel 2 are decoupled from each other for any λ∗ . This gives rise to the following implicit optimal
solution:
( (
1 ∗ 1 ∗
− 4 ν = 0 λ∗ − 1 ν2 = 0
x∗1 = λ 1 ∗
∗
, x 2 =
0 ν1∗ > 0. 0 ν2∗ > 0.
The functions above are in terms of λ∗ whereas the domains of the functions are stated in terms of ν1∗ and
ν2∗ . Therefore, we rewrite the optimal solution completely in terms of λ∗ as (argue why this can be written)
( (
1 ∗ 1 1 ∗
− 4 λ ≤ λ∗ − 1 λ ≤ 1
x∗1 = λ ∗
∗ 4 , x2 =
0 λ∗ > 14 0 λ∗ > 1.

Now, we enforce the last constraint x∗1 + x∗2 = 1. Distinguish three cases: λ∗ ≤ 41 , 14 < λ∗ ≤ 1, and
∗
λ > 1. Bearing nonnegativity of the decision variables x1 , x2 in mind, it is easy to observe that only the
second case 14 < λ∗ ≤ 1 leads to consistent results; namely x∗1 = 0, x∗2 = 1 with λ∗ = 1/2.

Question 3 Consider the optimal supply-demand balancing problem:

2
X 1 2
f (p) = fi (pi ), f1 (p1 ) = p , f2 (p2 ) = p22 , p1 + p2 = 6.
i=1
2 1

By using duality, find the minimum value of the cost function f .

Note: We write the solution here more generally for fi (pi ) = 21 qi p2i , i = 1, 2, and p1 + p2 = d.
The Lagrangian function is given by:
1 1
L(p, λ) = ( q1 p21 + q2 p22 ) + λ(p1 + p2 − d)
2 2
∂L ∂L
By setting = 0 and = 0, we obtain
∂p1 ∂p2
λ λ
p1 = − , p1 = − .
q1 q1
Therefore,
1 λ2 1 λ2
g(λ) = infn L(p1 , p2 , λ) = − − − λd.
x∈R 2 q1 2 q2
Next, we maximize the dual function as:
∂g ∗ d
Maximizeλ g(λ) −→ (λ ) = 0 −→ λ∗ = − 1 1
∂λ q1 + q2

By zero-duality gap, f (p∗ ) = g(λ∗ ). Therefore, the minimum value of f is obtained as

1 λ∗ 2 1 λ∗ 2
f (p∗ ) = g(λ∗ ) = − − − λ∗ d = · · ·
2 q1 2 q2

Note: Substituting λ∗ = − 1
d
+ q1
in the above is left for you.
q1 2

2 There are different ways to solve the equations and inequalities. The one presented here is more suitable for extensions to

n > 2.

Page 3