- •Основные понятия.
- •1. Безусловная оптимизация (многомерные функции)
- •1.1 Методы первого порядка (градиентные методы)
- •1.1.1. Градиентный метод с постоянным шагом
- •1.1.2. Выпуклые функции и множества
- •Теорема
- •Определение.
- •Без доказательства
- •2.Теорема:
- •1.2. Градиентные методы (продолжение)
- •1.2.1. Градиентный метод с дроблением шага.
- •1.2.2. Метод наискорейшего спуска.
- •Без доказательства
- •1.2.3. Масштабирование
- •1.3. Метод Ньютона.
- •1.4. Многошаговые ( двухшаговые ) методы.
- •1.3.1. Метод тяжелого шарика
- •1.3.2. Метод сопряженных градиентов
- •1.3.3. Модификация Полака-Ривьера
- •1.5. Квазиньютоновские методы
- •1.6. Методы нулевого порядка (методы прямого поиска)
- •1.6.1. Методы аппроксимации
- •Метод покоординатного спуска
- •1.6.3. Метод симплексов (Нелдера-Мида)
- •1.6.4. Метод Пауэлла (сопряженных направлений)
- •1.7. Методы прямого поиска в задачах одномерной минимизации.
- •1.7.1. Метод квадратичной интерполяции.
- •1.7.2. Метод дихотомии ( половинного деления.).
- •1.7.3. Метод «золотого» сечения.
- •1.7.4. Метод Фибоначчи.
- •2. Условная минимизация.
- •2.1 Задача нелинейного программирования.
- •2.1.1. Ограничения типа равенства.
- •2.1.2. Ограничения типа неравенств.
- •2.2. Задача выпуклого программирования
- •2.3. Методы условной минимизации.
- •2.3.1. Метод проекции градиента.
- •2.3.2. Метод условного градиента.
- •2.3.3. Метод модифицированной функции Лагранжа.
- •2.3.4. Метод штрафных функций.
- •2.4. Двойственность звп
- •2.4.1. Двойственность злп
- •3. Линейное программирование
- •3.1. Основные понятия
- •3.2. Геометрическая интерпретация злп.
- •3.3. Условие оптимальности для злп.
- •3.4. Базис и базисное решение.
- •3.5. Симплекс - метод решения злп.
- •3.6 Транспортная задача
- •3.5.1. Построение первоначального опорного плана.
- •3.5.2. Построение оптимального плана. Метод потенциалов.
- •4. Решение переборных задач.
- •4.1. Метод ветвей и границ.
- •4.1.1. Задача о коммивояжере.
- •4.2. Динамическое программирование.
- •4.2.1. Абстрактная схема.
- •4.2.2. Вывод уравнения Беллмана.
- •4.2.3. Методика применения функции Беллмана для решения исходной задачи.
- •4.2.4. Примеры задач динамического программирования
- •5. Вариационное исчисление (ви)
- •5.1. Уравнение Эйлера-Лагранжа.
- •5.1.1. Частные случаи уравнения Эйлера-Лагранжа.
- •5.1.2. Задача о брахистохроне.
- •5.2. Вариационные задачи на условный экстремум.
- •5.2.1. Модельные задачи на условный экстремум.
- •6. Принцип максимума Понтрягина ( на примере задачи оптимального управления ).
- •6.1. Принцип максимума в задаче о быстродействии.
- •Список литературы
5.1. Уравнение Эйлера-Лагранжа.
Лемма Дюбуа-Раймона:
Пусть для некоторой функции f, непрерывной на [a, b] , и для всех функций h , непрерывных на [a, b] вместе со своей производной и таких, что h(a) = h(b) = 0
справедливо: ,тогдаf 0 (б/д)
Разложим J((x)) в ряд Тейлора в окрестности точки = 0:
J((x)) = J() + +o()
SJ = -первая вариация функционала.
При фиксированных (x) и (x) функционал зависит от параметра и необходимым условием экстремума функционала является: SJ = 0
Получим необходимое условие экстремума функционала в более конструктивной форме: функционал J, рассматриваемый как функция от , может быть записан в виде:
Тогда необходимое условие экстремума:
== 0
= (по частям) =
т.к.
==0
Это справедливо для любого (x) , дифференцируемого с краевыми условиями:
Отсюда с помощью леммы следует:
- уравнение Эйлера-Лагранжа
Определение: Всякое решение уравнения Эйлера-Лагранжа называется
экстремалью.
Таким образом, функция, доставляющая экстремум функционалу находится среди экстремалей. Уравнение Эйлера-Лагранжа - необходимое условие экстремума.
Одно из достаточных условий локального минимума - условие Лежандра:
Обозначим ,
Уравнение Эйлера-Лагранжа:
Раскроем второй член выражения:
= ++ ( формула дифф-я сложной функции)
Уравнение Эйлера-Лагранжа:
= 0 (*)
( если все производные существуют)
Отсюда следует, что в общем случае уравнение Эйлера-Лагранжа является нелинейным дифференциальным уравнением второго порядка. Поэтому его решение затруднено.
5.1.1. Частные случаи уравнения Эйлера-Лагранжа.
f (x, y) не зависит от производной .
Тогда
= 0 ( уравнение Эйлера-Лагранжа)
f (x, ) не зависит отy:
= 0 0
f (y, ) не зависит отx:
(*) 0\ умножим данное выражение на \
()0
Пример:
5.1.2. Задача о брахистохроне.
Как выбрать профиль горки, чтобы можно было скатиться с неё за минимальное время (трение отсутствует, под действием силы тяжести)?
Перерисуем для удобства рассмотрения :
Здесь V –скорость, - угол наклона горки, g ускорение свободногопадения.
Справедливы следующие соотношения:
dx = V cos j dt (*)
tg j = (x) cos j = (1)
v-? (найдем формулу скорости)
Закон сохранения энергии для решения заданной задачи имеет вид:
= mgy,
отсюда V = (2)
Подставим (1) и (2) в (*), получим:
= dt
Проинтегрируем обе части:
(Т – время спуска шарика.)
Итак, требуется найти функцию y=y(x), минимизирующую указанный выше интеграл.
Отметим, что F зависит от y и , т.е. это третий частный случай уравнения Эйлера - Лагранжа Þ
F –const - уравнение Эйлера-Лагранжа для F(y,Y’).
Вынесем 2g из рассмотрения, т.к. на экстремум оно не влияет
Приведем к общему знаменателю:
Выберем c = const =
тогда : (**)
Это уравнение надо решить. Делаем подстановку:
= tg t \ t- вспомогательная переменная \
Из (**) следует:
Интегрируем:
==
y через x выразить трудно.
Константы берутся из начальных условий.
Полученная кривая называется циклоидой.
График:
Брахистохрона (решение) является локальным минимумом.
Доказано, что это глобальный минимум (>0).