Теорема 9 (критерий Сильвестра).




1. Для того, чтобы матрица Гессе была положительно определена в точке и точка являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:

/

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

Положительная (отрицательная) определенность матрицы Гессе может быть проверена также с помощью ее собственных чисел. Пусть - собственные числа матрицы Гессе в точке .

Теорема 10.

1. Для того, чтобы матрица Гессе была положительно определена в точке и точка являлась точкой локального минимума, необходимо и достаточно, чтобы

/

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

.

 

2.3. Классификация численных методов поиска экстремума функции нескольких переменных без ограничений

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

1. Функция может не иметь непрерывных частных производных до второго порядка включительно.

2. Решение системы может представлять трудоемкую, а иногда и неразрешимую(аналитически) задачу.

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

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

При этому

(2.8)

-начальная точка, - текущая точка, приемлемое направление в точке (направление спуска), величина шага в направлении из точки .

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

1. Методы нулевого порядка, использующие только информацию о значении функции . К методам нулевого порядка относятся: метод покоординатного спуска, метод Хука и Дживса, метод деформируемого многогранника(Нелдера-Мида) и другие.

2. Методы первого порядка, использующие информацию о первых частных производных. Эти методы часто называют градиентными. К ним относятся: метод наискорейшего спуска, метод сопряженных градиентов (Флетчера и Ривса), метод Давидона-Флетчера-Пауэлла и ряд других.

3. Методы второго порядка, требующие для реализации знание вторых производных. К ним относятся методы Ньютона и Ньютона-Рафсона.

Работоспособность метода еще не гарантирована доказательством сходимости соответствующей последовательности. Нужна определенная скорость сходимости. Следует заметить, что на практике общую теорию сходимости нужно использовать с большой осторожностью. Нельзя оценивать алгоритм только по величине теоретической скорости сходимости генерируемых им последовательностей, так как условия, при которых они достижимы, реализуются довольно редко. Точно также нельзя пренебрегать алгоритмом лишь по той причине, что теоремы о скоростях сходимости для него не доказаны. Это может объясняться и низким качеством метода, но и не исключено, что доказательства нет просто потому, что провести его сложно.

Определение 14. Последовательность называется сходящейся с порядком сходимости , если - максимальное число, для которого выполнены неравенства:

(2.9)

При этом называется асимптотической скоростью сходимости., а c – асимптотическим параметром ошибки.

 

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

Линейная сходимость – это сходимость со скоростью геометрической прогрессии.

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

1. Функция Розенброка:

(2.10)

- глобальный минимум.

2. Функция Пауэлла:

(2.11)

- глобальный минимум.

3. двумерная экспоненциальная функция:

(2.12)

 

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

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

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

После этого переходим ко второй координате и делаем для нее все тоже самое.

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

При этом есть модификации метода, когда шаги по каждой координате одинаковы и когда эти шаги разные. Мы рассмотрим второй случай, так как первый является частным случаем второго.

Введем обозначения - единичные орты по каждой координате.

Приведем алгоритм метода покоординатного спуска.


Алгоритм

1. Задать: начальную точку ;точность ;шаги по координатам

;коэффициент уменьшения ;

2. а) Если то ;

б) Если то ;иначе

в) ;

3. Если ; то ; на 2; иначе

4. Если то на 2;иначе

5. Если ; то ;конец; иначе

Если то на 2

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

 

2.5. Метод Хука и Дживса(метод конфигураций)

Метод Хука и Дживса представляет собой комбинацию исследовательского поиска(реализованной в методе покоординатного спуска) и ускоряющего поиска по образцу. Исследовательский поиск ориентирован на выявление локального поведения целевой функции и определения направления убывания ее вдоль «оврагов». Полученная информация используется при поиске по образцу при движении вдоль «оврагов».

Алгоритм

1.Задать: начальную точку ;точность ;шаги по координатам

;коэффициент уменьшения ;коэффициент ускорения ;

2.Осуществить исследовательский поиск

а) Если то ;

б) Если то ;иначе

в) ;

3. a)Если ; то ; на 2; иначе

б) Если то на 4;иначе

на 5.

4. Провести поиск по образцу.

на 2.

5. Если ; то ;конец; иначе

Если то на 2

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

Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом, то есть направлением противоположным градиенту в данной точке. Поиск шага в этом направлении осуществляется с помощью одного из методов одномерной минимизации. В простейших случаях можно использовать классический подход, но, как правило, приходится использовать численный метод. Обычно в качестве такового выбирают метод «золотого» сечения.

Алгоритм

1.Задать: начальную точку ;точность ;

2.Вычислить ; ;

3.Если , то ;конец;иначе

4. Находим

5.

6. переход на 2.

Теорема 10. Пусть функция дифференцируема и ограничена снизу на пространстве а ее градиент удовлетворяет условию Липшица

. (2.13)

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

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

 

2.7. Метод Флетчера-Ривса

Метод Флетчера и Ривса (Fletcher R.,Reeves C.M.) основан на том, что для квадратичной функции переменных одномерных поисков вдоль взаимно сопряженных направлений позволяет найти минимум.

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

Алгоритм

1.Задать: начальную точку ;точность ; ;

2.Вычислить ; ;

3. Находим

4.

5.

6..Если , то ;конец; иначе

7. , где

8. переход на 3.

Замечание 1. Для квадратичной функции метод Флетчера-Ривса является конечным и сходится за число шагов, не превышающих . В этом случае говорят, что метод имеет свойство квадратичного окончания.

Замечание 2. Часто используется модификация метода, принадлежащая Полаку и Рибьеру:

(2.15)

Теорема 11. Пусть функция дифференцируема и ограничена снизу на пространстве , а ее градиент удовлетворяет условию Липшица

.

Тогда при произвольной начальной точке последовательность точек , построенная методом Флетчера-Ривса (в том числе в модификации Полака-Рибьера), обладает свойством .

2.8. Эвристический выбор начального интервала одномерной
минимизации

В предыдущих алгоритмах поиск оптимального шага на каждой итерации производился с помощью методов одномерной минимизации. При этом, если использовать численный метод (например, метод «Золотого» сечения), то требуется для запуска этого метода задание начального интервала. В то же время нам требуется найти , где .Таким образом, возникает задача – указать верхнюю границу интервала изменения переменной . Рассмотрим алгоритм Свена(Swann W.H.), решающий эту задачу.

Алгоритм

1. Задать параметры: начальная точка ;начальный шаг ;

2. Вычислить функцию в трех точках ;

3. Проверить условие окончания:

a) если и то , конец; иначе

б) если и то функция не унимодальна, конец; иначе

в)

4.

5.Если то ; переход на 4; иначе ;

В результате работы алгоритма получим начальный интервал


2.9. Метод Давидона-Флетчера-Пауэлла

Метод Давидона-Флетчера-Пауэлла (Davidon W.C.,Fletcher R., Powell M.J.D) на построении последовательности положительно определенных матриц в пределе сходящихся к матрице, обратной матрице Гессе, которые позволяют определить направление поиска на каждом шаге.

Алгоритм

1.Задать: начальную точку ;точность ; ;

2.Вычислить ; ;

3. Находим

4.

5.

6. Находим

7..Если , то ;конец; иначе

8. ,

9. где ;

10. переход на 3.

 

 

Теорема 12 (Флетчера-Пауэлла). Матрицы построенные алгоритмом ДФП являются симметрическими и положительно определенными.

 

Теорема 13. Пусть функция дифференцируема и ограничена снизу на пространстве , а ее градиент удовлетворяет условию Липшица

.

Тогда при произвольной начальной точке последовательность точек , построенная методом Давидона-Флетчера-Пауэлла обладает свойством .

2.10. Методы Ньютона и Ньютона-Рафсона.

Пусть функция дважды непрерывно дифференцируема в окрестности точки . Тогда

 

Обозначим через

Найдем экстремум данной квадратичной функции.

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

(2.18)

Приведем алгоритм метода Ньютона.

Алгоритм

1.Задать: начальную точку ;точность ; ;

2.Вычислить ;

3..Если , то ;конец; иначе

4. Находим матрицу Гессе . Находим матрицу, обратную матрице Гессе .

5.

6. Переход на 2.

Сходимость данного алгоритма сильно зависит от выбора начальной точки

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

Алгоритм

1. Задать: начальную точку ;точность ; ;

2. Вычислить ;

3. Если , то ;конец; иначе

4. Находим матрицу Гессе . Находим матрицу, обратную матрице Гессе .

5.

6. Находим

7.

8. Переход на 2.

Теорема 14. Пусть функция дважды непрерывно дифференцируема и сильно выпукла на пространстве с константой , а ее матрица Геесе удовлетворяет условию Липшица

.

Начальная точка такова, что

Тогда последовательность точек , построенная методом Ньютона(в том числе в модификации Рафсона), сходится к точке минимума с квадратичной скоростью.

 

2.11. О методе наименьших квадратов

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

x x1 x2 xN
y y1 y2 yN

Предположим, что функция зависит от нескольких параметров:

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

То есть:

Таким образом, получили задачу минимизации функции нескольких переменных без ограничений.

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

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


Глава 3. Многомерная оптимизация с ограничениями

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

Рассмотрим задачу

(3.1)

Где функции непрерывно дифференцируемые функции нескольких переменных, ограниченные в некоторой области .

Рассмотрим обобщенную функцию Лагранжа:

(3.2)

Теорема 15. Пусть точка локального экстремума функция при ограничениях . Тогда существует нетривиальный набор множителей Лагранжа , то есть , такой, что

(3.3)

Заметим, что система 3.3 линейно однородно относительно множителей Лагранжа . Это значит, что если вектор удовлетворяет системе, то ей удовлетворяет и вектор . Поэтому остается одна степень свободы. При этом возникает 2 случая

1.

2. . В этом случае для удобства берут .

Определение 17. Точка условного экстремума называется регулярной, если среди наборов множителей Лагранжа существует набор с

Определение 18. Дифференциалом второго порядка для функции Лагранжа в точке мы будем называть

(3.4)

Теорема 16.(достаточные условия существования условного экстремума.) Пусть имеется точка , удовлетворяющая системе (3.3) при условии

. Если в этой точке , то точка является точкой условного локального минимума.

 

3.2 Нелинейное программирование

Рассмотрим задачу

(3.5)

Перейдем от неравенств к равенствам, применив прием Валлентайна:

Рассмотрим обобщенную функцию Лагранжа

(3.6)

(3.7)

(3.8)

Из последнего соотношения, имеем

(3.9)

 

Из 3.8 и 3.9 получаем так называемые условия дополняющей нежесткости:

(3.10)

Теорема 17. (Каруша-Джона) Пусть точка - точка условного локального минимума задачи 3.5. и функции , непрерывно дифференцируемы в окрестности точки . Тогда существует нетривиальный набор для которых выполняются условия.

(3.11)

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

Дальнейшее исследование, так же как и ранее проводится с помощью дифференциала второго порядка для функции Лагранжа. Так же как и в классическом случае в нелинейном программировании важно рассмотрение регулярного и нерегулярного случаев.

 

3.3 Классификация численных методов многомерной оптимизации при наличии ограничений

Снова рассмотрим задачу

(3.5)

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

I. Методы, использующие преобразование задачи условной оптимизации в последовательность задач безусловной оптимизации путем введения вспомогательных функций (чаще всего штрафных функций).

II. Методы непосредственного решения задачи условной оптимизации, основанные на движении из одной допустимой точки, где выполнены все ограничения, к другой допустимой точке с лучшим значением целевой функции. Эти методы часто называют методами возможных направлений.

Основная идея методов первой группы состоит в том, чтобы аппроксимировать исходную задачу условной оптимизации некоторой вспомогательной задачей, решение которой менее сложно, чем решение исходной. Если ограничиться одной вспомогательной задачей, можно получить лишь приближенное решение, причем иногда приближение не слишком хорошее. Если же использовать последовательность задач, в определенном смысле «сходящихся» к исходной, то искомое решение в большинстве случаев окажется пределом соответствующей последовательности приближенных решений. Идея преобразования задачи с ограничением в последовательность задач без ограничений связана с наличием эффективных и надежных численных методов безусловной оптимизации.

В рамках единой методологии можно выделить несколько подходов.

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

 

Определение 19. Последовательность называется последовательностью внешних штрафных функций, если:

1.

2.

3.

4.

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

Определение 20. Последовательность называется последовательностью внутренних штрафных функций(барьерных функций), если:

1.

2.

3.

Где - все внутренние точки множества , а - граница множества .

Мы будем предполагать, что множество ‑ замкнуто и Ø.

Третий подход связан с добавлением штрафов не к целевой функции, а к ее функции Лагранжа. Такие методы называют методами множителей Лагранжа.

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

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

Последовательность точек строится так:

/

К данной группе методов относятся метод проекции градиента и метод возможных направлений.

Определение 21. Ненулевой вектор называется возможным направлением в точке Ошибка! Объект не может быть создан из кодов полей редактирования., если .

 

3.4 Метод внешних штрафных функций

Будем предполагать, что дважды непрерывно дифференцируемая функция. Рассмотрим задачу:

(3.5)

Рассмотрим вспомогательную функцию

- штрафная функция, - параметр. Наиболее часто используется следующая штрафная функция:

/ (3.12)

Здесь - срезка. (3.13)

Штрафная функция обладает свойством:

, если нарушаются ограничения.

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

 

Алгоритм

1.Задать: начальную точку ;точность ; ; ;

2. Составить вспомогательную функцию , где

3. Находим точку безусловного минимума функции с помощью одного из методов безусловной минимизации 0,1 или 2 порядка:

.

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

4. Проверяем условия окончания работы метода:

a) Если , то считаем, что



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-10-11 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: