Постановка вопроса

Модели выпуклого программирования

Постановка вопроса

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

Эффективные численные методы разработаны лишь для отдельных классов задач нелинейного программирования, про которые априори известно, что они не являются многоэкстремальными. Таковы, например, задачи выпуклого программирования.

Выпуклое программирование – это раздел нелинейного программирования, занимающийся исследованием и отысканием решений задачи минимизации выпуклой функции (максимизации вогнутой функции) на выпуклом множестве, заданном системой неравенств.

Х₁

y=f(x₁,x₂)

y

Функция f(Х), определенная на выпуклом множестве М n-мерного пространства En, называется выпуклой на М, если для любых точек Х₁ и Х₂, принадлежащих М, и для любого числа λ, 0 ≤ λ≤1 справедливо неравенство

N

Х₂

f((1- λ) Х₁+ λ Х₂) ≤(1- λ) f(Х₁)+ λ f(Х₂) (8.1)

x₂

т.е., график выпуклойфункции f(Х) расположен ниже (не выше) любой своей хорды (рис. 8.1).

Х₁

Х₂

N

Иногда выпуклые функции называют выпуклыми вниз, а вогнутые – выпуклыми вверх.

Рис. 8.1.

x₁

Если в условии (8.1) знак ≤ изменить на ≥, получим определение вогнутой функции.

Если неравенство (8.1) выполняется как строгое, то функция называется строго выпуклой (или строго вогнутой).

Выпуклость (вогнутость) функции одной или двух переменных видна по ее графику.

В теории выпуклого программирования в качестве основной обычно рассматривается задача отыскания вектора , который удовлетворяет условиям

x_j ≥ 0, j=1, 2, …, n (8.2)

g_i(X) ≤ 0, i=1, 2, …, m (8.3)

и доставляет глобальный минимум функции F=f(x₁, x₂, …, x_n). При этом заданные функции f, g₁, g₂, …, g_m, определенные на n-мерных векторах X с неотрицательными компонентами, предполагаются выпуклыми.

Векторы, удовлетворяющие условиям (8.2) и (8.3), называются допустимыми, а искомые векторы – оптимальными.

Дата добавления: 2015-09-01