Задачи нелинейного программирования

В большинстве задач оптимизации критерий оптимальности является функцией нескольких независимых переменных - Если он является непрерывной функцией, имеющей непрерывные частные производные первого и второго порядка по всем переменным uй (й = 1, n) , то необходимым условием экстремума в точке является равенство нулю в этой точке первых производных по всем переменным, т.е. точки, в которой функция может достигать экстремума, определяются решением системы уравнений , t=.

Достаточные условия существования экстремума определяются в результате анализа знака квадратичной формы B=, коэффициенты которой определяются соотношениями

; i,j=.

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

т.е. все главные миноры матрицы

A=

должны быть строго положительны.

Квадратичная форма будет отрицательно определенной, если все главные миноры матрицы A, имеющие нечетный порядок, отрицательны, а, имеющие четный порядок, положительны, т.е.

Если квадратичная форма является положительно определенной, то исследуемая точка является точкой минимума, если же квадратичная форма будет отрицательно определенной, то в точке {uй} имеет место максимум.

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

Пусть в реакторе идеального смешения протекает реакция первого порядка (A > P). Требуется определить оптимальные условия - время пребывания и температуру, при которой себестоимость продукта P будет минимальной.

Критерий оптимальности - себестоимость задается функцией

Q(

где u1 - время пребывания, u2 - константа скорости химической реакции, связанная с температурой уравнением Аррениуса u2 = exp(- E / RT), E и R - константы; СА - стоимость единицы расходуемого сырья; Сq - стоимость дополнительного оборудования реактора, исчисляемая с учетом амортизации; Сv -стоимость единицы объема реактора, исчисляемая с учетом его амортизации; U - нагрузка реактора по исходному сырью; xA0 - начальная концентрация вещества А.

Необходимые условия экстремума функции Q(u1, u2) дают систему уравнений:

Последнее уравнение не удовлетворяет ни каким значениям u1, u2, поэтому разумно выдерживать максимально возможную температуру ведения процесса, что определит значение u2. Оптимальное значение времени пребывания, соответствующее принятому значению температуры в этом случае определится как

Минимальная себестоимость составит

.

Найти экстремум функции Q (u1, u2) = Необходимые условия экстремума записываются в виде системы:

Решение полученной системы уравнений дает три подозрительные точки на экстремум: (0, 0); (1, 1); (-1, -1). Для определения существования экстремума в найденных точках требуется проверить достаточные условия. С этой целью составляется матрица

.

В найденных точках

Матрица - знаконеопределенна, следовательно, точка (0, 0) не является экстремальной. Матрицы положительно определенные поэтому в точках (1, 1) и (-1,-1) будет минимум -.

1.4 Метод неопределенных множителей Лагранжа

Пусть требуется найти экстремум функции, например, минимум

Q(, при условии

,

Согласно методу Лагранжа для решения задач на условный экстремум функции составляется вспомогательная функция Лагранжа, которая определяется соотношением

,

где , = - неопределенные множители Лагранжа.

Таким образом, задача нахождения условного экстремума функции сводится к задаче нахождения безусловного экстремума функции, но число неизвестных в ней n + k (uй, й = 1, n ; лj , j = 1, k ).

Как известно из п. 1.2 необходимым условием безусловного экстремума функции является равенство нулю частных производных, которые для данного конкретного случая записываются в виде

.

и дает n уравнений для определения неизвестных. Эта система уравнений дополняется к уравнениям и, следовательно, получается (n + k) неизвестных и (n + k) уравнений.

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

В окончательном решении задачи фактически множители Лагранжа не известны, поэтому задача совместного решения системы, иногда ставится как задача исключения "k" неизвестных переменных uй с последующим решением остающейся системы n уравнений с n неизвестными.

Задача Лагранжа имеет "n - k" степеней свободы.

1.4.2 Геометрическая интерпретация метода множителей Лагранжа

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

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

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

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

В этом смысле шаговые методы поиска оптимума называются итеративными.

Методы нелинейного программирования в зависимости от способа задания шага подразделяются на три основных класса: 1) градиентные методы; 2) безградиентные методы; 3) методы случайного поиска. Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации (u-скаляр) и многомерной оптимизации (u-вектор).

Задача нелинейного программирования в общем случае рассматривается в n-мерном пространстве, где наглядное графическое изображение отсутствует, в связи с этим используется следующий прием графического представления.

Если целевая функция непрерывна в области U, то вокруг точки uопт всегда можно провести в данной плоскости замкнутую линию, вдоль которой значение Q(u) постоянно (рис. 2.1, а). Эти замкнутые линии называются линиями равного уровня функции и отвечают различным значениям =qй . Вокруг точки uопт можно провести сколько угодно линий уровня, причем каждая из них будет целиком охватывает любую линию, для которой значение целевой функции меньше (или больше).

Рисунок 2.1 - Геометрическое представление целевой функции:

а - линии равного уровня; б - линии равного уровня и связи типа равенств; в - линии равного уровня и ограничения типа неравенств

При наличии связи , что в n-мерном пространстве определяет (n-1) -мерную поверхность, пересечение которой с рассматриваемой поверхностью определяет область (рис. 2.1, б), в которой и ищется оптимальное решение.

Ограничения типа неравенств независимо от их числа наглядно представлены на рис. 2.1, в. Здесь заходить в заштрихованную область нельзя.

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

которое выполняется для любых допустимых значений u. Если существуют другие оптимумы, то они называются локальными, и соотношения типа выполняется только в окрестностях точек . Для отыскания глобального оптимума необходимо найти и проверить, вообще говоря, все без исключения локальные оптимумы, имеющейся целевой функции. Среди методов, применяемых для решения задач нелинейного программирования значительное место занимают методы поиска решения, основанные на анализе производных оптимизируемой функции. Эта функция должна быть непрерывно дифференцируемой. Для этого вводится понятие производной по направлению l

,

где u, u* - точки, расположенные на прямой l. Эта производная характеризует скорость изменения функции Q (u) в точке и в направлении l, она может быть выражена через производные по координатам, число которых конечно и равно размерности n. Согласно правилу дифференцирования сложных функций, можно записать

.

Рассмотрим расчет ?uй /?l в пространстве двух переменных (рис. 2.2).

Рисунок 2.2 - К определению направляющих косинусов

Из прямоугольного треугольника АВС можно записать

l=.

Таким образом, величины /dl есть не что иное, как направляющие косинусы выбранного направления l по отношению к осям координат. Следовательно, можно переписать следующим образом

.

Если теперь рассмотреть поверхность равного уровня, которая имеет (n-1) независимых переменных, то в каждой точке этой поверхности, называемой гиперповерхностью, можно провести (n-1) взаимно перпендикулярных касательных в соответствии с числом измерений этой поверхности. Кроме того, в этой же точке можно провести ось, перпендикулярную всем касательным и, следовательно, направленную по нормали к поверхности. Подобное построение для случая (n = 3) изображено на рис. 2.3

Рисунок 2.3 - Система координат, связанная с произвольной точкой

поверхности постоянного уровня

Касательные и нормаль могут рассматриваться как система координат с началом в выбранной точке поверхности. Данная система координат обладает тем важным свойством, что частные производные от

функции Q(u) по направлениям осей равны нулю, так как вдоль этих направлений функция Q(u) сохраняет постоянное значение. В соответствии со сказанным производная по произвольному направлению l запишется как

,

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

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

Формулу можно записать как - проекция градиента функции по направлению l. Отсюда следует, что проекции вектора градиента на оси координат равны производным функции Q (u) по соответствующим переменным, т.е. .

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

2.2 Методы одномерной оптимизации

2.2.2 Метод половинного деления

Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке с точностью . Отрезок делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках

x_1,2=.

На основе анализа значений и вдвое уменьшается интервал неопределенности и процесс повторяется пока . Блок-схема этого метода приведена на рис. 2.5, б.

Рисунок 2.5 - Метод деления отрезка пополам:

а - геометрическая интерпретация; б - блок-схема

2.2.3 Метод "золотого сечения"

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод "золотого сечения": интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении Это соотношение выполняется при ...

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 2.6, б) по формуле

x1 = b - (b - a) / 1,618033989…

Рисунок 2.6 - Метод "золотого сечения":

а - золотое сечение; б - геометрическое представление

Точка x2 определяется как точка,симметричная точке x1 на отрезке (a-b).

На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий уни-модальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше . Блок-схема алгоритма метода "золотого сечения" представлена на рис. 2.7.

Рисунок 2.7 - Блок-схема метода "золотого сечения"

2.2.4 Метод Фибоначчи

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением

F0 = F1 = 1; Fk = Fk-1 + Fk-2; k = 2, 3, …

При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения".

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от , число вычислений значений функции Q (u).

По заданному определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения

В остальном схема метода близка к методу "золотого сечения" в котором значение x1 и x2 (см. рис. 2.8) определяются отношением соответствующих чисел Фибоначчи.

Рис. 2.8- Блок-схема метода Фибоначчи

2.3 Методы многомерной оптимизации