Seminar course - Optimization 2 Sheet 4

Seminar course - Optimization 2
Sheet 4
Laurent Pfeiffer, University of Graz
October 24, 2014
Vocabulary Let f : Rn → R, g : Rn → Rm , and e : Rn → Rp be three differentiable functions. For all row-vectors λ ∈ Rm and µ ∈ Rp , we define the Lagrangian
L as follows:
L : (x, λ, µ) ∈ Rn × Rm × Rp 7→ L(x, λ, µ) = f (x) + λg(x) + µe(x) ∈ R.
Consider now the optimization problem with equality and inequality constraints:
inf f (x),
x∈Rn
subject to: g(x) ≤ 0, e(x) = 0.
(1)
We say that x
¯ ∈ Rn is feasible if g(¯
x) ≤ 0 and e(¯
x) = 0. Let x
¯ ∈ Rn be a feasible
point, let I be the set of active inequality constraints, defined by:
I = {i = 1, ..., m | gi (¯
x) = 0}.
We say that x
¯ is qualified if the following row-vectors
{Dgi (¯
x), i ∈ I} ∪ {Dei (¯
x) | i = 1, ..., p}.
(2)
are linearly independent. Finally, we say that x
¯ satisfies the KKT conditions if there
p such that D L(¯
×
R
x
,
λ,
µ)
= 0 and such that for all i = 1, ..., n,
exists (λ, µ) ∈ Rm
x
+
i ∈
/ I =⇒ λi = 0. This last condition is called complementarity condition and is
equivalent to λg(¯
x) = 0.
An important result in the optimization theory states that if x
¯ is a qualified local
optimal solution to problem (1), then it satisfies the KKT conditions.
Exercise 1: stationary points Consider the following problem:
inf
(x,y)∈R2
(x − 2)2 + 2(y − 1)2 ,
subject to: x + 4y ≤ 3, x ≥ y.
Compute the Lagrangian and solve the problem using the KKT conditions.
Exercise 2: stationary points and sensitivity analysis Consider the optimization problem
min x2 + 1, subject to (x − 2)(x − 4) ≤ 0.
1. Give the feasible set, the optimal solution x∗ , the associated Lagrange multiplier λ∗ and the value p∗ of the problem.
1
2. Plot the objective function and show on the graph the feasible set, the optimal
solution(s), the value of the problem, and plot the Lagrangian function L(x, λ)
for a few positive values of λ. Check that for λ ≥ 0,
p∗ ≥ inf L(x, λ).
x∈R
3. Sensitivity analysis. Let u ∈ R, let us denote by p∗ (u) the value of the following
problem:
min x2 + 1, subject to (x − 2)(x − 4) ≤ u,
parameterized by u. Plot u 7→ p∗ (u) and check that dp∗ (0)/du = −λ∗ .
Exercise 3: sufficiency of the KKT conditions in the convex case The goal
of this exercise is to prove that in the case of a convex problem, the KKT conditions
are not only necessary conditions, but also sufficient conditions for optimality.
Let g : Rn → Rm be such that for all i = 1,...,m, gi is a differentiable convex
function, let e : Rn → Rp be an affine function (i.e. there exists A ∈ Rp×n and b ∈ Rp
such that for all x, e(x) = Ax + b). We consider the problem P :
min f (x), subject to: g(x) ≤ 0, e(x) = 0.
(P )
x∈Rn
Let x∗ be a feasible point satisfying the KKT conditions. We denote by L(x, λ, µ) =
f (x) + λg(x) + µe(x) the Lagrangian, let (λ∗ , µ∗ ) be the Lagrange multipliers associated with x∗ . We also define:
n
⊤
∗
N (x∗ ) = (λ, µ) ∈ Rm
(3)
+ × R such that λ g(x ) = 0 .
1. Prove that x∗ is a global minimizer of x 7→ L(x, λ∗ , µ∗ ).
2. Prove the following inequality : for all feasible point x of problem P , for all
(λ, µ) ∈ N (x∗ ),
f (x) − f (x∗ ) ≥ L(x, λ, µ) − L(x∗ , λ, µ).
(4)
3. Deduce that x∗ is a global minimizer of problem P .
Exercise 4: min-max duality This exercise is the continuation of exercise 4. It
can be solved independently, the result of question 3.1 can be used.
1. Compute for all x ∈ Rn the following expression:
sup
L(x, λ, µ).
(5)
p
(λ,µ)∈Rm
+ ×R
2. Prove, without using any of the assumptions on f , g, and e, that
sup
inf L(x, λ, µ) ≤ inf
sup
p
x∈Rn (λ,µ)∈Rm
+ ×R
p x∈Rn
(λ,µ)∈Rm
+ ×R
3. Prove that (6) is an equality.
The left-hand-side of (6) is called dual problem.
2
L(x, λ, µ)
(6)
Exercise 5: dual of a linear-quadratic problem This exercise is an application
of exercises 3 and 4, it can be solved independently.
Let Q ∈ Rn×n be a positive definite symmetrix matrix, let d ∈ Rn . Let A ∈
Rm×n , A¯ ∈ Rp×n , b ∈ Rm , ¯b ∈ Rp , consider the following optimization problem:
inf
x∈Rn
1 ⊤
x Qx + d⊤ x,
2
¯ ≤ ¯b.
subject to: Ax = b, Ax
(7)
1. Formulate the KKT conditions.
2. The optimization as the same form as problem P in exercise 3. Using the
notations of this exercise, compute explicitely:
inf L(x, λ, µ)
x∈Rn
(8)
and write the dual problem of problem (7).
3. Write the dual problem of the optimization problem studied in exercise 2 of
sheet 3. Solve it.
3

Download Report