chapters/done.tex - dev - ozzzernova/ConicApproximationInLinearProgramming

chapters/done.tex
38 строк8 KB
ozzzernova
intro
19 дек 2024, 15:49
19 дек 2024, 15:49b65c09f
\newpage
\begin{center}
  \textbf{\large ПРОДЕЛАННАЯ РАБОТА ПО НИР НА ТЕМУ КОНИЧЕСКИЕ АППРОКСИМАЦИИ ЛИНЕЙНЫХ ПРОГРАММ}
\end{center}
\refstepcounter{chapter}
\addcontentsline{toc}{chapter}{ПРОДЕЛАННАЯ РАБОТА ПО НИР НА ТЕМУ КОНИЧЕСКИЕ АППРОКСИМАЦИИ ЛИНЕЙНЫХ ПРОГРАММ}

Методы оптимизации — это математические подходы, направленные на нахождение оптимальных решений для различных задач с ограничениями. Оптимизация охватывает широкий спектр дисциплин, включая экономику, инженерию, финансы, физику и другие области, где требуется максимизировать или минимизировать некоторую цель при соблюдении определённых условий.

Одним из наиболее распространённых и важных классов задач оптимизации является линейное программирование. Линейное программирование используется для решения задач, где целевая функция и ограничения являются линейными. Одним из самых известных и широко используемых алгоритмов для решения задач линейного программирования является симплекс-метод, разработанный Джоржем Данцигом. Несмотря на свою теоретическую экспоненциальную сложность, он работает очень быстро на практике для большинства реальных задач. Кроме того, с развитием вычислительных методов, возникли и другие подходы к решению линейных задач, такие как методы внутренней точки, которые в теории имеют полиномиальную сложность и могут быть более эффективными в некоторых случаях.

Несмотря на то, что основополагающие методы линейного программирования были разработаны десятилетия назад, они обладают широким спектром применения и постоянным совершенствованием алгоритмов, так как многие ограничения в прикладных задач можно выразить через алгебраические понятия сравнительно простого вида. Их использование можно встретить в машинном обучении, экономике, задачах транспорта и логистики. Тем не менее, эти алгоритмы все еще являются вычислительно сложными, к тому же машинная вычислительная точность также воздействует на нахождение решения. Эти и другие факторы способствуют постоянному развитию алгоритмов в целях повышения точности решений, а также улучшения времени работы, что позволит усовершенствовать системы, которые их используют.

Методы первого типа, в частности, метод внутренней точки Нестерова-Тодда для самосогласованных барьеров решают задачу за полиномиальное от точности время $\mathcal{O} (n \log\frac{1}{\epsilon}) $, однако, как можно показать, при реализации на машинах с относительной точностью представления чисел $ \epsilon_M $ сходятся к минимуму целевой функции с точностью $ \sqrt{\epsilon_M} $ , что недопустимо для некоторых практических задач, например банковского планирования.

С другой стороны, симплекс-метод лишён проблем с точностью по аргументу, так как его траектория проходит только по вершинам допустимого полиэдра. Однако, как известно, симплекс-метод тратит в худшем случае экспоненциальное время для поиска ответа, причём на практике метод внутренней точки справляется значительно быстрее и является более предпочтительным.

Таким образом, предполагается проверить гипотезу о нахождении решения конической программы с помощью итерации метода внутренней точки, на некоторых шагах которого аналитически решается вспомогательная задача минимизации на эллипсоидальном конусе, далее аппроксимируя найденные решения на исходный конус. В качестве основы будем использовать классическую задачу линейного программирования с ограничениями на конус

\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_+ $.

Задача линейного программирования была впервые предложена Дж. Данцигом и набрала популярность благодаря простоте и выразительности.
На практике, помимо упомянутых симплекс-алгоритма и методов внутренней точки, существует и полиномиальный по времени точный алгоритм эллипсоидов, однако степень полинома и константа являются недопустимыми для большинства практических приложений.
Другим достоинством метода внутренней точки является его общность. Этот метод позволяет решить задачу оптимизации для произвольной выпуклой целевой функции на произвольном выпуклом конусе (заметим, что постановка задачи использует линейную целевую функцию и положительный ортант в качестве конуса), если для неё можно придумать барьерную функцию. В данной работе упор будет на использование алгоритма Нестерова-Тодда для метода следования прямо-двойственному пути и изучение возможности его улучшения с помощью аппроксимирующих конусов.