Метод внутренней точки (Bymk; furmjyuuyw mkctn)

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

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

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

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

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

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

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

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

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

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

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

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

Фаза 1

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

См. также

• Метод Ньютона

Литература

• Системный анализ и исследование операций.Авторы: Ю. Черников
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. Numerical optimization: Theoretical and practical aspects (англ.). — Second revised ed. of translation of 1997 French. — Berlin: Springer-Verlag, 2006. — P. xiv+490. — (Universitext). — ISBN 3-540-35445-X. — doi:10.1007/978-3-540-35447-5.
• Karmarkar, N. Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84 (англ.) : journal. — 1984. — P. 302. — ISBN 0-89791-133-4. — doi:10.1145/800057.808695. Архивировано 28 декабря 2013 года. Архивная копия от 28 декабря 2013 на Wayback Machine
• Mehrotra, Sanjay. On the Implementation of a Primal-Dual Interior Point Method (англ.) // SIAM Journal on Optimization : journal. — 1992. — Vol. 2, no. 4. — P. 575. — doi:10.1137/0802028.
• Nocedal, Jorge; Stephen Wright. Numerical Optimization (неопр.). — New York, NY: Springer, 1999. — ISBN 0-387-98793-2.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, B. P. Section 10.11. Linear Programming: Interior-Point Methods // Numerical Recipes: The Art of Scientific Computing (англ.). — 3rd. — New York: Cambridge University Press, 2007. — ISBN 978-0-521-88068-8.
• Wright, Stephen. Primal-Dual Interior-Point Methods (неопр.). — Philadelphia, PA: SIAM, 1997. — ISBN 0-89871-382-X.
• Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization (неопр.). — Cambridge University Press, 2004.
• Бабынин М. С., Жадан В. Г. Прямой метод внутренней точки для линейной задачи полуопределённого программирования, ЖВМиМФ, 48:10 (2008), 1780–1801
• Жадан В. Г., Орлов А. А. Двойственные методы внутренней точки для линейной задачи полуопределённого программирования, ЖВМиМФ, 51:12 (2011), 2158–2180
• Жадан В. Г., Орлов А. А. Допустимый двойственный метод внутренней точки для линейной задачи полуопределённого программирования, Автомат. и телемех., 2012, 2, 25–40

Ссылки

• Методы оптимизации в машинном обучении:Метод внутренней точки