WikiSort.ru - Программирование

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

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

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

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

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

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

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

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 31 июля 2015 года.

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

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

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

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 31 июля 2015 года.

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

Фаза 1

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 31 июля 2015 года.

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

См. также

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

Примечания

Литература

• Системный анализ и исследование операций.Авторы: Ю. Черников
• Bonnans, J. Frédéric. Numerical optimization: Theoretical and practical aspects / J. Frédéric Bonnans, Gilbert, Lemaréchal … [и др.]. — Second revised ed. of translation of 1997 French. — Berlin : Springer-Verlag, 2006. — P. xiv+490. — ISBN 3-540-35445-X. — DOI:10.1007/978-3-540-35447-5.
• Karmarkar, N. (1984). “Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84” (PDF): 302. DOI:10.1145/800057.808695. ISBN 0-89791-133-4. Архивировано из оригинала (PDF) 2013-12-28. Проверено 2015-03-10. Используется устаревший параметр |deadlink= (справка); Параметр |chapter= пропущен (справка на английском)
• Mehrotra, Sanjay (1992). “On the Implementation of a Primal-Dual Interior Point Method”. SIAM Journal on Optimization. 2 (4): 575. DOI:10.1137/0802028.
• Nocedal, Jorge. Numerical Optimization. — New York, NY : Springer, 1999. — ISBN 0-387-98793-2.
• Press, WH. Section 10.11. Linear Programming: Interior-Point Methods // Numerical Recipes: The Art of Scientific Computing / WH Press, Teukolsky, Vetterling … [и др.]. — 3rd. — 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. Convex Optimization / Stephen Boyd, Vandenberghe. — Cambridge University Press, 2004.

Ссылки

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

Для улучшения этой статьи желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).