Lösning till Tentamen TMA946/MAN280 Tillämpad Optimeringslära 020311

1a. Vi har problemet

min 3x_{1} + x_{2}
Då 3x_{1} + 2x_{2} ≥ 1
2x_{1} + x_{2} ≤ 2
x_{1}, x_{2} ≥ 0

till för slackvariabler:

min 3x_{1} + x_{2}
Då 3x_{1} + 2x_{2} − s_{1} = 1
2x_{1} + x_{2} + s_{2} = 2
x_{1}, x_{2}, s_{1}, s_{2} ≥ 0

Ingen uppenbar bas: inför fas I målfunktion och artificiell variabel

\begin{aligned}min & a_{1} \\ Då & 3x_{1} + 2x_{2} − s_{1} + a_{1} = 1 \\ & 2x_{1} + x_{2} + s_{2} = 2 \\ & x_{1}, x_{2}, s_{1}, s_{2}, a_{1} ≥ 0 \end{aligned} ⇔ \begin{matrix}min[0 0 0 0 1] α_{1} ; ⋮ ; a_{1} \\ [ \begin{matrix}3 & 2 & −1 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 \end{matrix} ] & α_{1} ; ⋮ ; a_{1} \end{matrix} = {1 \atop 2}

Vi har bas a_{1}, s_{2} and B = 1 0 0 1 , B^{−1} = 1 0 0 1

Reducerad kostnad blir

c̄ = c_{N}^{T}−c_{B}^{T}B^{−1}N = [0 0 0]−[1 0] [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}3 & 2 & −1 \\ 2 & 1 & 0 \end{matrix} ] = [−3, −2, 1]

Vi väljer första icke-basvariabel som inkommande, ty den har lägst reducerad kostnad.

Sätt y = B_{ink}^{−1} ↙ kolonn ur A för x_{1} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}3 \\ 2 \end{matrix} ] = {3 \atop 2}

Vidare har vi B^{−1}b = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] {1 \atop 2} = {1 \atop 2}

Vi får nu utgående som

u_{t} = argmin_{i,y_{i}>0} ↑ Det index \frac{(B^{−1}b)_{i}}{y_{i}} ↑ som mini- merar detta = 1 ty \frac{1}{3} < \frac{2}{2}

Därmed blir första basvariabeln (a_{1}) utgående. Då a_{1} ej är med i basen vet vi att a_{1} = 0, och vi har en inåten bas till originalproblemet. Fas II: Vi har bas x_{1}s_{2} och problemet

min[3 1 0 0] [ x_{1} ; ⋮ ; s_{2} ]

Då [ \begin{matrix}23 & 2 & −1 & 0 \\ 2 & 1 & 1 \end{matrix} ] [ x_{1} ; ⋮ ; s_{2} ] = [ \begin{matrix}1 \\ 2 \end{matrix} ]

B = [ \begin{matrix}3 & 0 \\ 2 & 1 \end{matrix} ] , B^{−1} = \frac{1}{3} [ \begin{matrix}1 & 0 \\ −2 & 3 \end{matrix} ]

Vi får reducerad kostnad (Bas=x_{1}s_{2}), (icke bas (x_{2}, s_{1}))

\begin{matrix}c̄ = c_{N}^{T} − c_{B}^{T}B^{−1}N = [1 0] − [3 0]\frac{1}{3} [ \begin{matrix}1 & 0 \\ −2 & 3 \end{matrix} ] [ \begin{matrix}2 & −1 \\ 1 & 0 \end{matrix} ] = \\ = [1 0] − [2 − 1] = [−2 1] \end{matrix}

Vi får att första icke-basvariabeln blir inkommande (d.v.s. x_{2}).

Bilda

y = B^{−1}A_{ink} = \frac{1}{3} [ \begin{matrix}1 & 0 \\ −2 & 3 \end{matrix} ] [ \begin{matrix}2 \\ 1 \end{matrix} ] = \frac{1}{3} [ \begin{matrix}2 \\ −1 \end{matrix} ] , B^{−1}b = \frac{1}{3} [ \begin{matrix}1 & 0 \\ −2 & 3 \end{matrix} ] {1 \atop 2} = \frac{1}{3} [ \begin{matrix}1 \\ 4 \end{matrix} ]

ut = argmin_{i,y_{i}>0} \frac{(B^{−1}b)_{i}}{y_{i}} ⇒ ut = 1 ⇒ x_{1} blir utgående. (första basrum)

Ny bas: x_{2}, s_{2}, B = [ \begin{matrix}2 & 0 \\ 1 & 1 \end{matrix} ] B^{−1} = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ]

\begin{matrix}c̄ = c_{N}^{T} − C_{B}^{T}B^{−1}N = [3 0] − [1 0]\frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}3 & −1 \\ 2 & 0 \end{matrix} ] = \\ = [3 0] − \frac{1}{2}[3 − 1] = \frac{3}{2} 1 \end{matrix}

c̄ ≥ 0 ⇒ x_{2}, s_{2} är optimal bas.

Vi har [ \begin{matrix}x_{2} \\ s_{2} \end{matrix} ] = B^{−1}b = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] {1 \atop 2} = [ \frac{1}{2} \frac{3}{2} ]

1b. Ritar vi en bild får vi Om vi minskar d får vi x_{1} = x_{2} = 0 då d = 0 Vidare blir problemet olösligt för d > 4. Titta analytiskt: om vi förändrar hl får vi

\begin{matrix}x_{2} \\ s_{2} \end{matrix} = B^{−1} [ \begin{matrix}d \\ 2 \end{matrix} ] = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}d \\ 2 \end{matrix} ] = [ 2 − \frac{d}{2}^{\frac{d}{2}} ]

basen är tillåten för 0 ⩽ d ⩽ 4

z(d) = c_{B}^{T} · x_{B}(d) = [1 0] [ 2 − \frac{d}{2}^{\frac{d}{2}} ] = \frac{d}{2}

för d < 0 har vi x_{1} = x_{2} = 0 ⇒ z = 0

Vi får därmed z(d) = \{ \begin{matrix}0 , & d < 0 \\ \frac{d}{2} , & 0 ⩽ d ⩽ 4 \\ ∞ , ↑ problemet otillåtet & d > 4 \end{matrix}

2a. Vi kallar Kalles lösning för x̄ och motsvarande duala lösning för y. Vi har problemet

\begin{matrix}min & c^{T} x \\ Då & Ax ≥ b \\ x ≥ 0 \end{matrix}  med dual \begin{matrix}max b^{T} y \\ Då A^{T} y ≤ c \\ y ≥ 0 \end{matrix}

Optimalitetskriterierna för LP ger oss att (komplementaritet)

y^{T} (Ax̄ − b) = 0 x̄^{T} (A^{T} y − c) = 0

Låt Ā vara de kolonner som svarar mot x̄ > 0. P.S.S. för c̄. Då är Ā en m × m + k matris för att vi skall ha

Ā^{T} y = c̄.

Detta överbestämda ekvationssystem har exakt en lösning, den unika duala lösningen.

2b. Titta på Ax̄ ≥ b.

Vi lägger till slackvariabler och får [AI] x̄ ; s̄ = b, x̄ och s̄ är Kalles optimala

lösning. Välj nu ut de kolonner som svarar mot x̄ eller s̄ > 0 och vi får ekvationssystemet

Ã^{0} = b medx̃^{0} > 0

Hitta nu en vektor p. Ã^{0}:s nollrum. Då x̃ > 0 har vi att x̃^{0} + αp^{0} > 0 för små α. Välj nu α s..a. x̃^{0} + αp^{0} ≥ 0 med minst ett element = 0 (notera att vi vet att c̃^{T} p^{0} = 0 ty annars hade x̄ aldrig varit optimal.) Vi kan nu ta bort de kolonner i Ã^{0} som svarar mot x̃ + αp = 0. Vi får då Ã^{2} med färre kolonner. Vi itererar tills dess Ã:s nollrum endast innehåller 0-vektorn. Vi har då hittat ett hörn av polyedern och därmed en baslösning.

3. min \frac{1}{2}(x_{1}^{2} + |x_{2}|^{ρ}) + 2x_{2} s.t. _{2} = 0.

1) KKT-conditions (ρ > 1):

\{ \begin{matrix}x_{2} = 0 \\ ( \begin{matrix}x_{1} \\ \frac{ρ}{2}|x_{2}|^{ρ−1} + 2 \end{matrix} ) + λ ( \begin{matrix}0 \\ 1 \end{matrix} ) = ( \begin{matrix}0 \\ 0 \end{matrix} ) \end{matrix} primal feasibility ⇔ \{ \begin{matrix}x_{1} = 0 \\ x_{2} = 0 \\ λ = −2 \end{matrix}

KKT are sufficient for global optimality because the problem is convex.

2) ρ = 2 σ > 0

\begin{matrix}min \frac{1}{2}(x_{1}^{2} + |x_{2}|^{2}) + 2x_{2} + σx_{2}^{2} = min F(x_{1}, x_{2}) \\ ∇f̃ = ( \begin{matrix}x_{1} \\ x_{2} + 2 + 2σx_{2} \end{matrix} ) = 0 ⇒ \{ \begin{matrix}x_{1} = 0 \\ x_{2} = −\frac{2}{1+2σ} \end{matrix} \end{matrix}

f̃ is convex ⇒ ∇f̃ = 0 is a sufficient for otpimality condition

x_{σ}^{∗} = ( \begin{matrix}0 \\ −\frac{2}{1+2σ} \end{matrix} ) \begin{aligned}& > \\ σ → ∞ \end{aligned} ( \begin{matrix}0 \\ 0 \end{matrix} ) = x^{∗}

3) ρ = 1 σ > 0 min \frac{1}{2}(x_{1}^{2} + |x_{2}|) + 2x_{2} + σx_{2}^{2} = min f̄(x_{1}, x_{2}) 3 cases:

(1) x_{2} > 0 & ∇f̄( \begin{matrix}x_{1} \\ −\frac{1}{2} + 2 + 2σx_{2} \end{matrix} ) = 0 – contradiction

(2) x_{2} = 0 → min \frac{1}{2}x_{1}^{2} ⇒ x_{1} = 0

f̄(0, 0) = 0

(3) x_{2} > 0 ∇f̄ = ( \begin{matrix}x_{1} \\ −\frac{1}{2} + 2 + 2σx_{2} \end{matrix} ) = 0 ⇒ \{ \begin{matrix}x_{1} = 0 \\ x_{2} = −\frac{3}{4σ} \end{matrix}

f̄(0, −\frac{3}{4σ}) = −\frac{3}{16σ} < 0 – golobal mh! (f̄ is convex)

x_{σ}^{∗} = ( \begin{matrix}0 \\ −\frac{3}{4σ} \end{matrix} ) \begin{aligned}& > \\ σ > ∞ \end{aligned} ( \begin{matrix}0 \\ 0 \end{matrix} ) = x^{∗}

We cannot use groelient-based method, because f̄ is not differentiable!

4a. Definition: en funktion f : ℝ^{n} ↦ ℝ är konvex om, for varje val av x^{1}, x^{2} ∈ ℝ^{n} och λ ∈ [0, 1] gäller att

(⊛)  f(λx^{1} + (1 − λ)x^{2}) ≤ λf(x^{1}) + (1 − λ)f(x^{2}).

C^{1}: För varje val av x^{2}, x^{2} ∈ ℝ^{n} gäller att

(⊛⊛)  f(x^{2}) ≥ f(x^{1}) + ∇f(x^{1})^{T} (x^{2} − x^{1}).

C^{2}: För varje val av x ∈ ℝ^{n} och p ∈ ℝ^{n} gäller att

p^{T} ∇^{2}f(x)p ≥ 0.

C^{1} igen:

(⇐) Vi har: ⊛⊛ ger:

f(x^{1}) ≥ f(λx^{1} + (1 − λ)x^{2}) + (1 − λ)∇f(λx^{1} + (1 − λ)x^{2})^{T} (x_{1} − x_{2}) f(x^{2}) ≥ f(λx^{1} + (1 − λ)x^{2}) + λ∇f(λx^{1} + (1 − λ)x^{2})^{T} (x_{2} − x_{1}) Addera: λ · (rad 1) + (1 − λ) · (rad 2) ⇒ ⊛

(⇒) ⊛ ⇒ (1−λ)f(x^{2}) ≥ (1−λ)f(x^{1})+[f(x^{1}+(1−λ)(x^{2}−x^{1}))−f(x^{1})]. Dividera med 1 − λ och låt λ → 1. Då fås ⊛⊛

b) Det mesta talar för en quasi-Newton algoritm: vi har bara tillgång till ∇f, inte ∇^{2}f; problemet är konvext, så approximationen av Newton-riktningen bör vara bra; problemet är ganska stort men varje rang-2-uppdatering fordrar bara ytterligare 2 ∗ n i minnesutrymme. c)

(D) \begin{matrix}max(b^{k})^{T} y \\ då A^{T} y ≤ c \\ y ≥ 0 \end{matrix} Lös dualen! Återanvänd den optimala basen för nästa k – reoptimera!

5. Variabler: d : godstjocklek (m) ℓ : längd hos cylinder delen (m) r : radie har kloten (m)

Modell:

minimera (2π_{r}ℓ + 4πr^{2})d

då

2r + ℓ ≤ 5.87 − 2d  (längd)
2r ≤ 2.34 − 2d  (bredd)
prc_{2} ≤ d  (kapacitet)
p(πr^{2} + 3/4πr^{3}) = c_{1}  (tryck-volym)
d, r, ℓ ≥ 0

6a) Lagrange funktion: L(x, λ) := f(x) − ∑_{i=1}^{m} λ_{i}g_{i}(x).

Lagrangedual funktion: L_{∗}(λ) := min_{x∈X} L(x, = lambda), λ ≥ 0^{m}.

Det Lagrangeduala problemet är:

(LD)  maximera_{λ≥0^{m}}L_{∗}(λ).

Svag dualitet: Antag att x̄ är tillåten i ursprungsproblemet (1)–(3), och att λ̄ ≥ 0^{m}, dvs, tillåten i (LD). Då gäller att L_{∗}(λ̄) ≤ f(x̄).

Bevis:

f(x̄) ≥ f(x̄) − ∑_{i=1}^{m} λ̄_{i}g_{i}(x̄)  /λ̄ ≥ 0^{m}, g(x̄) ≥ 0^{m}/
= L(x̄, λ̄)
≥ L_{∗}(λ̄). ■  /x̄ ej säkert i argmin_{x∈X}L(x, λ̄)/

b) Antag att λ̄ ≥ 0^{m} (tillåten i (LD)). Om följande mängd är icke-tom innehåller den samtliga optimala lösningar till (1)–(2), λ̄ är optimal i (LD), och L_{∗}(λ̄) = f(x^{∗}):

X^{∗} = argmin_{x∈X}L(x, λ̄) ∩ {x ∈ ∖^{n}|g(x) ≥ 0^{m}} ∩ {x ∈ ∖^{n}|λ̄^{T} g(x) = 0} Bevis: Låt x^{∗} ∈ X^{∗}. Då är x^{∗} tillåten (1)–(3). Dessutom: L_{∗}(λ̄) = f(x^{∗}) − λ̄^{T} f(x^{∗}) = f(x^{∗}). Eftersom svag dualitet gäller enligt a) måste x^{∗} vara optimal i (1)–(3) och λ̄ i (LD).

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

För (P) är då L(x, λ) := c^{T} x − λ^{T} (Ax − b) = (c − A^{T} λ)^{T} x + b^{T} λ, och med X = {x ∈ ℝ^{n}|x ≥ 0^{n}} får att

L_{x}(λ) := \{ \begin{matrix}b^{T} λ & om c ≥ A^{T} λ \\ −a & annars. \end{matrix}

Alltså är (Ld) ekvivalent med (D). Optimalitetsvillkoren är: x^{∗} tillåten i (P), y^{∗} tillåten i (D), x^{∗} och y^{∗} är komplementära.

\begin{matrix}\begin{matrix}Ax^{∗} ≥ b \\ x^{∗} ≥ 0 \end{matrix} ; \begin{matrix}A^{T} y^{∗} ≤ c \\ y^{∗} ≥ 0 \end{matrix} ; \begin{matrix}y^{∗T} (Ax^{∗} − b) = 0 \\ x^{∗T} (A^{T} y^{∗} − c) = 0 \end{matrix} \\ (a)  (b)  (c) \end{matrix}

Från g(x^{∗}) ≥ 0 och x^{∗} ∈ X finner vi (a). Från λ̄^{T} g(x^{∗}) = 0 finner vi y^{∗T} (T x^{∗} − b) = 0. Kvar: x^{∗} löser min_{x∈X} L(x, λ̄). I fallet LP fås: x^{∗} minimerar (c − A^{T} y^{∗})^{T} x över x ≥ 0. Detta problem separerar över x_{j}: min(c_{j} −A_{j}^{T} b^{∗})x_{j} över x_{j} ≥ 0.

Optimum: Antingen är x_{j}^{∗} > 0 och c_{j} = A_{j}^{T} y^{∗} eller x_{j}^{∗} = 0 och c_{j} ≥ A_{j}^{T} y^{∗} eller

∵ x^{∗} ≥ 0; c ≥ A^{T} y^{∗}; x^{∗T} (A^{T} y^{∗} − c), dvs resten av (a)–(c). Klart.

7. Refined optimality conditions 1) \underline{Necessary conditions} Suppose x_{0} is a local min, but

f′(x_{0}) = … = f^{(n−1)}(x_{0}) = 0 and f^{(n)}(x_{0}) ≠ 0

for some odd integer n.

Taylor expansion:

\begin{matrix}f(x) = f(x_{0}) + f′(x_{0})(x − x_{0}) + … + \frac{1}{n!}f^{(n)}(x̃)(x − x_{0})^{n} = \\ = f(x_{0}) + \frac{1}{n!}f^{(n)}(x̃)(x − x_{0})^{n}, \end{matrix}

where x̃ is a point between x and x_{0}. For all sufficiently close to x_{0} points x both f^{(n)}(x̃) and f^{(n)}(x_{0}) have the same sign. Therefore, we can get f(x) < f(x_{0}) by approximating x_{0} from left (if f^{(n)}(x_{0}) > 0) or right (if f^{(n)}(x_{0}) < 0), which contradicts local minimality of x_{0}. The other possibility is to have

f′(x_{0}) = … = f^{(n−1)}(x_{0}) = 0 & f^{(n)}(x_{0}) < 0

for some even integer n. Taylor expansion: f(x) = f(x_{0}) + \frac{1}{n!}f^{(n)}(x̃)(x − x_{0})^{n} < f(x_{0}) for all sufficiently close to x_{0} points x!

2)

Sufficient conditions Taylor expansion

f(x) − f(x_{0}) = \frac{1}{n!}f^{(n)}(x̃)(x − x_{0})^{n} > 0

for all x, sufficiently close to x_{0} (since x̃ is a point between x and x_{0}, f^{(n)}(x_{0}) > 0, and f^{(n)}(·) is a continuous function).

3) “Gap”

\begin{matrix}f_{1}(x) < 0 & for & x < 0 \\ f_{1}(x) > 0 & for & x > 0 \end{matrix} ⇒ \begin{matrix}f(0) = 0 \\ x_{0} = 0 \end{matrix} is not a local min

\begin{matrix}f_{2}(x) > 0 & for & x ≠ 0 \\ f_{2}(x) = 0 & for & x = 0 \end{matrix} ⇒ x_{0} = 0 is a strict local min

However, f_{i}^{(n)}(0) = lim_{x→0} f_{i}^{(n)}(x) = lim_{x→0} P_{i}^{n}(\frac{1}{x})e^{−1/x^{2}} = 0, where P_{n}^{i} is a some polynomial function. Therefore, necessary conditions hold for f_{1} at x_{0} = 0, but it is not a local minimum! Sufficient conditions are violated for f_{2} of x_{0} = 0, but it is a strict local minimum!