Tentamen TMA945 Tillämpad optimeringslära 980527

1 a) y_{3}^{∗} = 1. Giltighet:

B^{−1}b^{NY} = B^{−1}(b + [ \begin{matrix}0 \\ Δ \\ 0 \end{matrix} ] ) = [ \begin{matrix}5 \\ 3 \\ 3 \end{matrix} ] + Δ [ \begin{matrix}1/2 \\ 0 \\ −1/2 \end{matrix} ) ≥ 0

⇔ Δ ∈ [−10, 6] ∵ b_{2} ∈ [−3, 13].

b) Δb_{2} = 8 > 6. Nuvarande bas B är optimal men otillåten. Duala simplex återställer tillåtenhet.

bas −z x_{1} x_{2} s_{1}  s_{2}  s_{3}  b
−z 1 0 0 0  −1 −2 −21
x_{2} 0 0 1 0  1/2 1/2 9  s_{1} utgående
x_{1} 0 1 0 0  0  1 3  s_{2} inkommande
s_{1} 0 0 0 1 −1/2 3/2 −1
−z 1 0 0 −2  0  −5 −19
x_{2} 0 0 1 1  0  2 8  tillåten!
x_{1} 0 1 0 0  0  1 3
s_{2} 0 0 0 −2  1  −3 2

Nytt optimum: x^{∗} = (3, 8)^{∗}; z^{∗} = 19. Förändring i Δz = 6.

c) I den nuvarande basen har x_{3} den reducerade kostnaden

c̄_{3} = c_{3} − c_{B}^{T}B^{−1}a^{3} = c_{3} − (0, 1, 2) [ \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ] = c_{3} − 3.

For att z^{∗} skall öka måste c̄_{3} > 0 gäller, d.v.s. c_{3} > 3.

2 a) (Motsägelsebevis) Antag att för något b > 0 det existerar ett x̄ med f(x̄) < f(x^{∗}), x̄ ∈ x, g(x̄) ≤ b. Bilda x_{λ} = x^{∗} +λ(x̄−x^{∗}). För λ > 0 tillräckligt litet gäller att g(x_{λ}) < 0, ty g(x_{λ}) ≤ λg(x̄)+(1−λ)g(x^{∗}) ≤ g(x^{∗})+λ(b−g(x^{∗})). Men vi har också att f(x_{λ}) ≤ λf(x̄) + (1 − λ)f(x^{∗}) < f(x^{∗}). Om λ ≤ 1 gäller dessutom att x_{λ} ∈ C. Alltså är x_{λ} tillåten i [p], och f(x_{λ}) < f(x^{∗}) motsäger optimaliteten hos x^{∗} i [p]. ■ b) Konvexitet är nödvändigt! Motexempel

I princip kan konvexa problem lösas genom att först lösa ett problem där färre bivillkor tas med, och adderas successivt då de blir överskridna. På motsvarande sätt tas redundanta villkor bort. Detta är en typ av ’active set’-metod som dock kan vara ineffektiv, då det kan kräva många iterationer att identifiera de bivillkor som måste vara med (d.v.s. vilka andra som kan tas bort.)

3 a) [D] min p(y) = b_{1}^{∗}y_{1} + b_{2}^{∗}y_{2} + b_{3}^{T} y_{3}

då \{ \begin{matrix}A_{11}^{T}y_{1} + A_{21}^{T}y_{2} +  ≥ c_{1} \\ A_{12}^{T}y_{1}  + A_{32}^{T}y_{3} ≥ c_{2} \\ y_{1} ≥ 0, y_{2} ≤ 0, y_{3}fri \end{matrix}

b) f_{2}^{∗} ≤ f^{∗} ≤ f_{1}^{∗}. (Ökning av b_{1} ger större tillåten mängd, medan ökning av b_{2} ger mindre tillåten mängd. Ökning av b_{3} \underline{kan} ge något av dessa fall, men det beror på data A och b.)

4. Variabeldef.: x_{ijk} = antal ärenden av type i som flyter in under vecka j och behandlas under vecka k, i = 1, …, m; j = 1, …, n; k = j, …, n. Bivillkor:

• ∑_{i=1}^{m} ∑_{j=1}^{k} a_{i}x_{ijk} ≤ b_{k}, k = 1, …, n (kapacitet)

• ∑_{k=j}^{n} x_{ijk} = h_{ij}, i = 1, …, m; j = 1, …, n (alla ärenden behandlas)

• x_{ijk} ≥ 0, heltal, i = 1, …, m; j = 1, …, n, (def.)

k = j, …, n

Förslag på målfunktion

minimera f(x) = ∑_{i=1}^{m} ∑_{j=1}^{n} ∑_{k=j}^{n} kx_{ijk}

5 a) Om x̄ uppfyller Ax̄ ≥ b och β ≥ 0^{m} följer att β^{T} Ax̄ ≥ β^{T} b. Alltså är den tillåtna mängen i [p(β)] större än i [p], varur olikheten följer.

b) Optimalitetsvillkoren för [p] är:

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

Motsvarande för [p(β)] är: /π dualvar/

\begin{matrix}β^{T} Ax ≤ β^{T} b \\ x ≥ 0^{n} \end{matrix} ; \begin{matrix}π · (β^{T} Ax − β^{T} b) = 0 \\ x^{T} (A^{T} βπ − c) = 0 \end{matrix} ; \begin{matrix}A^{T} βπ ≥ c \\ π ≥ 0 \end{matrix}  (∗∗)

Låt (x^{∗}, y^{∗}) lösa (∗). Sätt β^{∗} = y^{∗} och π^{∗} = 1. Det är lätt att se att (x^{∗}, β^{∗}, π^{∗}) löser (∗∗). Speciellt gäller alltså att x^{∗} löser [p(β^{∗})], varur likheten följer.

6 a) f(x) = \frac{1}{2}(x_{1} − 2x_{2})^{2} + x_{1}^{4}; ∇f(x) = [ \begin{matrix}x_{1} − 2x_{2} + 4x_{1}^{3} \\ −2x_{1} + 4x_{2} \end{matrix} ];

∇^{2}f(x) = [ \begin{matrix}1 + 12x_{1}^{2} & −2 \\ −2 & 4 \end{matrix} , x^{0} = (2, 1)^{T} , f(x^{0}) = 16.

∇f(x^{0}) = [ \begin{matrix}32 \\ 0 \end{matrix} ]; ∇^{2}f(x^{0}) = ( \begin{matrix}49 & −2 \\ −2 & 4 \end{matrix} =]

∇^{2}f(x^{0})d^{1} = −∇f(x^{0}) ⇔ d^{1} = −\frac{1}{3} [ \begin{matrix}2 \\ 1 \end{matrix} ]

∇(x^{0})^{T} d^{1} = −(d^{1})^{T} ∇^{2}f(x^{0})d^{1} = −64/3.

Sätt ℓ = 1. x^{0} + ℓd^{1} = \frac{2}{3} [ \begin{matrix}2 \\ 1 \end{matrix} ]. f(x^{0} + ℓd^{1}) = 256/81.

Gäller

\begin{aligned}f(x^{0} + ℓd^{1}) − f(x^{0}) & ≤ αℓ∇f(x^{0})^{T} d^{1}? \\ & ⇔ \\ −12\frac{68}{81} & ≤ −α · 64/3 \end{aligned}  (∗)

Med α = 0.3 är svaret ’ja’. Låt ℓ = 1.

x^{1} = \frac{2}{3} [ \begin{matrix}2 \\ 1 \end{matrix} ] .

b) Olikheten (∗) uppfyller om α˜∈(0, 0.60).

7 a) [p_{1}(ρ)] min π(x, ρ) = f(x) + (ρ/2) ∑_{i=1}^{m} h_{i}^{2}(x)

p_{2}(μ)] min β(x, μ) = f(x) − μ ∑_{j=1}^{n} log(g_{j}(x))

b) p_{1}(ρ)] ∇_{x}π(x, ρ) = ∇f(x) + ρ ∑_{i=1}^{m} ∇h_{i}(x)h_{i}(x) = 0

Sätt λ_{i}(ρ) = −ρh_{i}(x), vilket ger ∇f(x) − ∑_{i=1}^{m} λ_{i}(ρ)∇h_{i}(x) = 0

[p_{2}(μ)] ∇_{x}β(x, μ) = f(x) − μ ∑_{j=1}^{r} ∇g_{i}(x)/g_{j}(x) = 0

Sätt λ_{j}(r) = μ/g_{j}(x), vilket ger \{ \begin{matrix}∇f(x) = ∑_{j=1}^{r} λ_{j}(μ)∇g; (x) = 0 \\ λ_{j}(μ) ≥ 0, ∀j \\ λ_{j}(μ)g_{j}(x) = μ, ∀j \end{matrix}

Om x konvergerar mot en KKT-punkt då ρ → +∞ resp. μ → 0 går λ_{i}(ρ) resp. λ_{j}(μ) mot multiplikatorer.