Задачи выпуклого программирования

Пусть дана система неравенств вида

φ_i (x₁, x₂, …, x_n) ≤ b_i, (i=1, 2, …, m) (8.7)

и функция F = f (x₁, x₂, …, x_n) (8.8)

причем все функции φ_i(Х) являются выпуклыми на некотором выпуклом множестве М, а функция F либо выпукла на множестве М, либо вогнута. Задача выпуклого программирования (ВП) состоит в отыскании такого решения системы ограничений (8.7), при котором либо выпуклая целевая функция F достигает минимального значения, либо вогнутая функция F достигает максимального значения.

В общем случае задачи ВП являются задачами нелинейного программирования. Выделение задач ВП в специальный класс объясняется экстремальными свойствами выпуклых функций: всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным; выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума. Отсюда вытекает, что если целевая функция F является строго выпуклой (строго вогнутой), то задача ВП всегда имеет единственное решение. В этом случае минимум выпуклой (максимум вогнутой) функции достигается внутри области решений, если там имеется стационарная точка, или на границе этой области, если внутри нее нет стационарной точки.

Пример 8.4..........

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