chapters/introduction.tex - dev - ozzzernova/ConicApproximationInLinearProgramming

chapters/introduction.tex
55 строк9 KB
ozzzernova
intro
19 дек 2024, 15:49
19 дек 2024, 15:49b65c09f
\newpage
\begin{center}
  \textbf{\large АННОТАЦИЯ}
\end{center}


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

К задачам исследования относятся:
\begin{enumerate}
  \item Изучить уже существующие алгоритмы нахождения оценок для решения задач такого типа.
  \item Развить идею улучшения оценки с использованием представленных методов и расширить способы решения подзадач на конус.
  \item Проверить гипотезу нахождения решения на конусе и улучшаемость оценки по сравнению с уже предложенными алгоритмами.
\end{enumerate}

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

\onehalfspacing
\setcounter{page}{2}

\newpage
\renewcommand{\contentsname}{\centerline{\large СОДЕРЖАНИЕ}}
\tableofcontents

\newpage
\begin{center}
  \textbf{\large ВВЕДЕНИЕ}
\end{center}
\addcontentsline{toc}{chapter}{ВВЕДЕНИЕ}


\textbf{Актуальность}

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

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

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

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

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

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

\textbf{Цель выпускной квалификационной работы} -- проверить гипотезу об улучшении оценки решения задачи линейного программирования с коническими ограничениями, найденного путем аппроксимации решений на промежуточных эллипсоидальных конусах Дикина с помощью вариаций симплекс-метода и метода внутренней точки.

\textbf{Задачи выпускной квалификационной работы:}
\begin{enumerate}
  \item Изучить уже существующие алгоритмы нахождения оценок для решения задач такого типа.
  \item Развить идею улучшения оценки с использованием представленных методов и расширить способы решения подзадач на конус.
  \item Проверить гипотезу нахождения решения на конусе и улучшаемость оценки по сравнению с уже предложенными алгоритмами.
  \item (предположительно) По результатам исследования предоставить соответствующий алгоритм.
  \item (предположительно) Произвести сравнительное тестирование точности и производительности предложенного алгоритма по сравнению с уже существующими решениями.
\end{enumerate}