Programowanie wypukłe. Wstęp.

Niech $\mathbf{X}$ jest przestrzenią liniową, a f - zadaną funkcją

$$f:X\longrightarrow \overline {\mathbb{R}}=\{\mathbb{R}\cup\{\pm\infty\}\}.$$ (7.1)

Z każdą taką funkcją można skojarzyć takie dwa zbiory:
$dom f:=\{x\in X: f(x)<\infty\}$ - tzw. zbiór efektywny ,
$epi f:=\{(\alpha,x)\in\mathbb{R}\times X: f(x)\le\alpha, x\in dom f\}$ - nadwykres.
Funkcja $f:X\longrightarrow\mathbb{R}$ nazywa się własną, jeżeli
$f(x)>- \infty$ dla $\forall x\in X \Leftrightarrow f:X\longrightarrow\mathbb{R}$ przy $dom f \ne \varnothing$.
Oczywiście, funkcja $f:X\longrightarrow\mathbb{R}$ jest wypukła wtedy i tylko wtedy, kiedy

$$f(\alpha x+(1-\alpha)y) \leqslant \alpha f(x)+(1-\alpha) f(y)$$ (7.2)

dla $\forall\: x, y \in X, \alpha\in[0,1]$
Nierówność () nazywa się nierównością Jensena.

7.1   Twierdzenie Minkowskiego () Zwarty zbiór w $\mathbb{R}^{n}$ jest wypukłą powłoką swoich punktów skrajnych.

Mamy działania nad zbiorami:

1)

suma : $A_{1} + A_{2}:=\{x \in X : x_{1}+x_{2}=x\,,\, x_{1}\in A_{1}\,,\, x_{2}\in A_{2} \}.$

2)

konwolucja : $A_{1}\,\blacklozenge\, A_{2}:=\bigcup\{\alpha A_{1}\bigcap (1-\alpha)A_{2}\, :\, \alpha\in[0,1]\}.$

3)

przecięcie : $A_{1}\bigcap A_{2}=\{x\in A_{1} \:i\: x\in A_{2}\}$.

4)

wypukła powłoka lub łączność wypukła nad $A_{1}$ i $A_{2}$ :
$A_{1}\, conv\bigcup A_{2}:=conv(A_{1}\bigcup A_{2})$.

7.2   Definicja Transformacją lub sprzężeniem Legendre'a-Young'a-Fenchela funkcji $f:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ nazywamy odwzorowanie:

$$f^{\star}(y):=\sup_{x\in\mathbb{R}^n}(<x,y>-f(x))$$ (7.3)

gdzie funkcja $f:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ jest dowolna.

Z definicji widać, że $f^{\star}:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ jest górną obwiednią rodziny funkcji afinicznych, tj. $f^{\star}:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ jest wypukła.

Odpowiednio, funkcja $f^{\star\star}:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ , gdzie

$$f^{\star\star}(x):=\sup_{y\in\mathbb{R}^n}(<x,y>-f^{\star}(y))$$ (7.4)

nazywa się drugim skojarzeniem lub sprzężeniem L-Y-F do funkcji $f:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$.

Z samej definicji oraz () otrzymujemy, że:

$$<x,y>\leqslant f(x)+f^{\star}(y) \quad dla\; x\,,\,y\in\mathbb{R}^n.$$ (7.5)

7.3   Przykład. Weźmy $f_{\alpha}(x):=<\xi,x>-\alpha$, gdzie $\xi\in\mathbb{R}^n$ oraz $\alpha\in\mathbb{R}^1$ są zadane. Wtedy, oczywiście, na mocy () otrzymujemy, że:
$f^{\star}_{\alpha}(y\vert\xi)=\alpha$, jeśli $y=\xi$ i $f^{\star}_{\alpha}(y\vert\xi)=+\infty$, jeśli $y\ne\xi$.
Łatwo wykazać, że $f^{\star\star}_{\alpha}(y\vert\xi)=<x,\xi>-\alpha$.

Niech teraz $A\subset\mathbb{R}^n$ jest zbiorem niepustym.

7.4   Definicja. Polarą zbioru $A\subset\mathbb{R}^n$ nazywamy zbiór:

$$A^0:=\{y\in\mathbb{R}^n: <x,y>\,\leqslant 1\: \forall x\in A\}$$ (7.6)

Zbiór $A^{00}:=\{x\in\mathbb{R}^n: <y,x>\,\leqslant 1\: \forall x\in A^0\}$ nazywamy bipolarą zbioru $A$.

Z samej definicji widzimy, że $A^0$ jest przecięciem rodziny semiprzestrzeni zawierających zero, tj. wypukły zbiór z zerem.

7.5   Przykłady. Polarą odcinka $[0,x]\subset\mathbb{R}^n$ jest półpłaszczyzna
$\Pi_{x}:=\{y\in\mathbb{R}^n:<x,y>\,\leqslant1\}$, i odwrotnie $\Pi_{x}^0=[0,x]$. Polarą kuli
$B_{r}(0):=\{x\in\mathbb{R}^n:\vert\vert x\vert\vert\leqslant r\}$ jest kula $B_{1/r}(0).$

Niech $K\subset\mathbb{R}^n$ jest stożkiem w $\mathbb{R}^n$.

7.6   Definicja. Stożkiem sprzężonym do stoźka $K\subset\mathbb{R}^n$ nazywamy zbiór:

$$K^{\star}:=\{y\in\mathbb{R}^n:<x,y>\geqslant\,0\:\forall\, x\in K\}$$ (7.7)

Odpowiednio, stożek

$$K^{\star\star}:=\{x\in\mathbb{R}^n:<x,y>\geqslant\,0\:\forall\, y\in K^{\star}\}$$ (7.8)

nazywamy drugim sprzężeniem do stożka $K\subset\mathbb{R}^n$.

Na mocy definicji (7.7) widzimy od razu, że $K^{\star}$ jest zbiorem wypukłym, domkniętym. Poza tym mamy następującą właściwość:

$$K^{\star}=-K^0.$$ (7.9)

7.7   Definicja. Subpochodną funkcji subliniowej $p:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ nazywamy zbiór:

$$\partial p:=\{y:<x,y>\,\leqslant\,p(x)\:\forall\, x\}.$$ (7.10)

Norma $\vert\vert x\vert\vert$ jest, oczywiście, funkcją subliniową. Korzystając z () otzrymujemy, że:

$$\partial \vert\vert x\vert\vert=\{x\in\mathbb{R}^n:\vert\vert x\vert\vert<1\}=B_{1}(0).$$ (7.11)

7.8   Definicja. Subpochodną funkcji (wypukłej własnej) w punkcie $\hat{x}\in\mathbb{R}^n$ nazywamy zbiór:

$$\partial f(\hat{x}):=\{y\in\mathbb{R}^n:f(x)-f(\hat{x})\geqslant<y,x-\hat{x}>\:\forall x\in\mathbb{R}^n\}.$$ (7.12)

Od razu widać, że $\partial p$ oraz $\partial f(\hat{x})$ są zbiorami wypukłymi w $\mathbb{R}^n$. Są one również domknięte.

Niech teraz $A\subset\mathbb{R}^n$ jest niepustym (!) podzbiorem $\mathbb{R}^n$

7.9   Definicja. Funkcję

$$s_{A}(y):=\sup\{<x,y>:x\in A\}$$ (7.13)

nazywamy ,,oporną'' dla $A\subset\mathbb{R}^n$.

Oczywiście subpochodną funkcji liniowej $f(x):=<x,\xi>$ jest punkt $\xi\in\mathbb{R}^n$. Oporną funkcją elementu $\xi\in\mathbb{R}^n$ jest funkcja liniowa $s_{\xi}:= <x,\xi>,\:\forall x\in\mathbb{R}^n$.

7.10   Definicja. Funkcja

$$\delta_{A}(x):=\left\{ \begin{array}{ll} 0 & x \in A, \\ +\infty & x\notin A, \end{array} \right.$$ (7.14)

nazywa się indykatorem lub wskaźnikiem zbioru $A\subset\mathbb{R}^n$.

7.11   Przykład. Funkcją Minkowskiego kuli ${B_{\vert\vert x\vert\vert}}_{p}(0)$ w $l^n_{p}$ jest normą $\vert\vert x\vert\vert _{p}$ w $l_{p}$:

$$\mu_{{B}_{{\Vert x\Vert}_{p}}(0)}(x)={\Vert x\Vert}_{p}:=(\sum_{j=1}^{n}{\vert x_{j}\vert}^p)^{1/p}$$ (7.15)

gdzie $1\leqslant p<\infty$. Jeśli $p=\infty$

$$\mu_{{B}_{{\Vert x\Vert}_{\infty}}(0)}(x)=\max_{i=\overline{1,n}}\vert x_{i}\vert.$$ (7.16)

Przejdźmy teraz do własności dwoistości lub dualności obiektów wypukłych w $\mathbb{R}^n$.

7.12   Twierdzenie

a)

Funkcja $f:\mathbb{R}^{n}\longrightarrow \overline {\mathbb{R}}$ równa się swojemu drugiemu sprzężeniu $f^{\star\star}$ wg. L-Y-F wtedy i tylko wtedy, gdy ona jest wypukła i domknięta (tj. jej nadwykres jest zbiorem domkniętym i wypukłym).

b)

Niech $A$ jest niepustym zbiorem w $\mathbb{R}^n$. Wtedy $A=A^{00}$ wtedy i tylko wtedy, kiedy $A$ jest wypukłym, domkniętym zbiorem, zawierającym zero.

c)

Stożek $K\subset\mathbb{R}^n$ równa się $K^{\star\star}$ wtedy i tylko wtedy, kiedy jest stożkiem wypukłym i domkniętym.

d)

Niech $p:\mathbb{R}^{n}\longrightarrow \mathbb{R}$ jest funkcją jednorodną pierwszego stopnia z subpochodną $\partial p\ne\varnothing$. Żeby była spełniona równość $\delta_{\partial p}=p$, jest koniecznym i wystarczającym, żeby funkcja $p:\mathbb{R}^{n}\longrightarrow \mathbb{R}$ była subliniowa i domknięta.

e)

Niech $A\subset\mathbb{R}^n$ jest niepustym podzbiorem $\mathbb{R}^n$. Żeby zachodziła równość $\partial s_{A}=A$ jest koniecznym i wystarczającym, żeby zbiór $A\subset\mathbb{R}^n$ był domknięty i wypukły.

7.13   Uwaga. Twierdzenie (a) w często nazywa się twierdzeniem Fenchela - Moro.

$\vartriangleleft$ Dowód Twierdzenia (b). Na mocy definicji mamy, że:

$$A^{00}=\bigcap_{y\in A^{0}}\Pi_{y}\;,\;\Pi_{y}:=\{x\in\mathbb{R}^n\:<x,y>\leqslant 1\}.$$ (7.17)

Jeżeli $A=A^{00}$, to $A$ jest oczywiście zbiorem wypukłym, domkniętym i zawierającym zero.
W drugą stronę mamy: jeśli $x\in A$, $y\in A^{0}$, to z definicji wynika, że $<x,y> \leqslant 1$, tj. $A\subset A^{00}$. Załóżmy, że istnieje element $\hat{x}\in A^{00} \setminus A$. Wtedy, na mocy tego, że $A$ jest zbiorem domkniętym i wypukłym, z twierdzenia o oddzielaniu można znaleźć taki element $\hat{y}\in\mathbb{R}^n$, że

$$\sup_{x\in A} <x,\hat{y}>\leqslant 1\;\wedge\;<\hat{x},\hat{y}>\,>1.$$ (7.18)

Z tego, że $<x,\hat{y}>\leqslant 1$ dla wszystkich $x\in A$, z () otrzymujemy, że $\hat{y}\in A^{0}$. Z drugiej nierówności otrzymujemy także, że $<\hat{x},\hat{y}>\,>1$, co przeczy założeniu, że $<\hat{x},\hat{y}>\,\leqslant 1$, ponieważ $\hat{x}\in A_{00}$. $\rhd$

Następne twierdzenie ma szerokie zastosowania (podamy bez dowodu).

7.14   Twierdzenie o zwartości.

a)

Niech $A$ jest otwartym otoczeniem zera w $\mathbb{R}^n$. Wtedy jego polara jest zwarta.

b)

Niech $p:\mathbb{R}^{n}\longrightarrow \mathbb{R}$ jest ciągłą subliniową funkcją na $\mathbb{R}^{n}$. Wtedy jej subpochodna $\partial p$ jest zbiorem wypukłym i zwartym.

c)

Jeśli $p:\mathbb{R}^{n}\longrightarrow \mathbb{R}$ jest subliniową funkcją domkniętą, to $\partial p$ jest zbiorem domkniętym wypukłym.