На главную   ::   Содержание



Теорема Куна--Таккера (необходимые и достаточные условия оптимальности решения задачи выпуклого программирования)

Определение 1.   $ h\in \mathbb{R}^n$ называется направлением убывания функции $ f$ в точке $ x^\ast$, если $ \forall \alpha>0$ (малого) $ f(x^\ast+\alpha h)<f(x^\ast)$. Множество всех направлений убывания функции $ f$ в точке $ x^\ast$ обозначается $ U(x^\ast,f)$.

Определение 2.   $ h\in \mathbb{R}^n$ называется возможным направлением в точке $ x^\ast\in X$ относительно $ X$, если для любого малого $ \alpha>0$ точка $ x^\ast+\alpha h\in X$. Множество всех возможных направлений -- $ V(x^\ast,X)$.

Рассмотрим общую задачу оптимизации:

$\displaystyle f(x)\to\min,\quad x\in X.
$

Теорема 1. (Критерий оптимальности общей задачи оптимизации)   пусть $ x^\ast$ -- локальное решение задачи. Тогда $ U(x^\ast,f)\cap
V(x^\ast,X)=\varnothing$.

Теорема 2.   Пусть $ X$ -- выпуклое множество, $ f(x)$ определена на $ X$, дифференцируема в точке $ x^\ast\in X$. Тогда
  1. если $ x^\ast$ -- локальное решение, то $ \left<f'(x^\ast),x-x^\ast \right>\geq
0,\quad\forall  x\in X$;
  2. если $ f$ -- выпуклая на $ X$ и выполнено условие 1, то $ x^\ast$ -- глобальное решение.

Рассмотрим задачу математического программирования

\begin{displaymath}
\begin{array}{ll}
f(x)\to\min\\
g_i(x)\leq 0,& i=1,\dots,k\\
g_i(x)=0,&i=k+1,\dots,n\\
x\in P
\end{array}
\end{displaymath}

Пусть $ X=\{x\in P:  g_i(x)\leq 0, i=1,\dots,k, 
g_i(x)=0, i=k+1,\dots,n\}$ -- допустимое множество. Пусть $ Q=\{y\in\mathbb{R}^m:  y_i\geq 0,  i=1,\dots,k\}$. Введем функцию Лагранжа для задачи математического программирования:

$\displaystyle \mathcal L (x,y_0,y)=y_0f(x)+\sum_{i=1}^n y_i g_i(x),\quad
x\in\mathbb{R}_n, y_0\in \mathbb{R}, y\in Q.
$

Теорема 3. (Принцип Лагранжа)   Пусть $ P$ -- выпуклое, $ f,g_1,\dots,g_k$ -- определены на $ P$ и дифференцируемы в точке $ x^\ast$, $ g_{k+1},\dots,g_m$ -- непрерывно дифференцируемы в некоторой окрестности точки $ x^\ast$. Тогда если $ x^\ast$ -- локальное решение задачи, то существует $ y_0^\ast\geq 0, y^\ast\in
Q$, не равные нулю одновременно, такие что
  1. $ \left<\mathcal L_x (x^\ast,y_0^\ast,y^\ast),x-x^\ast\right>\geq 0,\quad \forall  x\in P$;
  2. $ y_i^\ast g_i(x^\ast)=0,\quad \forall  i=1,\dots,k$.

Теорема 4.   Пусть $ P$ -- выпуклое, $ f,g_1,\dots,g_k$ -- выпуклые на $ P$ и дифференцируемые в точке $ x^\ast$, $ g_{k+1},\dots,g_m$ -- линейные. Тогда если существует $ y^\ast\in Q$ такой, что условия 1 и 2 принципа Лагранжа выполнены при $ y_0^\ast=1$, то $ x^\ast$ является глобальным решением.

Теорема 5. (Условие регулярности в задаче математического программирования)   Пусть в задаче математического программирования множество $ P$ -- выпуклое, $ f$ -- дифференцируема в точке $ x^\ast$, $ g_1,\dots,g_k$ -- выпуклые на $ P$ и дифференцируемые в точке $ x^\ast$, $ g_{k+1},\dots,g_m$ -- линейные и пусть выполнено хоть одно из двух условий:
  1. $ k=m$ и $ \exists  \overline x\in P:  g_i(\overline x)<0,\quad
i=1,\dots,m$.
  2. $ P$ -- полиэдр, $ g_1,\dots,g_k$ -- линейны. Тогда если $ x^\ast$ -- локальное решение задачи математического программирования, то $ \exists  y^\ast\in Q$ такие, что условия 1 и 2 в теореме Лагранжа выполнены при $ y_0^\ast=1$.

Определение 3.   Задача математического программирования называется задачей выпуклого программирования, если целевая функция выпукла и допустимое множество задачи выпукло.

Теорема 6. (Куна--Таккера в дифференциальной форме)   Пусть в дополнение к условиям теоремы 5. $ f$ -- выпукла на $ P$. Тогда $ x^\ast$ является глобальным решением задачи выпуклого программирования $ \Leftrightarrow$ $ \exists  y^\ast\in Q$ такой, что условия 1 и 2 в теореме Лагранжа выполнены при $ y_0^\ast=1$.

Доказательство. Необходимость: теорема 5., достаточность теорема 4.. $ \blacksquare$

На главную   ::   Содержание