Задачи и методы поисковой однокритериальной оптимизации
создание документов онлайн
Документы и бланки онлайн

Обследовать

Администрация
Механический Электроника
биологии
география
дом в саду
история
литература
маркетинг
математике Физика информатики химия
медицина
музыка
образование
психология
разное
художественная культура
экономика


Задачи и методы поисковой однокритериальной оптимизации

математике


Отправить его в другом документе Tab для Yahoo книги - конечно, эссе, очерк Hits: 824


дтхзйе дплхнеофщ

МОДЕЛИ ПОТРЕБИТЕЛЬСКОГО СПРОСА
Закон распределения вероятностей случайной величины
Скрытые фигуры статико-динамической геометрии
ИНЖЕНЕРНАЯ ГРАФИКА - Рабочая тетрадь для записи лекций для студентов 1 курса заочной формы обучения
Теорема сложения вероятностей несовместных событий
Графика и визуализация данных
СПОСОБЫ ПРЕОБРАЗОВАНИЯ ПРОЕКЦИЙ
Математический анализ функции одной переменной
Обращение матрицы методом Жордана
Элементы комбинаторики
 

Задачи и методы поисковой однокритериальной оптимизации

ВВЕДЕНИЕ В ОПТИМИЗАЦИЮ

ЗНП          Найти  

Классификация оптимизационных задач

Типы

Типы



Функция одной переменной

Линейная функция

Сумма квадратов линейной функций

Сумма квадратов нелинейной функций

Гладкая нелинейной функция

Нелин. Функция с разреженной

матрицей Гессе

Негладкая нелинейная функция

Стохастическая функция

Векторная функция

Ограничения отсутствуют

Простые ограничения

Линейные функции

Линейные функции с разреженной матрицей коэффициентов

Гладкие нелинейные функции

Нелинейные функции с разреженной

матрицей Якоби

Негладкие нелинейные функции

Стохастические функции

Классификация методов решения ОЗ по информации о  и

Сведения из математического анализа

Скалярная функция  -мерного аргумента  называется дифференцируемой в точке , если найдется вектор , такой, что для  выполняется:

.

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

Функция дифференцируема в точке , если она допускает линейную аппроксимацию в этой точке.

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

Скалярная функция  называется дважды дифференцируемой в точке , если она дифференцируема в этой точке и найдется симметричная -матрица , такая, что для  выполняется:

.

Матрица  называется матрицей вторых производных, матрицей Гессе или гессианом и обозначается , .

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

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

Подмножество  в  называется выпуклым, если  для , .

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

Пусть  и  - выпуклые множества в . Тогда множество  - выпукло, где   .

Пусть  - выпуклое множество, , тогда .

Пересечение любого числа выпуклых множеств выпукло.

Векторная сумма  называется выпуклой комбинацией точек , если , , и .

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

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

В конечномерном пространстве выпуклая оболочка множества обладает следующим свойством: любая точка из  представима в виде выпуклой комбинации не более чем  точки из  (теорема Каратеодори).

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

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

Ограничение  называется регулярным на выпуклом множестве , если существует точка , такая, что .

Множество  называют регулярным, если все ограничения , , регулярны на .

Функция  называется выпуклой, если выполняется:

 .

Функция  называется строго выпуклой, если для  выполняется:

 .

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

С определением выпуклой функции тесно связано такое важное свойство: для любого  множество  выпукло.

При построении выпуклых функций, выпуклость которых уже установлена, полезны следующие свойства.

Пусть ,  - семейство выпуклых функций, , тогда  является выпуклой функцией.

Пусть ,  - выпуклые функции. Тогда функция  также выпукла.

Дифференцируемая выпуклая функция обладает следующими свойствами:

- , ,

- вторая производная  положительно определенная,

- функция  имеет только один минимум.

Точка  называется локальным минимумом  на , если найдется , такое, что  , где  - -окрестность точки  ().

Точка  называется глобальным минимумом функции  на , если для   .

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

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

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

.

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

Необходимое условие минимума первого порядка. Пусть  - точка минимума  на  и  дифференцируема в точке . Тогда .

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

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

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

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

Пусть  - точка локального минимума  на , а , ,  - непрерывно дифференцируемы в окрестности  (условие гладкости). Тогда существует ненулевой вектор множителей Лагранжа , , такой, что для функции Лагранжа задачи нелинейного математического программирования:

выполняются условия:

а) стационарности ,    или   ;

б) дополняющей нежесткости , ;

в) неотрицательности , .

Теорема Куна-Таккера:

1. Если  - решение задачи выпуклого программирования, то найдется ненулевой вектор множителей Лагранжа

, такой, что для функции Лагранжа    выполняются условия:

а) принцип минимума для функции Лагранжа:   ;

б) дополняющей нежесткости , ;

в) неотрицательности , .

2. Если для допустимой точки  выполнены условия а) - в) и выполнено условие Слейтера (т. е. существует точка , для которой , ), то  - точка минимума.

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

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

Вопросы.

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

Сформулировать условия минимума в этих задачах. Дать геометрическую интерпретацию условий минимума.

Некоторые примеры задач оптимизации

Задачи идентификации

Статистическая задача оценки параметров

Пусть , - независимая выборка с плотностью распределения . Требуется определить .

Метод максимального правдоподобия -  выбирают так, чтобы максимизировать вероятность реализации :   или ,   (1).

Задание. Убедитесь, что метод макс. правдоподобия для оценки среднего и дисперсии нормального распределения приводит к минимизации

,  

Задачи регрессии

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

Пусть - случайные ошибки, независимы с плотностью вероятности .

Метод макс. правдоподобия  .

Метод наименьших квадратов  (2).

Задание. Показать, что для нормальных ошибок (1) и (2) совпадают.

Анализ данных.

, - вход и выход объекта, - модель объекта.   - мера рассогласования объекта и модели (критерий идентичности).

Найти

.

Задание. Пусть . Найти оценку  для различных  ().

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

.

Задача сводится к  ,  .

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

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Найти       на .

Функция  называется унимодальной на отрезке , если существуют  , такие, что

1) функция  строго монотонно убывает на отрезке ;

2) функция  строго монотонно возрастает на отрезке ;

3)  при .

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

Метод деления отрезка пополам

Пусть функция  унимодальна на отрезке .

Алгоритм

1. Выбрать , вычислить .

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

3. Сравнить  и :

а) если , то , . Перейти к п. 5;

в) если , то перейти к п. 4.

4. Сравнить  и :

а) если , то , . Перейти к п. 5;

в) если , то , . Перейти к п. 5.

5. . Проверить условие останова  . При выполнении условия останова поиск прекратить, за минимум принять точку с минимальным значением функции , иначе перейти к п. 2.

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

Пусть  ‑ число вычислений ,  ‑ длина исходного отрезка ,  ‑ длина отрезка после  вычислений , тогда скорость сходимости метода . К достоинствам метода можно отнести простоту, к недостаткам - низкую скорость сходимости.

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

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

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

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

,   ,   ,   ,   где  - точка золотого сечения.

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

Алгоритм

1. , . Вычислить , .

2. Сравнить значения  и :

а) если  , то  , вычислить значение  и перейти к п. 3;

в) если  , то  , вычислить значение  и перейти к п. 3.

3. . Проверить условие останова  . При выполнении условия останова поиск прекратить, за минимум принять точку с минимальным значением функции , иначе перейти к п. 2.

Скорость уменьшения исходного интервала неопределенности описывается соотношениями:   .

Для метода деления отрезка пополам и золотого сечения можем записать выражения для определения числа вычислений при сокращении исходного интервала неопределенности в  раз:

,   ,   ,   .

Приводимая таблица дает представление о значениях .

7

9

14

20

6

8

11

16

0.1

0.05

0.01

0.001

Метод Фибоначчи

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

,   .

Начальными членами последовательности  будут числа 1, 1, 2, 3, 5, 8, 13. При фиксированном количестве  обращений к процедуре вычисления значений функции  поиск Фибоначчи состоит в просмотре точек, дробящих интервалы неопределенности в отношениях, заданных числами  Если принять длину исходного интервала за , то длиной -го интервала будет , а его оцениваемые внутренние точки будут отстоять от левой границы на  и на, причем в одной из них значение функции  всегда известно из предыдущего шага.

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

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

Метод парабол

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

Алгоритм

1. Выбрать .

2. .

3. Вычислить значения функции , .

4. Если , то  . Если , то  .

5. Вычислить значение функции  и найти

,   .

6. По точкам  вычислить .

7. Проверить выполнение неравенств:

.

При выполнении поиск прекратить, иначе перейти к п. 8.

8. Выбрать наилучшую точку ( или ) и две точки по обе стороны от нее. Обозначить точки в естественном порядке (так, чтобы ) и перейти к п. 5.

Опишем вычисление точки минимума параболы . Пусть заданы  и значения функции в этих точках . Уравнение параболы имеет вид:

,   где    ; ,

;

;   .

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

Для вычисления  нужно по значениям  вычислить значения  и подставить их в выражение для .

Метод стохастической аппроксимации

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

,

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

Поиск минимума осуществляют с помощью рекуррентной процедуры:

,                  (А)

Для сходимости процедуры должны выполняться условия:

, , , , ,   (В)

где  - длина шага (рабочий шаг),  - длина пробного шага.

Данные условия, например, выполняются при   , .

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

,   ,

где последовательности ,  удовлетворяют условиям (В),  

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

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ГЛАДКИХ ФУНКЦИЙ

,  

Схема методов.

Обобщенный алгоритм

1. , выбрать начальную точку .

2. Проверка условий останова. Если условия выполнены, то поиск прекратить, - решение, иначе перейти к п.3.

3. Расчет направления поиска 

4. Расчет длины шага. Определить , обеспечивающее, например, .

5. Пересчет оценки решения. , перейти к п.2.

                        Сходимость схемы.

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

                        Скорости сходимости.

Если  . При - линейная;  при  - сверхлинейная;  при - порядка , Если , то скорость сходимости ниже линейной.

Методы первого порядка.

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

- неравенство Коши-Буняковского

 ,     

 при малом  .

                        Версии градиентного метода

1. Наискорейший спуск.  определяем из

2. Выбор , обеспечивающего выполнение неравенства     (1)  ; выбирают , а затем уменьшают его до  выполнения  (1).

3. Выбор , обеспечивающего выполнение неравенства ,  ()

4. Программная версия. Выбор, удовлетворяющего условиям:   .

    Например, . Нет монотонного убывания  .

5. Если известно значение  , то   .

Критерии останова.

,   ,   .

Скорость сходимости. ,    - ниже линейной

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

Для градиентного метода имеет место оценка: ,    - спектральное число обусловленности матрицы . Например,  (малое уменьшение).

Овражный метод (эвристический).

1. Задают точки .

2. Из точек  совершают один шаг методом наискорейшего спуска, получают точки .

3. .

4. Производят овражный шаг, получают точку:

,

где  - овражный шаг.

5. Из точки  совершают один шаг методом наискорейшего спуска, получают точку .

6. Проверяют условие останова. При выполнении поиск прекращают, запоминают наилучшую точку, иначе , и переходят к п. 4.

Методы второго порядка. Метод Ньютона.

, доступна информация о значениях функции, ее градиента и гессиана:

,   .

Методы второго порядка представимы в виде рекуррентного соотношения:

.

                        Версии метода.

1. Метод Ньютона. Выбор  при  

,

 

и если матрица  невырожденная, то   ,  

2. Выбор , где  - минимальное натуральное число, при котором выполняется неравенство:

,   .

3. Выбор, решая задачу минимизации:   ,   .

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

Сходимость

Для сильно выпуклых функций:   ,  

и начального приближения , для которого    или  

имеет место оценка скорости сходимости (квадратичная):

Вопросы.

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

2. Предложить варианты изменения величины шага в методе оврагов и модифицировать метод для случая многомерного дна оврага.

3. Построить экономичную версию метода Ньютона без вычисления обратного гессиана на каждом шаге.

4. Почему метод Ньютона не сходится из любых начальных условий ?

5. За сколько шагов минимизируется квадратичная функция методом Ньютона, наискорейшим спуском ?

6. Оценить трудоемкость рассмотренных методов.

МЕТОДЫ ПЕРВОГО ПОРЯДКА. КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ

,      ,

где - матрица , метрика;  отражает кривизну функции (накопленную), аппроксимирует обратную матрицу Гессе  .

Рассмотрим разложение в ряд Тейлора в окрестности точки

Линейная оценка кривизны функции  в направлении  определяется скалярным произведением: .

Данное соотношение становится точным, если - квадратичная функция.

Метод квазиньютоновский, если  .

Формула пересчета:  - корректирующая матрица. Требуется, чтобы .

Пусть    или  

Отсюда         - произвольные векторы; имеем семейство решений.

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

       ,

Формула сохраняет симметрию и положительную определенность матриц;

- определяют одномерной минимизацией в направлении

Метод Бройдена-Флетчера-Шенно

Более слабая зависимость от точности одномерного поиска.

Методы переменной метрики

Задано скалярное произведение с матрицей :   - метрика:    

Разложим  в ряд в новой метрике:  ,

где  - градиент в новой метрике.

Градиентный метод:

Если  , то это метод Ньютона.

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

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

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

      

Варианты методов отличаются выбором :

1. Метод Полака-Рибьера   ,

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

Методы можно интерпретировать как градиентный метод с памятью.

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

Для методов выполняются соотношения: .

Рассмотрим минимизацию квадратичной функции: ,

где  - симметричная положительно определенная матрица,  - точка минимума.

1. Пусть - начальная точка. По правилам метода: .

Для полученной точки  выполняются  условия:  .

Если , то имеем гиперплоскость размерности  :   .

Точка  , так как  .

2. По правилам метода  ,   ,   .

Выберем  так, чтобы вектор  был коллинеарен плоскости . Из условия коллинеарности имеем:   .

При полученных   имеют место следующие соотношения:

  , .

Отсюда

.

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

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

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

Поясним термин сопряженность, используемый в названии методов. Векторы  называются сопряженными относительно матрицы , если . Именно сопряженные направления используются в рассмотренных методах.

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

Вопросы.

1. Почему квадратичные функции можно выбирать в качестве основы для построения методов минимизации ?

2. При каких предположениях совпадают шаги методов ДФП, БФШ и методов сопряженных градиентов ?

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

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

5. Зачем нужно перезапускать рассмотренные методы ?

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

7. Нужно ли в методах сопряженных градиентов точное решение задач одномерной минимизации ?

8. Почему квазиньютоновские методы можно отнести к методам переменной метрики ?

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

ГЛАДКИЕ ФУНКЦИИ. КОНЕЧНО-РАЗНОСТНАЯ АППРОКСИМАЦИЯ ПРОИЗВОДНЫХ

Пусть  . Правая аппроксимация производной: 

Ошибка отбрасывания:  .

Ошибка условий. Пусть значения функции известны неточно:  ,

где   - абсолютные ошибки вычисления (измерения) значения функции, тогда

,  

где - ошибка условий.

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

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

В многомерном случае градиент  аппроксимируется в точке  вектором , -я компонента которого вычисляется по

- -й орт.

Нужно создать набор конечно-разностных  интервалов , которые выбираются независимо.

Если точности правой конечно-разностной аппроксимации не хватает, то используют центральную аппроксимацию:

,  для которой ошибка отбрасывания пропорциональна , а ошибка условий -

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

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

Вопросы.

1. Какие сложности возникают при конечно-разностной аппроксимации градиента функции ?

2. Почему неточность оценки градиента может повлиять на свойства метода минимизации ?

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

4. Какие свойства методов первого порядка наиболее чувствительны к неточности в оценке градиента ?

5. Предложите наиболее эффективные методы первого порядка на различных этапах оптимизации.

 

МЕТОДЫ ПРЯМОГО ПОИСКА

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

 

Пусть  -  -й единичный координатный вектор, - начальная точка;  .

Пусть известна точка  и  число .

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

Вычислим значение функции  в точках  и   и проверим выполнение неравенства .

Если неравенство выполняется, то .

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

Если неравенство выполняется, то .

Если шаг неудачен, то  ,              

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

Версия метода.

,   где  определяется из условий ,   ,  

Метод сеточного поиска (Хука-Дживса)

Алгоритм.

1. Задать: начальную точку , приращения ,   ,   ,   .

2. Провести цикл покоординатного спуска, определить точку  (исследующий поиск).

3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением функции)?

    Если - да, то перейти к п. 5, если - нет, то перейти к п. 4.

4. Проверка останова поиска. Выполняется ли неравенство ? Если - да, то поиск прекратить, если - нет, то уменьшить приращения: ,     и перейти к п. 2.

5. Произвести шаг (поиск по образцу)  .

6. Произвести исследующий поиск, используя  в качестве базовой (исходной) точки, определить точку .

7. Выполняется ли неравенство ?

    Если - да, то  ,     и перейти к п. 5. Если - нет, то перейти к п. 4.

Метод сопряженных направлений (Пауэлла)

Определение. Пусть - симметрическая матрица , направления  ,      называются - сопряженными, если эти направления линейно независимы и .

Утверждение. Пусть - квадратичная функция, пусть задано направление (вектор)  и точки . Если - минимизирует , - минимизирует , то направление  сопряжено с , т.е.

.

Действительно из    .

Алгоритм.

1. Задать  и  линейно независимых направлений, например, ,   .

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

3. Определить новое сопряженное направление .

4. ,   ,   ,   перейти к п. 2.

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

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

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

,   где  - величина рабочего шага.

Для сходимости метода его параметры должны удовлетворять условиям:

,   ,   ,   ,   .

2. Алгоритм с возвратом при неудачном шаге.

где параметр  для сходимости метода должен удовлетворять условиям:

,   ,   ,   .

3. Алгоритм с усреднением направления за несколько шагов. Для того чтобы сделать процедуру поиска минимума более детерминированной, целесообразно усреднять векторы спуска , вычисленные на предыдущих итерациях процесса поиска. Усреднение направлений движения выгодно проводить в задачах минимизации функций овражного типа, так как среднее направление может совпадать с направлением дна оврага.

,

,

,    ,   ,   .

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

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

Методы деформируемых конфигураций.

Симплексные методы

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

Построение симплекса

,    - -я вершина симплекса ,   ,    - центр симплекса ,   - радиус описанной гиперсферы симплекса , - -я строка матрицы

,   . Матрицасоответствует симплексу радиуса 1 с центром в 0.

Метод с отображением одной вершины.

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

Отображение.

Порождается ,   ,  

Локально оптимальные методы.

Правильная нумерация вершин симплекса:

Отображение 1   вершин:

,

,               ,        

,      ,

,                                       

.

Отображение 2   вершин:

,

,               ,        

,      ,

,                                      

,

.

Порождается множество  возможных направлений смещения симплекса

Критерии выбора локально оптимального направления

1. ,

2. ,  

3. ,  

4.

5.

6. ,    ,

7. ,   ,

к  отображаемым вершинам относятся те вершины, для которых выполнены условия:

,    ,

  или   

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

,                         

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

Управление размером (адаптация) симплекса

- монотонно убывающая последовательность

Размер симплекса изменяют при невыполнении правила успешности шага:

по закону: ,  

Сжатие симплекса:  

Локальные свойства.

Для симплексных алгоритмов имеет место:

  для критериев,

 для критерия  ,

 для критерия  ,

 для критерия  ,

,        для критерия  ,

   для критерия  ,

где  - угол между       и    

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

Теорема.  Пусть - выпуклая, удовлетворяющая условиям:

1. ,  

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

,    ,

при       

при        .

Симплексно-градиентные методы

,    

Методы с деформируемыми симплексами

Управление формой и размером (адаптация) симплексов с помощью .

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

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

 

Обобщенная схема методов

1. Построение

2. Измерение  в

3. Определение

4. Определение

5. Отображение  вершин

6. Измерение  в новых вершинах

7. Определение успешности шага

8. Адаптация симплекса. Переход к п.2 или п.3

Методы с деформируемыми комплексами

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

Диалоговые методы деформируемых конфигураций для минимизации качественных функций и решения задач многокритериальной оптимизации.  См. главу 3 [1].

Задание 6.

(срок сдачи  с  7  по  13 мая)

1. Ответить на вопросы и решить задачи 1‑59 из файла «Задачи по численным методам оптимизации» раздаточного материала [5].

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