Tentamen i TMA945 Tillämpad optimeringslära 980819

1. Matematisk modell:

x_{j} = antal enheter som körs i process j, j = 1, 2;
y = antal halvtimmar som fotomodellen anlitas

maximera f(x, y) :=50(3x_{1} + tx_{2}) − 3(x_{1} + 2x_{2})
− 2(2x_{1} + 3x_{2}) − 5000y,

då \begin{matrix}x_{1} + 2x_{2} ≤ 20, 000, \\ 2x_{1} + 3x_{2} ≤ 35, 000, \\ 3x_{1} + 5x_{2} ≤ 1, 000 + 200y \\ x_{1} ≥ 0, x_{2} ≥ 0, 0 ≤ y ≤ \end{matrix}

2. Antag att x_{1}, …, x_{m} är startbas. Inför ett extra bivillkor

∑_{j=m+1}^{n} x_{j} ≥ M, M ≪ 0.

Låt s vara slackvariabel i villkoret. En baslösning är (x_{1}, …, x_{m}, s). En dualt tillåten baslösning skapas nu som följer: välj som inkommande basvariabel x_{j^{∗}}, där j_{j^{∗}} ∈ arg min{c̄_{j}|j = m + 1, …, n}. Om c_{j^{∗}} ≥ 0 är den nuvarande basen redan dualt tillåten, annars väljs s som utgående basvariabel. Nya reducerade kostnader är 0 för x_{1}, …, x_{m}, c̄_{j} − c̄_{j^{∗}}(≤ 0) för x_{m+1}, …, x_{n} och −c̄_{j^{∗}} för s, och alltså gäller att den nya basen är dualt tillåten.

Detta är ekvivalent med stora M-metoden. Det framgår till exempel genom att studera dualen till det nya problemet.

[p] \begin{matrix}minimera f(x) := c^{T} x \\ då \begin{matrix}Ax = b \\ 1^{T} x ≤ M \\ x ≥ 0 \end{matrix} 1 = (1, 1, …, 1)^{T} \end{matrix}

har ett dualt problem som är ekvivalent med LP-problemet.

[D′′] \begin{matrix}maximera g(y, a) := b^{T} y − Ma, \\ då & \begin{matrix}A^{T} y − 1a ≤ c, \\ a ≥ 0 \end{matrix} \end{matrix}

och de två pivoteringarna är dualt ekvivalenta, ty att prirotera in a i [D′′] så att högerledet (c̄) blir positivt är precis detsamma som att pivotera ut s i [p′].

3. Fall I: {∇f(x^{T})} → 0^{n}, {x^{t}} och {f(x^{t})} divergerar. Exempel: f(x) = − log x; {x^{t}} → ∞, {f(x^{t})} → −∞, {f′(x^{t})} → 0 Fall II: {∇f(x^{t})} → 0^{n}, {x^{t}} divergerar , {f(x^{t})} konvergerar. Exempel: f(x) = 1/x; {x^{t}} → ∞, {f(x^{t})} → 0, {f(x^{t})} → 0 Fall III: {∇f(x^{t})} → 0^{n}, {x^{t}} är begränsad, {f(x^{t})} är begränsad.

Exempel: f(x) = \frac{1}{3}x^{3} − x; x^{t} = \{ \begin{matrix}1 + 1/t, & t udda \\ −1 − 1/t & t jämna \end{matrix}

{x^{t}} har två hopningspunkter, ±1, och {f(x^{t})} har två hopningspunkter ±2/3. Fall IV: {∇f(x^{t})} → 0^{n}, {x^{t}} är begränsad, {f(x^{t})} konvergerar. Exempel: f(x) = x^{2} − 1; x^{t} som ovan; {f(x^{t})} → 0. Fall V: {∇f(x^{t})} → 0^{n}, {x^{t}} och {f(x^{t})} konvergerar. Exempel: f som ovan, x^{2} − 1 + 1/t

4 a) I en baslösning (x_{0}, x_{N}) gäller att

BX_{B} + NX_{N} = b ⇔ X_{B} = B^{−1}b − B^{−1}NX_{N}. Om x_{j}(j ∈ N) ökar från noll fås därför att

X^{NY} = [ \begin{matrix}B^{−1} \\ 0 \end{matrix} ] + ℓ [ \begin{matrix}−B^{−1}a_{j} \\ e_{j} \end{matrix} ] ,

där a_{j} är kolumn j i N och e_{j} ör den j:te enhetsvektorn ∵ p_{j} = [ \begin{matrix}−B^{−1}a_{j} \\ e_{j} \end{matrix} ] I baslösningen gäller också att den reducerade kostnaden är

C̄_{N}^{T} = C_{N}^{T} − C_{B}^{T}B^{−1}N.

Vi har nu att

\begin{aligned}C^{T} ρ_{j} & = (C_{B}, C_{N})^{T} ρ_{j} = −C_{B}^{T}B^{−1}a_{j} + C_{N}^{T}e_{j} \\ & = C_{j} − C_{B}^{T}B^{−1}a_{j} = C̄_{j}. \end{aligned}

Att välja minsta värdet på C̄_{j} är alltså detsamma som att välja minsta värdet av ρ_{j}. b) Inkommandekriteriet är skalningsberoende, och beror till exempel på längden

hos varje halvlinjes riktningsvektor ρ_{j}. Ett skalningsoberoende mått är i stället

min_{j∈N} \{\frac{C^{T} ρ_{j}}{∥ρ_{j}∥} \}.

5. Antag att x̂ ∈ X̂. Konvexiteten hos f ger att

f(x^{∗}) ≥ f(x̂) + ∇f(x̂)^{T} (x^{∗} − x̂) = f(x̂) + ∇f(x^{∗})^{T} (x^{∗} − x̂)
= f(x̂). Alltså är x̂ ∈ x^{∗}, och X̂ ≤ X^{∗} gäller.

Antag att x̂ ∈ X^{∗}. Konvexiteten hos f ger att

\begin{matrix}f(x^{∗}) ≥ f(x̂) + ∇f(x̂)^{T} (x^{∗} − x̂) \\ f(x̂) ≥ f(x^{∗}) + ∇f(x^{∗})^{T} (x̂ − x^{∗}) \end{matrix} \} ⇒ [∇f(x̂) = ∇f(x^{∗})]^{T} (x̂ − x^{∗}) ≥ 0.

Men den omvända olikheten gäller också, eftersom

\begin{matrix}x̂ ∈ X^{∗} ⇒ ∇f(x̂)^{T} (x^{∗} − x̂) ≥ 0 \\ x^{∗} ∈ X^{∗} ⇒ ∇f(x^{∗})^{T} (x̂ − x^{∗}) ≥ 0 \end{matrix} enligt optimalitetsvillkorer.

Alltså gäller att [∇f(x^{∗}) − ∇f(x̂)]^{T} (x^{∗} − x̂) = 0. Vi får då ur konvexitetsolikheten

f(x̂) ≥ f(x^{∗}) + ∇f(x^{∗})^{T} (x̂ − x^{∗})

att ∇f(x^{∗})^{T} (x̂−x^{∗}) = 0 måste gälla, ty f(x̂) = f(x^{∗}) gäller och ∇f(x^{∗})^{T} (x̂− x^{∗}) ≥ 0. Från konvexiteten hos f fås nu att f(x) ≥ f(x^{∗}) + ∇f(x^{∗})^{T} (x − x^{∗}) = f(x̂) + ∇f(x^{∗})^{T} (x − x̂), ∀x ∈ X, ty f(x̂) = f(x^{∗}). Alltså är ∇f(x^{∗}) = ∇f(x̂).

Alltså är x̂ ∈ X̂, och x^{∗} = X̂ gäller. ■

6 a) Lös LP-problemet med målfunktionskoefficient c^{2} + λ_{p}, där p = C^{1} − C^{2}, och lös först för λ = 0.

Givet optimalbasen B bestäms det högsta värdet för λ för vilket optimalitet bibehålls: vi skall ha

\begin{matrix}(C_{N}^{2} + λp_{N})^{T} − (C_{B}^{1} + λp_{B})^{T} B^{−1}N ≤ 0 ⇔ \\ λ(p_{N}^{T} − p_{B}^{T}B^{−1}N) ≤ −(C_{N}^{2T} − C_{B}^{T_{2}}B^{−1}N). \end{matrix}

Av intresse är de i för vilka (p_{N}^{T} − p_{B}^{T}B^{−1}N)_{i} > 0. Vi får:

λ̄ = min_{i} \{ − \frac{(C_{N}^{2^{T}} − C_{B}^{2^{T}} B^{−1}N)_{i}}{(p_{N}^{T} − p_{B}^{T}B^{−1}N)_{i}} |(p_{N}^{T} − p_{B}^{T}B^{−1}N)_{i} > 0\}.

Det index i som ger min motsvarar den inkommande basvariabeln vid besbytet som sker då λ > λ̄. Om inget index i finns betyder det att basen är optimal för alla λ ≥ 0, annars pivoteras till en ny optimal bas är nådd, varefter förfarandet upprepas från nästa aktuella värde av λ(λ̄). Kompromisslösningarna består av de optimala lösningar som passerats då λ har ändrats från 0 till 1.

b) Geometrisk lösning ger att

x^{∗} = [ \begin{matrix}0 \\ 3 \end{matrix} ] för λ ∈ [0, 1/2]
x^{∗} = [ \begin{matrix}2 \\ 4 \end{matrix} ] för λ ∈ [1/2, 1]

7 a) Brantaste lutningsmetodens sökriktning ges till exempel av min ∇f(x^{t})^{T} p+ 1/(2γ)∥ρ∥^{2}, ty första ordningens villkor är att ∇f(x^{t}) + (1/γ)ρ = 0^{n}, d.v.s. ρ = −γ∇f(x^{t}). Motsvarande p från min ∇f(x^{t})^{T} ρ då ∥p∥ ≤ Δ fås genom att betrakta det ekvivalenta problemet min ∇f(x^{t})^{T} p. Eftersom målfunktionen då ∥p∥^{2} ≤ Δ^{2} är linjär är bivillkoret med nödvändighet bindande, varför vi får att, för något λ > 0,

∇f(x^{t}) + 2λ · ρ = 0^{n} eller ρ = −1/(2λ)∇f(x^{t}),

dvs samma riktning som minus gradienten av f i x^{t} i båda fallen.

b) I. Ett ekvivalent problem är

\begin{matrix}min & ψ_{t}(p) \\ då & ∥p∥^{2} ≤ Δ_{t}^{2}. \end{matrix}

första ordningens nödvändiga krav ger att

∇ψ_{t}(ρ) + λρ = 0^{n}, dvs
∇f(x^{t}) + ∇^{2}f(x^{t})ρ + λρ = 0^{n}, eller
[∇^{2}f(x^{t}) + λI^{n}]ρ = −∇f(x^{t}).

Andra ordningen nödvändiga krav ger att

∇^{2}f(x^{t}) + λI^{n} är positivt semidefinition 7.

II. Om λ = 0 fås att p är Newtonriktningen. Då λ ökar mot ∞ fås i stället en sökriktning som i limes är brantaste lutningsriktningen. (Det förra händer om Δ_{t} är start nog medan det senare inträffar när Δ_{t} blir allt mindre. För att se det kan man använda relationen Δ_{t} ≥ ∥p∥ = ∥(∇^{2}f(x^{t}) + λI)^{−1}∇f(x^{t})∥.) Fördelen med en trustregion är att medan en sökmetod fixerar sökningen så får den här variera (med Δ_{t}) så att metoden bättre anpassas till problemets egenskaper.