Lösning till Tentamen TMA946/MAN280 Optimeringslära 020529

1a) Vi skriver om problemet på standardform och får med s_{1} och s_{2} som slack-

variabler

minimera z = −2x_{1} − x_{2}
då  x_{1} + 2x_{2} − s_{1} = 1,
− 2x_{1} + x_{2} + s_{2} = 1,
x_{1}, x_{2}, s_{1}, s_{2} ≥ 0

Observera att vi har bytt tecken på målfunktionen då vi hade ett maximeringsproblem. Vi ser ingen uppenbar tillåten bas, därför tar vi och inför en artificiell variabel, vilket ger FASI problemet

minimera w =  a
då  x_{1} + 2x_{2} − s_{1}  a = 1,
− 2x_{1} + x_{2} + s_{2} = 1,
x_{1}, x_{2}, s_{1}, s_{2}, a ≥ 0.

Vi väljer a, s_{2} som vår bas. Vi beräknar reducerade kostnaden, vilken ges av

c̄^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}N

vilket för oss blir

[0 0 0] − [1 0] [ \begin{matrix}1 & 0 \\ ′0 & 1 \end{matrix} ] [ \begin{matrix}1 & 2 & −1 \\ −2 & 1 & 0 \end{matrix} ] = [−1 − 2 1]

vi ser att inkommande variabel blir x_{2}

Vi beräknar

y = B^{−1}A_{ink} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}2 \\ 1 \end{matrix} ] = [ \begin{matrix}2 \\ 1 \end{matrix} ]

samt

b̂ = B^{−1}b = b = [ \begin{matrix}1 \\ 1 \end{matrix} ] .

Utgående ges av

argmin_{i,y_{i}>0} \frac{b_{i}}{y_{i}}

vilket ger att a blir utgående. Ny bas blir x_{2}, s_{2}, med basmatris

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

Då alla artificiella variabler utgått ur basen har vi att basen är tillåten. Vi tittar nu på originalproblemet för att hitta en inkommande.

Vi har

c̄^{T} = c^{t} + N − c_{B}^{t}B^{−1}N

vilket blir

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

den inkommande variablen blir x_{1}.

P.S.S. som tidigare beräknas

\begin{aligned}y = B^{−1}A_{ink} & = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}1 \\ −2 \end{matrix} ] = \frac{1}{2} [ \begin{matrix}1 \\ −5 \end{matrix} ] \\ b̂ = B^{−1}b & = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}1 \\ 1 \end{matrix} ] = \frac{1}{2} [ \begin{matrix}1 \\ 1 \end{matrix} ] = [ \begin{matrix}1 \\ 3 \end{matrix} ] \end{aligned}

När vi nu tittar på utgående kriteriet

argmin_{y_{i}>0} \frac{b_{i}}{y_{i}}

hittar vi ingen utgående. Detta innebär att oavsett hur mycket vi ökar s_{1} får vi aldrig en otillåten punkt. Därmed vet vi att problemet är obegränsat.

Vi kan verifiera detta genom att titta på den punkt vi stod i med x_{1}, s_{2} som bas. Där har vi x_{2} = s_{1} = 0, x_{1} = 1, x_{2} = 3, en tillåten punkt.

Med hjälp av y ovan ser vi att värdet på x_{1} och s_{2} kommer att ökas med 1 respektive 2 för varje enhet vi ökar s_{1} därmed har vi att punkterna (x_{1}, x_{2}, s_{1}, s_{2}) = (1, 0, 0, 3) + λ(1, 0, 1, 2) är tillåtna för λ ≥ 0, samt att målfunktionenens värde går mot ∞.

1b) Svag dualitte ger omedelbart att duala problemet saknar lösning.

2. Vad vi söker är en metod att från en primal tillåten lösning hitta en dual tillåten lösning. Vi har problemet

minimera c^{T} x  (1)
Då Ax ≥ 1  (2)
x ≥ 0  (3)

Dualen till detta problemg ges av

maximera 1^{T} y  (4)
Då y^{T} A ≤ c^{T}  (5)
y ≥ 0  (6)

Om vi tittar på den reducerade kostnaden för det primala problemet så ges denna av

c̄ = c^{T} − c^{T} B^{−1}A

Om vi sätter y^{T} = c_{B}^{T}B^{−1} så har vi vidare att

c^{T} − y^{T} A ≥ 0 → y^{T} A ≤ c^{T} .

Men

c^{T} − y^{T} A ≥ 0

precis då vi har en primal optimal bas. Detta ger att ju närmre optimum vi kommer, desto närmre en dual tillåten lösning kommer y.

Vår heuristik bygger därför på att ta en primalt tillåten lösning och från denna skapa en dualt tillåten lösning. En metod för att skapa en dualt tillåten låsning lyder som följer

steg 0. Bilda y = c_{B}^{T}B^{−1}

steg 1. Hitta i sådant att y^{T} A_{.,i} > c_{i}. Om sådant i ej existerar, avsluta ty y är tillåten.

steg 2. Hitta k så att y_{k} > 0 samt A_{k,i} = 1.

steg 3. sänk värdet på y_{k} tills dess att y_{k} = 0 eller y^{T} A_{.,i} = c_{i}.

steg 4. Gå till steg 1.

Detta kommer att ge oss en tillåten dual lösning y och därmed en undre gräns för det optimala målfunktionsvärdet. Dessutom kommer den undre gränsen att närma sig det riktiga optimalvärdet då vi kommer närmare och närmare en optimal bas.

Vi vet att metoden kommer att hitta en tillåten lösning, då vi för varje gång vi passerar steg 3 antingen gör ett bivillkor tillåtet eller sätter en ykomponent till 0. Då y = 0 är en tillåten lösning kommer denna metod att terminera.

3a) Vi tillåter att g_{i}(x) > 0 till en kostnad genom att införa en “bristvariabel”

a_{i}:

g_{i}(x) − a_{i} ≤ 0.

Om g_{i}(x̄) > 0 fås att a_{i} > 0;

Om g_{i}(x̄) ≤ 0 är a_{i} = 0 möjligt.

Om vi alltså inför bivillkoret

a_{i} ≥ 0

kommer a_{i} bara bli nollskilt om x är otillåten i bivillkor i, och för tillåtna x ser vi till att a_{i} = 0.

Låt p vara proportionalitetskonstanten (p > 0). Ny modell:

maximera_{(x,a)}φ(x, a) := f(x) − p ∑_{i=1}^{m} a_{i}

då \begin{matrix}g_{i}(x) − a_{i} ≤ 0, & i = 1, …, m \\ a_{i} ≥ 0, & i = 1, …, m \\ h_{j}(x) = 0. \end{matrix}

Notera att eftersom, för varje givet x̄, maximeringen av φ(x̄, ·) är, för varje i, ekvivalent med att minimera a_{i}

då a_{i} ≥ 0, a_{i} ≥ g_{i}(x̄)

med globalt min a_{i} = max{0, g_{i}(x̄)}. Ett ekvivalent problem är därför att

maximera f(x) − p ∑_{i=1}^{m} max{0, g, (x̄)}
då h(x) = 0^{ℓ}

dvs. den klassiska exakta straffunktionsansatsen.

3b) SQP är en Newton-metod, som normalt kräver att f, g och h ∈ C^{2}. Quasi-Newton-modifieringar finns, men ett krav är

∗) f, g, k ∈ C^{1} (en gång kontinuerligt differentierbara)

Förutom detta fordras förstås att den punkt som nås är optimal. SQP är en lokal metod som bygger på att uppfylla KKT-villkoren. Följaktligen kvävs att dessa är tillräckliga för globalt min:

∗) f är konvex, g_{i} är konvexa och h_{j} är affina funktioner.

Även om det fordras andra tekniska krav för ett global optimallösning ska hittas (det måste t.ex. finnas en!) är ovanstående de krav som är mest självklara och enkla att nedteckna.

4a) min_{x∈ℝ} \underbrace{(x + 1)^{2}}_{f_{1}(x)} + \underbrace{(x − 1)^{2}}_{f_{2}(x)}.

f(x) = f_{1}^{2}(x) + f_{2}^{2}(x) = (x + 1)^{2} + (x − 1)^{2} = 2x^{2} + 2 ⇒ ⇒ min_{x∈ℝ} f(x) = 2, x^{∗} = 0.

α = \frac{1}{2}, x_{0} = 2 ∇f_{1} ≡ 1, ∇f_{2} ≡ 1

Steg 1: \begin{matrix}x_{0}^{(0)} = 2 \\ x_{0}^{(1)} = 2 − 2 · \frac{1}{2} · (2 + 1) · 1 = −1 \\ x_{0}^{(2)} = −1 − 2 · \frac{1}{2} · (−1 − 1) = 1 \\ \underline{x_{1} = 1} & ♣ \end{matrix}

Steg 2: \begin{matrix}x_{1}^{(0)} = 1 \\ x_{1}^{(1)} = 1 − 2 · \frac{1}{2} · (1 + 1) − 1 \\ x_{2}^{(2)} = 1 − 2 · \frac{1}{2} · (−1 − 1) = 1 \\ \underline{x_{2} = 1} & ♣ \end{matrix}

4b) α ∈ (0, 1) y_{k} = x_{k} − 2α(x_{k} + 1) · 1 x_{k+1} = y_{k} − 2α(y_{k} − 1) · 1

Antag att {(x_{k}, y_{k})} → (x^{∗}, y^{∗})

Då:

♣samma punkt! Kommer inte att konvergera mot 0 (vi har inte minne!)

\{ \begin{matrix}y^{∗} = x^{∗} − 2α(x^{∗} + 1) \\ x^{∗} = y^{∗} − 2α(y^{∗} − 1) \end{matrix} ⇔

⇔ \{ \begin{matrix}(1 − 2α)x^{∗} − y^{∗} = 2α \\ −x^{∗} + (1 − 2α)y^{∗} = −2α \end{matrix} ⇔

⇔ \{ \begin{matrix}x^{∗} = −y^{∗} \\ (2 + 2α)x^{∗} = 2α \end{matrix} ⇔ \{ \begin{matrix}x^{∗} = \frac{α}{1·α} \\ y^{∗} = −\frac{α}{1·α} \end{matrix}

om α → 0 då x^{∗}(α) = \frac{α}{1−α} → 0, dvs. mot den optimala lösningen.

5. Variabler:

x_{j} = \{ \begin{matrix}1, & om kontrakt skrivs med verkstad j, \\ 0, & annars, \end{matrix}
j = 1, 2, 3
y_{ij} = \{ \begin{matrix}1, & om återförs. i utnyttar verkstad j \\ 0, & annars, \end{matrix}
i = 1, 2, 3, 4; j = 1, 2, 3

Konstanter: k_{j} = kostnad för kontrakt med verkstad j (inkr) c_{ij} = kostnad för återf. att anlita verkstad j (inkr) b_{i} = service behov hos återf. i (i h/dag) v_{j} = kapacitet hos verkstad j (i h/dag) k = budget för kontrakt (inkr)

((k_{j})_{j=1,2,3} = (150, 160, 100) (c_{ij})_{i,j} ges i tablell. (b_{i})_{i=1,2,3,4} = (5, 3, 3, 4) (v_{j})_{j=1,2,3} = (10, 10, 7) k = 350)

Modell: minimera f(x, y) = ∑_{j=1}^{3} k_{j}x_{j} + ∑_{i=1}^{4} ∑_{j=1}^{3} c_{ij}y_{ij}

då

∑_{i=1}^{4} b_{i}y_{ij} ≤ v_{j}x_{j}, j = 1, 2, 3  (1)
∑_{j=1}^{3} v_{j}y_{ij} ≥ b_{i}, i = 1, 2, 3, 4  (2)
∑_{j=1}^{3} y_{ij} ≤ 1, i = 1, 2, 3, 4  (3)
∑_{i=1}^{4} y_{i1} ≤ 2,  (4)
∑_{j=1}^{3} k_{j}x_{j} ≤ k  (5)
x_{j} ∈ {0, 2}, j = 1, 2, 3, 4  (6)
y_{ij} ∈ {0, 1}, i = 1, 2, 3 j = 1, 2, 3, 4

(1) a) y_{ij} = 0 om x_{j} = 0, dvs kan ej utnyttja verkstad om ej kontrakt

skrivits.

b) total kapacitet hos verkstad överskrids ej.

(2) efterfrågan hos återförsäljare, av service, tillfredställs.

(3) varje återförsäljare skickar uppdrag till max en verkstad.

(4) verkstad 1 har högst serva två återförsäljare.

(5) kontraktsbudget överskrids ej.

(6) fysikaliska/logiska villkor.

6a) min x^{2} då sin(x) ≤ −1 x ∈ \{y| sin(y) ≤ −1\} ⇔ x_{k} = −\frac{δ}{2} + 2δk, k ∈ ℤ ⇒ varje punkt x_{k} = −\frac{δ}{2} + 2δk är ett lokallt min (och xxx, faktiskt) Global min min_{k∈ℤ}(x_{k})^{2} om k = 0 dvs x^{∗} = −\frac{δ}{2}. KKT ser inte tillräckliga (problemet är inte xxxx)

Nödvändiga? \{ \begin{matrix}2x + λ cos(x) = 0 & (1) \\ sin(x) ≤ −1 & (2) \\ λ(sin(x) + 1) = 0 & (3) \\ λ ≥ 0 & (4) \end{matrix}

(2) ⇒ x = x_{k} för något k, ⇒ sin(x) + 1 = 0 ⇒ (3)∀λ ≥⇒ (n). x = x_{k} ⇒ cos(x) = 0 ⇒ 2x = 0 – omöjligt! Alltså, KKT är inte nödvändiga ty varje x_{k} är lok min!

b) F J : \{ \begin{matrix}α2x + λ cos(x) = 0 & (1) \\ sin(x) ≤ −1 & (2) \\ λ(sin(x) + 1) = 0 & (3) \\ (α, λ0 ≥ 0, (α, λ) ≠ 0 & (4) \end{matrix}

(2) ⇒ x = x_{k} = −\frac{δ}{2} + δk, något k ∈ ℤ ⇒ (3)∀λ ≥ 0 x = x_{k} ⇒ cos(x) = 0 ⇒ (1) och (4) för varje λ > 0, α = 0! Så varje x_{k} uppfyller FJ-villkoren.

6c) min y

då \{ \begin{matrix}x^{2} + y^{2} ≤ \\ x^{3} ≥ y^{4} \end{matrix} | \begin{matrix}g_{1}(x, y) ≤ 0 \\ g_{2}(x, y) ≤ 0 \end{matrix}

Om vi kan hitta något λ ≥ 0, λ ≠ 0

så att \begin{matrix}λ_{1}∇ρ_{1} + λ_{2}∇ρ_{2} = 0 \\ λ_{1}g_{1} = 0 \\ λ_{2}ρ_{2} = 0 \\ g_{1} ≤ 0, ρ_{2} ≤ 0 \end{matrix} (∗)

då uppfyller vi F J-villkoren med α = 0.

Om \begin{aligned}(x, y) = (0, 0) ⇒ \\ g_{1} = −1 & ∇ρ_{2} ( \begin{matrix}0 \\ 0 \end{matrix} ) & λ_{1} = 0 \\ φ_{2} = 0 & ∇ρ_{2} = ( \begin{matrix}0 \\ 0 \end{matrix} ) & ∀λ_{2} > 0 \\ & har vi (∗) \end{aligned}

⇒ \{ \begin{matrix}(x, y) = (0, 0) \\ (α, λ_{1}, λ_{2}) = (0, 0, λ)∀λ > 0 \end{matrix}

uppfyller F J. 7a)

C^{∗} := \begin{matrix}minimum \\ x ∈ G \end{matrix} ℓ(x) \begin{matrix}≤ \\ ↑ \\ x ⊆ G \end{matrix} \begin{matrix}minimum \\ x ∈ X \end{matrix} ℓ(x) \begin{matrix}≤ \\ ↑ \\ ℓ ≤ f \\ p : X \end{matrix} \begin{matrix}minimum \\ x ∈ X \end{matrix} f(x) =: f^{∗}

b) Vi identifierar: • X = {x ∈ ℝ^{n}|g_{i}(x) = 0, i = 1, …, m}

• G = ℝ^{n}

• L(x) = θ(x) := f(x)+∑_{i=1}^{m} v_{i}g_{i}(x)+pP (g(x)), där P (y) \{ \begin{matrix}= 0, & y = 0^{m} \\ > 0, & y ≠ 0^{m} \end{matrix}

Vi har altså:

i) X ⊆ G, ty X ⊆ ℝ^{n} ii) ℓ(x) = f(x) på X ty där är g(x) ≡ 0^{m} Vi är klara.

c) Vi behöver samtliga av följande förutsättningar:

i) problemet ska ha en tillåten lösning ii) problemet ska ha en optimal lösning iii) SAP-algoritmen ska vara tillämpbar iv) problemet ska vara konvext v) nedför kravet att f, g_{i}, k_{j} samtliga är minst en gång kontinuerligt dif-

ferentierbar.

vi) nedför kravet att f är konkav, g_{i} är konvex för alla i och k_{j} är affin för alla j.