вычисляется значение целевой функции в этой точке Z0;
в соответствии с выражением (1.15) в этой точке вычисляется градиент целевой функции grad Z;
из исходной точки в направлении убывания целевой функции выполняется шаг.
Рисунок 1.4 - Иллюстрация метода проектирования градиента
Выбор величины шага может осуществляться различным образом. Выберем шаг в соответствии с алгоритмом метода скорейшего спуска и получим первое приближение - точку с координатами х11, х21. Вычисляется значение целевой функции в этой точке Z1.
Необходимо проверить, принадлежит ли точка с координатами х11, х21 области допустимых значений переменных. Для этого проверяется неравенство (1.23), в которое подставляются координаты х11, х21:
(1.23)
Если это неравенство выполняется, вычислительный процесс продолжается.
Из точки с координатами х11, х21 выполняется следующий шаг. В результате этого шага имеем второе приближение - точку с координатами х12, х22. значение целевой функции в этой точке Z2.
Пусть для этой точки неравенство не выполняется. Следовательно, точка с координатами х12, х22 вышла из области и необходимо выполнить возврат в эту область.
Возврат в область выполняется следующим образом. Из точки с координатами х12, х22 опускается перпендикуляр на прямую т.е. конец вектора (х11, х21; х12, х22) проектируется на эту прямую. В результате получается новое приближение - точка с координатами х13, х23, которая принадлежит области . В этой точке вычисляется значение целевой функции Z3.
Дальнейший спуск к относительному минимуму целевой функции продолжается из точки х13, х23. на каждом шаге вычисляется значение целевой функции и проверяется принадлежность нового приближения к области . Вычислительный процесс заканчивается при выполнении условия (1.16).
1.6 Метод штрафных функций
Рассмотрим задачу поиска локального минимума критерия оптимальности W в области, ограниченной системой неравенств (3.16)-(3.17). Введение обобщенного критерия оптимальности по методу штрафных функций [3,5] производится с помощью непрерывной функции
. (1.24)
Обобщенным критерием оптимальности согласно методу штрафных функций является выражение
T=W+RQ(x),
где R - некоторое положительное число, называемое коэффициентом штрафа.
Рассматривается некоторая неограниченная, монотонно возрастающая последовательность {Rk}, k=1,2,... положительных чисел. Для первого элемента этой последовательности с помощью метода покоординатного спуска отыскивается локальный минимум функции T. Пусть этот минимум достигается при значениях (b*,R1).
Вектор (b*,R1) используется как начальное приближение для решения задачи поиска минимума функции T где R2>R1 и т.д. Таким образом, решается последовательность задач минимизации функций T(b*,Rk), k=1,2 ..., причем результат предыдущей оптимизации используется в качестве начального приближения для поиска последующей.
Рисунок 1.5 - Блок-схема метода штрафных функций
1.7 Методы полиномиальной аппроксимации
Согласно теореме Вейерштрасса об аппроксимации, непрерывную функцию в некотором интервале можно аппроксимировать полиномом достаточно высокого порядка [6]. Следовательно, если функция унимодальна и найден полином, который достаточно точно ее аппроксимирует, то координаты точки оптимума функции можно оценить путем вычисления координаты точки оптимума полинома.
Рассмотрим следующие вопросы:
квадратичная аппроксимация <#"1.files/image051.gif">
1.7.1.1Метод Пауэлла
Если известны значения функции f(x) в трех разных точках α, β, γ равные соответственно fα, fβ, fγ, то функция f(x) может быть аппроксимирована квадратичной функцией
ö(x)=Ax2+Bx+C, (1.26)
где А, В и С определяются из уравнений
Aá2+Bá+C=fá,
Aâ2+Bâ+C=fâ,
Aã2+Bã+C=fã. (1.27)
После преобразований этих уравнений получаем
A=[(ã-â)fá+(á-ã)fâ+(â-á)fã] / D,
B=[(â2-ã2)fá+(ã2-á2)fâ+(á2-â2)fã] / D,
C=[âã(ã-â)fá+ãá(á-ã)fâ+áâ(â-ã)fã] / D, (1.28)
где D=(á-â)(â-ã)(ã-á)
Ясно, что φ(x) будет иметь минимум в точке
x=-B/2A,
если А>0. Следовательно, можно аппроксимировать точку минимума функции f(x) значением
(1.29)
Этот метод может непосредственно применяться к функциям одной переменной. Он может быть очень полезен для выполнения линейного поиска в процедурах, описанных в теме №3. В этих процедурах требуется найти минимум функции f(x) в точках прямой x0+λd, где x0- заданная точка, а d определяет заданное направление. Значение функции f(x0+λd) на этой прямой является значениями функции одной переменной λ:
φλ = f(x0+λd). (1.30)
Идеи и результаты, изложенные выше, преобразуются в вычислительные процедуры, описанные далее. Предположим, что заданы унимодальная функция одной переменной f(x), начальная аппроксимация положения минимума и длинна шага D, является величиной того же порядка, что и расстояние от точки А до точки истинного минимума x*(условие, которое не всегда просто удовлетворить). Вычислительная процедура имеет следующие шаги:
Шаг 1. x2 = x1 + D x.
Шаг 2. Вычислить W(x1) и W(x2).
Шаг 3.
если W(x1) > W(x2), то x3 = x1 + 2 D x;
если W(x1)< W(x2), то x3 = x1 - D x;
W(x1) > W(x2),
Шаг 4. Вычислить W(x3) и найти
Wmin = min{ W(x1),W(x2), W(x3)},
Xmin = xi, соответствующая Wmin.
Шаг 5. По x1, x2, x3 вычислить x*, используя формулу для оценивания с помощью квадратической аппроксимации.
Шаг 6. Проверка окончания
если | Wmin - W(x*)| < W, то закончить поиск. В противном случае к шагу 7;
если | Xmin - x*| < x, то закончить поиск. В противном случае к шагу 7.
Шаг 7. Выбрать Xmin или x* и две точки по обе стороны от нее. Обозначить в естественном порядке и перейти к шагу 4.
Заметим, что если точка Е задана слишком малой, то á, â, ã, а также fá, fâ, fã будут очень близко друг к другу и значение d (1.29) может стать вообще недостижимыми. Чтобы преодолеть эту трудность, перепишем (1.29) для второй и последней интерполяции:
(1.31)
1.7.2 Кубическая интерполяция
Квадратичная интерполяция, которая рассматривалась в предыдущем разделе, называется методом Пауэлла и аппроксимирует функцию квадратным трехчленом. В этом разделе рассматривается метод Давидона [6,7], который гарантирует большую точность и аппроксимирует функцию кубическим полиномом.
Для кубической интерполяции в этом методе используются значения функции и ее производной, вычисленных в двух точках.
Рассмотрим задачу минимизации функции f(x) на прямой x0 + hd , то есть минимизацию функции
(1.32)
Предположим, что известные следующие значения:
(1.33)
Эту информацию можно использовать для построения кубического полинома a+bh+ch2+dh3, который будет аппроксимировать функцию φ(h) Если p=0 , то уравнения, которые определяют a, b, c, d имеют вид :
(1.34)
Следовательно, если r является точкой минимума кубического полинома,
(1.35)
где
Одно из значений этого выражения является минимумом. Друга производная равна 2c +6dh.
Если мы выберем положительный знак, то при
другая производная будет
(1.36)
(1.37)
Выбор точки q зависит от нас. Если Gp >0 , то надо выбрать значение q положительным, то есть сделать шаг в направлении уменьшения функции φ(h) , в другом случае значения q надо выбирать отрицательным. Значение должно быть таким, чтобы интервал (0, ) включал в себя минимум. Это будет верным, если φq > φ p или Gp >0.
Если ни одно из этих условий не исполняется, то мы удваиваем значения q , повторяя это в случае необходимости, пока указанный интервал не будет содержать в себе минимум.
Давидон, Флетчер и Пауэлл предложили выбирать q следующим путем:
(1.38)
где φm - оценка самого малого значения истинного минимума φ(h),
h- константа, значение которой обычно берут 2 или 1.
1.7.3 Квадратичные функции
Квадратичная функция [7,8]
(1.39)
где a - константа;
b - постоянный вектор;
G - положительно определенная симметричная матрица - имеет минимум в точке x* , где x* определяется следующим путем:
(1.40)
откуда
Любую функцию можно аппроксимировать в окрестности точки x0 функцией
(1.41)
где G(x0) - матрица Гессе, вычисленная в точке x0.
Аппроксимацией минимума функции f(x) может быть минимум функции φ(x). Если последний находится в точке xm, то
(1.42)
откуда
или
(1.43)
Таким образом точкой xи следующей аппроксимации минимума будет:
(1.44)
или
(1.45)
где λи - длина шага, определяется одномерным поиском в направлении G-1(xи)g(xи).
1.8 Метод Нелдера-Мида
Метод Нелдера-Мида (поиск по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта [7,8]. Множество (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n+1) вершинах симплекса и перемещении в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если n<=6.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
