Seminar4.tex

\documentclass[12pt]{beamer}
\usepackage{../latex-sty/mypres}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage[T2A]{fontenc}


\expandafter\def\expandafter\insertshorttitle\expandafter{%
  \insertshorttitle\hfill%
  \insertframenumber\,/\,\inserttotalframenumber}
\title[Семинар 4]{Методы оптимизации. \\
 Семинар 4. Сопряжённые множества. Лемма Фаркаша.}
\author{Александр Катруца}
\institute{Московский физико-технический институт,\\
Факультет Управления и Прикладной Математики} 
\date{\today}

\begin{document}
\begin{frame}
\maketitle
\end{frame}

\begin{frame}{Напоминание}
\begin{itemize}
\item Внутренность и относительная внутренность выпуклого множества
\item Проекция точки на множество
\item Отделимость выпуклых множеств
\item Опорная гиперплоскость
\end{itemize}
\end{frame}

\begin{frame}{Сопряжённое множество}
\begin{block}{Сопряжённое множество}
Сопряжённым (двойственным) к множеству $X \subseteq \bbR^n$ называют такое множество $X^*$, что
\vspace{-4mm}
\[
X^* = \{ \bp \in \bbR^n | \langle \bp, \bx \rangle \geq -1, \; \forall \bx \in X \}.
\]
\end{block}

\begin{block}{Сопряжённый конус}
Если $X \subseteq \bbR^n$~--- конус, тогда
\vspace{-4mm} 
\[
X^* = \{ \bp \in \bbR^n | \langle \bp, \bx \rangle \geq 0, \; \forall \bx \in X \}.
\]
\end{block}

\begin{block}{Сопряжённое подпространство}
Если $X$~--- линейное подпространство в $\bbR^n$, тогда 
\vspace{-4mm} 
\[
X^* = \{ \bp \in \bbR^n | \langle \bp, \bx \rangle = 0, \; \forall \bx \in X \}.
\]
\end{block}
\end{frame}

\begin{frame}{Факты о сопряжённых множествах}
\begin{theorem}
Пусть $X$~--- произвольное множество в $\bbR^n$. Тогда
\vspace{-4mm}
\[
X^{**} = \overline{\text{conv }(X \cup \{0\})}.
\] 
\end{theorem}

\begin{theorem}
Пусть $X$~--- замкнутое выпуклое множество, включающее~0. Тогда $X^{**} = X$.
\end{theorem}

\begin{theorem}
Пусть $X_1 \subset X_2$, тогда $X^*_2 \subset X^*_1$.
\end{theorem}
\end{frame}

\begin{frame}{Примеры}
Найти сопряжённые к следующим множествам:
\begin{enumerate}
\item Неотрицательный октант: $\bbR^n_+$
\item Конус положительных полуопределённых матриц: $\bS^n_+$
\item $\{ (x_1, x_2) | |x_1| \leq x_2 \}$
\item $\{ \bx \in \bbR^n | \| x \|_2 \leq r \}$
\item $\{ (\bx, t) \in \bbR^{n+1} | \| x \| \leq t \}$
\end{enumerate}
\end{frame}

\begin{frame}{Лемма Фаркаша}
\scriptsize
\begin{lemma}[Фаркаш]
Пусть $\bA \in \bbR^{m \times n}$ и $\mathbf{b} \in \bbR^m$. Тогда имеет решение одна и только одна из следующих двух систем:
\vspace{-4mm}
\begin{equation*}
\begin{split}
1)& \; \bA\bx = \mathbf{b}, \; \bx \geq 0\\
2)& \; \bp^{\T}\bA \geq 0, \; \langle \bp, \mathbf{b} \rangle < 0
\end{split}
\end{equation*}
\end{lemma}

\begin{block}{Важное следствие}
Пусть $\bA \in \bbR^{m \times n}$ и $\mathbf{b} \in \bbR^m$. Тогда имеет решение одна и только одна из следующих двух систем:
\vspace{-4mm}
\begin{equation*}
\begin{split}
1)& \; \bA\bx \leq \mathbf{b}\\
2)& \; \bp^{\T}\bA = 0, \; \langle \bp, \mathbf{b} \rangle < 0, \; \bp \geq 0
\end{split}
\end{equation*}
\end{block}

\begin{block}{Применение}
Если в задаче линейного программирования на минимум допустимое множество непусто и целевая функция ограничена на нём снизу, то задача имеет решение.
\end{block}

\end{frame}

\begin{frame}{Геометрическая интерпретация}
\begin{block}{Геометрия леммы Фаркаша}
$\bA\bx = \mathbf{b}$ при $\bx \geq 0$ означает, что $\mathbf{b}$ лежит в конусе, натянутым на столбцы матрицы $\bA$

$\bp^{\T}\bA \geq 0, \; \langle \bp, \mathbf{b} \rangle < 0$ означает, что существует разделяющая гиперплоскость между вектором $\mathbf{b}$ и конусом из столбцов матрицы $\bA$.
\end{block}
\end{frame}

\begin{frame}{Резюме}
\begin{itemize}
\item Сопряжённые множества
\item Свойства сопряжённых множеств
\item Лемма Фаркаша
\end{itemize}

\end{frame}

\end{document}