Optimizacijske metode

Definicija. Vrednosti $x_1, \dots, x_n, \lambda_1, \dots, \lambda_m$ ustrezajo Karush-Kuhn-Tuckerjevim (KKT) pogojem za problem vezanega ekstrema z neenačbami, če velja $$ \begin{align} L_{x_j} := {\partial L \over \partial x_j}(x_1, \dots, x_n, \lambda_1, \dots, \lambda_m) &= 0 & (1 \le j \le n) \\ \lambda_i g_i(x_1, \dots, x_n) &= 0 & (1 \le i \le m) \\ g_i(x_1, \dots, x_n) &\le 0 & (1 \le i \le m) \\ \lambda_i &\ge 0 & (1 \le i \le m) \end{align} $$

Ali so Karush-Kuhn-Tuckerjevi pogoji za $(x^\ast, \lambda^\ast)$ zadoščeni natanko tedaj, ko je $(x^\ast, \lambda^\ast)$ globalni ekstrem? V splošnem NE. Bo pa odgovor pritrdilen za konveksne optimizacijske probleme.

Primera.

1. $$ \begin{aligned} \min \ x^2 - y^2 \\[1ex] \text{p.p.} \quad x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\ x, y &\ge 0 \end{aligned} $$ Tak problem je neomejen - globalnega minimuma ni! Vseeno lahko najdemo točko, ki ustreza Karush-Kuhn-Tuckerjevim pogojem: $$ \begin{alignedat}{5} L(x, y, \lambda, \mu) &= x^2 - y^2 &&- \lambda x - \mu y \\ L_x &= 2x - \lambda &&= 0 & -\lambda x &= 0 &\qquad x &\ge 0 &\qquad \lambda &\ge 0 \\ L_y &= -2y - \mu &&= 0 & -\mu y &= 0 &\qquad y &\ge 0 &\qquad \mu &\ge 0 \\ x &= y = \lambda = \mu &&= 0 \end{alignedat} $$

2. $$ \begin{aligned} \min \ x \\[1ex] \text{p.p.} \quad x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\ 0 \le y &\le x^3 \end{aligned} $$ Globalni minimum je v točki $(x, y) = (0, 0)$:

   

   $$ \begin{alignedat}{5} L(x, y, \lambda, \mu) &= x - \lambda y +{} &\mu &(y - x^3) \\ L_x &= 1 - 3 \mu x^2 &&= 0 &\qquad -\lambda y &= 0 &\qquad y &\ge 0 &\qquad \lambda &\ge 0 \\ L_y &= -\lambda + \mu &&= 0 &\qquad \mu (y - x^3) &= 0 &\qquad y &\le x^3 &\qquad \mu &\ge 0 \\ \lambda &= \mu\ne 0 & y &= x = 0 & 1 &= 0 & \rightarrow\!&\!\leftarrow \end{alignedat} $$

Izrek. Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta konveksna množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ konveksne odvedljive funkcije. Če $(x^\ast, \lambda^\ast) \in \Omega \times \mathbb{R}^m$ zadošča Karush-Kuhn-Tuckerjevim pogojem, potem je $x^\ast$ globalni minimum funkcije $f|_D$, kjer je $D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}$ (tj., $x^\ast$ je optimalna rešitev ustreznega problema vezanih ekstremov z neenačbami).

Opomba. Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji zadostni za optimalnost rešitve.

Dokaz. Vzemimo poljuben $x \in D$. Zaradi konveksnosti (kriterij 1. odvoda) velja: $$ \begin{aligned} f(x) &\ge f(x^\ast) + (\nabla f(x^\ast))^\top (x - x^\ast) \\ \forall i \in \{1, 2, \dots, m\}: \ g_i(x) &\ge g_i(x^\ast) + (\nabla g_i(x^\ast))^\top (x - x^\ast) \qquad / \cdot \lambda_i^\ast \\ \hline f(x) \ge f(x) + \sum_{i=1}^m \lambda_i^\ast g_i(x) &\ge f(x^\ast) + \sum_{i=1}^m \lambda_i^\ast g_i(x^\ast) + \left(\nabla f(x^\ast) + \sum_{i=1}^m \lambda_i^\ast \nabla g_i(x^\ast)\right)^\top (x - x^\ast) \\ &= f(x^\ast) + (\nabla L(x^\ast, \lambda^\ast))^\top (x - x^\ast) = f(x^\ast) \\ \end{aligned} $$

Izrek. Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ funkcije, pri čemer je funkcija $f$ odvedljiva. Če je $x^\ast$ globalni minimum funkcije $f|_D$ za $D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}$ in velja vsaj eno od sledečega:

• funkcije $g_1, g_2, \dots, g_m$ so afine; ali
• množica $\Omega$ je konveksna, $\mathring{D} \ne \emptyset$ ter funkcije $f, g_1, g_2, \dots, g_m$ so konveksne; ali
• funkcije $g_1, g_2, \dots, g_m$ so odvedljive ter $(\nabla g_i(x^\ast))_{\!\!\!\!\!\substack{i = 1 \\ g_i(x^\ast) = 0}}^m$ je zaporedje linearno neodvisnih vektorjev,

potem obstaja tak $\lambda^\ast \in \mathbb{R}^m$, da $(x^\ast, \lambda^\ast)$ ustreza Karush-Kuhn-Tuckerjevim pogojem.

Dokaz izpustimo. V dokazu se uporabi Farkaseva lema.

Opomba. Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji potrebni za optimalnost rešitve.

Posledica. Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta konveksna množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ konveksne odvedljive funkcije, tako da velja $\mathring{D} \ne \emptyset$. Potem je $x^\ast \in \Omega$ globalni minimum problema vezanih ekstremov z neenačbami natanko tedaj, ko obstaja tak $\lambda^\ast \in \mathbb{R}^m$, da $(x^\ast, \lambda^\ast)$ ustreza Karush-Kuhn-Tuckerjevim pogojem.

Opomba. Takemu problemu rečemo konveksni problem oziroma problem konveksne optimizacije. Čim najdemo eno rešitev Karush-Kuhn-Tuckerjevih pogojev, smo našli optimalno rešitev takega problema (tj., globalni minimum).

Primer. $$ \begin{aligned} \min \ x \\[1ex] \text{p.p.} \quad x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\ 0 \le y &\le x^3 \end{aligned} $$ Globalni minimum je v točki $(x^\ast, y^\ast) = (0, 0)$, kjer pa Karush-Kuhn-Tuckerjevi pogoji niso izpolnjeni. Velja namreč: $$ \begin{aligned} g_1(x, y) &= -y & g_1(0, 0) &= 0 & \text{afina} \\ g_2(x, y) &= y - x^3 & g_2(0, 0) &= 0 & \text{ni afina} \\ H_{g_2}(x, y) &= \begin{bmatrix} -6x & 0 \\ 0 & 0 \end{bmatrix} \not\ge 0 & (\text{za } x &> 0) & \text{ni konveksna} \\ \nabla g_1(x, y) &= \begin{bmatrix} 0 \\ -1 \end{bmatrix} & \nabla g_2(x, y) &= \begin{bmatrix} -x^2 \\ 1 \end{bmatrix} \\ \nabla g_1(0, 0) &= \begin{bmatrix} 0 \\ -1 \end{bmatrix} & \nabla g_2(0, 0) &= \begin{bmatrix} 0 \\ 1 \end{bmatrix} & \text{nista linearno neodvisna} \end{aligned} $$

Trditev. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica, $f: K \to \mathbb{R}$ konveksna funkcija, ter $b \in \mathbb{R}$. Potem je množica $A = \{x \in K \mid f(x) \le b\}$ konveksna.

Dokaz. Vzemimo poljubne $x, y \in A$ ter $\lambda \in [0, 1]$. Potem velja $$ f((1 - \lambda) x + \lambda y) \le (1 - \lambda) f(x) + \lambda f(y) \le (1 - \lambda) b + \lambda b = b. $$ Velja torej $(1 - \lambda) x + \lambda y \in A$, zato je množica $A$ konveksna.

Opomba. Če je množica $\Omega$ konveksna in so funkcije $g_1, g_2, \dots, g_n: \Omega \to \mathbb{R}$ konveksne ter $b \in \mathbb{R}^n$, potem je množica $\{x \in \Omega \mid \forall i \in \{1, 2, \dots, n\}: g_i(x) \le b_n\}$ konveksna. Na primer, za $f(x, y) = x^2 + y^2$ imamo $H_f(x, y) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \ge 0$, torej je $f$ konveksna funkcija in je tako $\{(x, y) \in \mathbb{R}^2 \mid f(x, y) \le 4\}$ konveksna množica.

Primer (prvi del). $$ \begin{aligned} \min \ {1 \over x} + {2 \over y} \\[1ex] \text{p.p.} \quad x &> 0 \\ y &> 0 \\ x + y &\le 5 \\ 3x^2 + 2y^2 &\le 35 \end{aligned} $$

To je konveksni problem: $$ \begin{aligned} \Omega &= \{(x, y) \in \mathbb{R}^2 \mid x > 0, y > 0\} & \text{konveksna,} &\ \text{odprta} \\ f(x, y) &= {1 \over x} + {2 \over y} & H_f(x, y) &= \begin{bmatrix} 2x^{-3} & 0 \\ 0 & 4y^{-3} \end{bmatrix} \ge 0 \\ g_1(x, y) &= x + y - 5 && \text{afina} \\ g_2(x, y) &= 3x^2 + 2y^2 - 35 & H_{g_2}(x, y) &= \begin{bmatrix} 6 & 0 \\ 0 & 4 \end{bmatrix} \ge 0 \end{aligned} $$

$$ \begin{alignedat}{3} L(x, y, \lambda, \mu) &= {1 \over x} + {2 \over y} + \lambda (x + y &{} - 5) &+ \mu (3x^2 &{} + 2y^2 - 35) \qquad \\ \text{KKT:} \quad L_x &= -{1 \over x^2} + \lambda + 6 \mu x &&= 0 \\ L_y &= -{2 \over y^2} + \lambda + 4 \mu y &&= 0 \\ 0 &= \lambda (x + y - 5) & \lambda &\ge 0 & x + y - 5 &\le 0 \\ 0 &= \mu (3x^2 + 2y^2 - 35) & \mu &\ge 0 & 3x^2 + 2y^2 - 35 &\le 0 \end{alignedat} $$

1. $g_1(x, y) = x + y - 5 = 0$: $y = 5 - x$ $$ \begin{alignedat}{3} L(x, 5 - x, \lambda, \mu) &= {1 \over x} + {2 \over 5 - x} + \mu (5x^2 - 20x &&+ 15) \qquad \\ \text{KKT:} \quad L_x &= -{1 \over x^2} + \lambda + 6 \mu x &&= 0 \\ L_y &= -{2 \over (5 - x)^2} + \lambda + 4 \mu (5 - x) &&= 0 \\ 0 &= \mu (5x^2 - 20x + 15) && \lambda, \mu \ge 0 \qquad 5x^2 - 20x + 15 \le 0 \end{alignedat} $$

   1. $g_2(x, 5 - x) = 0$: $x = 2 \pm 1$, $y = 3 \mp 1$ $$ \begin{alignedat}{3} x = 1, y = 4: \\ L(1, 4, \lambda, \mu) &= 1 + {1 \over 2} &&= {3 \over 2} &\qquad \lambda, \mu &\ge 0 \\ \text{KKT:} \quad L_x &= -1 + \lambda + 6 \mu &&= 0 \\ L_y &= -{1 \over 8} + \lambda + 16 \mu &&= 0 \\ \mu &= -{7 \over 80} < 0 &&\rightarrow\!\leftarrow \\[2ex] x = 3, y = 2: \\ L(3, 2, \lambda, \mu) &= {1 \over 3} + 1 &&= {4 \over 3} &\qquad \lambda, \mu &\ge 0 \\ \text{KKT:} \quad L_x &= -{1 \over 9} + \lambda + 18 \mu &&= 0 \\ L_y &= -{1 \over 2} + \lambda + 8 \mu &&= 0 \\ \mu &= -{7 \over 180} < 0 &&\rightarrow\!\leftarrow \end{alignedat} $$