Ekonomia matematyczna

Wykład 2: Optymalizacja statyczna I

Pojęcie ekstremum

Definicja (Ekstremum lokalne). Niech dana będzie funkcja f:(ℝ^n)->(ℝ^1). Powiemy, że punkt (Subscript[x, 0]) jest minimum lokalnym jeżeli

(Underscript[∃, ϵ>0]) (Underscript[∀, x∈B((Subscript[x, 0]),ϵ)])  f((Subscript[x, 0]))≤f(x).

Podobnie powiemy, że punkt (Subscript[x, 0]) jet maksimum lokalnym jeżeli

(Underscript[∃, ϵ>0]) (Underscript[∀, x∈B((Subscript[x, 0]),ϵ)]) f((Subscript[x, 0]))≥f(x).

Uwaga. Obie własności — minimum i maksimum — są własnościami lokalnymi. Funkcja może posiadać wiele ekstremów.

Obie własności — minimum i maksimum — są własnościami lokalnymi. Funkcja może posiadać wiele ekstremów. Żadna z własności nie gwarantuje nawet lokalnej jednoznaczności.

Przykład. Rozważmy funkcję f:(ℝ^2)->ℝ zdefiniowaną jako

f(x,y)=|x|.

Każdy punkt (0,y) jest minimum lokalnym. Wykres tej funkcji jest przedstawiony poniżej.

Plot3D[Abs[x],{x, -1, 1},{y, -1,1},PlotTheme->"Scientific",Axes->True,AxesOrigin->{0,0,0}]

Przykład (zadana liczba maksimów, konstrukcja). Bardzo łatwo skonstruować funkcję, która ma dowolna skończoną liczbę ekstremów. Rozważmy funkcję

f(x)=α (e^(-(((x-(Subscript[x, 0])))^2))).

Funkcja ta ma następujący wykres.

Manipulate[
Plot[Evaluate[α Exp[-(x-x0)^2]],{x, -10, 10},
PlotRange->{{-10,10},{-2,2}},
Ticks->{{x0},{α}},
GridLines->{{x0},{α}}],
{{x0,0,"parametr (Subscript[x, 0])"}, -5, 5},
{{α,1,"parametr α"},-1,1},
SaveDefinitions->True,ContinuousAction->False]

Stosując sumę funkcji takiej postaci można otrzymać funkcję o dowolnej skończonej liczbie ekstremów, ograniczoną. Przykładowa suma dwóch takich funkcji jest zamieszczona poniżej.

Manipulate[
Plot[Evaluate[α1 Exp[-(x-x01)^2]+α2 Exp[-(x-x02)^2]],{x, -10, 10},
PlotRange->{{-10,10},{-2,2}},
Ticks->{{x01,x02},{α1,α2}},
GridLines->{{x01,x02},{α1,α2}}],
{{x01,0,"(Subscript[x, 0]) (funkcja 1)"}, -5, 5},{{α1,1,"α (funkcja 1)"},-1,1},
{{x02,0,"(Subscript[x, 0]) (funkcja 2)"}, -5, 5},{{α2,1,"α (funkcja 2)"},-1,1},SaveDefinitions->True,ContinuousAction->False]

Korzystając z powyższej konstrukcji można losować wartości parametrów (Subscript[x, 0]) z zadanego rozkładu losowego, przykład poniżej pokazuje jak mogą wyglądać tak wylosowane funkcje.

f=Total@Flatten@Table[10 Exp[-(x-RandomVariate[NormalDistribution[0,20],1])^2],{k,1,10}];
TraditionalForm[f]
Plot[f,{x, -40,50},PlotRange->All,PlotTheme->"Scientific"]//Quiet

Przykład (przeliczalnie wiele ekstremów). Rozważmy zwykłą funkcję trygonometryczną f(x)=cos(x). Jak wiadomo funkcja ta ma maksima lokalne w każdym punkcie postaci x=2 k π, gdzie k∈ℕ. Jest to zatem sytuacja gdzie mamy nieskończoną ale przeliczalną liczbę ekstremów.

Przykład (przeliczalnie wiele ekstremów na odcinku ograniczonym). Rozważmy funkcję postaci f(x)=sin((π/x)) określoną na odcinku (0,1). Wykres tej funkcji jest przedstawiony poniżej.

Plot[Sin[π/x],{x, 1/20, 1}, AxesOrigin->{0,0},Axes->True,PlotRange->{{-.1,1}, {-2,2}},PlotTheme->"Scientific"]

Funkcja ta posiada maksima w każdym punkcie x spełniającym

(π/x)=(π/2)+2 k π

skąd otrzymujemy

x=(π/((π/2)+2 k π)) dla k∈ℕ.

Przykład (nieprzeliczalnie wiele ekstremów). Typowy przykład to funkcja stała.

Definicja (Ekstremum globalne). Niech dana będzie funkcja f:(ℝ^n)->(ℝ^1). Powiemy, że punkt (Subscript[x, 0]) jest minimum globalnym jeżeli

(Underscript[∀, x∈(ℝ^n)]) f((Subscript[x, 0]))≤f(x).

Podobnie powiemy, że punkt (Subscript[x, 0]) jest maksimum globalnym jeżeli

(Underscript[∀, x∈(ℝ^n)]) f((Subscript[x, 0]))≥f(x).

Optymalizacja bez ograniczeń

Twierdzenie (warunki konieczne). Niech G⊂(ℝ^n) będzie otoczeniem punktu (Subscript[x, 0])∈(ℝ^n). Niech funkcja f:G->(ℝ^1). Niech (Subscript[x, 0]) będzie ekstremum lokalnym oraz niech istnieje pochodna kierunkowa ((df((Subscript[x, 0])))/(dh))w punkcie (Subscript[x, 0]) w kierunku wektora h. Wtedy pochodna kierunkowa w punkcie (Subscript[x, 0]) przyjmuje wartość 0, tj. ((df((Subscript[x, 0])))/(dh))=0.

Uwaga. W powyższym twierdzeniu nie zakładamy nawet, że funkcja f jest różniczkowalna (w istocie nie musi być nawet ciągła). Rozważmy następującą funkcję f:(ℝ^2)->(ℝ^1), zadaną jako f(x)=|(Subscript[x, 1])|. Wykres tej funkcji jest przedstawiony poniżej.

fig1=Plot3D[Abs[x],{x, -1, 1},{y, -1, 1}, 
PlotRange->{{-1,1}, {-1,1},{0,1}},
PlotTheme->"Scientific",SphericalRegion->True,PlotStyle->Directive[Opacity[.5]],AxesLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"],TraditionalForm["f((Subscript[x, 1]),(Subscript[x, 2]))"]},Lighting->"Neutral",AxesStyle->Thick,MeshStyle->Directive[Opacity[.1]]];
fig2=Graphics3D[{{Blue,,PointSize[0.03],Point[{{0,0,0}}]}}];
fig3=Graphics3D[{{Blue,Arrow[{{0,0,0},{0,1,0}}]}}];
fig4=ParametricPlot3D[{u,0,Abs[u]},{u, -1, 1},PlotStyle->Red];
Show[fig1,fig2,fig3,fig4,SphericalRegion->True]

Jest jasne, że pomimo tego, że funkcja f nie jest różniczkowalna w punkcie x=(0,0) to istnieje pochodna kierunkowa df/dh w kierunku wektora h=(0,1) i wynosi ona 0.

Wniosek

(a) Jeżeli istnieją pochodne cząstkowe (Subscript[D, i])f((Subscript[x, 0])) to zachodzi (Subscript[D, i])f((Subscript[x, 0]))=0.

(b) Jeżeli istnieje różniczka D f((Subscript[x, 0])) to zachodzi D f((Subscript[x, 0]))=0.

Twierdzenie (warunki wystarczające).

Niech funkcja f:G⊂(ℝ^n)->(ℝ^1), gdzie (Subscript[x, 0])∈G jest otoczeniem punktu (Subscript[x, 0]), będzie dwukrotnie różniczkowalna oraz niech zachodzi Df((Subscript[x, 0]))=0 i forma kwadratowa h->(D^2)f((Subscript[x, 0]))h h jest (a) dodatnio określona (b) ujemnie określona (c) nieokreślona.

Wtedy punkt (Subscript[x, 0]) jest (a) minimum lokalnym (b) maksimum lokalnym (c) nie jest ekstremum.

Uwaga. Jeżeli forma kwadratowa h->(D^2)f((Subscript[x, 0]))h h jest określona półdodatnio lub półujemnie, to twierdzenie  nie rozstrzyga czy punkt (Subscript[x, 0]) jest czy nie jest ekstremum.

Przykład (typowe zatosowanie). Rozważmy funkcje postaci f((Subscript[x, 1]),(Subscript[x, 2]))=(e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))). Wykres funkcji jest przedstawiony poniżej.

fig5=Plot3D[Exp[-x^2-y^2],{x, -2, 2},{y, -2, 2}, 
PlotRange->{Automatic, Automatic,{0,1}},
PlotTheme->"Scientific",
PlotStyle->Directive[Opacity[0.4]],
Boxed->True,Axes->True,SphericalRegion->True,AxesLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"],TraditionalForm["f((Subscript[x, 1]),(Subscript[x, 2]))"]},Lighting->"Neutral",AxesStyle->Thick,MeshStyle->Directive[Opacity[.1]]];
fig6=Graphics3D[{{Blue,PointSize[0.02],Point[{{0,0,1}}]}}];
Show[fig5,fig6,SphericalRegion->True]

Obliczają pochodne cząstkowe i przyrównując do 0 otrzymujemy układ równań postaci

({{-2 (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (Subscript[x, 1]), =, 0}, {-2 (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (Subscript[x, 2]), =, 0}})

Część wyrażenia (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) jest zawsze dodatnia stąd istnieje tylko jeden punkt podejrzany o ekstremum, tj. (Subscript[x, 1])=(Subscript[x, 2])=0.

Aby sprawdzić czy punkt (0,0) rzeczywiście jest ekstremum możemy obliczyć macierz drugiej pochodnej, tzw. hessjan. Obliczając pochodne cząstkowe drugiego rzędu dostajemy

(D^2)f((Subscript[x, 1]),(Subscript[x, 2]))=(({{(e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (-2+4 (Subscript[x, 1]^2)), 4 (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (Subscript[x, 1]) (Subscript[x, 2])}, {4 (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (Subscript[x, 1]) (Subscript[x, 2]), (e^(-(Subscript[x, 1]^2)-(Subscript[x, 2]^2))) (-2+4 (Subscript[x, 2]^2))}}))=f((Subscript[x, 1]),(Subscript[x, 2])) (({{ (-2+4 (Subscript[x, 1]^2)), 4  (Subscript[x, 1]) (Subscript[x, 2])}, {4  (Subscript[x, 1]) (Subscript[x, 2]),  (-2+4 (Subscript[x, 2]^2))}})).

Natępnie obliczamy wartość drugiej pochodnej w punkcie podejrzanym o ekstremum otrzymując

(D^2)f(0,0)=(({{-2, 0}, {0, -2}})).

Aby zbadać określoność drugiej różniczki w punkcie (D^2)f(0,0) można np. skorzystać z odpowiedniego warunku opartego o minory główne. W tym przypadku wartości poszukiwanych minorów wynoszą odpowiednio -2 i 4 skąd wnioskujemy, że druga różniczka jest ujemnie określona. Można również zauważyć, że macierz drugiej różniczki jest już od razu w formie diagonalnej stąd ma ona tylko jedną wartość własną -2 o krotności algebraicznej i geometrycznej równej 2. Stąd również wynika, że jest to forma ujemnie określona. Konsekwentnie punkt (0,0) jest maksimum lokalnym funkcji f.

Przykład (brak rozstrzygnięcia). Rozważmy funkcje postaci f((Subscript[x, 1]),(Subscript[x, 2]))=(Subscript[x, 1]^2)+(Subscript[x, 2]^4). Wykres funkcji jest przedstawiony poniżej.

fig7=Plot3D[x^2+y^4,{x, -2, 2},{y, -2, 2}, 
PlotRange->{Automatic, Automatic,{0,4}},
PlotTheme->"Scientific",
Boxed->True,Axes->True,PlotStyle->Directive[Opacity[.3]],AxesLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"],TraditionalForm["f((Subscript[x, 1]),(Subscript[x, 2]))"]},Lighting->"Neutral",AxesStyle->Thick,MeshStyle->Directive[Opacity[.2]],ClippingStyle->None];
fig8=Graphics3D[{{Blue,PointSize[0.02],Point[{{0,0,0}}]}}];
Show[fig7,fig8,SphericalRegion->True]

Podobnie jak poprzednio wykonujemy identyczne obliczenia. Warunki pierwszego rzędu są zatem postaci

({{2 (Subscript[x, 1]), =, 0}, {4 (Subscript[x, 2]^3), =, 0}})

skąd otrzymujemy punkt podejrzany o ekstremum (0,0). Druga pochodna jest postaci

(D^2)f((Subscript[x, 1]),(Subscript[x, 2]))=(({{2, 0}, {0, 12 (Subscript[x, 2]^2)}}))

skąd mamy

(D^2)f(0,0)=(({{2, 0}, {0, 0}})).

Obliczając odpowiednie minory główne otrzymujeny kolejno 2, 0 i 0 a zatem druga pochodna w punkcie (0,0) jest określona półdodatnio. Pomimo tego, że punkt (0,0) jest ewidentnym minimum globalnym twierdzenie  nie rozstrzyga o tym, czy jest to czy nie jest to ekstremum.

Przykład (punkt siodłowy). Rozważmy funkcje postaci f((Subscript[x, 1]),(Subscript[x, 2]))=(Subscript[x, 1]) (Subscript[x, 2]). Wykres funkcji jest przedstawiony poniżej.

fig9=Plot3D[x y,{x, -2, 2},{y, -2, 2}, 
PlotRange->{Automatic, Automatic,{-4,4}},
PlotTheme->"Scientific",
Boxed->True,Axes->True,PlotStyle->Directive[Opacity[.3]],AxesLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"],TraditionalForm["f((Subscript[x, 1]),(Subscript[x, 2]))"]},Lighting->"Neutral",AxesStyle->Thick,MeshStyle->Directive[Opacity[.2]],ClippingStyle->None];
fig10=Graphics3D[{{Blue,PointSize[0.02],Point[{{0,0,0}}]}}];
fig11=ParametricPlot3D[{u,u,u^2},{u,-2,2},PlotStyle->Blue];
fig12=ParametricPlot3D[{u,-u,-u^2},{u,-2,2},PlotStyle->Red];
Show[fig9,fig10,fig11,fig12,SphericalRegion->True]

Podobnie jak poprzednio wykonujemy identyczne obliczenia. Warunki pierwszego rzędu są zatem postaci

({{y, =, 0}, {x, =, 0}})

skąd otrzymujemy punkt podejrzany o ekstremum (0,0). Druga pochodna jest postaci

(D^2)f((Subscript[x, 1]),(Subscript[x, 2]))=(({{0, 1}, {1, 0}}))

skąd mamy

(D^2)f(0,0)=(({{0, 1}, {1, 0}})).

Obliczając minor główny drugiego stopnia otrzymujemy -1 skąd wiemy, że druga pochodna jest nieokreślona i w konsekwencji punkt (0,0) nie jest ekstremum.

Optymalizacja z ograniczeniami w postaci równości

Uwaga (sformułowanie zagadnienia). Zanim przejdziemy do sformułowania warunków koniecznych zajmiemy się zformułowaniem zagadnienia optymalizacji z ograniczeniami w postaci równości oraz podamy przykład takiego zagadnienia.

Przede wszystkim musimy mieć funkcję, której maksimum lub minimum poszukujemy. Funkcja ta nazywa się często funkcją kryterium lub funkcją celu. W zakresie niniejszego wykładu jest to funkcja

f:(ℝ^N)->(ℝ^1).

Zbiór rozwiązań dopuszczalnych jest zadany poprzez układ równości postaci

({{(Subscript[g, 1])(x), =, (Subscript[b, 1])}, {⋮, ⋮, ⋮}, {(Subscript[g, M])(x), =, (Subscript[b, M])}})

gdzie (Subscript[g, m]):(ℝ^N)->(ℝ^1) są zadanymi funkcjami. Dodatkowo zakładamy, że M<N oraz, że wszystkie funkcje są różniczkowalne.

Przez macierz Jacobiego będziemy rozumieli linearyzację powyższego układu równań a więc macierz postaci

J(x)=(({{∇(Subscript[g, 1])(x)}, {⋮}, {∇(Subscript[g, M])(x)}})),

gdzie ∇(Subscript[g, m])(x)=((Subscript[D, 1])(Subscript[g, m])(x), …,(Subscript[D, N])(Subscript[g, m])(x)) jest gradientem funkcji (Subscript[g, m]).

Twierdzenie (warunki konieczne). Niech funkcje f, (Subscript[g, m]), dla m=1,…,M będą różniczkowalne. Niech punkt (Subscript[x, 0]) będzie ekstremum funkcji f w zbiorze rozwiązań dopuszczalnych zadanych układem () oraz niech macierz Jacobiego w punkcie (Subscript[x, 0]), J((Subscript[x, 0])) będzie rzędu M.

Wtedy istnieją liczby (Subscript[λ, 1]),…,(Subscript[λ, M]) takie, że zachodzi równość

∇f((Subscript[x, 0]))=(∑_(m=1)^M)(Subscript[λ, m]) ∇(Subscript[g, m])((Subscript[x, 0])).

Uwaga (inne sformułowanie twierdzenia). Klasycznie twierdzenie  jest formułowane w termianch tzw. funkcji Lagrange’a postaci

L(x)=f(x)-(∑_(m=1)^M)(Subscript[λ, m]) ((Subscript[g, m])(x)-(Subscript[b, m])),

która jest następnie różniczkowana po zmiennych (Subscript[x, n]). Pochodne te są następnie przyrównywane do 0 co prowadzi do równania wektorowego podanego w powyższym twierdzeniu.

Przykład. Rozważmy funkcje postaci f((Subscript[x, 1]),(Subscript[x, 2]))=(Subscript[x, 1]) (Subscript[x, 2]) optymalizowanej na zbiorze rozwiązań dopuszczalnych zadanych równaniem (Subscript[x, 1]^2)+(Subscript[x, 2]^2)=1. Sytuacja ta jest przedstawiona na poniższym wykresie.

fig13=Plot3D[x y,{x, -1.1, 1.1},{y, -1.1, 1.1}, 
PlotRange->{{-1.1,1.1}, {-1.1,1.1},{-2,2}},
PlotTheme->"Scientific",
Boxed->True,Axes->True,PlotStyle->Directive[Opacity[.3]],AxesLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"],TraditionalForm["f((Subscript[x, 1]),(Subscript[x, 2]))"]},
Lighting->"Neutral",AxesStyle->Thick,MeshStyle->Directive[Opacity[.2]],ClippingStyle->None];
fig14=ParametricPlot3D[{Cos[u],Sin[u],0},{u,0,2 π},PlotStyle->Directive[Thin,Black]];
fig15=ParametricPlot3D[{Cos[u],Sin[u],Cos[u] Sin[u]},{u,0,2 π},PlotStyle->Directive[Thick,Blue]];
fig16=ParametricPlot3D[{u,u,u^2},{u,-2,2},PlotStyle->Directive[Red]];
fig17=ParametricPlot3D[{u,-u,-u^2},{u,-2,2},PlotStyle->Directive[Red]];
fig18=Graphics3D[{{Red,PointSize[0.02],Point[{{1/Sqrt[2],1/Sqrt[2],1/2},{-1/Sqrt[2],1/Sqrt[2],-1/2},{1/Sqrt[2],-1/Sqrt[2],-1/2},{-1/Sqrt[2],-1/Sqrt[2],1/2}}]}}];
fig19=ContourPlot3D[x^2+y^2==1,{x,-2,2},{y,-2,2},{z,-2,2},ContourStyle->Directive[Purple,Opacity[.3]],Mesh->None];
Show[fig13,fig14,fig15,fig16,fig17,fig18,fig19,SphericalRegion->True]

Aby znaleźć punkty podejrzane o ekstremum wypisujemy funkcje Lagrange’a otrzymując

L(x,λ)=(Subscript[x, 1]) (Subscript[x, 2]) - λ ((Subscript[x, 1]^2)+(Subscript[x, 2]^2)-1).

Natępnie obliczamy pochodne cząstkowe i przyrównujemy do 0 otrzymując układ równań postaci

({{-2 λ (Subscript[x, 1])+(Subscript[x, 2]), =, 0}, {(Subscript[x, 1])-2 λ (Subscript[x, 2]), =, 0}, {(Subscript[x, 1]^2)+(Subscript[x, 2]^2), =, 1}})

Rozwiązując powyższy układ równań otrzymujemy czteru punkty postaci (±1/(Sqrt[2]),±1/(Sqrt[2])). Aby sprawdzić czy punkty te są rzeczywiście ekstremami konieczne są warunki dostateczne.

Twierdzenie (warunki dostateczne). Niech funkcje f, (Subscript[g, m]), dla m=1,…,M będą dwukrotnie różniczkowalne oraz niech L(x)=f(x)-(∑_m)(Subscript[λ, m])((Subscript[g, m])(x)-(Subscript[b, m])). Dodatkowo niech punkt (Subscript[x, 0]) będzie rozwiązaniem dopuszczalnym oraz niech macierz Jacobiego J((Subscript[x, 0])) będzie rzędu M w punkcie (Subscript[x, 0]) i niech zachodzi równość ∇f((Subscript[x, 0]))=(∑_m)(Subscript[λ, m]) ∇(Subscript[g, m])((Subscript[x, 0])). Niech forma kwadratowa h->(D^2)L((Subscript[x, 0]))h h będzie (a) dodatnio określona (b) ujemnie określona (c) nieokreślona na przestrzeni stycznej do ograniczenia w punkcie (Subscript[x, 0]) postaci

T={w∈(ℝ^N) : (Underscript[∀, m]) ⟨∇(Subscript[g, m])((Subscript[x, 0]))|w⟩=0}.

Wtedy punkt (Subscript[x, 0]) jest (a) minimum lokalnym (b) maksimum lokalnym (c) nie jest ekstremum na zbiorze rozwiązań dopuszczalnych.

Przykład (kontynuacja).

Kontynuujemy poprzedni przykład. Wypisaliśmy funcje Lagrange’a

L(x)=(Subscript[x, 1]) (Subscript[x, 2]) - λ ((Subscript[x, 1]^2)+(Subscript[x, 2]^2)-1)

i wyznaczyliśmy warunki pierwszego rzędu postaci

({{-2 λ (Subscript[x, 1])+(Subscript[x, 2]), =, 0}, {(Subscript[x, 1])-2 λ (Subscript[x, 2]), =, 0}, {(Subscript[x, 1]^2)+(Subscript[x, 2]^2), =, 1}})

Rozwiązując powyższy układ równań otrzymaliśmy czteru punkty postaci (±1/(Sqrt[2]),±1/(Sqrt[2])). Dodatkowo, jak nietrudo sprawdzić mamy λ=±1/2. Aby sprawdzić czy punkty te są ekstremami musimy sprawdzić określoność drugiej pochodnej (D^2)L na przestrzeniach stycznych do ograniczenia w tych danych punktach. W pierwszym kroku obliczamy drugą pochodną (D^2)L otrzymując

(D^2)L((Subscript[x, 1]),(Subscript[x, 2]))=(({{-2λ, 1}, {1, -2λ}})).

Następnie musimy zobaczyć jak wyglądają przestrzenie styczne. W dalszczej części skupimy się jedynie na punkcie a=(1/(Sqrt[2]),1/(Sqrt[2])) ale obliczenia są identyczne dla wszystkich czterech punktów. Mamy następującą sytuację.

fig20=ContourPlot[x^2+y^2==1,{x, -2,2},{y,-2,2}];
fig21=Graphics[{{Red,PointSize[0.02],Point[{{1/Sqrt[2],1/Sqrt[2]}}]}}];
fig22=Graphics[{{Arrow[{{1/Sqrt[2],1/Sqrt[2]},{1/Sqrt[2],1/Sqrt[2]}+{Sqrt[2],Sqrt[2]}}]}}];
fig23=Graphics[{{Blue,Arrow[{{1/Sqrt[2],1/Sqrt[2]},{1/Sqrt[2],1/Sqrt[2]}+{-1,1}}]}}];
fig24=ContourPlot[Evaluate[{x,y}.{1,1}=={1/Sqrt[2],1/Sqrt[2]}.{1,1}],{x,-4,4},{y,-4,4},
ContourStyle->Directive[Blue,Dashed]];
fig25=Graphics[{{Text[TraditionalForm["a"],Scaled[{-0.02,-0.02},{1/Sqrt[2],1/Sqrt[2]}]]},
{Text[TraditionalForm["∇g(a)"],Scaled[{0.03,-0.03},{1/Sqrt[2]+1,1/Sqrt[2]+1}]]},
{Text[TraditionalForm["T"],Scaled[{0.03,0.03},{1/Sqrt[2]-1,1/Sqrt[2]+1}]]}}];
Show[fig20,fig21,fig24,fig23,fig22,fig21,fig25,Axes->True,
FrameLabel->{TraditionalForm["(Subscript[x, 1])"],TraditionalForm["(Subscript[x, 2])"]},
PlotRange->{{-3,3},{-3,3}}]

Wyznaczamy gradient ograniczenia w punkcie a otrzymując

∇g(a)=[2 (Subscript[x, 1]),2 (Subscript[x, 2])](Subscript[|, x=a])=[(Sqrt[2]),(Sqrt[2])].

Aby wyznaczyć bazę przestrzeni stycznej do ograniczenia wystarczy znaleźć wszystkie liniowo niezależne wektory prostopadłe do wektora ∇g(a). W tym konkretnym przypadku może to być wektor np. [-1,1].  Każdy inny wektor prostopadły jest postaci α[-1,1]. Mamy więc bazę przestrzeni stycznej do ograniczenia w punkcie a.

Następnie sprawdzamy jak określona jest forma kwadratowa (D^2)L(a) na przestrzeni stycznej do ograniczenia. Wystarczy to sprawdzić na wszystkich elementach bazy. W tym konkretnym przypadku mamy tylko jeden element bazy, dla którego otrzymujemy

(({{-1, 1}})) (({{-1, 1}, {1, -1}})) (({{-1}, {1}}))=(({{-1, 1}})) (({{2}, {-2}}))=-4<0.

Zatem na dowolnym elemencie przestrzeni stycznej wartość formy kwadratowej (D^2)L(a) będzie wynosiła -4 (α^2) a więc z definicji jest to forma ujemnie zdefiniowana. Konkludujemy, że punkt a jest lokalnym maksimum.

Przykład (optymalizacja konsumenta). Rozważamy klasyczną optymalizację konsumenta. Dalsze obliczenia są dobre dla dowolnej różniczkowalnej funkcji użyteczności ale rysunki będą przedstawiały funkcję Cobba-Douglasa. Opis zadania optymalizacji rozwiązywanego przez konsumenta składa się z funkcji użyteczności u((Subscript[x, 1]),(Subscript[x, 2])) oraz ograniczenia budżetowego postaci (Subscript[p, 1]) (Subscript[x, 1])+(Subscript[p, 2]) (Subscript[x, 2]) ≤w, gdzie (Subscript[p, k]), k=1,2 to ceny dóbr a w to bagactwo. Zagadnienie jest więc postaci

(max_(((Subscript[x, 1]),(Subscript[x, 2])))) u((Subscript[x, 1]),(Subscript[x, 2])) przy ograniczeniach (Subscript[x, 1])≥0, (Subscript[x, 2])≥0, (Subscript[p, 1]) (Subscript[x, 1])+(Subscript[p, 2]) (Subscript[x, 2]) ≤w.

Przy standardowych założeniach o funkcji użyteczności powyższe zagadnienie możemy zapisać jako

(max_(((Subscript[x, 1]),(Subscript[x, 2])))) u((Subscript[x, 1]),(Subscript[x, 2])) przy ograniczeniu  (Subscript[p, 1]) (Subscript[x, 1])+(Subscript[p, 2]) (Subscript[x, 2]) =w.

Funkcja Lagrange’a jest tutaj postaci

L((Subscript[x, 1]),(Subscript[x, 2]))=u((Subscript[x, 1]),(Subscript[x, 2]))-λ ((Subscript[p, 1]) (Subscript[x, 1])+(Subscript[p, 2]) (Subscript[x, 2])-w).

Warunki pierwszego rzędu są więc następujące

({{((∂u)/(∂(Subscript[x, 1])))-λ (Subscript[p, 1]), =, 0,}, {((∂u)/(∂(Subscript[x, 2])))-λ (Subscript[p, 2]), =, 0.}})

Warunki te mają dobrą interpretację geometryczną. Przekształcając je i dzieląc stronami otrzymuje się warunek postaci

((∂u/∂(Subscript[x, 1]))/(∂u/∂(Subscript[x, 2])))=((Subscript[p, 1])/(Subscript[p, 2]))=((∂(Subscript[x, 2]))/(∂(Subscript[x, 1]))).

Lewa strona to krańcowa stopa substytucji (marginal rate of substitution). Aby zobaczyć dlaczego geometrycznie oznacza to styczność warstwicy (krzywej obojętności) do ograniczenia budżetowego wystarczy zobaczyć, że

(Subscript[p, 1]) (Subscript[x, 1]) + (Subscript[p, 2]) (Subscript[x, 2]) =w    prowadzi do  (Subscript[x, 2])=-((Subscript[p, 1])/(Subscript[p, 2]))(Subscript[x, 1])+(w/(Subscript[p, 2])).

Zatem nachylenie ograniczenia budżetowego to -(Subscript[p, 1])/(Subscript[p, 2]). Nachylenie krzywej obojętności w danym punkcie (OverHat[x]) można wyznaczyć pamiętając, że gradient funkcji jest prostopadły do jej warstwicy. Zatem prosta styczna do warstwicy funkcji użyteczności musi być postaci

⟨∇u((OverHat[x]))|x⟩=⟨∇u((OverHat[x]))|(OverHat[x])⟩   co można zapisać jako (Subscript[x, 2])=-((∂u/∂(Subscript[x, 1]))/(∂u/∂(Subscript[x, 2])))(Subscript[x, 1])+stała.

Zatem warunek optymalności pierwszego rzędu wymaga aby współczynniki kątowe nachylenia obu prostych — stycznej od ograniczenia budżetowego oraz stycznej do krzywej obojętności — były takie same co geometrycznie oznacza styczność.

Warunki drugiego rzędu wymagają znalezienia przestrzeni stycznej do ograniczenia. Bez problemu widać, że bazą takiej przestrzeni jest np. wektor (({{-(Subscript[p, 2]), (Subscript[p, 1])}})). Druga pochodna jest postaci

(D^2)L((Subscript[x, 1]),(Subscript[x, 2]))=(D^2)u((Subscript[x, 1]),(Subscript[x, 2])).

Warunek jest zatem postaci

(({{-(Subscript[p, 2]), (Subscript[p, 1])}})) (D^2)u((Subscript[x, 1]),(Subscript[x, 2])) (({{-(Subscript[p, 2])}, {(Subscript[p, 1])}}))<0.

W kolejnym wykładzie pokażemy, że jest to warunek na wklęsłości funkcji użyteczności. Całość zagadnienia jest przedstawiona na poniższym wykresie.

Manipulate[
u=Sqrt[x y];
figa=Plot3D[u,{x, 0, 2},{y, 0, 2},
PlotStyle->Directive[Blue, Opacity[.3]],
MeshStyle->Directive[Blue,Opacity[.2]]];
figb=ParametricPlot3D[{(1-u) w/(Subscript[p, 1]),u w/(Subscript[p, 2]),0},{u,0,1}];
figc=Graphics3D[{{Red,PointSize[0.02],Point[{{px,py,0}}]}}];
figd=ParametricPlot3D[{Sqrt[px py/ Tan[u]],Sqrt[px py Tan[u]],0},{u,0+π/100,π/2-π/100},PlotStyle->Black];
fige=ParametricPlot3D[{Sqrt[px py/ Tan[u]],Sqrt[px py Tan[u]],Sqrt[Sqrt[px py/ Tan[u]] Sqrt[px py Tan[u]]]},{u,0+π/100,π/2-π/100},PlotStyle->Directive[Blue,Dashed]];
figf=Graphics3D[{{Black,Arrow[{{px,py,0},{px+Sqrt[py/px]/2,py+Sqrt[px/py]/2,0}}]}}];
figg=Graphics3D[{{Red,Dashed,Arrow[{{px,py,0},{px+(Subscript[p, 1])/2,py+(Subscript[p, 2])/2,0}}]}}];
Show[figa,figb,figc,figd,fige,figf,figg,figa,
SphericalRegion->True,PlotRange->{{0,2},{0,2},{0,3}}],
{{(Subscript[p, 1]),1,"Cena (Subscript[p, 1])"},1,2},{{(Subscript[p, 2]),1,"Cena (Subscript[p, 2])"},1,2},
{{w,2,"Bogactwo"},0,2},
{{px,1,"Dobro (Subscript[x, 1])"},0.01,2},{{py,1,"Dobro (Subscript[x, 2])"},0.01,2},SaveDefinitions->True,ContinuousAction->Automatic]

Optymalizacja z ograniczeniami w postaci nierówności

Uwaga (Sformułowanie zagadnienia). Zaczynamy od sformułowania zagadnienia. Tak jak porzednio dysponujemy funkcją celu

f:(ℝ^N)->(ℝ^1).

Zbiór rozwiązań dopuszczalnych jest opisany układem równości

({{(Subscript[g, 1])(x), =, (Subscript[b, 1])}, {⋮, ⋮, ⋮}, {(Subscript[g, M])(x), =, (Subscript[b, M])}})

oraz nierówności postaci

({{(Subscript[h, 1])(x), ≤, (Subscript[c, 1])}, {⋮, ⋮, ⋮}, {(Subscript[h, K])(x), ≤, (Subscript[c, K])}})

gdzie funkcje (Subscript[g, m]) i (Subscript[h, k]) są zadane. Przez C oznaczymy zbiór rozwiązań dopuszczalnych

C={x∈(ℝ^N) : (Subscript[g, m])(x)=(Subscript[b, m])   dla   m=1,…,M, (Subscript[h, k])(x)≤(Subscript[c, k])   dla   k=1,…,K}.

Przez (OverTilde[K])(x) oznaczymy zbiór tych indeksów, dla których nierówności są spełnione z równością, a więc

(OverTilde[K])(x)={k∈ℕ : (Subscript[h, k])(x)=(Subscript[c, k])}.

Twierdzenie (twierdzenie Kuhna-Tuckera). Niech funkcje f, (Subscript[g, m]), (Subscript[h, k]), dla m=1,…,M, k=1,…,K będą różniczkowalne oraz niech (Subscript[x, 0])∈C będzie maksimum lokalnym. Dodatkowo niech wektory ∇(Subscript[g, m])((Subscript[x, 0])), m=1, …,M, i ∇(Subscript[h, k])((Subscript[x, 0])), k∈(OverTilde[K])((Subscript[x, 0])) będą liniowo niezależne.

Wtedy istnieją liczby (Subscript[λ, m])∈ℝ, m=1, …,M, oraz liczby (Subscript[λ, k])∈(SubPlus[ℝ]), k=1, …,K, dla których zachodzi

∇f((Subscript[x, 0]))=(∑_(m=1)^M)(Subscript[λ, m]) ∇(Subscript[g, m])((Subscript[x, 0]))+(∑_(k=1)^K)(Subscript[λ, k]) ∇(Subscript[h, k])((Subscript[x, 0]))

i równocześnie jest spełniony warunek

(Underscript[∀, k=1, …,K]) (Subscript[λ, k]) ((Subscript[h, k])((Subscript[x, 0]))-(Subscript[c, k]))=0.

Uwaga. Drugi warunek w powyższym twierdzeniu sprowadza się do zastrzeżenia, że jeżeli dla ustalonego punktu (Subscript[x, 0]) zachodzi k ∉(OverTilde[K])((Subscript[x, 0])) to odpowiadający czynnik (Subscript[λ, k])=0. W przeciwnym wypadku czynnik ten może być albo zerowy albo dodatni.

Powyższe twierdzenie sprowadza optymalizaję z ograniczeniami w postaci nierówności do optymalizacji albo bez ograniczeń albo z ograniczeniami w postaci równości (dbając przy okazji o kierunek dopuszczalnych poprawek!). Załóżmy przez chwilę, że nie mamy żadnych ograniczeń będących równościami a jedyne ograniczenia są w postaci nierówności. Wtedy warunki z powyższego twierdzenia mówią jedynie tyle, że jeżeli dana nierówność jest spełniona ostro to nie bierzemy jej pod uwagę i wchodzi ona jako 0 do równania (). Jeżeli dana nierówność jest spełniona jako równość to traktujemy ją jako równość. W skrajnym przypadku jeżeli wszystkie nierówności są spełnione ostro to równanie () sprowadza się do żądania aby ∇f((Subscript[x, 0]))=0 a więc warunku koniecznego z optymalizacji bez ograniczeń. W przypadku gdy wszystkie równości są spełnione jako równości to warunek () sprowadza się do warunku koniecznego z optymalizacji z warunkami zadanymi równościami, tj. do warunku ∇f((Subscript[x, 0]))=(∑_(m=1)^M)(Subscript[λ, m]) ∇(Subscript[g, m])((Subscript[x, 0])).

Przykład (optymalizacja firmy). Niech Y⊂(ℝ^2) będzie  zbiorem dopuszczalnych planów produkcyjnych z typowym planem produkcyjnym y∈Y. Przykładowo jeżeli y=(({{-2, 1}})) to taki plan produkcyjny interpretujemy jako plan, w którym używając 2 jednostek dobra pierwszego można wyprodukować 1 jednostkę dobra drugiego.

Zbiory produkcyjne opisuje się zazwyczaj poprzez podanie funkcji F:(ℝ^2)->ℝ jako

Y={y∈(ℝ^2) : F(y)≤ 0}.

Zbiór będący brzegiem  zbioru Y, a więc zbiór {y : F(y)=0} nazywa się transformation frontier (bariera technologiczna, DEA, SFA).

Niech dany będzie wektor cen dla wszystkich dóbr p=(({{(Subscript[p, 1]), (Subscript[p, 2])}}))≫0. Przy zadanym planie produkcyjnym y∈Y zysk firmy to iloczyn skalarny wektora cen i wektora opisującego plan produkcyjny, a więc ⟨p|y⟩. Zadaniem firmy jest maksymalizacja zysku przy ograniczeniach zadanych funkcją F, jest to więc zagadnienie postaci

(max_y) ⟨p|y⟩    z warunkami F(y)≤ 0.

Warunki optymalności pierwszego rzędu mają postać

({{∇⟨p|(Subscript[y, 0])⟩, =, λ ∇F((Subscript[y, 0]))}, {λ (F((Subscript[y, 0]))-0), =, 0}})

Zauważamy, że ∇⟨p|(Subscript[y, 0])⟩=p. Mamy, że jeżeli F((Subscript[y, 0]))<0 to z drugiego warunku λ=0 co z pierwszego warunku daje p=0. Jeżeli F((Subscript[y, 0]))=0 to λ>0 i pierwszy warunek redukuje się do warunku

({{p, =, λ∇F((Subscript[y, 0]))}, {((Subscript[p, 1])/(Subscript[p, 2])), =, ((∂F/∂(Subscript[y, 1]))/(∂F/∂(Subscript[y, 2])))}})

a więc do znanego warunku na równość krańcowej stopy  transformacji (marginal rate of transformation) ze znaną interpretacją geometryczną styczność lini stałego zysku do transformation frontier.