Tentamen TMA945 Tillämpad optimeringslära 990528

1 a) Efter införande av slackvariabler är problemet ekvivalent med problemet att

minimera f(x) := −x_{1} + 2x_{2} + x_{3}

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

Ett Fas-I problem skapas genom tillägg av en artificiell variabel i det andra bivillkoret:

minimera h(a) := a

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

Startbas: s_{1}, a; målfunktionen uttryckt i övriga

variabler: h(a) = a = 3 + x_{1} − 2x_{2} − 3x_{3} + s_{2}.

Tablå:

bas −h x_{1} x_{2} x_{3} s_{1} s_{2}  a b̄
−h 1  1 −2 −3 0  1  0 −3 x_{3} ink.
s_{1} 0  2  1 −1 1  0  0 7 a utg.
a 0 −1 2 3 0 −1 1 3
−h 1  0  0 0 0  0  1 0 red. kostn. ≥ 0 op-

timum i Fas-I tillåten bas i s_{1}, x_{3}

s_{1} 0 5/3 5/3 0 1 −1/3 1/3 8

x_{3} 0 −1/3 2/3 1 0 −1/3 1/3 1 inför f, uttryckt i ickebasvar.

f(x) = −x_{1} + 2x_{2} + x_{3}

= −x_{1} + 2x_{2} + (1 + \frac{1}{3}x_{1} − \frac{2}{3}x_{2} + \frac{1}{3}s_{2})

= 1 − \frac{2}{3}x_{1} + \frac{4}{3}x_{2} + \frac{1}{3}s_{2}

Fas-II: bas −f x_{1} x_{2} x_{3} s_{1}  s_{2}  b̄ −f 1 −2/3 4/3 0 0  0  −1 x_{1} ink. s_{1} 0 5/3 5/3 0 1 −1/3 8 s_{1} utg. x_{3} 0 −1/3 2/3 1 0 −1/3 1 −f 1  0  2 2/5 2/5 1/5 1/5 red. kostn. ≥ 0 Optimum i Fas-II x_{1} 0  1  1 0 3/5 −1/5 24/5 x_{3} 0  0  1 1 1/5 −2/5 13/5

x^{∗} = (24/5, 0, 13/5)^{T}; z^{∗} = −11/5

b) Skuggpriserna ges av de optimala värdena hos variablerna i motsvarande duala problem. Tecknen hos dem är ≤ 0 respektive ≥ 0, och deras numeriska värden (sånär som på tecken) återfinns som reducerade kostnader hos slackvariablerna. Följaktligen är y^{∗} = (−2/5, 1/5). Om nu 3 ersätts med 3+ϵ i högerledet för bivillkor två kommer det optimala värdet förändras med ϵ/5.

2 a)

Index: i = individ (i = 1, …, 6)

j = veckodag (j = 1, …, 6)

Kostnader: p_{ij} = poäng för dag j satt av individ i

c_{i} = \{ \begin{matrix}1 & om individ i behärskar espressomaskinen \\ 0 & annars \end{matrix}

Modell:

• Variabler:

x_{ij} = \{ \begin{matrix}1 & om individ i arbetar dag j \\ 0 & annars \end{matrix}

• Bivillkor:

∑_{i} x_{ij} = 4, j = 1, …, 6( personalbehov)
∑_{i} c_{i}x_{ij} ≥ 1, j = 1, …, 6( maskinkompetens)
∑_{j} x_{ij} ≤ 4, i = 1, …, 6( arbetsbegränsning)
x_{ij} ∈ {0, 1}, ∀i, j

• Målfunktion: maximera lyckan = ∑_{i} ∑_{j} p_{ij}x_{ij}

b)

Ny variabel: z = lyckan hos den sämst lottade.
Ny modell: maximera z.

då \begin{matrix}∑_{j} p_{ij}x_{ij} ≥ z, i = 1, …, 6 \\ ∑_{i} c_{ij} = 4, j = 1, …, 6 \\ ∑_{i} c_{ij}x_{ij} ≥ 1, j = 1, …, 6 \\ x_{ij} ∈ \{0, 1\}, ∀i, j, z fri \end{matrix}

Kommentar: den egentliga målfunktionen är att maximera den lägsta lyckan d.v.s. att maximera f(x) := min_{i}(∑_{j} p_{ij}x_{ij}). Eftersom denna funktion inte är linjär konverteras den enligt ovanstående med hjälp av en extra variabel.

3 a)

s_{ij} = flöde på båge (i, j)
f = flödesstyrka genom grafen

Maxflödesproblemet: maximera f

då \{ \begin{matrix}∑_{j:(i,j)∈E} x_{ij} − ∑_{j:(j,i)∈E} x_{ij} = \{ \begin{matrix}f & i = s \\ 0 & ≠ s, t \\ −f & i = t \end{matrix} \\ u_{ij} ≥ x_{ij} ≥ 0 ∀(i, j) ∈ E \\ f fri \end{matrix}

b) Inför dualvariabler π_{i} för nodjämviktsvillkoren och α_{ij} för kapacitetsvillkoren.

Dualt problem:

minimera ∑_{(i,j)∈E} u_{ij}α_{ij}

då [ \begin{matrix}π_{i} − π_{j} + α_{ij} ≥ 0, & ∀(i, j) ∈ E \\ π_{t} − π_{s} = 1 \\ α_{ij} ≥ 0. & ∀(i, j) ∈ E \\ π_{i} fri, & i ∈ N \end{matrix}

Låt S ∈ N vara sådant att s ∈ S, t ∉ S. Då beskriver mängderna S och N\S ett \underline{snitt} i grafen. Maxflödes-minusnittsteoremet säger att f^{∗} (den maximala flödesstyrkan) är lika med den minimala kapaciteten hos något snitt i grafen, vilket kan uttryckas som ∑_{\begin{matrix}(i,j)∈E \\ i∈S \\ j∉s \end{matrix}} u_{ij}, vilken minimeras över

S ⊂ N. Motivering mha LP-dualitet: Sätt

π_{i} = \{ \begin{matrix}0, & i ∈ s & (0 på s-sidan, \\ 1, & i ∉ s & 1 på t-sidan) \end{matrix}

α_{ij} = \{ \begin{matrix}1, & (i, j) ∈ E, i ∈ S, j ∉ s \\ 0 \end{matrix} (bågar över snittet)

Detta är en dualt tillåten lösning, och målfunktionsvärdet är lika med ∑_{\begin{matrix}(i,j)∈E \\ i∈s,j∉s \end{matrix}} u_{ij}, d.v.s. styrkan hos snittet definerat av nodmändgen s. Svag du-

alitet visar att f^{∗} inte kan överstiga styrkan hos något snitt. Den minimala styrkan motsvarar ett flöde x där lflödet av maximalt (u_{ij}) på varje båge som passerar över snittet. Eftersom f = ∑_{\begin{matrix}(i,j)∈s \\ i∈s,j∉s \end{matrix}} u_{ij} gäller där måste x vara

optimalt och f den maximala flödesstyrkan.

4. f(x) = (x_{1} + 2x_{α} − 3)^{2} + (x_{1} − α)^{2};

∇f(x) = [ \begin{matrix}4x_{1} + 4x_{2} − 10 \\ 4x_{1} + 8x_{α} − 12 \end{matrix} ]; ∇^{2}f(x) = [ \begin{matrix}4 & 4 \\ 4 & 8 \end{matrix} ]; x_{0} = [ \begin{matrix}0 \\ 0 \end{matrix} ]

a) p_{0} = −∇f(x_{0}) = [ \begin{matrix}10 \\ 12 \end{matrix} ]; x_{1} = x_{0} + α_{0}p_{0} = 2α_{0} [ \begin{matrix}5 \\ 6 \end{matrix} ]

α_{0} = −\frac{∇f(x_{0})^{T} p_{0}}{p_{0}^{T} ∇^{2}f(x_{0})p_{0}} = … = \frac{61}{628} ⇒ x_{1} = \frac{122}{628} [ \begin{matrix}5 \\ 6 \end{matrix} ]

∇f(x_{1}) = \frac{2}{157} [ \begin{matrix}−114 \\ 95 \end{matrix} ]; p ∈ R^{α} är en avtagande riktning i x_{1} om p^{T} ∇f(x_{1}) < 0, d.v.s., om

p^{T} [ \begin{matrix}−114 \\ 95 \end{matrix} ] < 0 ⇔ −114p_{1} + 95p_{α} < 0

⇒ x_{1} är \underline{inte} optimallösning, ty f(x_{1} + p̃) < f(x_{1}) om −114p̃_{1} + 95p̃_{2} < 0 och ∥p̃∥ är tillräckligt liten.

p_{0} = −(∇^{2}f(x_{0}))^{−1}∇f(x_{0}) = −\frac{1}{16} [ \begin{matrix}8 & −4 \\ −4 & 4 \end{matrix} ] [ \begin{matrix}−10 \\ −12 \end{matrix} ] = [ \begin{matrix}2 \\ 1/2 \end{matrix} ]

x_{1} = x_{0} + α_{0}p_{0} = \frac{α_{0}}{α} [ \begin{matrix}4 \\ 1 \end{matrix} ]; α_{0} = \frac{−∇f(x_{0})^{T} p_{0}}{p_{0}^{T} ∇^{2}f(x_{0})p_{0}} = … = 1 (ty kvadratisk).

⇒ x_{1} = [ \begin{matrix}2 \\ 1/2 \end{matrix} ]; ∇f(x_{1}) = [ \begin{matrix}0 \\ 0 \end{matrix} ] ⇒ p^{T} ∇f(x_{1}) = 0 ≮ 0 för alla p ∈ R^{α} ⇒

inga avtagande riktningar existerar. f är konvex, ty ∇^{2}f(x) = [ \begin{matrix}4 & 4 \\ 4 & 8 \end{matrix} ]

är positivt definite för alla x ∈ R^{2} ⇒ x är globalt optimum. (f är strikt konvex ⇒ x_{1} är \underline{unikt} optimum).

5 a) Låt y_{k}, k ∈ K, vara mängden av samatliga extrempunkter till mängden av tillåtna lösningar i LP-dualen. Då kan vi skriva

v(b) = \begin{matrix}max c^{T} x \\ då Ax ≤ b \\ x ≥ 0 \end{matrix} = \begin{matrix}min b^{T} y \\ då A^{T} y ≤ c \\ y ≥ 0 \end{matrix} = min_{k∈K} b^{T} y_{k}.

Enligt antagandet är (säg) y_{k} den unika optimala extrempunkten. Då följer att funktionen v(·) är differentierbar i en omgivning av b, och gradienten

∇v(b) = y_{k^{∗}}. Speciellt gäller att den partiella derivatan \frac{∂v(b)}{∂b_{i}} ges av (y_{k^{∗}})_{i},

d.v.s. element i i den optimala duallösningen. I känslighetsanalysen utnyttjas att v(b) = c_{B}^{T}B^{−1}b för en optimal bas B, och att (y^{∗})^{T} = c_{B}^{T}B^{−1} är en optimalduallösning. Formeln för skygpriset, y_{i}^{∗} = (c_{B}^{T}B^{−1})_{i} är alltså korrekt.

b) Om y_{k^{∗}} inte är den enda optimala extrem punkten är inte v(˙) differentierbar i punkten b. Om vi är intresserade av att finna det korrekta skuggpriset för villkor i måste formeln i a) förändras. Intressanta blir nu alla de ectrempunkter y_{k} som ger värdet v(b) (de \underline{aktiva} extrempunkterna). Det korrekta skuggpriset är då en riktningsderivata av v(·) i b med avseende på en önskad förändringsriktning δ:

v′(b; δ) := lim_{t↓0} \frac{1}{t}(v(b + tδ) − v(b)).

(I de fall då v(·) är differentierbar i b gäller att v′(b; δ) = δ^{T} ∇v(b), vilket betyder att användandet av riktningsderivatan vid härledningen av skuggpriset är det mest generella och är \underline{alltid} korrekt.) Om vi speciellt söker skuggpriset för villkor i låter vi δ = δ_{+i} := (0, 0, …, 0, 1, 0, …, o)^{T} där bara element i är nollskilt, om de är en \underline{ökning} av höger ledet vi undersöker, medan vi låter δ = δ_{−i} := (0, 0, …, 0, −1, 0, …, 0)^{T} om vi vill undersöka en minskning. Detta är en viktig observation: om inte v(·) är differntierbar är inte säkert v′(b; δ_{+i}) = −v′(b_{j}δ_{−i}) eftersom höger- och vänsterderivatorna inte sammanfaller, och vi måste alltså skilja mellan dessa fall.

För konvexa funktioner (som v(·) är ett exempel på) gäller formeln v′(b_{j}δ) = max{δ^{T} ξ|ξ ∈ ∂v(b)}, där ∂v(b) är mängden av alla möjliga lutningar hos v(·) i b (de så kallade subgradienterna). Speciellt fås att

v′(b_{j}δ_{+i}) = max{(y_{y^{∗}}); |y_{k^{∗}} är en optimal duallösning}.

alltså det \underline{största} värdet som dualvariabeln y_{i} har i någon optimallösning.

Notering: Vi kan också, mer informellt, i det duala problemet se att om y_{k^{∗}} är unik gäller det också vid små förändringar av b (lutningen hos målfunktionen) medan om fler än en extrempunkt y_{k} är optimal för något b förändrar kanske z^{∗} mer oförutsägbart. Detta ger en annan bild av differentierbarheten av z^{∗}.

6. minimera f(x) := 61.8+5.72x_{1}+0.0175(x_{3})^{0.85}+0.0094(x_{4})^{0.75}+0.006t, xx_{3}

då

t_{2}x_{1} ≥ d_{1}t_{1} + d_{2}(t_{2} − t_{1})
x_{2} ≥ p_{0}
x_{2} = 36.25\frac{(d_{2} − x_{1})(t_{2} − t_{1})}{t_{1}} ln (\frac{x_{2}}{p_{0}} )
x_{1} = 348, 300\frac{(d_{2} − x_{1})(t_{2} − t_{1})}{x_{2}}
x_{j} ≥ 0, ∀j

⇒

minimera f(x) := 61.8 + 5.72x_{1} + 0.0175x_{3}^{0.85} + 0.0094x_{4}^{0.75} + 0.0036x_{3} då

g_{1}(x) :=x_{1} − 17.5 ≥ 0
g_{2}(x) :=x_{2} − 200 ≥ 0
h_{1}(x) :=x_{3} − 24\frac{1}{6}(40 − x_{1}) ln (\frac{x_{2}}{200}) = 0
h_{2}(x) :=x_{4} − 139, 320(40 − x_{1})/x_{2} = 0
g_{3}, …, g_{6}(x) :=x_{1}, …, x_{4} ≥ 0

Vi kontrollerar om KKT-villkoren är uppfyllda i x̄ = (17.5, 473.7, 468.8, 6618)^{T}:

g_{1}(x̄) = 0, g_{2}(x̄) > 0, h_{1}(x̄) ≈ 0, h_{2}(x̄) ≈ 0, g_{3}, …, g_{6}(x̄) > 0.

Aktiva olikhetsvillkor alltså enbart bivillkor 1.

∇g_{1}(x̄) = (1, 0, 0, 0)^{T}
∇H_{1}(x̄) = (24\frac{1}{6} ln(x̄_{2}/200), 24\frac{1}{6}(40 − x̄_{1})/(200x̄), 1, 0)^{T} ≈ (20.84, 0.005739, 1, 0)^{T}
∇H_{2}(x̄) = (139, 320/x̄_{2}, 139, 320(40 − x̄_{1})/x̄_{2}^{2}, 0, 1)^{T} ≈ (294.1, 13.97, 0, 1)^{T}
∇f(x̄) = (5.72, 0, 0.85 · 0.0175x̄_{3}^{−0.15} + 0.0036, 0.75 · 0.0094x̄_{4}^{−0.25}) ≈
(5.72, 0, 0.00513, 0.0007896).

Finn en lösning till

∇f(x̄) − λ_{1}∇g_{1}(x̄) − μ_{1}∇h_{1}(x̄) − μ_{2}∇h_{2}(x̄) = 0

[ \begin{matrix}1 & 20.84 & 294.1 \\ 0 & 0.005739 & 13.97 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}λ_{1} \\ μ_{1} \\ μ_{2} \end{matrix} ] = [ \begin{matrix}5.72 \\ 0 \\ 0.009513 \\ 0.0007816 \end{matrix} ] ⇒

μ̄_{1} = 0.009513(≥ 0!) och μ̄_{2} = 0.0007816(≥ 0!) ur rad 3 - 4, vilket i rad 1 ger att λ̄_{1} = 5.292(≥ 0!). Ekvation 2 uppfylls inte exakt med dessa val, men felet är litet:

∇_{x}L(x̄, λ̄, μ̄) = ∇f(x̄)−λ̄_{1}∇g_{1}(x̄)−μ̄_{1}∇h_{1}(x̄)−μ̄_{2}∇h_{3}(x̄) = (0, 0.011, 0, 0)^{T}

vilket innebär att ∥∇_{x}L(x̄λ̄, μ̄)∥ = 0.011. En ytterligare bild av att (x̄, λ̄, μ̄) är att betrakta som en acceptabelt nära stationär punkt till L är att det vanligt förekommande avbrottskriteriet i obegränsad optimering, applicerat på min_{x} L(x, λ̄ < μ̄),

∥∇_{x}L(x̄, λ̄, μ̄)∥ ≤ ϵ(1 + |L(x̄, λ̄, μ̄)|), ϵ > 0

är uppfyllt med ϵ ≈ 6·10^{−5}. Eftersom x̄ är primalt tillåten (approximativt), (λ̄, μ̄) ≥ 0, x̄ och (λ̄, μ̄) är komplementära och (x̄, λ̄, μ̄) är en stationär punkt till L(·, λ̄, μ̄) (approximativt), betraktar vi (x̄, λ̄, μ̄) som en approximativ KKT-punkt.

Betraktar vi sedan ∇_{xx}^{2}L(x̄, λ̄, μ̄) finner vi att den är mycket nära en nollmatris. Vi uppfyller alltså också den andra ordningens nödvändiga villkor för ett lokalt minimum (åtminstone approximativt).

Studerar vi nu problemet närmare ser man att x_{1} dominerar kostnadsbidraget kraftigt. Vi kan också se att λ̄_{1} är stor, vilket indikerar att en minskning av dess värde skulle ha blivit effekten av en lägre undre gräns. Om vi betraktar x_{1} som fixt på sin lägsta nivå kan vi betrakta problemet som ett optimeringsproblem enbart i x_{1}, eftersom x_{2} och x_{4} ges av värdena hos x_{1} och x_{2}. Målfunktionen, satt i x_{2}, är av formen k_{1}(lu x_{2})^{0.85} +k_{2}x_{2}^{−0.75} för några k_{1}, k_{2} > −. För de stora värden av x_{2} som krävs är funktionen mycket flack, d.v.s. linjär. Detta antyder också av att ∇_{w}L(x̄, λ̄, μ̄) är nära noll. I det intressanta området är alltså optimeringsproblemet i det närmaste att betrakta som ett LP-problem, snarare om det (icke-konvex) ILP-problem som vi ser i urspringsformuleringen. Vi kan troligen lita på att x̄ är en bra lösning, efatersom KKT-villkoren är både nödvändiga och tillräckliga för global optimalitet hos LP-problem. (Det faktum att utskriften gavs med få signifikanta siffror gör att vi inte kan räkna med att kunna uppfylla optimalitetsvillkoren exakt, och eftersom ursprungsdata optimalitetsvillkoren exakt, och eftersom ursprungsdata troligen är bekräftade med fel är x̄ att betrakta som ett tillräckligt bra närmevärde.)

Notering och en alternativ analys:

Vi kan se att modellen är olyckligt formulerad. Till exempel ser vi att x_{1} dominerar kostnaden totalt, till priset av att övriga variablers värden blir nästan försumbara. Ett bättre angreppssätt hade varit att skala variablerna så att deras inflytande blivit mer jämbördiga.

Utdata från programmet kan också användas på ett annorlunda sätt än vi gjorde. Eftersom x_{3} och x_{4} är funktioner av x_{1} och x_{2} borde en rimligare approximation av deras optimala värden ha utnyttjat sambanden (2c) och (2d) givet värdena hos x_{1} och x_{2}. Med denna modifiering hade vi vunnit flera saker. (1) Vi hade uppfyllt alla bivillkor, speciellt de fysikaliska sambanden (2c) och (2d). (2) Vi hade därmed sluppit flelet i KKT-villkoren (∇_{x}L(x̄, λ̄, μ̄) = 0) vars värde i analysen föranleder en viss betänksamhet. Notera att felet (residualen) som är 0.011, är flera storleksordningar större än högerleden. En numerisk analytiker skulle hävda att lösningen (λ̄, μ̄) (speciellt μ̄) inte har särskilt många korrekta siffror...; vi hade också fått en annorlunda lösning om vi hade angripit systemet annorlunda. Vi noterar slutligen att med utnyttjar de av en omskrivning av f i (x_{1}, x_{2}) kan visa

att KKT-villkoren gäller, inklusive andra ordningens villkore.

7 a) Betrakta problemet

minimera _{x} ∈ Xf(x)
då \begin{matrix}g_{i}(x) ≤ g_{i}(x̄), & i ∈ I := \{i = 1, …, m|ȳ_{i} > 0\} \\ g_{i}(x) ≤ b_{i}, & i ∉ I, där b_{i} ≥ g_{i}(x̄). \end{matrix} (P)

Vi visar att (x̄, ȳ) är en sadelpunkt till (P), och detta medför direkt att x̄ är optimal i (P). (Beviset för det senare kan utnyttja resultatet i b).) Låt

L(x, y) = f(x) + ∑_{i∈I} y_{i}(g_{i}(x) − g_{i}(x̄)) + ∑_{i∉I} y_{i}(g_{i}(x) − b_{i}), x ∈ X, y ∈ ℝ_{+}^{m}.

(x̄, ȳ) är en sadelpunkt till L på x × ℝ_{+}^{m} om

L(x̄, y) ≤^{(1)} L(x̄, ȳ) ≤^{(2)} L(x, ȳ), ∀(x, y) ∈ X × ℝ_{+}^{m}.

Olikhet 1: Fixera x = x̄ och studera problemet att max_{y∈ℝ_{+}^{m}}L(x̄, y) = f(x̄) + ∑_{i∉I} y_{i}(g_{i}(x̄) − b_{i}). Eftersom y_{i}, i ∈ I, inte förekommer i L(x̄, y) kan vi sätta y_{i} = ȳ_{i}, i ∈ I. Enligt förutsättningarna är b_{i} ≥ g_{i}(x̄), i ∉ I. Det är därför optimalt att välja y_{i} = 0, i ∉ I. Detta bevisar att olikhet 1 gäller.

Olikhet 2: Fixera y = ȳ och studera problemet att minimera_{x∈X}L(x, ȳ) = f(x) + ∑_{i∈I} ȳ_{i}(g_{i}(x) − g_{i}(x̄)). Eftersom ȳ_{i} · g_{i}(x̄) är konstant är detta problemet ekvivalent med att minimera_{x∈X}f(x) + ∑_{i=1}^{m} ȳ_{i}g_{i}(x), vilket enligt förutsättningarna har optimallösning x̄. Detta bevisar att olikhet 2 gäller.

b) Resultatet följer direkt av svaga dualsatsen:

\begin{aligned}L(ȳ) ≤ f^{∗}, ∀ȳ ∈ ℝ_{+}^{m} & ⇒ f(x̄) + ∑_{i=1}^{m} ȳ_{i}g_{i}(x̄) ≤ f^{∗} \\ & ⇔ f(x̄) − f^{∗} ≤ ∑_{i=1}^{m} ȳ_{i}g_{i}(x̄). \end{aligned}

Om x̄ är tillåten (d.v.s. g_{i}(x̄) ≤ 0, i = 1, …, m) är högerledet icke-negativt, vilket betyder att x̄ är en optimal lösning (f(x̄) = f^{∗}) om ∑_{i=1}^{m} ȳ_{i}g_{i}(x̄) = 0, d.v.s. om x̄ och ȳ är komplementära. Sammanfattningsvis är x̄ optimal i problemet om:

i) x̄ är primalt tillåten: g_{i}(x̄) ≤ 0, i = 1, …, m ii) ȳ är dualt tillåten: ȳ_{i} ≥ 0, i = 1, …, m

iii) x̄ löser problemet att minimera_{x∈X}L(x, ȳ)

iv) x̄ och ȳ är komplementära: ȳ_{i} · g_{i}(x̄) = 0, i = 1, …, m.

Relation till KKT-villoren: KKT-villkoren formuleras för en specialiserad fform av problemet där X = ℝ^{n} och där f och g_{i}, i = 1, …, m är differentierbara funktioner. Under dessa förutsättningar motsvarar KKt-villkoren optimalitetsvillkoren ovan precis, sånär som på en viktig skillnad: i KKTvillkoren ersätts ii) med kravet att x̄ är en stationär punkt till Lagrangefunktionen. Det kravet är svagare än iii), vilket innebär att x̄ inte bara uppfyller första ordningens krav på att x̄ är ett lokalt minimum till L(·, ȳ) utan att faktiskt x̄ är ett globalt minimum till L(·, ȳ). Med det starkare kravet följer också det starkare resultaet att x̄ är ett globalt minimum till f i urspringsproblemet, medan KKT-villkoren, som vi vet, bara medför detta under extra förutsättningar om problemets konvexitet.