методы решения задач безусловной оптимизации (1006295)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Билет 54: методы решения задач безусловной оптимизации.

В общей постановке задача оптимального проек­тирования представляет собой задачу математического программи­рования. Если отсутствуют ограничения на значения управляемых параметров, то имеем задачу безусловной оптимизации (или зада­чу на безусловный экстремум).

Классический метод, основанный на необходимом и достаточном условиях экстремума

Классический метод нахождения безусловного экстремума функции f(X) можно использовать, когда известно ее аналитиче­ское выражение и она по крайней мере дважды дифференцируе­ма по X.

Градиентом функции f(X) в произвольной точке называется вектор первых частных производ­ных f(X) по всем в этой точке X :

Матрицей Гессе А (X ) функции f(X) в точке X' называется симметрическая матрица размером n х п частных производных второго порядка функции f(X) в точке X' :

Необходимое условие экстремума функции f(X) в точке X' имеет вид:

или в скалярной форме:

(1)

Точки X' , в которых выполняется (1.3), называются стационарными. Точка X* экстремума (минимума или максимума) обязательно является стационарной точкой, но стационарные точки – не обязательно точки экстремума (точки перегиба).

Классический метод нахождения безусловного экстремума функции состоит в формировании на основе необходимого усло­вия экстремума системы уравнений (1.4) для поиска стационарных точек исследуемой функции, решении данной системы и в выявлении точек минимума и максимума среди стационарных то­чек на основе использования достаточного условия экстремума.

Достаточным условием максимума функции f(X) в точке X ' является отрицательная определенность матрицы Гессе А (X*) этой функции в точке X* , а достаточным условием мини­мума — положительная определенность А (X* ).

По теореме Сильвестра матрица Гессе A(X*) будет положи­тельно определенной, если для всех ее определителей c первого до n-го порядка выполняются условия:

и отрицательно определенной, если < 0 при нечетных j и > 0 при четных j .
Отсюда следует, что если вес определители > 0 , то X * — точка минимума; если знаки определителей чередуются, начиная с отрицательного, то X* точка максимума.

Отметим, что

где D _ik — алгебраическое дополнение элемента ; — до­полнительный минор, получающийся из определителя вычеркиванием строки i и столбца к.

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

В случае, когда точное решение системы уравнений (1) най­ти трудно, применяют приближенные численные методы ее реше­ния. К ним относят метод Ньютона, который обеспечивает быст­рую сходимость, но имеет трудность выбора начального прибли­жения, гарантирующего сходимость.

Итерационный алгоритм нахождения стационарных точек по методу Ньютона состоит в следующем.

1. Находим .

2. Выбираем начальную точку и точность решения , находим f(X^{0)) .

3. Формируем систему уравнений относительно неизвестных и

1. Примем к= 0 .

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

3. Решая данную систему, определяем Т^(к)

4. Находим и

5. Если , тогда примем k= к+ 1 и переходим к п. 5, иначе к п.9.

9. Конец алгоритма.

Общий алгоритм решения задач безусловной оптимизации с помощью итерационных методов поиска безусловного экстремума

Существует две группы таких итерационных методов:

1. градиентные методы;

2. методы случайного поиска.

Основными в первой группе являются следующие методы:

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

- сопряженных градиентов.

Во второй группе выделяют следующие основные методы.

- с возвратом на неудачном шаге;
- наилучшей пробы;

- с обучением.

Общий алгоритм решения задач безусловной оптимизации помощью итерационных методов состоит в следующем:

1. Выбираем начальное приближение и точность решения , принимаем к = 0 .

2. Определяем направление поиска экстремума на итерации к.

3. Выбираем величину шага в направлении поиска.

4. Вычисляем

5. Рассчитываем и дополнительно для градиентных методов вектор и его норму

6. Если выполняется критерий завершения поиска экстрему­ма, то переходим к п. 7, иначе принимаем к= к + 1 и переходим к п. 2.

7. Конец алгоритма.

Критерием завершения поиска экстремума служит:

1) для градиентных методов ;

2) для методов случайного поиска ;

последний критерий означает, что на протяжении трех итерации значение функции практически не изменяется.

Итерационные методы отличаются между собой тем, как вы­бираются направление и шаг поиска экстремума. Особенности этого выбора в шести перечисленных методах будут рас смотрены ниже.

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

Направление градиента есть направление наибыстрейшего возрастания функции f(x) в точке X. Поэтому за направление поиска максимума на итерации к принимаем , а минимума . В обоих случаях шаг – достаточно малое положительное число.

На каждой итерации к следует проверять выполнение усло­вия:

при поиске минимума ,

(1.11)
при поиске максимума.

В противном случае надо уменьшить значение h, иначе итерационный процесс может быть расходящимся или зацикливаться.
В общем случае при невыполнении на (k_s + 1)-й итерации (s= 1 , 2 , ... ) условия выбираем шаг в направлении поиска экстремума на итерации к следующим образом:

h ^{к) = h = const при ,

h ^{к) = = const(s) при , s=1,2,…, где h> (s=1,2,…) и данные константы выбираются (путем их уменьшения с ростом s) так, чтобы выполнялось условие.

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

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

, где , .

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

Направление градиента и антиградиента функции f(X) в любой точке перпендикулярно касательной к поверхности (при п = 2 к линии) постоянного уровня функции в этой точке. Такой поверхностью (линией) называется поверхность (линия), на которой значение функции постоянно. На рис. изображены линии постоянного уровня функции (v= 1 ,4 причем с ₁> с₂> с ₃ > с₄ ). выбранная начальная точка Х⁽⁰⁾ и полученные в соответствии с методом градиентного спуска первые три точки Х^(К) при поиске минимума f(x). При этом каждая следующая точка расположена на расстоянии от предыдущей.

Методы наискорейшего спуска и сопряженных градиентов

Расчетная формула для направления поиска экстремума в методе наискорейшего спуска имеет тот же вид, что и в методе градиентного спуска: ,где «+» используют при поиске максимума, «-» при минимуме.
В методе сопряженных градиентов при вычислении направления g^(k) учитывается предыстория поиска экстремума:

где =0. Отметим, что при к=0 данная формула совпадает с формулой для в методе наискорейшего спуска.

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

В обоих рассматриваемых методах в отличие от метода градиентного спуска шаг в направлении поиска экстремума выбираем оптимальным на каждой итерации к, т.е. не равно const. Рассмотрим два способа определения оптимального шага

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

На каждой итерации к получаем выражение для в виде функции от :

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

(1.13)

причем в качестве экстремума будет минимум функции при поиске минимума функции f(X) и максимум - при максимуме f(X).

Для решения задачи (1.13) используется классический метод, основанный на необходимом условии экстремума: Для решения задачи используется классический метод, основанный на необходимом условии экстремума и достаточном условии минимума и максимума , где - производная порядка v функции z по в точке .

Если , то исследуются производные более высокого порядка. Достаточным условием экстремума будет четный порядок v (v=4,6,…) первой встречающейся ( наиболее низкого порядка) производной , не равной 0, и при >0 достигается минимум z в точке , а при <0 – максимум.

2. Приближенный способ

Это способ нахождения оптимального шага или многократного деления или умножения шага на дробное положительное число

Алгоритм определения на каждой к-ой итерации значений и при поиске минимума f(X) состоит в следующем:

1. Принимаем = .

2. Вычисляем и определяем f(x).

3. Если f(x) , то , где (для способа половинного деления или умножения шага принимаем за 0.5)

Пп. 2 и 3 алгоритма повторяем до тех пор, пока не будет выполнено условие f(X)<f(x^{k)) Тогда примем X^{k+1)=X и переходим на п. 5. (Слишком большой шаг приводит к расходящемуся процессу при поиске экстремума, поэтому шаг уменьшают до того значения, при котором обеспечивается сходимость процесса поиска минимума).

4. Если f(X)<f(x^{k)), то . Запоминаем предыдущее значение X: X'=X. Вычисляем новое значение и f(X).

II. 4 повторяется до тех пор, пока не выполнится условие f(x) , тогда в качестве Х^{к+1} берем предыдущее значение: Х^(К+1)= Х'. (Слишком маленький шаг приводит к недостаточной скорости сходимости процесса поиска экстремума (большому числу итераций), поэтому шаг увеличивают до тех пор, пока процесс поиска минимума остается сходящимся).

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов ответов (шпаргалок)