MO25

Элементы выпуклого анализа. Теорема Куна-Таккера. Понятие о двойственной задаче (основные теоремы). Методы условной оптимизации. Правило множителей Лагранжа для задач с ограничениями типа равенств и неравенств. Метод штрафных функций. Метод проекции градиента.
– Изучение ряда базовых алгоритмов, которые используются для решения конечномерных задач оптимизации.
– Получение теоретических и концептуальных представлений, достаточных для понимания, оценки этих алгоритмов и, если необходимо, создания новых.
Цель курса:

Оптимизация (по латыни optimus – наилучший) - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Предмет и история развития методов оптимизации. Общая постановка задач оптимизации и основные положения.
В 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.) Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

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

Что можно изменять, чем можно управлять при
решении задачи?
Формализация задачи оптимизации
1. Определяем искомые переменные:
- Что нужно найти?
2. Определяем допустимое множество:
Какие есть ограничения на выбранные переменные?
3. Определяем целевую функцию:
Что является показателем качества решения?
Как этот показатель зависит от выбранных
переменных?

Формализация задачи оптимизации

Формализация задачи оптимизации

Формализация задачи оптимизации

Общая постановка задачи оптимизации
Постановка задачи оптимизации содержит
В векторной форме
- прямые ограничения
- функциональные ограничения

Примеры постановок задач оптимизации
Площадь поверхности сферы равна . Какова высота
цилиндра наибольшего объема, вписанногов эту сферу?
Обозначим высоту цилиндра AD=h, OB=R.
По условию
Из
Объем цилиндра
По смыслу задачи

Вблизи h=3 производная меняет знак с “+” на “-”,
значит при этой высоте объем цилиндра будет наибольшим
Аналитическое решение задачи оптимизации
Производная

Модель старинной русской задачи
Пошла баба на базар, на людей посмотреть, да кое-что продать. Сколько надо взять бабе на базар для продажи живых гусей, уток и кур, чтобы выручить как можно больше денег, если она может взять товара не более Р килограмм и известно, что:
масса одной курицы – b1 кг, стоимость – с1 руб.;
масса одной утки – b2 кг, стоимость – с2 руб.;
масса одного гуся – b3 кг, стоимость – с3 руб.
x – длина стороны квадратов, вырезаемых по углам листа жести
Модель
Модель

Примеры задач оптимизации
1. Завод выпускает три типа деталей А, В и С. Детали каждого типа можно изготовить на любой из двух имеющихся на заводе производственных линий, но расходы на работу каждой линии зависят от типа производимой на ней детали. На завод поступил заказ на производство 50 деталей А, 40 деталей В и 15 деталей С со сроком выполнения 10 суток. Необходимо составить такой план загрузки линий, чтобы суммарные затраты завода были минимальными. Данные по производительности линий и затратам на производство в зависимости от типа деталей приведены в таблице.

2. Студент Коля любит ходить по ночным клубам и в то же время получать зачеты. Предельные полезности ночи в клубе и зачета известны и постоянны. Однако Коля обладает известным ограниченным бюджетом и ему приходится распределять его на клубы и репетиторов, так как сам Коля подготовиться не может. Если Коля днем занимается, то ночью он спит; если он ночью в клубе, то днем он заниматься не может. Стоимость одной ночи в клубе и одного дня с репетитором известны. Коля также не может выносить более определенного количества клубов в неделю, так как он начинает себя плохо чувствовать, и не может нанимать сверх определенного числа репетиторов в неделю, так как ему становится скучно. Определите, сколько суток в неделю Коле необходимо уделить клубам и сколько – подготовке к зачетам, чтобы максимизировать свою полезность.
3. Девушка решила похудеть и выбрала модную диету, в которой разрешено питаться только двумя продуктами P и Q (овсянка и творог). Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q - 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q - 25 руб. В какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

Общая постановка задачи оптимизации
Постановка задачи поиска минимума функции содержит

Основные положения задачи оптимизации
Замечания
2) Глобальный экстремум всегда является одновременно локальным, но не наоборот.

Основные положения задачи оптимизации

Разрешимость задачи оптимизации
Теорема Вейерштрасса
Следовательно, задача оптимизации разрешима, если
выполняются следующие три условия:
1. Множество допустимых решений замкнуто;
2. Множество допустимых решений ограничено;
3. Целевая функция непрерывна на допустимом множестве.

Вопросы для проверки знаний
Предмет и история развития методов оптимизации.
Общая постановка задач оптимизации и основные положения.
Теорема Вейерштрасса о достижении нижней грани функции на множестве.

НЕОБХОДИМОЕ УСЛОВИЕ ЭКСТРЕМУМА
2-ОЕ ДОСТАТОЧНОЕ УСЛОВИЕ ЭКСТРЕМУМА
1-ОЕ ДОСТАТОЧНОЕ УСЛОВИЕ ЭКСТРЕМУМА
Методы безусловной минимизации
функций одной переменной

Методы безусловной минимизации
функций одной переменной
Правило исследования функции на экстремум

Пример
Методы безусловной минимизации
функций одной переменной

Методы безусловной минимизации
функций одной переменной

Прямые методы одномерного поиска
Задача
Минимизировать функцию одной переменной f(x)
при условии , то есть найти
такую что для .
Интервал называется интервалом неопреде-
ленности; функция f (x) называется минимизирующей
или целевой функцией.
Поскольку задачи максимизации и минимизации легко
преобразуются одна в другую, то в дальнейшем будем
рассматривать только задачи минимизации.

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

Определение
Функция f(x), заданная в выпуклой области Q,
называется выпуклой или вогнутой в этой области,
если для любых двух точек и для любого
числа выполняется неравенство
-для выпуклой функции;
-для вогнутой функции.
Прямые методы одномерного поиска
Определение
Если неравенства (1) выполняются как строгие, то
функция f(x) называется строго выпуклой (вогнутой).
(1)

Определение
Функция f(x), определенная на непустом выпуклом
множестве X, называется квазивыпуклой, если для
любых двух точек и для любого
числа выполняется неравенство
Прямые методы одномерного поиска
(2)
Функция f(x) называется квазивогнутой,
если – f(x) – квазивыпуклая функция.
Определение
Если неравенство (2) выполняется как строгое,
то функция f(x) называется строго квазивыпуклой.

Определение
Прямые методы одномерного поиска
Другими словами функция f(x) является унимодальной в данной области,
если в этой области имеет единственный экстремум, с увеличением x слева от x* она монотонно убывает, справа – монотонно возрастает
Графики унимодальных
функций

Теорема
f(x)-унимодальна или выпуклая или строго квазивыпуклая
в интервале . Пусть такие, что .
Если , то для любого .
Если , то для любого .
Прямые методы одномерного поиска
Доказательство
Пусть и .
Предположим, что утверждение теоремы не верно, то есть пусть .
Так как можно представить в виде выпуклой комби-нации точек , то существует такое, что .

Учитывая, что f(x) строго квазивыпуклая функция, имеем .
Но это противоречит утверждению, что .
Полученное противоречие доказывает теорему.
Аналогично доказывается второе неравенство теоремы.
Ч.Т.Д.
МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ
Метод половинного
деления
Метод «золотого»
сечения
Метод Фибоначчи

Стратегия поиска минимума функции одной переменной
Методы исключения отрезков

Выбор начального интервала неопределенности

Выбор начального интервала неопределенности

ВЫБРАТЬ
-
Метод половинного деления
НАЧАЛО
КОНЕЦ
+
+
-

1 [0,5,2]
2 [2,5999,5,2]
3 [2,5999,3,90005]
4 [2,5999,3,250075]
5 [2,9248875,3,250075]
6 [2,9248875,3,08758125]
7 [2,9248875,3,006334375]
8 [2,9655109375,3,006334375]
9 [2,98582265625,3,006334375]
10 [2,995978515625,3,006334375]
11 [2,995978515625,3,0012564453125]
12 [2,99851748046875,3,0012564453125]
13 [2,99978696289063,3,0012564453125]

Метод половинного деления
ЗАМЕЧАНИЕ
ПРИМЕР

ВЫБРАТЬ
-
Метод золотого сечения
НАЧАЛО
КОНЕЦ
+
+
-

1 [0,5,2]
2 [1,98622325850055,5,2]
3 [1,98622325850055,3,97244651700109]
4 [2,74489303400219,3,97244651700109]
5 [2,74489303400219,3,50356280950383]
6 [2,74489303400219,3,21377674149945]
7 [2,92399067349508,3,21377674149945]
8 [2,92399067349508,3,10308831298797]
9 [2,92399067349508,3,03467910200656]
10 [2,96626989102515,3,03467910200656]
11 [2,96626989102515,3,00854910855523]
12 [2,98241911510389,3,00854910855523]
13 [2,99239988447649,3,00854910855523]
14 [2,99239988447649,3,00238065384909]
15 [2,99621219914295,3,00238065384909]
16 [2,99856833918263,3,00238065384909]
17 [2,99856833918263,3,00092447922231]
18 [2,99946830459553,3,00092447922231]
«Золотым сечением» отрезка называется деление отрезка на две части так, что отношение длин всего отрезка к длине больше части равно отношению длин большей части к меньшей
Золотое сечение отрезка производит две симметрично расположенные точки

Метод золотого сечения
ЗАМЕЧАНИЕ
ПРИМЕР

ВЫБРАТЬ
-
Метод Фибоначчи
НАЧАЛО
КОНЕЦ
+
+
-
-
+
-

1 [0,5,2]
2 [1,98622320768662,5,2]
3 [1,98622320768662,3,97244652899663]
4 [2,74489298777015,3,97244652899663]
5 [2,74489298777015,3,50356281125395]
6 [2,74489298777015,3,21377673233568]
7 [2,92399063683997,3,21377673233568]
8 [2,92399063683997,3,1030882961552]
9 [2,92399063683997,3,03467907935246]
10 [2,96626985863631,3,03467907935246]
11 [2,96626985863631,3,00854908285127]
12 [2,9824190848553,3,00854908285127]
13 [2,99239985570846,3,00854908285127]
14 [2,99239985570846,3,00238062713257]
15 [2,99621217106099,3,00238062713257]
16 [2,99856831156195,3,00238062713257]
Метод Фибоначчи основан на последовательности Фибоначчи, которая определяется следующим образом:

Метод Фибоначчи
НЕДОСТАТКИ
ПРИМЕР
1) Надо хранить избыточный набор чисел Фибоначчи либо многократно генерировать числа по мере необходимости; необходимость предварительной оценки требуемого числа итераций;
2) Метод Фибоначчи нелегко приспособить к часто используемому критерию останова, требующему, чтобы значения функции на окончательном интервале неопределенности разнились на величину меньше заданной погрешности

-
СХОДИМОСТЬ
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Метод Фибоначчи
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Характеристика относительного уменьшения начального интервала
неопределенности находится по формуле
N – количество вычислений функции
Метод золотого сечения
Метод половинного деления

Сходимость

Метод Ньютона
Выберем начальную точку
Достаточное условие надежной работы метода Ньютона
Замечание

Метод Ньютона
Сходимость

Метод Ньютона
НАЧАЛО
КОНЕЦ
+
-

ПРИМЕР

1 [0,5,2]
2 [3,03124946640485,3,46538461538462]
3 [3,00016107700165,3,03124946640485]
4 [3,00000000432407,3,00016107700165]

Программная реализация

Вывод
Точное решение

Работа: «Методы одномерного поиска»
Ознакомиться с методами одномерного поиска. Сравнить
различные алгоритмы по эффективности на тестовых примерах.
ЦЕЛЬ РАБОТЫ
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
ВАРИАНТЫ
ТЕСТОВЫХ
ЗАДАНИЙ
СОДЕРЖАНИЕ ОТЧЕТА
титульный лист; цель работы; задание;
таблицы с результатами исследований по каждому методу, где должны быть отражены границы и длины интервалов на каждой итерации; соотношение длины интервала на k +1 итерации к длине интервала на k итерации;
график зависимости количества вычислений целевой функции от логарифма задаваемой точности; - выводы по всем пунктам задания.

Вопросы для проверки знаний
- Определения отрезка, выпуклого множества, выпуклой (строго выпуклой) функции, квазивыпуклой (строго квазивыпуклой) функции, унимодальной функции.
- Прямые методы минимизации функций одной переменной. Теорема о сокращении интервала неопределённости.
- Метод половинного деления для решения задач минимизации функции одной переменной: идея метода, геометрическая интерпретация, алгоритм, пример.
- Метод золотого сечения для решения задач минимизации функции одной переменной: идея метода, геометрическая интерпретация, алгоритм, пример.
- Метод Фибоначчи для решения задач минимизации функции одной переменной: идея метода, геометрическая интерпретация, алгоритм, пример.
- Метод Ньютона для решения задач минимизации функции одной переменной: идея метода, геометрическая интерпретация, алгоритм, пример.

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