(1) - линейная (min(max))
(2) - линейная система ограничений. i =1…m.
Любая задача, не удовлетворяющая (1)-(2) называется нелинейной. Класс задач нелинейного программирования значительно шире.
Основные результаты в математическом программировании достигнуты при рассмотрении задач, в которых система ограничений линейна, а целевая функция нет. Но даже в этих случаях оптимальное решение может быть найдено для очень узкого класса функций. Решение может быть найдено при наложении дополнительных условий на целевую функцию.
В случае, когда целевая функция нелинейна, точка экстремума может лежать как внутри области допустимых значений, так и на вершине, поэтому найти экстремум можно при наложении дополнительных ограничений.
Ещё большие трудности возникают в задачах с нелинейной системой ограничений. в этом случае накладывается условие сепарабельности.
В классической задаче оптимизации в случае нелинейности (1)-(2) предполагают, чтобы система ограничений содержала лишь уравнения. Условие неотрицательности и целочисленности как правило отсутствует, а функции и требуется, чтобы были непрерывными и имели частные производные второго порядка. Выше перечисленные задачи нахождения условного экстремума, но наряду с ними существует задача нахождения безусловного экстремума.
Одним из методов решения является метод множителей Лагранжа:
max функции при ограничениях =0, i =1…m предполагается что и непрерывны вместе со своими первыми частными производными. Идея этого метода может быть рассмотрена на следующем примере:
(1)
(2) , неотрицательность и целочисленность отсутствует, но и непрерывно дифференцируемы.
Свойства таковы, что из (2) что можно выразить (3), требуется выяснить необходимое условие, которому должно удовлетворять точка локального экстремума функции Z.
Подставим в (1), получим
Эта функция задает ограничение, которое на плоскости будет представлять линию. Нас будут интересовать лишь точки принадлежащие линии (3). Если в какой-либо из этих точек Z получим экстремум, то и достигает экстремума , причём этот экстремум не является условным, т.к. сам способ построения функции предусматривает учёт исходных условий и никаких дополнительных не нужно. будет являться первой координатой той искомой точки экстремума функции Z и её () можно найти из условия.
= - (это из функции дифф-ния неявной функции )
, -=0, =
(*)
Совместное решение уравнений данной системы позволяет найти все точки, в которых ожидается локальный экстремум функции Z.
Данную систему можно получить чисто формальным путём в более общем виде:
Пусть задана и , i=1…m, и непрерывны вместе с первыми производными.
Строим
Определяем частные производные от неё и приравниваем к нулю.
; ; i =1…m; j =1…m
F – функция Логранжа
- множители (коэффициенты Логранжа)
Решая систему получаем множество точек, в котором функция Z может иметь экстремум значения. Конечно при этом остаётся неизвестными методы нахождения глобального экстремума, но его можно найти перебором.
Метод Логранжа можно приложить и тогда, когда ограничения представляются в виде неравенств, введением дополнительных переменных.
Пример:
Составляем функцию Логранжа:
.
Понятие выпуклого программирования:
Df: функция f , определённая на выпуклом множестве Ω называется выпуклой, если для любых точек ,, принадлежащих Ω и для любой точки =выполнено.
Выпуклая означает, что график ограничен функцией f на любой отрезок в с концами , лежит не выше хорды, соединяющей точки и .
Свойства выпуклости:
1. линейная функция выпукла, т.к. , т.к. условие выпуклости выполнимо.
2. если и выпуклы, то их сумма тоже выпукла.
Пример:
- выпукла, т.к.
- выпукла, по свойству 1 f(x) – выпукла по свойству 2.
Df: функция g называется вогнутой(выпуклой вверх), если f = - g является выпуклой.
Свойства:
1. Линейная функция вогнута
2. Сумма вогнутых – вогнута.
Теорема. Если f выпуклая функция, то множество , заданное условием , т.е. , является выпуклым
- множество ограниченное линией уровня.
Доказательство.
Возьмём , ,тогда =,
линейная композиция точек тоже принадлежит множеству , т.е. оно выпукло.
Зам: Выпуклой является и любая плоскость, заданная уравнением , где - линейная функция.
Если множество заданно системой ограничений (условий) вида
Где - выпуклые, - вогнутые, - линейные, то это множество Ω есть выпуклое множество.
Выпуклая функция f, заданная на выпуклом множестве Ω обладает свойствами:
Любой локальный min f на Ω является глобальным. Это означает, что точка принадлежащая выпуклому множеству Ω такова, что у неё существует окрестность, целиком принадлежащая Ω, в котором является min функции f(x), а f в точке - min на всём множестве Ω.
Для вогнутых функций min меняется на max.
Если матрица Гессе функции f(x) является положительным (отрицательным) определителем, то f выпукла (вогнута) на Ω.
Пусть f(x) () – функция, определённая на некотором множестве S и имеющая на этом множестве непрерывную частную производную не ниже 2-го порядка, тогда f(x) есть вогнутая функция на множестве S, когда знак любого главного минора k-го порядка Гессеана для f(x) совпадает со знаком выражения
во всех точках множества S. Для выпуклости надо, чтобы любой главный k-ый минор был 0.
Гессиан f(x) – матрица , на пересечении i строки j столбца находятся значения смешанных производных 2-го порядка
Пример:
докажем что f выпукла на всей оси определения:
Минором k-го порядка матрицы называется значения любого определителя, полученного путём удаления из данной матрицы строк и столбцов с теми же номерами.
1 порядка: вычеркиваем n-k, т.е. 2
1-2 строки и 1-2 столбцы – 4>0
1 и 3 строку и столбец - 2 >0
2 и 3 строку и столбец - 2 >0
k = 2 , n-2=1
1 строка и 1столбец -
det=
2 строка и 2 столбец -
det=
3 строка и 3 столбец
det=
k=3
det= все главные миноры положительны функция выпукла.
Методы, позволяющие вести поиск наименьшего(наибольшего) значения функции на выпуклом множестве.
1 метод: Метод покоординатного спуска.
Двигаемся по координатным осям от точки до точки.
Пусть найти наименьшее значение целевой функции , . Выберем начальную точку и рассмотрим эту функцию при фиксированных значениях всех переменных, кроме . Тогда она станет функцией одного переменного и будем изменять эту переменную, двигаясь от до её min. Это значение обозначим . Тогда
Теперь зафиксируем переменные все, кроме . И рассмотрим f как функцию переменной и будем изменять , двигаясь от начального значения в сторону убывания функции. Дойдем до min значения и обозначим через .
и проведём такую минимизацию по всем переменным.
Дойдя до конца получим:
Затем вернёмся к и продолжим этот процесс.
Оборвать этот процесс можно на некотором шаге k и принять за наименьшее значение функции. В качестве критерия оценки можно считать или . Этот процесс будет сходящимся.
2 метод: Метод градиентного спуска.
Направление параллельно координатным осям, по которым мы двигались в предыдущем методе не является как правило направлением наиболее быстрого убывания функции. Такое направление будет определятся градиентом. Направление улучшающее скорость нахождения наискорейшего спуска есть направление антиградиента.
Метод состоит в следующем:
Выбирается начальная точка и вычисляется градиент рассматриваемой функции. Делается шаг в обратном направлении. В результате приходят в точку, в которой значение меньше первоначального, в новой точке повторяется предыдущая процедура. Продолжая процесс будем двигаться в сторону наибыстрейшего убывания функции. Специально обусловленный выбор направления на каждом шаге позволяет надеяться, что приближение к наименьшему значению будет наиболее быстрым. Метод градиентного спуска требует всегда вычисления градиента :
Вычисление градиента на каждом шаге может замедлить процесс вычислений, т.к. это достаточно сложная операция. Поэтому часто используют модификацию метода. Согласно этой модификации градиентного спуска после вычисления градиента в начальной точке делают не маленький шаг, а двигаются до тех пор пока функция убывает. Достигнув точки min, снова вычисляют градиент и повторяют описанную процедуру.
3 метод: Метод наискорейшего спуска.
При это методе градиент вычисляется гораздо реже– только при смене направления. Кроме того этот метод позволяет преодолеть проблему “оврагов”, т.е. может возникнуть следующая ситуация:
Общая схема методов (градиентных) состоит в построении последовательных приближений , исходя из соотношений , где - антиградиент(min), градиент (max).
В градиентном методе берется равным антиградиенту f(x) в точке . Коэффициент может быть определён разными методами: если длина шага выбирается из условий минимизации функции вдоль антиградиента, то получим метод наискорейшего градиентного спуска.
Пример:
Найти max f.
В качестве начальной точки возьмём
Вычисляем градиент:
Подберём значение шага таким образом, чтоб достигался max нашей функции:
Тогда
Скорость изменения равна нулю, т.е. алгоритм на этом заканчивается, т.е.
(3,2) – max f = 0.
