3.2. Выпуклое программирование Постановка задачи выпуклого программирования.

Рассмотрим задачу нелинейного программирования:

f (x₁, x₂, ..., x_n)max, (3.3)

g_i (x₁, x₂, ..., x_n)b_i (i=1, ..., m), (3.4)

x_i0 (j=1, ..., n), (3.5)

где f и g_i — некоторые функции n переменных x₁, x₂, ..., x_n.

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X₁ и X₂ из X и любого 01 выполняется соотношение

Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X₁, X₂ из X и любого 01 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x₁, x₂, ..., x_n) является вогнутой (выпуклой), а функции g_i (X) (i=1, ..., m) — выпуклыми.

Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка X_i, принадлежащая ОДР такая, что g_i (X_i)<b_i (i=1,..., m).

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.

Для задачи выпуклого программирования (3.3) — (3.5), множество допустимых решений которой обладает свойством регулярности, X₀ тогда и только тогда является оптимальным решением, когда существует такой вектор , что — седловая точка функции Лагранжа.

Эта теорема называется также теоремой о седловой точке.

3.3. Классические методы оптимизации Метод прямого перебора.

Если известна функциональная связь целевой функции Y и искомой переменной X, то можно последовательно вычислить значения целевой функции для некоторых значений искомой переменной. Вычисления повторяются до тех пор, пока не будет найден min (max) значения целевой функции

Y=f(x₁, ..., x_i, ..., x_n, u₁, ..., u_j, ..., u_m),

x_i=x_0i+x_ik (k=0, 1, 2, ..., l).

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

Особенность и преимущества метода прямого перебора заключаются: 1) в независимости поиска от вида и характера целевой функции; 2) в цикличности поисковой процедуры; 3) в определении глобального экстремума целевой функции; 4) в простоте алгоритма и программы оптимизации; 5) в малом объеме необходимой машинной памяти.

В случае большой области изменения искомой переменной и (или) наличия более чем одного экстремума исследуемой функции использование этого метода неэффективно.