Lösningsförslag tentamen TMA945 Tillämpad optimeringslära 990308

1 a) Modell: sök ett maximal flöde mellan nod s och nod t:

max f

då \begin{matrix}Σ_{i}x_{si} = f, \\ Σ_{j}x_{ij} − x_{si} = 0, i = 1, …, 7, \\ x_{jt} − Σ_{i}x_{ij} = 0, j = 1, …, 5 \\ −Σ_{j}x_{jt} = −f \\ 0 ≤ x_{si} = 3, i = 1, …, 7; 0 ≤ x_{ij} ≤ 1, i = 1, …, 7, j = 1, …, 5; 0 ≤ x_{·t} ≤ (6, 4, 5, 4, 3) \end{matrix}

b) Bågar motsvarande ’x’ i tabellen (variabler x_{ij}) stryks.

2 a) Efter tillägg av en slackvariabel s_{1}) fås:

min z = 3x_{1} + 2x_{2} + x_{3}

då \begin{matrix}2x_{1}  + x_{3} − s_{1} = 3 \\ 2x_{1} + 2x_{2} + x_{3} = 5 \\ x_{1}, x_{2}, x_{3}, s_{1} ≥ 0 \end{matrix}

för att identifiera en tillåten baslösning, löses först Fas-1 problemet att minimera w = a_{1} + a_{2} = (3 − 2x_{1} − x_{3} + s_{1}) + (5 − 2x_{1} − 2x_{2} − x_{3}) = 8 − 4x_{1} − 2x_{2} − 2x_{3} + 5_{1}.

bas w x_{1} x_{2} x_{3}  s_{1}  a_{1} a_{2}  b̄
−w 1 −4 −2 −2  1  0  0 −8 x_{1} ink. a_{1} utg.
a_{1} 0 2 0 1  −1  1  0 3
a_{2} 0 2 2 1  0  0  1 5
−w 1 0 −2 0  −1  2  0 −2 x_{2} ink, a_{2} utg.
x_{1} 0 1 0 1/2 −1/2 1/2 0 3/2
a_{2} 0 0 2 0  1  −1 1 2
−w 1 0 0 0  0  1  1 0 c̄_{j} ≥ 0∀j, optimum
x_{1} 0 1 0 1/2 −1/2  1/2 0 3/2 w_{∗} = 0 ⇒ tillåten bas
x_{2} 0 0 1 0 1/2 −1/2 1/2 1 funnen.

Inför

\begin{aligned}z & = 3x_{1} + 2x_{2} + x_{3} = 3 · (3/2 − 1/2x_{3} + 1/2s_{1}) + 2 · (1 − 1/2s_{1}) + x_{3} \\ & = 13/2 − 1/2x_{3} + 1/2s_{1} \end{aligned}

uttryckt i icke-basvariabler och genomför Fas-2.

bas z x_{1} x_{2} x_{3} s_{1} b̄
−z 1 0 0 −1/2 1/2 −13/2 x_{2} ink. x_{1} utg.
x_{1} 0 1 0 1/2 −1/2 3/2
x_{2} 0 0 1  0  1/2  1
−z 1 1 0  0  0  −5 c̄_{j} ≥ 0, ∀j, optimum
x_{3} 0 2 0  1  −1  3
x_{2} 0 0 1  0  1/2  1

x_{∗} = (0, 1, 3)^{T} , z_{∗} = 5

bas z x_{1} x_{2} x_{3} s_{1} b̄
−z 1 1 0 0  0 −5 s_{1} ink, x_{2} utg.
x_{3} 0 2 0 1 −1 3
x_{2} 0 0 1 0 1/2 1
−z 1 1 0 0  0 −5 c̄_{j} ≥ 0, ∀j, optimum
x_{3} 0 2 2 1  0  5
s_{1} 0 0 2 0  1  2

En alternativ optimal extrempunkt är

x_{∗} = (0, 0, 5)^{T} , z_{∗} = 5.

\underline{Samtliga} optimallösningar ges av mängden.

{x̄ ∈ ℝ^{3}/x̄ = λ(0, 1, 3)^{T} + (1 − λ)(0, 0, 5)^{T} för något λ ∈ [0, 1]}.

3 a) min_{x∈ℝ^{2}} f(x) = \frac{1}{2}(x_{1} + x_{2} − 1)^{2} + \frac{1}{2}(x_{1} − x_{2} − 2)^{2} + \frac{1}{2}(x_{1} − 2x_{2})^{2}.

b) Se kurslitteraturen. Låt x_{0} = (0, 0)^{T}.

∇f(x) = [ \begin{matrix}(x_{1} + x_{2} − 1) + (x_{1} − x_{2} − 2) + (x_{1} − 2x_{2}) \\ (x_{1} + x_{2} − 1) − (x_{1} − x_{2} − 2) − 2(x_{1} − 2x_{2}) \end{matrix} ] = [ \begin{matrix}3x_{1} − 2x_{2} − 3 \\ −2x_{1} + 6x_{2} + 1 \end{matrix} .

∇^{2}f(x) = [ \begin{matrix}3 & −2 \\ −2 & 6 \end{matrix} ], positivt definit ⇒ f är strikt konvex.

p_{0} = −∇^{2}f(x_{0})^{−1}∇f(x_{0}) = −\frac{1}{12 − 4} [ \begin{matrix}6 & 2 \\ 2 & 3 \end{matrix} ] [ \begin{matrix}−3 \\ 1 \end{matrix} ] = \frac{1}{14} [ \begin{matrix}16 \\ 3 \end{matrix} ] .

f kvadratisk ⇒ optimalt steg i riktning p_{0} ges av

α_{0} = −\frac{∇f(x_{0})^{T} p_{0}}{p_{0}^{T} ∇^{2}f(x_{0})p_{0}} = \frac{∇f(x_{0})^{T} ∇^{2}(x_{0})^{−1}∇f(x_{0})}{[∇^{2}f(x_{0})^{−1}∇f(x_{0})]^{T} ∇^{2}f(x_{0})[∇^{2}f(x_{0})^{−1}∇f(x_{0})]} = 1.

x_{1} = x_{0} + α_{0}p_{0} = \frac{1}{14} [ \begin{matrix}16 \\ 3 \end{matrix} ]. I x_{1} är ∇f(x_{1}) = (0, 0)^{T}. Eftersom f är

konvex är x_{∗} = \frac{1}{14} [ \begin{matrix}16 \\ 3 \end{matrix} ] den optimala lösningen. c) Se kurslitteraturen. Låt x_{0} = (0, 0)^{T} .p_{0} = −∇f(x_{0}) = (3, −1)^{T}.

α_{0} = −\frac{∇f(x_{0})^{T} p_{0}}{p_{0}^{T} ∇^{2}f(x_{0})p_{0}} = \frac{1)}{(3, −1)(11, −12)^{T}} = 2/9 x_{1} = x_{0} + α_{0}p_{0} = \frac{2}{9}([ \begin{matrix}3 \\ −1 \end{matrix} ]

p_{1} = −∇f(x_{1}) = \frac{5}{9} [ \begin{matrix}1 \\ 3 \end{matrix} ] , α_{1} = −\frac{∇f(x_{1})^{T} p_{1}}{p_{1}^{T} ∇^{2}f(x_{1})p_{1}} p_{1}^{T} ∇^{2}f(x_{1})p_{1} = \frac{10}{(1, 3)(−3, 16)} = 2/9

x_{2} = x_{1} + α_{1}p_{1} = \frac{4}{81} [ \begin{matrix}16 \\ 3 \end{matrix} ] .

4. (P) min f(x) := ∑_{j=1}^{n} c_{j}x_{j}

då \begin{matrix}g_{0}(x) := ∑_{j=1}^{n} x_{j}^{2} − 1 ≤ 0 \\ g_{j}(x) := x_{j} ≥ 0, j = 1, …, n \end{matrix}

a) f är linjär och alltså konvex; g_{0} är konvex ty ∇^{2}g_{0}(x) = 2 · I^{n} är positivt definit, och därför är mängden {x ∈ ℝ^{n}|g_{0}(x) ≤} konvex; g_{j} är linjär och alltså konkav, och därför är mängden {x ∈ ℝ^{n}/x ≥ 0} konvex. Eftersom skärningen av konvexa mängder är en konvex mängd, och vi skall minimera en konvex funktion över mängden, är problemet konvext.

b) KKT-villkoren: (L(x, λ, μ) = f(x) − λg_{0}(x) − ∑_{j=1}^{n} μ_{j}x_{j}, λ ≤ 0, μ_{j} ≥ 0)

(1) \frac{∂L(x, λ, μ)}{∂x_{j}} := c_{j} − 2λx_{j} − μ_{j} = 0, j = 1, …, n,

(2) λ ≤, μ_{j} ≥ 0, j = 1, …, n,

(3) λ(∑_{j=1}^{n} x_{j}^{2} − 1) = 0, μ_{j}x_{j} = 0, j − 1, …, n,

(4) ∑_{j=1}^{n} x_{j}^{2} − 1 ≤ 0, x_{j} ≥ 0, j = 1, …, n.

Låt λ̄ = −\frac{1}{2}(∑_{j=1}^{n}(min\{0, c_{j}\})^{2})^{1/2}, x̄_{j} = min\{0, c_{j}\}/(2λ̄), j = 1, …, n, μ̄_{j} = max\{0, c_{j}\}, j = 1, …, n.

(1) c_{j} − 2λ̄x̄_{j} − μ̄_{j} = c_{j} − max{0, c_{j}} − min{0, c_{j}} = 0. OK

(2) OK

(3) ∑_{j=1}^{n} x̄_{j}^{2} = 1; λ̄ > 0 ger att μ̄_{j}x̄_{j} = 0. OK

(4) OK c) Genom insättning av (1) i Lagrangefunktionen kan vi uttrycka det Lagrange

duala problemet i (λ, μ) som ett explicit konvext problem. Detta har en unik lösning, som är (λ̄, μ̄), och den enda KKT-punkten x är den som uppfyller (1), d.v.s. x̄. Således är x̄ den unika optimallösningen.

L(x(λ, μ), λ, μ) = λ + \frac{1}{4λ} ∑_{j=1}^{n}(c_{j} − μ_{j})^{2} =: L_{∗}(λ, μ).

L_{∗} är monoton i μ_{j}. \frac{∂L_{∗}(λ, μ_{)}}{∂μ_{j}} = −\frac{1}{2λ}(c_{j} − μ_{j}) ≥ 0 måste gälla, vilket ger

μ̄.

En stationär punkt till L_{∗} måste ha λ > 0. \frac{∂L_{∗}(λ, μ̄)}{∂λ} = 0 ger λ̄.

Alternativ: ∇_{xx}^{2}L(x̄, λ̄, μ̄) = −2λ̄I^{n} (positivt definit) utnyttjas.

5. (P) \begin{matrix}min c^{T} x \\ då Ax = b \\ x ≥ 0 \end{matrix} (D) \begin{matrix}max b^{T} y \\ då A^{T} y ≤ c \end{matrix}

Starka dualsatsen: Om det ena problemet av (P) eller (D) har en ändlig optimallösning så har också det andra det, och deras optimala målfunktionsvärden är lika.

Bevis: Antag att x_{∗} löser (P). Antag (utan inskränkning) att x_{∗} är en extrempunkt och betrakta en tillåten baslösning motsvarande x_{∗} och som i en simplextablå uttrycker dess optimalitet:

\begin{matrix}bas & −z & x & b̄ \\ −z & 1 & c^{T} − c_{B}^{T}B^{−1}A & −c_{B}^{T}B^{−1}b \\ x_{B} & 0 & B^{−1}A & B^{−1}b \end{matrix}

Sätt y_{∗} = (B^{−1})^{T} c_{B}, d.v.s. y_{∗}^{T} = c_{B}^{T}B^{−1}. Tablån uttrycker optimalitet, d.v.s. att c̄^{T} := c^{T} − c_{B}^{T}B^{−1}A ≥ 0^{T}. Vi får att c^{T} − y_{∗}^{T} A ≥ 0^{T}, d.v.s. att A^{T} y_{∗} = leqc. Vektorn y_{∗} är därmed tillåten i (D). Dessutom fås att c^{T} x_{∗} = c_{B}^{T}B^{−1}b = y_{∗}^{T} b, d.v.s. att y_{∗} har samma målfunktionsvärde i (D) som x_{∗} har i (P). Eftersom c^{T} x ≥ b^{T} y gäller för alla (x, y) tillåtna i (P) och (D) [c^{T} x ≥ x^{T} A^{T} y = b^{T} y] måste y_{∗} vara optimal i (D).

6. (P) max z = 6x_{1} − 12x_{2} + 20x_{3}

då \begin{matrix}4x_{1} + 8x_{2} + 10x_{3} + x_{4} ≤ 60 & | & y_{1} ≥ 0 \\ 3x_{1} + 4x_{2} + x_{3} − 2x_{4} ≥ 20 & | & y_{2} ≤ 0 \\ x_{1}, x_{2},  x_{4} ≥ 0 \\ x_{3}  ≤ 0 \end{matrix}

(D) min w = 60y_{1} + 20y_{2}

då \begin{matrix}4y_{1} + 3y_{2} ≥ 6 & | & x_{1} ≥ 0 \\ 8y_{1} + 4y_{2} ≥ −12 & | & x_{2} ≥ 0 \\ 10y_{1} + y_{2} ≤ 20 & | & x_{3} ≤ 0 \\ y_{1} − 2y_{2} ≥ 0 & | & x_{4} ≥ 0 \\ y_{1} ≥ 0, y_{2} ≤ 0 \end{matrix}

Optimum i (D): y_{∗} = (3/2, 0)^{T} , w_{∗} = 90

Komplementaritet ger: x_{2} = x_{3} = x_{4} = 0 (ty slack i duala bivillkoren (2),

(3) och (4)), och att 4x_{1} = 60 (ty y_{1} ≠ 0). Den primala optimallösningen är alltså x_{∗} = (15, 0, 0, 0)^{T}.

Kontroll av primal tillåtenhet ger att samtliga optimalitetsvillkor är uppfyllda.

7 a) Optimalitetsvillkoren för [p′(x_{t})] ger

\begin{matrix}∇f(y) + γ(y − x_{t}) = 0 ↔ Qy + q + γ(y − x_{t}) = 0 ⇔ \\ (Q + γI)y = γx_{t} − q ⇔ (Q + γI) \underbrace{y − x_{t})} p \begin{matrix}= γx_{t} − q − (Q + γI)x_{t} \\ = −(Qx_{t} + q). \end{matrix} \end{matrix}

b) Om {x_{t}} konvergerar mot x_{∞} så måste {p_{t}} = {x_{t+1} − x_{t}} konvergera mot noll. Ur uppdateringsformeln fås att p_{t} = (Q + γI)^{−1}∇f(x_{t}) för alla t. Sekvensen {∇f(x_{t})} konvergerar mot ∇f(x_{∞}) eftersom f är kontinuerligt differentierbar. Om ∇f(x_{∞}) ≠ 0 skulle gälla fås ur uppdateringsformeln att {p_{t}} skulle konvergera mot (Q + γI)^{−1}∇f(x_{∞}) ≠ 0, ty (Q + γI)^{−1} är positivt definit när a + γI är det. Detta leder till en motsägelse. Således är ∇f(x_{∞}) = 0. Eftersom f är konvex är x_{∞} ett globalt minimum av f över ℝ^{n}.