Градиентные методы. 
Методы оптимизации при проектировании объектов

Метод наискорейшего спуска Рассмотрим grad целевой функции.

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

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

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

Пусть мы выбрали начальное приближение.

Отыскивая наименьшее значение по направлению траектории (наименьшее значение там где происходит касание grad f линии уровня).

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

Траектория

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

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

• 1. — один постоянный член любой точки данной функции является оптимальным — тривиальный случай;
• 2. линейная функция (двучлен)
• (возможно бесконечное уменьшение и увеличение)
• 1 и 2 не подходят для оптимизации

трехчлен.

;

без ограничения общности можно положить что матрица q — симметричная.

Разложим функцию в ряд Тейлора (должно быть 3 члена). Чтобы найти линейный член квадратичной функции, надо взять grad.

;

; С = 0.

Найдем матрицу Гесса (матрица вторых частных производных).

элемент матрицы Гесса является элементом функции Q. (все частные производные высших порядков равны 0).

Функция экстремальна, если grad в данной точке равен 0, следовательно условие экстремальности — система.

Необходимое условие оптимальности:

Если решение данной системы существует и оно единственное (совместная система).

Если решение данной системы существует и оно единственное, т. е. если Q знакоопределена, то существует решение и оно единственное.

Если имеем квадратичную функцию и матрица положительно определена, то линии уровня — эллипсы.

Собственные значения определяют оси эллипсов.

Чтобы определить координаты точки локального минимума, нужно решить систему .

Пусть f (x) — произвольная функция и надо найти точку локального минимума. Разложим функцию в ряд Тейлора в окрестности точки.

Пусть функция не квадратичная, эллипсы примерно отражают кривизну линий уровня и находятся в окрестности точки. В окрестности точки находим приближение и заменяем эту функцию квадратичной функцией, которая получается из разложения в ряд Тейлора. Далее решаем задачу минимизации.

Находим точку минимума и рассматриваем эту точку как следующее приближение и т. д.

Для нахождения точки минимума квадратичной функции (зависит от) необходимо решить систему:

Окончательно следующее приближение .

— формула Ньютона.

(обобщение формулы минимизации одной переменной) Выполнение метода останавливается когда, т. е. когда очень мало. Для получения практической точности достаточно выполнить 4 итерации метода Ньютона.

Если f — хороша, то метод Ньютона подходит, если f — квадратичная функция, то метод Ньютона приводит к минимальной точке за 1 шаг, из любой точки.

Недостатки:

• 1. на каждом шаге итерации надо находить решение системы ;
• 2. С ростом числа итераций Н — разрежается, т. е. большое число членов становится равными 0.

Все формулы безусловной минимизации можно записать в общую схему:

• 1. выбор направления;
• 2. выбор шага.

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

Допустим, требуется f (x)min; - начальное приближение; - текущее приближение.

• а) выбор направления ;
• б) движение вдоль выбранного направления