- •Оглавление
- •Основные понятия.
- •Процесс оптимизации.
- •2 Вида задач оптимизации:
- •Методы одномерной оптимизации.
- •2 Варианта:
- •2 Способа:
- •Аналитический способ нахождения локального минимума.
- •Численные методы.
- •Методы одномерного поиска.
- •Метод золотого сечения.
- •Одномерная оптимизация с использованием производных.
- •Методы для нахождения корня уравнения функции 1-ой переменной.
- •Метод Ньютона (метод касательной):
- •Обобщение
- •Безусловная оптимизация.
- •Функции 2-х переменных
- •Квадратичная аппроксимация (или квадратичное приращение)
- •Методы прямого поиска.
- •Метод координатного спуска.
- •Градиентные методы. Метод наискорейшего спуска.
- •Анализ метода.
- •Метод Ньютона.
- •1 И 2 не подходят для оптимизации.
- •Недостатки:
- •Задачи оптимизации с ограничениями – разностями (зор)
- •Метод исключения
- •Метод множителей Лагранжа.
- •5 Условий дают систему линейных уравнений Нелинейное программирование (нлп).
- •Задачи линейного программирования (лп).
Безусловная оптимизация.
Целевая функция зависит от нескольких переменных f(х1, х2, …, хn) min. Т.к. нет дополнительных условий накладывающихся на переменные – безусловная оптимизация.
Функции 2-х переменных
f(x1,x2)
x2
x1
Условия определяющие точку минимума – необходимо проанализировать поведение функции в некоторой точке.
х2
х2
Часто под окрестностью подразумевают шар.
Рассмотрим вспомогательное построение:
линейное векторное x3
п ространство
(х1,х2,х3)
x2
x1
Скалярное произведение векторов , где - длина вектора (норма вектора), - угол между векторами.
S
Допустим, что: ,
Тогда: ;
Допустим, что имеется 2 вектора:
Чтобы задать направление, мы задаем вектор.
Нормируем вектор
Нормированный вектор имеет тоже самое направление, но , длина.
Допустим, что задан нормированный вектор .
отрицательный
|
Скалярное произведение равно 0, тогда года прямой.
|
Возвращаемся к функции 2-х переменных:
Отбрасываем члены , приращение будет более точным.
х2
х1
|
|
Вектор - формула Тейлора.
х2
х1
|
Мы рассматриваем как изменяется точка вдоль данного направления. Функция становится функцией одной переменной. - скалярная величина.
|
- производная по направлению (вдоль данного направления)
- направление ряда равное направлению grad ( 0).
grad – вектор, в сторону которого функция изменяется более быстро.
Антиградиент – grad направленный в другую сторону (-grad).
х2 grad f f(x) х2
-grad f
х1 х1
|
Необходимое условие: - локальный минимум (или максимум). Точки локального экстремума.
|
Допустим что мы совершаем малое перемещение . В каком случае (в точке) будет: * больше, чем заданная: тогда, когда угол – острый .
* - если под прямым углом, то не изменяется;
* - если под тупым углом, то приводит к уменьшению функции.
1.
строим поверхности
z
y
x
2. Идет построение в плоскости х1 и х2. Берут точку – определяющую значение аргумента. Находят точку в которой функция имеет тоже самое значение, в результате получаем линию в которой функция имеет постоянное значение – изолиния (линия уровня).
х2
х2
х1 х1 - изолиния
|
z
изолиния
y x |
Вектор grad составляет прямой угол с изолинией.
Вернемся к формуле: