A 3 Sol

620-361 Operations Research Techniques and Algorithms Assignment 3 Solutions

1. [8 marks] Consider the non-linear program min s.t.

−x1 − x2 x1 ≥ 0 x2 ≥ 0 x21 + 21 x22 ≤ 1.

(a) Write down the Lagrangian of this program. (b) Write down the KKT conditions for this program. (c) Solve the KKT conditions. (d) Show that a constraint qualification holds at your KKT point. (e) Apply a sufficient condition to confirm that your KKT point is a minimum. (a) 1 L(x, λ) = −x1 − x2 + λ1 (−x1 ) + λ2 (−x2 ) + λ3 (x21 + x22 − 1). 2 (b) KKTa: ∇L(x, λ) = KKTb:

!

−1 − λ1 + 2λ3 x1 −1 − λ2 + λ3 x2

"

=

!

0 0

"

.

−x1 ≤ 0, λ1 ≥ 0, λ1 (−x1 ) = 0

−x2 ≤ 0, λ2 ≥ 0, λ2 (−x2 ) = 0 1 1 x21 + x22 − 1 ≤ 0, λ3 ≥ 0, λ3 (x21 + x22 − 1) = .0 2 2 (c) We know that 2λ3 x1 = 1 + λ1 > 0, so neither x1 nor λ3 can be 0. Hence λ1 = 0. We also know that x21 + 21 x22 − 1 = 0. Similarly, λ3 x2 = 1 + λ2 > 0, so x2 cannot be 0 and λ2 = 0. 1

Now 2λ3 x1 = 1 = λ3 x2 , and we know that λ3 %= 0, so 2x1 = x2 . Therefore x21 + 2x21 = 1, which (coupled with x1 ≥ 0) implies that 1 x1 = √ . 3 Back substitution then gives us √ 2 3 . x2 = √ , λ3 = 2 3 (d) The only active constraint at the KKT point is the third constraint. Therefore the only active gradient is " ! 2x1 . ∇g3 (x) = x2 At the KKT point this is 1 2 ∇g3 ( √ , √ ) = 3 3

#

√2 3 √2 3

$

.

Taking d = (−1, −1)T clearly satisfies the Mangasarian-Fromovitz constraint qualification. (e) The Hessian of the Lagrangian is 2

∇ L(x, λ) =

!

2λ3 0

0 λ3

"

.

0

$

.

At the KKT point this is 2

∇ L(x, λ) =

# √

3 0

√

3 2

This is positive definite, and so clearly positive definite on the critical cone. Therefore the KKT point is a minimum. 2. [7 marks] Consider the non-linear program in question 1. (a) Write down the l2 penalty function for this program with penalty parameter α. (b) Find the gradient of the penalty function when α = 41 . (c) Find a minimum of the penalty function when α = x1 > 0, x2 > 0, and x21 + 12 x22 > 1.

1 4

and

(d) The above penalty function has a minimum at an infeasible point. Do you expect the penalty function to have an infeasible minimum for α = 1000? Why or why not? 2

(a) Pα (x) = −x1 − x2 +

α 2

& % 1 (−x1 )2+ + (−x2 )2+ + (x21 + x22 − 1)2+ . 2

(b) ∇P1/4 (x) =

!

−1 − 14 (−x1 )+ + 12 x1 (x21 + 21 x22 − 1)+ −1 − 14 (−x2 )+ + 14 x2 (x21 + 21 x22 − 1)+

"

.

(c) In the specified region, ∇P1/4 (x) =

!

−1 + 12 x1 (x21 + 21 x22 − 1) −1 + 14 x2 (x21 + 21 x22 − 1)

"

.

This means that 1 1 1 1 x1 (x21 + x22 − 1) = 1 = x2 (x21 + x22 − 1) 2 2 4 2 which implies x2 = 2x1 . Then

1 3 1 −1 + x1 (x21 + 2x21 − 1) = x31 − x1 − 1 = 0. 2 2 2 The only real solution of this cubic is x1 = 1, which then gives x2 = 2.

(d) The minimum will also be infeasible. This is because the penalty is quadratically small near the boundary of the constraint, and any decrease in the function will ‘override’ it for small violations. 3. [5 marks] Show that any point on a line drawn between any two feasible points in a convex program is itself feasible. (In other words, that the feasible region is a convex set). If the points are x and y, then any point on the line between then can be expressed as αx + (1 − α)y for some α ∈ [0, 1]. Since gi (x) is convex, gi (αx + (1 − α)y) ≤ αgi (x) + (1 − α)gi (y) ≤ 0 since α ∈ [0, 1] and both x and y are feasible. Furthermore, since h(x) is affine, h(αx + (1 − α)y) = αh(x) + (1 − α)h(y) = 0. Therefore any point on the line is feasible.

3