Методы внутренних точек для решения задач выпуклой оптимизации: теория, преимущества (полиномиальное время), сравнение с симплекс-методом и методом эллипсоидов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритмы решения задач выпуклой оптимизации
Algorithms for solving convex optimization problems
Методы внутренних точек (также известные как барьерные методы или IPM) — это алгоритмы для решения линейных и нелинейных задач выпуклой оптимизации. Методы IPM сочетают в себе два преимущества ранее известных алгоритмов:
Interior point methods (also referred to as barrier methods or IPMs) are algorithms for solving linear and non linear convex optimization problems. IPMs combine two advantages of previously known algorithms:
Теоретически, их время работы полиномиально — в отличие от симплекс-метода, который в худшем случае имеет экспоненциальное время работы. Практически, они работают так же быстро, как и симплекс-метод — в отличие от метода эллипсоидов, который теоретически имеет полиномиальное время работы, но на практике работает очень медленно. В отличие от симплекс-метода, который проходит по границе допустимой области, и метода эллипсоидов, который ограничивает допустимую область снаружи, IPM достигает оптимального решения, двигаясь внутри допустимой области — отсюда и название.
Theoretically, their run time is polynomial—in contrast to the simplex method, which has exponential run time in the worst case. Practically, they run as fast as the simplex method—in contrast to the ellipsoid method, which has polynomial run time in theory but is very slow in practice. In contrast to the simplex method which traverses the boundary of the feasible region, and the ellipsoid method which bounds the feasible region from outside, an IPM reaches a best solution by traversing the interior of the feasible region—hence the name.
История
Метод внутренней точки был открыт советским математиком И. И. Дикиным в 1967 году. Метод был заново изобретен в США в середине 1980-х годов. В 1984 году Нарендра Кармаркар разработал метод линейного программирования, названный алгоритмом Кармаркара, который работает за доказуемо полиномиальное время (операции с L-битными числами, где n – число переменных и констант) и также очень эффективен на практике. Работа Кармаркара вызвала всплеск интереса к методам внутренней точки. Два года спустя Джеймс Ренегар изобрел первый метод внутренней точки, следующий по пути, с временем выполнения. Позднее метод был расширен с линейных задач оптимизации на выпуклые, основываясь на самосогласующей барьерной функции, используемой для кодирования выпуклых множеств. Любая задача выпуклой оптимизации может быть преобразована в минимизацию (или максимизацию) линейной функции над выпуклым множеством путем приведения к форме эпиграфа. Идея кодирования допустимого множества с помощью барьера и разработки барьерных методов была изучена Энтони В. Фиакко, Гартом П. Маккормиком и другими в начале 1960-х годов. Эти идеи в основном разрабатывались для общего нелинейного программирования, но впоследствии были заброшены из-за появления более конкурентоспособных методов для этого класса задач (например, последовательного квадратичного программирования). Юрий Нестеров и Аркадий Немировский предложили специальный класс таких барьеров, которые могут быть использованы для кодирования любого выпуклого множества. Они гарантируют, что число итераций алгоритма ограничено полиномом от размерности и точности решения.
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967. The method was reinvented in the U. S. in the mid 1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time ( operations on L bit numbers, where n is the number of variables and constants), and is also very efficient in practice. Karmarkar's paper created a surge of interest in interior point methods. Two years later, James Renegar invented the first path following interior point method, with run time The method was later extended from linear to convex optimization problems, based on a self concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encoding the feasible set using a barrier and designing barrier methods was studied by Anthony V. Fiacco, Garth P. McCormick, and others in the early 1960s. These ideas were mainly developed for general nonlinear programming, but they were later abandoned due to the presence of more competitive methods for this class of problems (e. g. sequential quadratic programming). Yurii Nesterov and Arkadi Nemirovski came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.
Определения
Нам дается выпуклая программа вида: где f — выпуклая функция, а G — выпуклое множество. Без потери общности можно предположить, что целевая функция f является линейной. Обычно выпуклое множество G представлено набором выпуклых неравенств и линейных равенств; линейные равенства можно исключить с помощью линейной алгебры, поэтому для простоты мы предполагаем, что есть только выпуклые неравенства, и программа может быть описана следующим образом, где gi — выпуклые функции: Мы предполагаем, что функции ограничений принадлежат некоторому семейству (например, квадратичным функциям), так что программа может быть представлена конечным вектором коэффициентов (например, коэффициентами квадратичных функций). Размерность этого вектора коэффициентов называется размером программы. Численный решатель для данного семейства программ — это алгоритм, который, получив вектор коэффициентов, генерирует последовательность приближенных решений xt для t = 1, 2, …, используя конечное число арифметических операций. Численный решатель называется сходящимся, если для любой программы из семейства и любого положительного ε > 0 существует некоторое T (которое может зависеть от программы и от ε), такое что для любого t > T приближенное решение xt является ε-приближенным, то есть: f(xt) − f* ≤ ε, gi(xt) ≤ ε для i = 1, …, m, xt ∈ G, где f* — оптимальное решение. Решатель называется полиномиальным, если общее число арифметических операций в первых T шагах не превышает poly(размер задачи) * log(V/ε), где V — некоторая зависящая от данных константа, например, разность между наибольшим и наименьшим значением в допустимом множестве. Другими словами, V/ε — это «относительная точность» решения — точность относительно наибольшего коэффициента. log(V/ε) представляет собой число «цифр точности». Следовательно, решатель является «полиномиальным», если каждая дополнительная цифра точности требует числа операций, полиномиального по размеру задачи.
We are given a convex program of the form:where f is a convex function and G is a convex set. Without loss of generality, we can assume that the objective f is a linear function. Usually, the convex set G is represented by a set of convex inequalities and linear equalities; the linear equalities can be eliminated using linear algebra, so for simplicity we assume there are only convex inequalities, and the program can be described as follows, where the gi are convex functions:We assume that the constraint functions belong to some family (e. g. quadratic functions), so that the program can be represented by a finite vector of coefficients (e. g. the coefficients to the quadratic functions). The dimension of this coefficient vector is called the size of the program. A numerical solver for a given family of programs is an algorithm that, given the coefficient vector, generates a sequence of approximate solutions xt for t=1,2, , using finitely many arithmetic operations. A numerical solver is called convergent if, for any program from the family and any positive ε>0, there is some T (which may depend on the program and on ε) such that, for any t>T, the approximate solution xt is ε approximate, that is: f(x t) f* ≤ ε
gi(x t) ≤ ε for i in 1, ,m,
x in G,where f* is the optimal solution. A solver is called polynomial if the total number of arithmetic operations in the first T steps is at mostpoly(problem size) * log(V/ε),where V is some data dependent constant, e. g., the difference between the largest and smallest value in the feasible set. In other words, V/ε is the "relative accuracy" of the solution the accuracy w. r. t. the largest coefficient. log(V/ε) represents the number of "accuracy digits". Therefore, a solver is 'polynomial' if each additional digit of accuracy requires a number of operations that is polynomial in the problem size.
Типы выпуклых программ, разрешимых с помощью методов внутренней точки
Вот некоторые специальные случаи выпуклых задач, которые могут быть эффективно решены методами внутренней точки.
Here are some special cases of convex programs that can be solved efficiently by interior point methods.
Полуопределенные программы
Методы внутренней точки могут быть использованы для решения задач полуположительного программирования.
Interior point methods can be used to solve semidefinite programs.