Условия оптимальности решения задачи нелинейного программирования

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

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

  • 1. Выписывают необходимые условия экстремума (если функция непрерывно дифференцируемая, то условия равенства нулю ее градиента). Эти условия выделяют множество «претендентов на решение» (критических точек) и имеют форму системы уравнений, число которых совпадает с размерностью вектора искомых переменных.
  • 2. Если решение существует, например выполнены условия теоремы Вейерштрасса, то, перебрав значения функции в критических точках, можно найти ее максимум либо минимум.

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

Постановка задачи нелинейного программирования

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

Формально

Множество векторов х, удовлетворяющих всем условиям задачи, образует множество допустимых решений D, принадлежащее п-мерному векторному пространству Мп. При этом множество Vx определяется ограничениями, наложенными на каждую из составляющих вектора х, типа

т. е. представляет собой параллелепипед в пространстве Шп.

Число условий в форме равенства меньше п. В противном случае решениями являются корни системы/;(х) = 0 (i = 1, 2, ..., ш) или множество допустимых решений пусто. Функции/0,/,-, cpv, если это специально не оговорено, предполагаются непрерывными и непрерывно дифференцируемыми.

Заметим, что условия в форме неравенств всегда можно свести к условиям в форме равенств, введя добавочные переменные. Например,

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

Задача НП называется выпуклой, если выполнено два условия:

  • а) функция/о (х) выпукла,
  • б) множество допустимых решений D также выпукло.

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

Последнее условие можно несколько ослабить, ведь нам нужно, чтобы линия уровня фу(х) = 0 ограничивала выпуклое множество. Функции же, обладающие этими свойствами по отношению к любой из линий уровня, называют квазивыпуклыми. Так, функция, изображенная на рис. 2.7, не выпукла, но квазивыпукла.

Чем же замечателен класс выпуклых задач? Чтобы пояснить это, введем понятие о локально-неулучшаемом решении х° как о таком элементе множества допустимых решений D, в сколь угодно малой окрестности которого, принадлежащей D, L(x° с D) (на множестве сравнения), не найдется другого «лучшего» элемента.

Пример квазивыпуклой функции

Рис. 2.7. Пример квазивыпуклой функции

Формально

Таким образом, любая сколь угодно малая по величине допустимая (не выводящая за пределы D) вариация 8х не приведет в точку, лучшую чем х°. В выпуклой задаче функция/0 и множество D, на котором она определена, выпуклы, значит, подграфик П является выпуклым множеством, а/о — его верхней границей.

Утверждение. Для выпуклой задачи любое локалъно-неулучшаемое решение х° доставляет функции /0 абсолютный максимум на D.

Действительно, точка с координатами (х°,/0(х°)) принадлежит границе выпуклого множества, причем ближайшим к ней точкам соответствуют значения/0, не большие чем/00). Таким образом, горизонтальная плоскость, проведенная через точку (х°,/00)), не проходит через внутренние точки подграфика, а всюду оказывается над ним (рис. 2.8). Следовательно, для любого х е D /0(х°) >/0(х).

Локально-неулучшаемые решения в задаче о максимуме выпуклых функций

Рис. 2.8. Локально-неулучшаемые решения в задаче о максимуме выпуклых функций

Определения. Значением задачи НП называют максимальное значение функции/0(х) на множество D. Оптимальным решением задачи НП называют такой элемент х* е D, для которого/0(х*) >/0(х) Vx е D. Иногда, когда по контексту это не вызывает недоразумений, его называют просто решением.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >