Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Безусловная многопарам. оптим-я Группы методов БМО: методы прямого поиска (вычисления только на основании. - презентация

1 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Безусловная многопарам. оптим-я Группы методов БМО: методы прямого поиска (вычисления только на основании значений целевой функции) градиентные методы методы второго порядка (наряду с первой производной используется вторая) Rev /

2 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы прямого поиска Эвристические (основаны на интуитивных геометрических представлениях) метод случайного поиска поиск по симплексу метод Хука-Дживса Теоретические (основаны на фундаментальных математических теоремах) метод сопряженных направлений Пауэлла

3 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод случайного поиска Метод случайного поиска основан на последовательной случайной генерации достаточно большого количества значений в промежутках нахождения корней с последующим сужением этих промежутков. Алгоритм метода случайного поиска 1.В каждой серии с помощью генератора случайных чисел образуется массив из N точек значений функции F(x i ), x i [x iL,x iU ] (i=1,2,...n; n – кол-во переменных) (N>100). 2.Среди элементов этого массива значений функции находится оптимальное значение (W min |W max ), а также соответствующее ему значение переменной (x min |x max ). 3.По каждой координате рассчитывается новый промежуток, в пределах которого будет производиться последующий выбор из N значений. Например, для уменьшения промежутка процентов на 10%, L=0.9*(b-a); a_new=x_optimal – L/2; if a_newb then b_new=b;

4 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Поиск по симплексу Регулярный симплекс в пространстве n независимых переменных – правильный многогранник с n+1 вершиной. Двумерный случай: симплекс – правильный треугольник, трехмерный: тетраэдр, четырехмерный: см. рисунок, и т.д. Алгоритм поиска по симплексу После построения в пространстве регулярного симплекса, оцениваются значения целевой функции в его вершинах. Самая неоптимальная (например, вершина с минимальным значение функции в случае поиска максимума) отбрасывается. Вместо нее строится новая вершина методом проецирования старой через центр тяжести остальных вершин симплекса. Если функция убывает достаточно плавно, то итерации продолжаются до тех пор, пока либо не будет накрыта точка оптимума (вершина, которую необходимо отбросить, была построена на предыдущей итерации), либо не начнется циклическое движение по двум или более симплексам (одна из вершин симплекса не исключается в течение нескольких N итераций).

5 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Поиск по симплексу Циклическое движение. Если некоторая вершина симплекса не исключается на протяжении более чем М итераций, то необходимо с помощью коэффициента редукции уменьшить размеры симплекса. Новый симплекс следует строить выбрав в качестве базовой точку, которой соответствует самое неоптимальное значение целевой функции. В качестве расчетной формулы числа итераций (с округлением до целого) использовать следующую эмпирическую зависимость: M = 1,65n + 0,05n 2, где n - размерность задачи. Критерий окончания поиска. Поиск завершается, когда или размеры симплекса, или разности между значениями функций в вершинах становятся достаточно малыми в контексте конкретной прикладной задачи. В этой связи необходимо задать величину параметра окончания поиска.

6 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Поиск по симплексу Построение регулярного симплекса x 0 – исходная заданная точка (может быть случайным образом в пределах интервала изоляции корней), – масштабный множитель, от которого зависит длина ребра симплекса. Для i-той вершины с координатами x i : i,j=1,2,...,N. N – количество переменных. i – номер точки, j – номер координаты. Приращения 1 и 2 зависят только от размерности задачи и длина ребра симплекса. x i = x 0 j + 2, ij x 0 j + 1, i=j

7 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Поиск по симплексу Расчет координат отраженной точки Пусть x j - точка, подлежащая отражению. Центр тяжести остальных N точек расположен в точке x c. Все точки прямой, проходящей через x j и x c, задаются формулой x = x j + (x c - x j ). При =0 получаем исходную точку x j, =1 - центр тяжести x c. Для того, чтобы построенный симплекс обладал свойством регулярности, отражение должно быть симметричным, следовательно, =2, т.е. x j новая =2x c – x j предыдущая. x1x1 x2x2 A(1,2) B(5,3) C(3,4) X c (3,3)

8 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Поиск по симплексу Характеристики метода поиска по симплексу: метод поиска надежно "работает" на любого вида функциях, даже разрывных и дискретных; метод достаточно прост, легко применим для задач с высокой размерностью, невысокий уровень требований к ЭВМ; возникает проблема масштабирования, поскольку все координаты вершин симплекса зависят от одного масштабного множителя. Чтобы избежать такого рода проблем в практических задачах, следует промасштабировать все переменные с тем, чтобы их значения были сравнимы по величине; алгоритм работает достаточно медленно, т.к. полученная на предыдущих итерациях информация не используется для ускорения поиска; не существует простого способа расширения симплекса, требуется перерасчет значений целевой функции во всех точках образца.

9 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод поиска Хука-Дживса Процедура поиска Хука-Дживса представляет собой комбинацию "исследующего поиска" и "ускоряющего поиска по образцу". Исследующий поиск: Последовательно по всем координатам (с разной величиной шага по разным координатам) проводят "замеры" направлений поиска, т.е. исследуют поведение функции W в точках x i -, x i, x i +. После перебора всех N координат и выбора направление движения (например, с положительным приращением по координатам x 1 и x 4 и отрицательным по x 3 ), проводят поиск по образцу.

10 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод поиска Хука-Дживса Поиск по образцу начинается в точке, найденной на этапе исследующего поиска, и ведется по определенному направлению последовательным перебором значений. x k+1 = 2x k - x k-1 Если значение целевой функции в пробной точке не хуже значения функции в исходной точке, то шаг поиска рассматривается как успешный. В противном случае шаг не выполняется и необходимо снова перейти к исследующему поиску. В случае, если исследующий поиск не выдает рекомендаций по направлению (значения целевой функции в окрестных точках хуже, чем в исходной), размеры шага по всем координатам необходимо уменьшить, например, по формуле i = i /2. Недостаток метода: при значительных нелинейностях метод вырождается в последовательность исследующих процедур без применения ускоряющего поиска по образцу.

11 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод сопряженных направлений Метод сопряженных направлений Пауэлла ориентирован на решение задач с квадратичными целевыми функциями и основывается на фундаментальных теоретических результатах. Основная идея метода заключается в том, что если построена система сопряженных направлений, то точку оптимума квадратичной функции W(x) можно найти в результате реализации в точности N 2 (N - размерность задачи) одномерных поисков. Если провести одномерный поиск из точки x 0 вдоль направления e 2, найдя точку экстремума x 1, затем уже из нее провести одномерный поиск по направлению e 1, потом из найденной точки x 2 снова по e 2, то направление (x 3 –x 1 ) будет сопряженным с e 1. И оптимум квадратичной функции будет лежать именно на этой прямой (всего 4 одномерных поиска). Если функция не строго квадратичная, то такой поиск необходимо провести еще несколько раз.

12 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод сопряженных направлений Трехмерный случай Серия одномерных поисков из x 0 проводится в направлении e 3, затем e 1, e 2 и снова e 3. В результате построены сопряженные направления e 1 и (x 4 -x 1 ). Направление e 1 заменяется новым направлением поиска 4. Следующая серия: направление 4, e 2, e 3 и снова 4. Новое направление (x 8 -x 5 ), 5, сопряжено не только с 4, но и с e 3. Следовательно, e 3, (x 4 -x 5 ) и (x 8 -x 5 ) образуют систему взаимно сопряженных направлений. Поэтому, если провести дополнительный поиск из точки x 8 в направлении (x 8 -x 5 ), то будет найдена точка x*, в которой должен достигаться оптимум квадратичной функции трех переменных W(x).

13 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод сопряженных направлений Алгоритм метода сопряженных направлений Пауэлла Шаг 1. Задать начальную точку x o и систему N линейно независимых направлений s i ; целесообразно принять s i =e i, i=1,2,...,N. Шаг 2. Минимизировать W(x) при последовательном движении по N+1 направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s N используется как при первом, так и при последнем поиске. Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства. Шаг 4. Заменить s 1 на s 2 и так далее (s i =s i+1 ). Заменить s N сопряженным направлением. Перейти к шагу 2. Шаг 5. По определенному на 3-ем шаге направлению провести одномерный поиск. Результат – найденный оптимум функции. Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает экстремумом, то эта точка находится в результате реализации N-1 циклов, включающих шаги 2-4. Если же функция W(x) не является квадратичной, то требуется более чем N-1 циклов.

14 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Градиентные методы Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой x k+1 = x k + k s(x k ), где x k - текущее приближение к решению x*, k - параметр, характеризующий длину шага, s(x k ) - направление поиска в N – мерном пространстве управляемых переменных x i, i=1,2,...,N. Способ определения k и s(x k ) на каждой итерации связан с особенностями применяемого метода. Обычно выбор k осуществляется путем решения задачи оптимизации W(x) в направлении s(x k ). Поэтому, при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.

15 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Простейший градиентный метод В основе метода лежит следующая итерационная формула: x k+1 = x k + W(x k ), где - заданный положительный коэффициент (связанный с длиной откладываемого отрезка), W(x k ) - градиент целевой функции первого порядка. Недостатки: необходимость выбора подходящего значения и медленная сходимость к точке оптимума ввиду малости W(x k ) в окрестностях этой точки.

16 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод наискорейшего спуска Метод наискорейшего спуска (метод Коши) свободен от первого недостатка простейшего градиентного метода, т.к. k на каждом шаге вычисляется путем решения задачи оптимизации W(x k ) вдоль направления W(x k ) с помощью одного из методов одномерной оптимизации (например, с помощью метода золотого сечения). Недостаток: несмотря на устойчивость, механизма ускорения на последних итерациях не существует (для одномерного поиска всегда необходим интервал поиска).

17 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Методы второго порядка Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле x k+1 = x k - k ( 2 W(x k )) -1 W(x k ). Дополнительная информация о второй производной в данной точке позволяет более быстро находить экстремум функции.