пользователей: 21281
предметов: 10473
вопросов: 178149
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Нелинейное программирование. Методы решения нелинейных задач, метод множителей Лагранжа. Понятие выпуклого программирования. Приближенны


(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.


06.08.2014; 14:00
хиты: 768
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь