Метод внутренней точки

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

Используется в решениях задач по сопромату, математическому моделированию и эконометрике.

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.[1]. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В.Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы.

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

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

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

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

Логарифмический барьер и центральный путь

Истоки алгоритмов центрального пути восходят к идее К.Фриша включения в целевую функцию штрафных слагаемых в виде логарифмаограничений-неравенств с параметром, монотонно уменьшающимся до нуля.

Появление алгоритма Кармаркара [51] подтолкнуло исследователей к активному применению функций логарифмического барьера в задачах линейного программирования.

Барьерный метод

Метод Кармакара аналогичен логарифмически-барьерному методу.

Фаза 1

Для запуска метода барьеров необходимо указать начальную внутреннюю точку, т.е. такую точку x, для которой fi(x) < 0 ∀i. В общем случае поиск внутренней точки x может оказаться нетривиальной задачей. Методы решения этой задачи получили название методов первой фазы. К ним относят метод барьеров и прямо-двойственный метод ньютона.

См. также

Примечания

  1. Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. — 1967. Т. 174, № 4. С. 747—748.
  2. Dantzig, George B.; Thapa, Mukund N. Linear Programming 2: Theory and Extensions (англ.). Springer-Verlag, 2003.

Литература

Ссылки


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.