chapters/chapter_1.tex - dev - ozzzernova/ConicApproximationInLinearProgramming

chapters/chapter_1.tex
46 строк4 KB
ozzzernova
presentation
19 дек 2024, 13:52
19 дек 2024, 13:52dc53297
\newpage
\begin{center}
  \textbf{\large 1. ПОСТАНОВКА ЗАДАЧИ И АНАЛИТИКА}
\end{center}
\refstepcounter{chapter}
\addcontentsline{toc}{chapter}{1. ПОСТАНОВКА ЗАДАЧИ И АНАЛИТИКА}


\section{Конические программы}

Рассмотрим задачу конического программирования
\begin{equation}
  \min_{x \in K} \langle c, x \rangle : \ Ax = b
\label{eq_classic}
\end{equation}
и двойственную к ней задачу
\begin{equation}
  \max_{s \in K^*, y} \langle b, y \rangle : \ s+A^Ty = c
\label{eq_classic_dual}
\end{equation}
Здесь $ K \subset \mathbb{R}^n $ -- регулярный конус, а

$$
K^* = \{ s \in \mathbb{R}^n | \langle s, x \rangle \geq 0 \ \forall x \in K \}
$$
двойственный к $K$ конус.

Для простоты будем рассматривать случай положительный ортант, то есть $ K = K^* = \mathbb{R}^n_+ $.

Пусть $v^*$ -- оптимальное значение задачи ~\ref{eq_classic}. Любая допустимая для ~\ref{eq_classic} дает верхнюю оценку $ \langle c, x \rangle $ на $ v^* $. С другой стороны, любая допустимая для задачи ~\ref{eq_classic_dual} пара $ \left( s, y \right) $ дает нижнюю оценку $ \langle b, y \rangle $ на $ v^* $. Цель -- сравнить эффективность разных способов генерации таких оценок.

Далее на матрицу и допустимое решение также будут наложены дополнительные ограничения.

\section{Обзор литературы}
 
Задача линейного программирования была впервые предложена Дж. Данцигом в ~\cite{dantzig2002} и набрала популярность благодаря простоте и выразительности.
На практике, помимо упомянутых симплекс-алгоритма и методов внутренней точки, существует и полиномиальный по времени точный алгоритм эллипсоидов ~\cite{karmarkar1984}, однако степень полинома и константа являются недопустимыми для большинства практических приложений.
Другим достоинством метода внутренней точки является его общность. Этот метод позволяет решить задачу оптимизации для произвольной выпуклой целевой функции на произвольном выпуклом конусе ~\cite{nesterov1994} (заметим, что постановка задачи использует линейную целевую функцию и положительный ортант в качестве конуса), если для неё можно придумать барьерную функцию.
Впервые метод следования прямо-двойственному центральному пути был предложен в ~\cite{renegar1988} и позднее развит в ~\cite{nesterov1998}.

В данной работе упор будет на использование алгоритма Нестерова-Тодда для метода следования прямо-двойственному пути.


\section{Барьеры и эллипсоиды Дикина}

\section{Аппроксимирующие задачи}