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

Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации. Используется в решениях задач по сопромату, математическому моделированию и эконометрике. Метод внутренних точек был впервые упомянут в 1967 году.. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В.Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы. В западной литературе утверждается, что метод внутренней точки был впервые предложен Джоном фон Нейманом и в первоначальном виде не обладал полиномиальной сложностью, как и не был эффективным. На практике он даже уступал симплекс-методу, также не обладавшему полиномиальной сложностью. Однако в 1984 году предложенный индийским математиком Нарендра Кармаркаром алгоритм линейного программирования демонстрировал полиномиальное время даже превосходил симплекс-метод. Согласно методам внутренней точки (иначе называемым методами барьерных функции), исходную для поиска точку можно выбирать только внутри допустимой области. Выбор начальной точки поиска осуществляется в зависимости от формулировки задачи. При отсутствии ограничений или их преобразовании к функциям штрафа с внешней точкой начальная точка выбирается произвольно. При наличии ограничений или их преобразовании к функциям штрафа с внутренней точкой начальная точка выбирается внутри допустимой области При этом множество точек делится на допустимые и недопустимые в зависимости от ограничений . В свою очередь множество допустимых точек в зависимости от ограничений также делится на граничные и внутренние.