Optimization - Homework 6
1. Solve the following problem
x1 x2 x3
Maximize f (x) = x 1 x2 x3 subject to + + = 1 and a 1, a2 , a3 ≥ 0
a1 a2 a3
x1 x2 x3 x1 x2 x3
Constrain is equivalent to + + − 1 = 0 , set c(x) = + + − 1
a1 a2 a3 a1 a2 a3
as the constrain function.
The problem is equivalent to find the maximum value of L(x, λ) = f (x) − λc(x)
where c(x) = 0
Basis matrix for the null space of the constrain:
a1 a2
⎧ − − ⎫
⎡ a2 a3 ⎤
Z = span ⎨ 1 0 ⎬
⎩ ⎭
⎣ ⎦
0 1
We find the stationary point by solving the tancency condition:
∇g(x) = ∇f (x) − λ∇c(x) = 0
λ λ λ
⟺ ∇f (x) − λc(x) = 0 ⟺ x2 x3 = , x2 x1 = , x1 x3 =
a1 a3 a2
√λ 3 √λ √λ √λ
Or x 1 x2 x3 = and x 1 = , x2 = , x3 =
a1 a2 a3 a2 a3 a1 a3 a1 a2
Because c(x) = 0 at stationary point in the feasible direction, we have
3√ λ = a 1 a 2 a 3 or λ = ( a1 a2 a3
3
)
2
. Then, g(x) have one stationary point
∗ a1 a2 a3
x = , x2 ∗ = , x3 ∗ =
1 3 3 3
At this point we have Z (x )∇f (x ) = 0. Now, calculate Z ∇ L(x , λ)Z , which
T ∗ ∗ T 2
xx
∗∗
is not negative definite. So x , the only stationary point is not the maximizer of f .
∗
I will also prove that there is no maximizer of f . Let x = a t 1 1
), and x = a ( ) with any arbitrary t in the domain. Thefore,
1 t 1 t
x = a (
2 −
2 − 3 3
2 2 2 2
x1 x2 x3
these x , x , and x satisfy the constraints
1 2 3 + + = 1 .
a1 a2 a3
When t → ∞ , we have f (x) → +∞. So, there does not exist a maximizer for f (x)
with the constrains.
2. f (x) = −x 2
1
+ x
2
2
− x1 x2
Let λ = (λ 1, λ2 , λ3 )
T
are associated Langrange multiplier with 3 constrains.
Therefore, the neccessary conditions for a local minimum at x are:
The constrains are satisfied (1)
2x 1 − x 2 ≥ 2
−x 1 − x 2 ≥ −4
x1 ≥ 0
Perpendicular conditions (2)
−2x 1 − x 2 2 −1 1
( ) = λ1 ( ) + λ2 ( ) + λ3 ( )
2x 2 − x 1 −1 −1 0
Lagrange multiplier (3)
(3.1)
λ 1 ≥ 0, λ 2 ≥ 0, λ 3 ≥ 0
(3.2)
λ 1 (2x 1 − x 2 − 2) = 0
λ 2 (x 1 + x 2 − 4) = 0
x1 λ3 = 0
If all constrains are active, there are no feasible points.
If the first two constrains are active and λ 3 = 0
we have x = 2 and x = 2 so that (2) satisfied, we found that λ
1 2 1 =
−8
3
and
λ =
2 . These value does not satisfied (3).
−2
If the first condition is not active, and λ = 0, from (3.2) we have x = 0 and x = 4.
1 1 2
Substitute with (2), we found λ = −8 and λ = −12. These does not satisfy (3.1).
2 3
If the second condition is not active, and λ 2 , from (3.2) we have x
= 0 1 = 0 and
x = −2. Substitute with (2), we found λ
2 1 = 4 and λ = −6
3
If only the first condition is active, and λ = 0 and λ = 0, from (2) and (3) we have
2 3
2x = x + 2, −2x − x = 2λ , 2x − x = −λ . Solve the three equations, we
1 2 1 2 1 2 1 1
have x 1 ,
= 3 x 2 = 4 λ 1 = −5 , , which don't hold (3.1)
If only the second condition is active, and λ = 0 and λ = 0. We have x + x = 4, 1 3 1 2
−2x − x = −λ and 2x − x = −λ . We have x = 6, x = −2, λ = 10, which
1 2 2 2 1 2 1 2 2
satisfy (3.1).
If only the third condition is active, and λ 1 = 0 , and λ 2 = 0 , we have x 1 = 0 , from
(2) we have no feasible points.
−2 −1
At point x ∗
1
= 6 x , ∗
2
= −2 , we need this matrix z T 2
∇ xx L(x, λ)z
T
= z
T
[ ]z
T
−1 2
to be positive definite where z is the matrix of active constrains at x , which can be ∗
(1, −1) . We have z Lz = 2 > 0, which is positive definite.
T T
Therefore, x∗ is the minimizer of f . In short, minimizer is achieved at x =6 and ∗
1
x = −2.
∗
2
3. Minimize f (x) = c T
x
st. ∑ n
i=1
xi = 0 ,∑ n
i=1
x
2
i
= 1
Let λ = (λ 1, λ2 )
T
be vector associated Langrange multiplier with 2 constrains.
The first order neccessary condition implies that at a local minimum (tagency
condition):
2x 1
⎡ ⎤
1
⎡ ⎤
2x 2
1
∇f = c = λ 1 + λ2 2x 3
1
...
⎣ ⎦
...
⎣ ⎦
2x n
Let c = (c 1, c2 , . . . , cn )
T
represents for vector c. We have the first order neccessary
conditions holds at :
c1 1
⎡ ⎤ ⎡ ⎤
c2 1
x =
2λ 2
1
( c3 − λ1 1 ) where ∑ n
i=1
xi = 0 and ∑ n
i=1
x
2
i
= 1
... ...
⎣ ⎦ ⎣ ⎦
cn 1
This is equivalent with x ∗
i
=
ci
2λ 2
−
λ1
2λ 2
(1) and the constrains are:
and
∇
xx
⎧x i ∗ =
λ2 =
2 ⎷
Consider Lagrange function L(x, λ
have
Hessian matrix:
2
L(x, λ 1 , λ 2 ) = 0 − λ
xx
ci
2λ 2
n
⎨λ 1 = ∑ i=1 c i ×
⎩
λ2 = −
1
2
1
minimizer is achieve at
√∑
λ1
n
2
2λ 2
i=1
The above constrains can rewrite as (2) and (3)
and
1
2
n
∑(c i − λ 1 )
i=1
c (1 +
i
T
1
× 0 − λ
c 1 + c 2 . . . +c n
∑(
i=1
1,
For any vector basis vector Z of the constrains(if exists), we have
T
Z ∇ L(x, λ , λ )Z = −2λ Z Z always positive definite for λ
2
n
1
2
2
T
) − 2∑
2λ 2
= ±
T
2
(c i − λ 1 )
λ1 = ∑ ci ×
2λ 2
i=1
2 ⎷
= −2λ 2 I n×n
i=1
4. a) Write the first- and second-order necessary conditions for a local solution.
1st order conditions (stationary, dual feasibility, primal feasibility,
complementary slackness)
∇f (x ) = A
λ ≥ 0
Ax ≥ 0
λ
T
ci λ1
∗
= n
∑ c (1 +
i
i=1
λ 2 ) = f (x) − λ 1 ∑
(Ax − b) = 0
)
n
2
2
= 1
T
2λ 2
λ
λ1
) − 2 ∑ ci λ1
1
i=1
2
n
i=1
x i − λ 2 (∑
< 0
n
i=1
x
. So the
2
i
− 1)
2nd necessary condition is KTT condition(1st order) are satisfied at (x ∗
, λ) and
z
T 2
is positive semidefinite where z is a null space matrix for active
∇ f (x ∗ )z
constrain at x . ∗
b)
While ∇ 2
f (x) = 0 , the second order sufficient condition does not hold
anywhere.
Suppose x∗ satisfying first order necessary condition is not the minimizer of f and
there is feasible direction d at x such that ∇f (x ) d < 0. Then, from the stationary
∗ ∗ T
condition, at x we have λ ∗ T
Ad < 0 . (1)
Now, d have to satisfying the constrains of the objective function A(x ∗
+ d) ≥ b .(
Ad ≥ 0while d is feasible direction) where A is matrix of active constrain at x . ∗
Now Ax ≥ b − Ad or Ax − b ≥ −Ad.
∗ ∗
From complementary slackness with λ ≥ 0 we have λ (Ax − b) = 0 ≥ −λ Ad or T ∗ T
λ Ad ≥ 0. This contradicts with (1). So there is no feasible direction of descent at x
T ∗
, x is local minimizer. While f is convex (affine function). It implies that x is a
∗ ∗
global minimizer.
5. L(x, λ) = ∑ n
i=1
x i log (
xi
ci
) − λ
T
(Ax − b)
Dual function is
n xi T
L ∗ (x, λ) = min x ∑ x i log ( ) − λ (Ax − b)
i=1 ci
Calculate x such that ∇L(x, λ) = 0, then x where A is the i th
T
−1+λ Ai
i = ci e i
column vector of matrix A.
Dual problem is:
T T T
n −1+λ Ai −1+λ Ai T n −1+λ Ai
maxg(λ) = ∑ ci e log (e ) − λ ((∑ Ai ci e ) − b)
i=1 i=1
T T
n −1+λ Ai T T n −1+λ Ai
= ∑ ci e (−1 + λ Ai ) − λ ((∑ Ai ci e ) − b)
i=1 i=1
=∑
T
n −1+λ Ai T
ci e (−1) − λ b
i=1
First derivative
∂g T
n −1+λ Ai
= −∑ Ai ci e − b
∂λ i=1
Second derivative
2
∂g n T
T −1+λ Ai
T
= −∑ A Ai ci e
∂λ∂λ i=1 i
