Programowanie wypukłe. Zagadnienia związane z równościami i nierównościami.

Niech $f_{i}:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$, $i=\overline{0, m}$, będą funkcjami $n\in\mathbb{N}$ zmiennych. Zachodzi następujące twierdzenie:

8.1   Twierdzenie (Lagrange'a). Niech $\hat{x}\in\mathbb{R}^n$ będzie ekstremum lokalnym dla problemu

$$extr_{x\in\mathbb{R}^n} f_{0}(x)\; -\; ?\;,\;f_{i}=0\,,\, i=\overline{1,m},$$ (8.1)

a funkcje $f_{i}:\mathbb{R}^{m}\longrightarrow \overline {\mathbb{R}}$, $i=\overline{0, m}$, są ciągle różniczkowalne w otoczeniu punktu $\hat{x}\in\mathbb{R}^n$. Wtedy istnieje niezerowy wektor mnożników Lagrange'a
$\lambda :=(\lambda_{0},\lambda_{1},\dots, \lambda_{m})\in\mathbb{R}^{m+1}$, taki, że dla funkcji

$$\mathcal{L}_{\lambda}:=\sum_{i=0}^{m}\lambda_{i}f_{i}(x)$$ (8.2)

spełniony jest warunek stacjonarności:

$$\partial\mathcal{L}_{\lambda}(x)/\partial x =0\;,\;\partial\mathcal{L}_{\lambda}(x)/\partial\lambda =0.$$ (8.3)

$\vartriangleleft$ Dowód (niewprost). Przypuśćmy, że warunek stacjonarności nie jest spełniony, tzn. że wektory

$$\{\partial f_{i}(\hat{x})/\partial x_{j}:j=\overline{1,n}\}\;,\; i=\overline{0,m}$$ (8.4)

są liniowo niezależne. To znaczy, że rząd macierzy $\vert\vert\partial f_{i}(\hat{x})/\partial x_{j}\vert\vert _{\underset{j=\overline{1,n}}{i=\overline{0,m} }}$ wynosi $m+1\leqslant n$. Wtedy na mocy twierdzenia o rzędzie istnieje macierz
$\{F_{ij}(\hat{x}):i,j=\overline{1,m+1}\}$ z wyznacznikiem różnym od zera. Przypuśćmy, że tą macierzą jest macierz

$$\left( \begin{array}{ccc} \frac{\partial f_{0}(\hat{x})}{\parti... ...(\hat{x})}{\partial x_{m+1}} \end{array}\right) = F'(\hat{x})\;,\;det F'\ne 0.$$ (8.5)

Będziemy rozważać przypadek, kiedy $f_{0}(\hat{x})=0$. Jeśli tak nie jest, to funkcja $f_{0}(x)!=f_{0}(x)-f_{0}(\hat{x})$ już spełnia ten warunek.
Weźmy wektor $\overline{x}:=(x_{1},x_{2},\ldots,x_{m+1})$ i zdefiniujmy odwzorowanie:

$$F(\overline{x}):=(F_{0}(\overline{x}),F_{1}(\overline{x}),\ldots,... ...ine{x})):= (f_{0}(\overline{x},\hat{x}_{m+2},\hat{x}_{m+3},\ldots,\hat{x}_{n}),$$

$$f_{1}(\overline{x},\hat{x}_{m+2},\hat{x}_{m+3},\ldots,\hat{x}_{n}),\ldots, f_{m}(\overline{x},\hat{x}_{m+2},\hat{x}_{m+3},\ldots,\hat{x}_{n}))$$ (8.6)

Odwzorowanie $F:\mathbb{R}^{m+1}\longrightarrow\mathbb{R}^{m+1}$ jest, oczywiście, niezdegenerowane, ponieważ $det\,F'\ne 0$ w otoczeniu punktu $\hat{\overline{x}}:=(\hat{x}_{1}, \hat{x}_{2},\ldots,\hat{x}_{m+1})\in\mathbb{R}^{m+1}$. Na mocy o odwzorowaniu odwrotnym w $\mathbb{R}^{m+1}$ istnieje odwrotne odwzorowanie
$F^{-1}:\mathbb{R}^{m+1} \longrightarrow\mathbb{R}^{m+1}$ w otoczeniu punktu zero, takie, że

$$\vert\vert F^{-1}(y)-\overline{x}\vert\vert\leqslant c\vert\vert y\vert\vert\:,$$ (8.7)

gdzie $c>0$ jest pewną stała. W szczególności dla wystarczająco małego $\vert\varepsilon\vert>0$ istnieje wektor $\overline{x}(\varepsilon)=F^{-1}(\varepsilon,0,\ldots,0)$, taki, że

$$F(\overline{x}(\varepsilon))=(\varepsilon,0,\ldots,0)\:,\;$$ (8.8)

$$\textrm{tj.}\quad f_{0}(\overline{x}(\varepsilon))=\varepsilon ,f_{i}(\overline{x}(\varepsilon))=0\;;\; i=\overline{1,m},$$

oraz spełnione są nierówności:

$$\vert\vert\overline{x}(\varepsilon)-\hat{\overline{x}}\vert\vert\... ...vert\vert x(\varepsilon)- \hat{x}\vert\vert\leqslant c\vert\varepsilon\vert\:,$$ (8.9)

gdzie $x(\varepsilon):=(\overline{x}(\varepsilon),\hat{x}_{m+2},\ldots,\hat{x}_{n})\in \mathbb{R}^{n}$.
Tak więc z () i () otrzymujemy, że wektor $\hat{x}\in\mathbb{R}^{n}$ nie spełnia warunku ekstremalności, ponieważ w jego pobliżu isnieją wektory $x(\varepsilon)\in\mathbb{R}^{n}$, na których funkcjonał $f_{0}:\mathbb{R}^{n} \longrightarrow\mathbb{R}^{1}$ przyjmuje wartości zarówno większe, jak i mniejsze od $f_{0}(\hat{x})=0$. A to przeczy temu, że $\hat{x}\in loc\, extr\,f_{0}$ i kończy dowód. $\rhd$

8.2   Uwaga. Warunek () powoduje, oczywiście, że $\lambda_{0}\ne 0$ ( $\Rightarrow 1$!), gdy wektory $grad\,f_{j}(\hat{x}),\;j=\overline{1,m}$, są liniowo niezależne.

Sformułujemy teraz warunki konieczne na ekstremum dla problemu z równościa-mi i nierównościami w $\mathbb{R}^{n}$:

$$\inf_{x\in \mathbb{R}^{n}}\, f_{0}(x)\;-\; ?\;,\; gdy\;f_{i}(x)\leqslant 0\;,\;i=\overline{1,m'\;,}$$ (8.10)

$$f_{i}(x)=0\;,\;i=\overline{m',m}.$$

8.3   Twierdzenie. Niech $\hat{x}\in\mathbb{R}^{n}$ będzie minimum dla problemu () i funkcji $f_{i}:\mathbb{R}^{n}\longrightarrow\mathbb{R}$, $i=\overline{1,m}$ ciągłych i różniczkowalnych w otoczeniu punktu $\hat{x}\in\mathbb{R}^{n}$. Wtedy istnieje niezerowy wektor mnożników Lagrange'a
$\lambda=(\lambda_{0},\ldots,\lambda_{m}) \in\mathbb{R}^{m+1}$, taki, że dla funkcji Lagrange'a problemu ()

$$\mathcal{L}_{\lambda}(x):=\sum_{i=0}^{m}\lambda_{i}\,f_{i}(x)$$ (8.11)

w punkcie $\hat{x}\in\mathbb{R}^{n}$ są spełnione warunki:

a)

stacjonarności:

$$\partial\mathcal{L}_{\lambda}(\hat{x})/\partial x=0\;,\;\partial\mathcal{L}_{\lambda}(\hat{x})/ \partial\lambda=0;$$ (8.12)

b)

dopełniającej elastyczności:

$$\lambda_{i}\, f_{i}(\hat{x})=0\;,\;i=\overline{0,m'};$$ (8.13)

c)

nieujemności:

$$\lambda_{i}\geqslant 0\;,\;i=\overline{0,m'}.$$ (8.14)

$\vartriangleleft$Dowód: Załóżmy, jak wcześniej, że $f_{0}(\hat{x})=0$. Jeżeli $f_{i}(\hat{x})\ne 0$, i= $\overline{1,m}$, to te ograniczenia odrzucamy, ponieważ dla ekstremum lokalnego ograniczenia $f_{i}(\hat{x})<0$ nie są ważne. Tym samym można stwierdzić, że warunek dopełniającej elastyczności jest spełniony.

Niech teraz $\hat{x}\in loc\,min\,f_{0}(x)$ i $rank\,\{ \partial f_{i}(\hat{x})/\partial x_{j}: i=\overline{m'+1,m},\,j=\overline{1,n}\}=$
$=m-m'$. Wtedy dla $k=\overline{1,m-m'}$ zbiory

$$A_{k}:=\{y\in\mathbb{R}^{n}: <grad\,f_{i}(\hat{x}),y>\,<0\,,\,i=\overline{k,m'}\,,\,$$

$$<grad\,f_{j}(\hat{x}),y>=0\,,\,j=\overline{m'+1,m}\}$$ (8.15)

dla $k=\overline{0,m'}$ spełniają relacje:

$$A_{0}\subset A_{1}\subset\ldots\subset A_{m'}$$ (8.16)

oraz $A_{0}=\varnothing$. Rzeczywiście, gdyby $A_{0}\ne\varnothing$, to istniałby wektor $\xi\in\mathbb{R}^{n}$, taki, że

$$<grad\,f_{i}(\hat{x}),\xi>=\beta_{i}\,<0\:,\:i=\overline{0,m'}\,,$$ (8.17)

gdzie $<grad\,f_{j}(\hat{x}),\xi>=0$ dla $j=\overline{m'+1,m}$. Ponieważ odwzorowanie
$\{grad\,f_{i}(\hat{x}):i=\overline{m'+1,m}\}:\mathbb{R}^{n}\longrightarrow\mathbb{R}^{m-m'}$ jest epimorfizmem, to dla dowolnych $\lambda\in\mathbb{R}\,,\vert\lambda <\epsilon\vert$ istnieje odwzorowanie $\tau :\mathbb{R}^{1}\longrightarrow\mathbb{R}^{n}$, takie, że

$$f_{i}(\hat{x}+\lambda\xi+\tau(\lambda))=0\;,\;i=\overline{m'+1,m}\,,$$ (8.18)

gdzie

$$\Vert\tau(\lambda)\Vert\leqslant c \Vert(f_{i}(\hat{x}+\lambda\xi)-f_{i}(\hat{x}):i=\overline{m'+1,m})\Vert=$$

$$=o(\lambda)\longrightarrow 0\;,\; \vert\lambda\vert\longrightarrow 0\;,\;i=\overline{0,m'}.$$ (8.19)

Na mocy () otrzymujemy, że

$$f_{i}(\hat{x}+\lambda\xi+\tau(\lambda))=f_{i}(\hat{x})+\lambda<grad\,f_{i}(\hat{x},\xi)>+o(\lambda)=$$

$$=\lambda\beta_{i}+o(\lambda)<0\;przy\;\lambda\longrightarrow0^{+}\,,\,i=\overline{0,m'}.$$ (8.20)

Nierówność () znaczy, że przy $\lambda>0$, wystarczająco mały element
$\hat{x}+\lambda\xi+\tau(\lambda)$ jest dopuszczalny dla problemu (), co przeczy temu, że $\hat{x}\in\underset{x\in\mathbb{R}^n}{loc\,min}\,f_{0}(x)$.

Dalej jest prawie oczywistym, że warunek stacjonarności funkcji Lagrange'a jest spełniony przy warunku $A_{m'}=\varnothing$. W przeciwnym przypadku
$\exists k\in \{\overline{0,m'-1}\}:A_{k}=\varnothing$ i $A_{k+1}\ne\varnothing$. Wtedy tylko $\xi\equiv 0$ jest rozwiązaniem problemu

$$\inf_{\xi\in\mathbb{R}^{n}}<grad\,f_{k}(\hat{x}),\xi>\,-\,?\;,\;gdy\qquad$$

$$<grad\,f_{j}(\hat{x}),\xi>\,\leqslant 0\,,\,dla\,j=\overline{k+1,m'}\,,$$ (8.21)

$$<grad\,f_{i}(\hat{x}),\xi>=0\,,\,dla\,i=\overline{m'+1,m}.$$

Rzeczywiście, niech $\overline{\xi}\ne 0$ rozwiązuje (). Wtedy

$$<grad\,f_{j}(\hat{x}),\overline{\xi}>\leqslant 0\,,\,dla\,j=\overline{k+1,m'}\,,$$

$$<grad\,f_{i}(\hat{x}),\overline{\xi}>= 0\,,\,dla\,i=\overline{m'+1,m}\,,$$ (8.22)

$$<grad\,f_{k}(\hat{x}),\overline{\xi}>\,<0.\qquad\qquad$$

Niech teraz element $\eta\in A_{k+1}\ne\varnothing$, tj.

$$<grad\,f_{i}(\hat{x}),\eta>\,<0\,,\,dla\,i=\overline{k+1,m'}\,,$$

$$<grad\,f_{j}(\hat{x}),\eta>\,=0\,,\,dla\,j=\overline{m'+1,m}.$$

Wtedy dla $\epsilon >0$ wystarczająco małego element $\overline{\xi}+\epsilon\eta\in A_{k}$, co przeczy założeniu, że $A_{k}=\varnothing$.

Dla zakończenia dowodu zastosujmy do problemu () twierdzenie Kuhna-Tuckera z warunkiem Slatera, ponieważ $A_{k+1}\ne\varnothing$. Na mocy tego twierdzenia można znaleźć takie nieujemne liczby $\lambda_{k}=1,\lambda_{k+1},\ldots, \lambda_{m'}$, że dla funkcji Lagrange'a problemu ()

$$\widetilde{\mathcal{L}}_{\lambda}(\xi):=\sum_{i=1}^{m'}\lambda_{i}<grad\,f_{i}(\hat{x}),\xi>$$ (8.23)

w punkcie $\overline{\xi}=0$ spełniony jest warunek minimum, tj.

$$\min \widetilde{\mathcal{L}}_{\lambda}(\xi)=\widetilde{\mathcal{L}}_{\lambda}(\overline{\xi})=0.$$ (8.24)

Ostatnia równość () daje dla wszystkich $\xi\in ker\{grad\,f_{j}(\hat{x}): j=\overline{m'+1,m}\}$

$$\widetilde{\mathcal{L}}_{\lambda}(\xi):=\sum_{i=1}^{m'}\lambda_{i}<grad\,f_{i}(\hat{x}),\xi> =0\,,$$

$$tj.\quad \sum_{i=1}^{m'}\lambda_{i}grad\,f_{i}(\hat{x})\in(ker\, grad\, f(\hat{x}) )^{\perp}. \quad$$ (8.25)

To znaczy, że istnieją liczby $\lambda_{s}\in\mathbb{R}^{n}$, $s=\overline{m'+1,m}$, takie, że

$$\sum_{i=k}^{m'}\lambda_{i}grad\,f_{i}(\hat{x})+\sum_{s=m'+1}^{m}\lambda_{s}grad\,f_{s} (\hat{x})=0.$$ (8.26)

Ale równość () jest dokładnie warunkiem stacjonarności funkcji Lagrange'a $\mathcal{L}_{\lambda}(x)$, $x\in \mathbb{R}^{n}$, $\lambda\in\mathbb{R}^{m}$, przy założeniu $\lambda_{0}=\lambda_{1}=\ldots=\lambda_{k-1}=0$, co kończy dowód. $\rhd$

8.4   Uwaga. Z twierdzenia wnioskujemy, że przy spełnieniu warunku $Range\{ grad\,f_{j}(\hat{x}): j=\overline{m'+1,m}\}=\mathbb{R}^{m}$ (tj. odwzorowanie $\{grad\, f_{j}:\mathbb{R}^{n}\longrightarrow\mathbb{R}:$
$j=\overline{m'+1,m}\}$ jest regularne w punkcie $\hat{x}\in\mathbb{R}^{n}$) oraz istnieje element
$h\in ker\{grad\,f_{j}(\hat{x}): j=\overline{m'+1,m}\}$, dla którego $<grad\,f_{j}(\hat{x}),h>\,<0,\,j=\overline{1,m'}$ (analogia warunku Slatera!), wtedy $\lambda_{0}\ne 0$, i można wziąć $\lambda_{0}=1$.

Twierdzenie było bazowane na twierdzeniu Kuhna-Tuckera, które formułuje-my i dowodzimy poniżej.

8.5   Problem programowania wypukłego:

$$\inf_{x\in A} f_{0}(x)\,-\,?\,,\,f_{i}(x)\leqslant 0\,,\,i=\overline{1,m}\,,$$ (8.27)

gdzie $f_{i}:\mathbf{X}\longrightarrow\overline{\mathbb{R}}\,,\,i=\overline{0,m}$, są wypukłe na $A\subset\mathbf{X}$.

8.6   Lemat. Niech $\mathbf{X}$ będzie przestrzenią unormowaną. Wtedy minimum lokalne problemu () jest minimum globalnym.

8.7   Twierdzenie (Kuhna-Tuckera). Niech $\mathbf{X}$ będzie przestrzenią liniową, $f_{i}:\mathbf{X}\longrightarrow\mathbb{R}\,,\,i=\overline{1,m}$, będą funkcjami wypukłymi na $\mathbf{X}$, a $A\subset\mathbf{X}$ - podzbiorem wypukłym. Wtedy:

i)

Jeśli $\hat{x}\in\mathbf{X}$ jest rozwiązaniem problemu programowania wypukłego, to można znaleźć niezerowy wektor mnożników Lagrange'a $\lambda=(\lambda_{0}, \lambda_{1}\ldots,\lambda_{m})$, taki, że dla funkcji Lagrange'a ) $\mathcal{L}_{\lambda}(x):= \sum_{i=0}^{m}\lambda_{i}f_{i}(x)$ zachodzą:

a)

zasada minimum dla $\mathcal{L}_{\lambda}(x)$

$$\min_{x\in A} \mathcal{L}_{\lambda}(x)=\mathcal{L}_{\lambda}(\hat{x})\,; \qquad$$ (8.28)

b)

wrunek dopełniającej elastyczności

$$\lambda_{i}f_{i}(x)=0\;,\;i=\overline{1,m}\,;\qquad$$

c)

warunek nieujemności : $\lambda_{i}\geqslant 0\,,\,i=\overline{0,m}$.

ii)

Jeśli $\lambda_{0}\ne 0$, to warunki a)-c) są wystrczające, żeby $\hat{x}\in A$ było rozwiązaniem.

iii)

Dla tego, żeby $\lambda_{0}\ne 0$ wystarczy wypełnienie warunku Statera, tj. istnienia takiego punktu $\overline{x}\in A$, dla którego $f_{i}(\overline{x})<0\,,\,i= \overline{1,m}$.

$\lhd$ Niech $\hat{x}\in A$ jest rozwiązaniem (). Załóżmy także, że $f_{0}(\hat{x})=0$. Zdefiniujmy

$$B:=\{b\in\mathbb{R}^{m+1}: \exists x\in A\,,\,f_{i}(x)\leqslant b_{i}\,,\,i=\overline{0,m}\}.$$ (8.29)

a) Zbiór $B$ jest oczywiście niepusty i wypukły. Oprócz tego $\mathbb{R}_{+}^{m+1} \subset B$ (przy $x=\hat{x}\in A$)! Zdefiniujmy zbiór $C:=\{c=(c_{0},0,\ldots,0) \in\mathbb{R}^{m+1}:c_{0}<0\}$.
b) Zbiór $C$ też jest niepusty i wypukły oraz $C\cap B=\varnothing$, ponieważ $f_{0} (x)\geqslant 0$,
$f_{0}(\hat{x})=0\,,\,x,\hat{x}\in A$. Na mocy twierdzenia o oddzielaniu zbiorów wypukłych istnieje wektor $\lambda\in\mathbb{R}^{m+1}$, taki, że

$$\inf_{b\in B}<\lambda,b>\,\geqslant\sup_{c\in C}<\lambda,c>.\qquad$$ (8.30)

Ponieważ $0\in B$, to $0\geqslant\sup_{c\in C}<\lambda,c>=\sup_{c\in C}\lambda_{0} c_{0}$. Stąd mamy $\lambda_{0}\geqslant 0$
i $\sup_{c\in C}\lambda_{0}c_{0}=0$. Nirówność () może być teraz przepisana jako

$$\sum_{i=0}^{m}\lambda_{i}b_{i}\geqslant 0\;,\;b\in B.\qquad$$ (8.31)

c) Ponieważ $\mathbb{R}^{m+1}_{+}\subset B$, z () natychmiast otrzymujemy, że $\lambda_{i}\geqslant 0\,,\,i=\overline{0,m}$.
d) Sprawdzimy teraz, że zachodzi warunek dopełniającej elastyczności
$\lambda_{i}f_{i}(x)=0\;,\;i=\overline{1,m}$.
Weźmy $x\in A$; wtedy $(f_{0}(x),f_{1}(x),\ldots,f_{m}(x))\in B$. Podstawiając ten wektor do () otrzymamy

$$\sum_{i=0}^{m}\lambda_{i}f_{i}(x)\equiv\mathcal{L}_{\lambda}(x)\geqslant 0.$$

Ponieważ $f_{0}(\hat{x})=0$, z warunku $\lambda_{i}f_{i}(\hat{x})=0\,,\,i=\overline{1,m}$, dla $x\in A$ mamy:

$$\mathcal{L}_{\lambda}(x)\geqslant 0=\sum_{i=0}^{m}\lambda_{i}f_{i}(\hat{x})=\mathcal{L} _{\lambda}(\hat{x})\,,$$

co udawadnia i).
e) Żeby udowodnić ii), połóżmy $\lambda_{0}\ne 0$, tj. $\lambda_{0}=1$. Wtedy dla dowolnego dopuszczalnego $x\in A$ otrzymujemy przy $(\lambda_{i}\geq 0, \, i=\overline{1,m})$

$$f_{0}(x)\geq f_{0}(x)+ \sum_{i=1}^{m}\lambda_{i}f_{i}(x)\overset... ...t{x}):=f_{0}(\hat{x})+ \sum_{i=1}^{m}\lambda_{i}f_{i}(\hat{x})=f_{0}(\hat{x}),$$ (8.32)

tj. $\hat{x}\in A$ jest rozwiązaniem ().

Dla dowodu $iii)$ załóżmy, że zachodzi warunek Statera, oraz $\lambda_{0}=0$. Wtedy otrzymujemy, że dla $\overline{x}\in A$

$$\mathcal{L}_{\lambda}(\overline{x})=\sum_{i=1}^{m}\lambda_{i}f_{i}(\overline{x})<0= \mathcal{L}_{\lambda}(\hat{x})$$

co jest sprzeczne z warunkiem $\mathcal{L}_{\lambda}(\overline{x}) \geq \mathcal{L}_{\lambda}(\hat{x})$, co kończy dowód $\rhd$