Опорный конспект лекции дисциплины «Методы оптимизации и исследование операции» (стр. 2 )

Пример: Негладкая функция ()=ê ê, R1 , т. к.

ç 1+(1-)2çê1ê+(1-) ê2 ê при 1, 2R1 ,[0,1]

Определение: Если функция (), Rn, дважды непрерывно дифференцируема f()с2 , то она выпукла тогда и только тогда когда матрица

Rn, её вторых производных неотрицательна.

Критерий Сильвестра: 1) для положительности матрицы А, чтобы все её последовательные главные миноры Ds были положительны: Ds=, 2) для неотрицательности матрицы А необходимо и достаточном, чтобы все её главные миноры были неотрицательными

1i1<i2<…<isn, s=

Свойства выпуклых множеств:

Пересечениечисла выпуклых множеств-выпуклое множество. Выпуклая комбинация () элементов i , i= выпуклого множества принадлежит этому множеству.

Свойства выпуклой функции :

Множество уровня выпуклой функции , Rn или пусто, или выпукло.

Если fi(), Rn , i=-выпуклые функции, то и = i=, (x)=max () - выпуклые функции.

Выпуклая функция , Rn - непрерывна в каждой точке .

В каждой точке Rn выпуклая функция() имеет производную по направлению L Rn

Вектор сRn называется субградиентом выпуклой функции , хRn в точке х*, если для всех выполняется неравенство:

-с(х-х*).

Функция называется вогнутой, если функция-выпукла.

Теорема: Пусть функция определена и непрерывна на выпуклых компактных множествах Rn, yYRm.Если функция при которой yY выпукла по, а при каждом хХ вогнута по yY, то она имеет седловую точку {0,y0}, 0, y0Y

и для неё справедлива теорема о минимаксе.

Функция , Rn называется строго выпуклой, если для , выполняется строгое неравенство

Функцию,Rn называют сильно выпуклой, если для и некоторой выполняется неравенство

Теорема Куна-Таккера.

Теорема Куна-Таккера в выпуклом программировании называется основной результат - критерии оптимальности, сформулированный в терминах седловой точки функции Лагранжа.

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

ОЗВП:

- выпуклое множество, и компоненты ,

-вектор функции-выпуклые функции.

Каждый n вектор удовлетворяет ограничениям задачи(1), называется, следуя задачи Л. П., планом (допустимыми точкой, вектором, решением).

Решение задачи (1) есть оптимальный план.

Если целевая функция - строго выпуклая, то оптимальный план задачи (1) единственный.

Определение: (2), - функция Лагранжа

Определение: Говорят, что ,- седловая точка функции Лагранжа (2), если для всех выполняется неравенство

(3)

Теорема: Если (), , - седловой точки функции Лагранжа(2),

то - оптимальный план задачи (1) и выполняется условие дополняющей нежесткости

=0 (4)

Определение: Говорят, что множество планов (ограничения) ОЗВП регулярно (удовлетворяет условие Слейтера), если на некотором плане выполняется неравенство (5)

Теорема ( Куна - Таккера): Для существования оптимального плана ОЗВП с регулярным множеством планов необходимо и достаточно существование такого неотрицательного вектора,что пара (,)- седловая точка функции Лагранжа и выполняется условие дополняющей нежесткости.

(6)

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

Минимизация функции одной переменной имеет самостоятельный интерес. От правильной организации одномерного поиска существенно зависит успех решения всей задачи. Пусть функция f(x), определенная на [a, b]. Функция f(x) называется унимодальной, если существует единственная точка х*, в которой функция f(x) принимает экстремальное значение. Унимодальная функция не может быть гладкой или даже непрерывной. Из определения унимодальности следует, что если то f(x1) >f(x2). Аналогично, если то f(x1) <f(x2). Задача состоит в построении такой последовательности {xk} , чтобы при некотором i минимальное значение функции достигалось на интервале , которое называется интервалом неопределенности. Алгоритм выбора абцисс {xk} называется стратегией поиска. При заданном количестве вычислении функции оптимальной стратегией является та, которая ведет к наименьшему интервалу неопределенности.

Алгоритм поиска.

Начальный отрезок [a, b] делим точками x1 и x2 и вычисляем значение f(x1), f(x2), т. к. f(x1) <f(x2), то минимум располагается или в [a, x1] или в [x1,x2], поэтому [x2,b] –отбрасываем, тем самым сужаем интервал неопределенности. Далее рассмотрим [a1,b1], где a1=а, b1=x2, выбираем две внутренние точки, но x1 осталась из предыдущего шага, достаточно выбрать х3. Поскольку f(x3)>f(x1), то минимум находится на [x3,b]. Обозначим этот отрезок [a2,b2], снова выбираем одну точку и повторяем процедуру сужения. Продолжаем до тех пор , пока длина очередного [an, bn] не станет меньше заданного e. Золотое сечение выбирается следующим образом. Отношения длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего.

Золотое сечение [a, b] производят две симметрично расположенные точки , где x1 производит золотое сечение [a, x2], a x2 производит золотое сечение [x1,b].

Метод дихотомии. ( Метод половинчатого деления)

Вычислительный алгоритм

1) Проверка условия , e-заданная погрешность вычисления .

Если условие выполняется, то идём к 6), иначе 2).

2) делим пополам и вычисляем 2 абсциссы, симметрично расположенные относительно точек

:

3) Вычисляем и

4) Проверка условия . Если оно выполняется то, и идём к) 1), иначе к 5).

5) и идём к 1).

6) Вывод на печать и вычисляем .

Задание. Выписать 1 и 2, сравнить данные. Сделать блок-схему.

Метод квадратичной интерполяции-экстраполяции.