Выпуклого программирования

2. Выпуклое программирование

Выпуклое программирование [convex programming] — раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений.

Общая задача выпуклого программирования состоит в отыскании такого вектора x (т. е. такой точки выпуклого допустимого множества), который доставляет минимум выпуклой функции f(x) или максимум вогнутой функции y(x). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторов предпочитают термин “вогнутое программирование”.
Выпуклость (вогнутость) важна тем, что гарантирует нахождение оптимального решения задачи, так как соответственно локальные и глобальный экстремумы здесь обязательно совпадают. Критериями оптимальности в первом случае могут быть, напр., издержки при различных сочетаниях факторов производства, во втором случае — величина прибыли при этих сочетаниях.
Как видим, есть сходство между задачами выпуклого (вогнутого) и линейного программирования (последнее можно рассматривать как частный случай первого). Но нелинейность зависимостей делает задачу намного сложнее.
Под задачей выпуклого программирования понимают задачу вида
где и - выпуклые функции. Для этих задач характерно то, что любой локальный минимум оказывается глобальным, и все сводится к нахождению этого единственного минимума.
Для решения задач этого типа разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях ¾ метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.


2. Градиентные методы решения задач выпуклого программирования

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

Используя градиентный метод, можно найти решение любой задачи нелинейного программирования. Применение этого метода в общем случае позволяет найти точку локального экстремума. Поэтому более целесообразно использовать его для нахождения решения задач выпуклого программирования. Процесс нахождения решения задачи с помощью градиентного метода состоит в том, что начиная с некоторой точки осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не будет найдено приемлемое решение исходной задачи.
Градиентные методы могут быть подразделены на две группы.
- К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка – Вульфа.
- Ко второй – методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу – Гурвица.
При нахождении решения задачи градиентными методами итерационный процесс продолжается до тех пор, пока градиент функции в очередной точке не станет равным нулю или же пока не выполнится неравенство , где (точность полученного решения).
Вообще говоря, градиентные методы можно применять к любой задаче нелинейного программирования. Но они приводят лишь к локальному экстремуму, а поэтому оказываются более эффективными при решении задач выпуклого программирования, где всякий локальный экстремум есть одновременно и глобальный.
В качестве основной в теории выпуклого программирования обычно рассматривается задача отыскания вектора который удовлетворяет условиям:

и доставляет глобальный минимум функции

функции предполагаются гладкими и выпуклыми.

Если — вогнутая функция, а — выпуклые функции, то получаем соответственную задачу: найти вектор удовлетворяющий условиям и доставляющий глобальный максимум функции
Множество точек удовлетворяющих условиям формулированных задач, является выпуклым.