Московский государственный авиационный институт

Московский государственный авиационный институт

Кафедра прикладной информатики

 

Лекции

по дисциплине:

“МЕТОДЫ ОПТИМИЗАЦИИ ”

 

Содержание:

1. Основные понятия

- понятие САПР

- процесс оптимизации

1. Методы одномерной оптимизации

- аналитический способ

- численный способ

1. Методы одномерного поиска

- метод “золотого сечения”

1. Одномерная оптимизация с использованием производных

- метод деление интервала пополам

- метод Ньютона (метод касательной)

1. Безусловная опртимизация
2. Квадратичная аппроксимация (или квадратичное приращение)
3. Методы прямого поиска

- приемущества

- недостатки

1. Метод координатного спуска
2. Градиентные методы

- метод наискорейшего спуска

- анализ метода

- метод Ньютона

- недостатки метода Ньютона

1. Задачи оптимизации с ограничениями – разностями (ЗОР)

- метод исключения

- метод множителей Лагранжа

1. Нелинейное программирование (НЛП)

- методы решения НЛП

1. Задачи линейного программирования (ЛП)

Основные понятия.

САПР – система автоматизированного проектирования. Проектирование сложный процесс, направленный на разработку отдельного объекта.

 

 

Способ уменьшения время проектирования – уменьшение числа разработчиков.

Система – совокупность людей, задач и программ, которые взаимосвязаны друг с другом.

Оптимизация – от латинского слова «оптимус» - наилучший – поиск наилучшего, поиск наилучшего проектного изделия.

 

Процесс оптимизации.

 

Имеется задача. Для решения задачи нужно формализовать объект и представить его в виде математической модели.

 

Модели:

- физические;

- геометрические (фотография, рисунок);

- математические.

 

Математическая модель, та которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией. Модель характеризуется параметрами, которые могут быть и числовыми . Их часть может характеризовать состояние объекта – параметры состояния , а другие могут относиться к процессу проектирования – переменные проектирования .

Определение параметров состояния - задача моделирования. Определение переменных проектирования – задачи проектирования или задачи оптимизации.

 

Допустим имеются 2 переменные . Задавая конкретные значения получаем точку.

R – множество чисел

R

G множество допустимых

вариантов

p₂ допустимое решение

p₁

недопустимое решение – не удовлетворяющее наложенным ограничениям

 

Плоскость множества возможных вариантов, на нее могут быть наложены ограничения.

 

Отображение множества - целевая функция позволяет формировать критерий для сравнения различных решений.

 

2 вида задач оптимизации:

- максимизации;

- минимизации.

 

Для оптимизационного решения задачи требуется:

1. Сформулировать задачу;
2. Построить математическую модель (определить множество переменных);
3. Определить ограничения на возможные решения;
4. Определить целевую функцию. Далее применим формальные математические методы, позволяющие найти решения.

Численные методы.

Пусть функция задана на интервале , при этом существует такая точка , что на – монотонно убывает, а на – монотонно возрастает, то функция унимодальная.

 

 

а b

 

Если из того что следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей.

 

Методы одномерного поиска.

 

Разобьем и вычислим значение функции в каждой точке.

 

искомый минимум

 

В результате остается интервал меньшего размера, к которому применяется тот же метод, и находим еще один интервал, в конце находим интервал с заведомо нужной точкой.

 

Интервал неопределенности – интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение – двумя точками на 3 равных отрезка.

 

 

 

1)

2)

 

- после выполнения n шагов сокращение исходного интервала

- точность с которой надо найти решение задачи.

 

 

N=2n, где n – число шагов, N – число вычислений (мера эффективности данного решения).

 

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

 

Точки должны быть расположены на равном расстоянии.

 

а b

; ; ;

; - золотое сечение.

 

а

 

 

- величина сокращения на каждом шаге

число итераций растет как логарифм функции.

 

Безусловная оптимизация.

 

Целевая функция зависит от нескольких переменных f(х₁, х₂, …, х_n)® min. Т.к. нет дополнительных условий накладывающихся на переменные – безусловная оптимизация.

 

Функции 2-х переменных

 

f(x_1,x₂)

 

 

 

x₂

x₁

 

Условия определяющие точку минимума – необходимо проанализировать поведение функции в некоторой точке.

х₂

 

 

х₂

 

 

Часто под окрестностью подразумевают шар.

 

Рассмотрим вспомогательное построение:

 

 

 

линейное векторное x₃

пространство

(х₁,х₂,х₃)

 

 

x₂

x₁

 

Скалярное произведение векторов , где - длина вектора (норма вектора), - угол между векторами.

 

S

Допустим, что: ,

 

Тогда: ;

 

Допустим, что имеется 2 вектора:

 

 

a

Чтобы задать направление, мы задаем вектор.

 

Нормируем вектор

 

Нормированный вектор имеет тоже самое направление, но , длина.

 

Допустим, что задан нормированный вектор .

отрицательный

Скалярное произведение равно 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. Идет построение в плоскости х₁ и х₂. Берут точку – определяющую значение аргумента. Находят точку в которой функция имеет тоже самое значение, в результате получаем линию в которой функция имеет постоянное значение – изолиния (линия уровня).

х2     х2     х1 х1 - изолиния

z   изолиния     y x

Вектор grad составляет прямой угол с изолинией.

Вернемся к формуле:

 

 

Квадратичная аппроксимация.

(или квадратичное приращение)

 

Линейное отображение:

- линейное отображение, если:

1. свойство аддитивности - ;

2. свойство однородности -

 

Линейное отображение можно задать матрицей:

 

т

; ;

п - основная формула

 

 

1 i

j

 

отображение

2 задачи:

- решение системы уравнений

и обратное отображение – найти х

А^-1 – обратное отображение;

следовательно строки матрицы ортогональны столбцам

другой матрицы

- нахождение собственных значений

 

Используя матрицу можно найти более сложную функцию: - квадратичная форма.

- функция нескольких переменных .

 

Рассмотрим подробнее.

Есть матрица:

- квадратичная форма

 

А и А^/ определяют одну и ту же квадратичную форму следовательно значения этой формы не однозначно. Если по заданной квадратичной форме найдем симметрию, то она будет однозначная.

;

;

Без ограничения общности можно считать, что матрица определяющая квадратичную форму является симметричной.

 

Вернемся к квадратичной форме:

Рассмотрим функцию 2-го порядка:

 

Допустим, что , матрица диагональная.

1.
Эллипсы	Эллиптический парабалоид
2.
3.
Гиперболы	Седло

Допустим, что . Тогда вся картина просто повернется на некоторый угол по оси Z.

 

Рассмотрим п -мерный случай.

Квадратичная форма называется положительно определенной областью если она не отрицательная.

1. , причем обращается в ноль, в том случае если х = 0 (). Этот случай соответствует эллиптическому параболоиду.
2. , .
3. Знаконеопределенность.

соответствует п -мерному эллиптическому гиперболоиду (п -мерное седло)

 

Рассмотрим 2-мерное пространство:

Если квадратная матрица называется положительно определенной, то и матрица положительно определенной.

Рассмотрим разложение функции 2-х переменных в ряд Тейлора:

квадратичная матрица задается матрицей Н

 

матрица составленная из членов 2-го порядка

 

- матрица симметрична

 

Матрица Н – матрица Гесса.

 

- определение матрицы Гесса

 

Если матрица (матрица Гесса) в точке локального экстремума положительно определена, то это точка – локального минимума, если матрица отрицательно определена, то это точка – локального максимума, а если не определена – седловые точки.

 

 

Локальный max или min

 

 

Седловая точка

 

Минимизируем:

Найти частные производные:

1. (grad = 0);

2.

 

Эта система позволяет найти все точки экстремума:

 

те х1 и х2 которые удовлетворяют уравнениям и будет точками экстремума.

 

Допустим, что . Надо составить функцию второго порядка и подставить и посмотреть их.

 

Необходимые условия – помогают охарактеризовать искомую точку:

1. grad f = 0
2. 

 

Н ³ 0 – локальный минимум;

Н £ 0 – локальный максимум;

Н – не определена – седловая точка.

 

Для поиска используют численные методы.

 

Постановка:

Требуется , где х – вектор - т.к. нет ограничений задача безусловной оптимизации.

Есть черный ящик, который по заданным значениям х позволяет вычислить значение функции.

 

 

Методы прямого поиска.

 

Должны задать начальное приближение точки х0; - некоторое приближение полученное после к – итераций; вычислить значение точки в окрестности точки ; Из данных точек выбрать точку в которой функция принимает наименьшее значение, выбираем ее и строим вокруг нее окрестность.

Выбираем точку где хуже. В окрестности существующей точки выбираем точку с меньшим значением, опять в ее окрестности есть точки с меньшим значением и т.д.

 

В таком виде этот метод не эффективен.

Пример:

Шаг по х1 берем больше, а по х2 – сохраняем. Поскольку мы свободны в выборе точек, то можно менять шаг и направление.

Методы:

1. Хука-Дживса;
2. Нелдера-Мида (используется п-1 угольник)

 

Преимущества метода прямого поиска:

1. простота;
2. не нужны производные.

 

Недостатки:

1. плохая сходимость;
2. применим для небольшого числа переменных.

 

п £ 10¸20
	2п точек: в случае 2-х переменных – 4 точки; в случае 3-х переменных – 6 точек.

 

Этот метод применим в простых случаях, когда эти недостатки себя не проявляют.

 

Метод координатного спуска.

 

Существует приближенная точка минимума. Минимизируя функцию по направлению к х1, на прямой используется любой метод одномерной минимизируют, х2 – фиксируют. Далее выполняют одномерную оптимизацию по х2, фиксируя х1.

Этот процесс повторяют до тех пор пока следующая точка не окажется близка к точке приближения.

 

Градиентные методы.

Метод наискорейшего спуска.

 

Рассмотрим grad целевой функции.

Движение по направлению вектора под острым углом будет приводить к уменьшению целевой функции, а движение против направления функции к увеличению целевой функции. Разумно за направление движения принять сам вектор – grad f.

 

 

 

 

 

 

 

 

Для выбора расстояния нужно применить метод одномерной оптимизации. Прекратить поиск, когда величина grad f станет достаточно малой. Этот метод гарантирует, что найдена либо точка локального минимума, либо седловая точка.

 

Анализ метода.

Рассмотрим целевую функцию, которая является квадратичной функцией, точка локального минимума совпадает с точкой начала координат. Пусть мы выбрали начальное приближение. Отыскивая наименьшее значение по направлению траектории (наименьшее значение там где происходит касание grad f линии уровня).

В случае когда масштаб выбирается следующим образом (линии уровня вытянуты).

 

Траектория

 

 

 

Если линии уровня - окружности, то приходим сразу в точку локального минимума.

 

 

Метод Ньютона.

 

1. - один постоянный член любой точки данной функции является оптимальным – тривиальный случай;
2. линейная функция (двучлен)

(возможно бесконечное уменьшение и увеличение)

 

Метод исключения

Численное решение:

точка min должна лежать на прямой.

g(x)

 

 

В каждый момент линия уровня будет касаться прямой эта точка и является точкой

условного локального min. Если в окрестности заданной точки, удовлетворяющей

всем значениям равенства, значение функции больше, чем в точке, то эта точка – есть точка условного локального min.

Пример:

(a,x)=0

 

 

 

 

 

 

Если (a₁x)=b

 

 

 

 

 

Допустим,

Прямая будет проходить через некоторую точку удовлетворяющую условию и

Для n переменных , Ax=b

Рассмотрим i-ое ограничение:

,

- задан x - все вектора, лежащие . Они и составляют гиперплоскость.

При добавлении еще одного условия, уменьшаются размерности. В конечном итоге получится пространство n-m.

 

Для двух переменных возможно 2 случая:

 

1.

2.

 

В случае 2 это не точка минимума, а седловая точка.

 

Рассмотрим точку 3-х переменных:

 

плоскость

Ограничение – плоскость, следовательно, все допустимые точки на плоскости. Если угол grad не равен 90 градусам следовательно можно двигаться дальше. На плоскости существует направление, которое будет составлять острый угол с – grad, и двигаясь в этом направлении можно уменьшить значение f. Если -grad f перпендикулярен плоскости эта точка может быть точкой минимума.

Пусть существует 2 ограничения:

 

 

Рассмотрим опять случай 3-х переменных:

Точка минимума должна принадлежать пересечению плоскостей.

Необходимое условие – вектор антиградиента должен составлять угол 90 градусов с прямой пересечения плоскостей.

Для п -мерного случая имеется п переменных следовательно рассматривая каждое ограничение, получаем п-1 гиперплоскость следовательно рассмотрев т ограничений получим п-т гиперплоскость (т<п).

 

все ограничения независимы

 

Если вектор grad (п -мерный) будет ортогонален п-т – пространству.