Минимизация функций без вычисления производных

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

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

xir+1 = xir + λirIi, i = 1,2, …, n. (5.94)

где Ii — i-й координатный n-мерный вектор с компонентами:

lij = 1, если i = j;
lij = 0 — в противном случае.

Длина шага λir вдоль направления поиска Ii может выбираться равной некоторой постоянной величине Δi по следующему правилу:

λir = Δi, если Q(xr + ΔiIi) < Q(xr);
λir = -Δi, если Q(xr — ΔiIi) < Q(xr) < Q(xr + ΔiIi). (5.95)

Если окажется, что λir = 0 для всех i = 1, 2, …, n, то длина пробных шагов Δi должна быть уменьшена (Δi = Δi/β, где β > 1). Поиск считается законченным при выполнении условия:

max Δi < ε. (5.96)

Алгоритм F29, реализующий описанную стратегию поиска точки минимума x*, называется методом покоординатного спуска с постоянным шагом.

Когда длина шага λir на каждой итерации определяется с помощью одномерной задачи оптимизации

Q(xr + λirIi) = min Q(xr + ∑λkrIk + λiIi) (5.97)

приходим к алгоритму F30, реализующему релаксационный метод Гаусса — Зейделя, процедура поиска точки минимума X* в котором сводится к следующей последовательности действий.

1. Задается начальное приближение хr = х°.
2. Осуществляется циклический покоординатный спуск из точки
хr по формуле (5.94) с выбором длины шага λkr, из условия (5.97) для
всех i от 1 до n. Эта процедура образует внутренний цикл, в процессе которого осуществляется одномерная минимизация функции Q (х) по каждой переменной:

min Q(х1r, …, хi-1r, xi, хi+1r, …, хnr), i = 1, 2, …, n.

3. После окончания внутреннего цикла в качестве начального приближения х° принимается точка хn и все вычисления повторяются с п. 2.

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

||хr — хn|| < ε.

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

Недостатком методов покоординатного спуска (алгоритмы F29 и F30) является то, что при минимизации функций, имеющих овраг, дно которого не ориентировано вдоль какой-то из координатных осей, процесс поиска сильно замедляется и может остановиться далеко от точки истинного минимума x*.

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

Процесс поиска начинается из начального приближения х°, которое принимается за базовую точку хr, характеризующуюся тем, что она является исходной точкой очередной итерации. Каждая итерация состоит из двух процедур: «пробного движения» в Δ-окрестности текущей точки испытания и «движения в допустимом направлении», т. е. в направлении вдоль которого гарантируется уменьшение функции Q (X).

Процедура «пробного движения» заключается в обследовании Δ-окрестности базовой точки хr с целью определения допустимого (удачного в смысле уменьшения функции Q (х)) направления Sr. Для этого в циклическом порядке, начиная с i = 1, по формуле (5.94) изменяется каждая переменная xi, i = 1,2, …, n, где размер шага вдоль координатного направления Ii выбирается из условия (5.95). При этом начальный размер шага Δi для каждой из переменных может иметь различные значения. Если полученное значение λir не равно нулю, то при выполнении пробного движения вдоль (i+1)-й координаты в качестве значения Q (хr) рассматривается либо Q (хr + ΔiIi) (если λir = Δi), либо Q (хr — ΔiIi) (если λir = — Δi). После просмотри всех координатных направлений Ii получается точка xnr, в которой значение функции Q (хnr) меньше или равно значению функции в баз вой точке Q (хr). Если окажется, что хnr = хr т. е. величина принятого пробного шага Δ настолько велика, что не позволяет определить допустимого направления, то необходимо его уменьшить (Δi = Δi/β, β > 1) и повторить пробные движения снова. Таким образом, пс мере приближения к точке минимума х* длина пробного шага Δ уменьшается. Поиск считается законченным, если размер всех пробных шагов Δi, i = 1, 2, …, n, станет меньше заданной точности ε.

В случае выполнения неравенства

Q (xnr) < Q (хr)

в качестве допустимого направления Sr выбирается вектор (xnr — хr), который указывает направление поиска вдоль дна оврага минимизируемой функции. Периодическое повторение пробных движений позволяет подстраивать траекторию поиска вдоль дна оврага.в тех случаях, когда (вследствие криволинейности оврага) установленное на предыдущей r-й итерации допустимое направление Sr оказывается неудачным для (r + 1)-й итерации.

Процедура «движения в заданном направлении» сводится к следующей последовательности действий. Вдоль направления определяется по формуле

xir+1 = xr + h(xnr — xr), (5.98)

где h > 1 шаг вдоль допустимого направления.

После каждого шага i = 1, 2,…, вдоль допустимого направления относительно точки хir+1 проводится процедура «пробного движения», целью которой является определение, не нуждается ли направление S в коррекции. Если полученная после проведения n пробных движений точка xinr+1 не совпадает с точкой хir+1, то в качестве скорректированного допустимого направления выбирается вектор (хinr+1 — хir+1), вдоль которого делается шаг h > 1:

хi+1r+1 = хir + h(хinr+1 — хir+1), (5.98)

где xir+1 — «удачная точка» вдоль допустимого направления Sr. Если точка хinr лежит на одной прямой с точками хr и хnr, то направление Sr сохраняется (не корректируется). В обоих случаях вычисление функции Q (х) вдоль допустимого направления продолжается до тех пор, пока в очередных точках испытания хi+1r+1 получаются уменьшающиеся значения функции Q (х). Когда в допустимом направлении не удается найти точку исйытания xi+1r+1 с меньшим значением функции Q (х), то поиск в направлении Sr считается законченным. В этом случае точка предыдущего удачного испытания xir+1 выбирается в качестве базовой точки для (r+1)-й итерации, из которой делается пробное движение с целью определения нового допустимого направления Sr+1.

На рис. 5.3 показана траектория поиска, ртеализующая пробные движения и движения в допустимом направлении для функции Q (x1, x2) «овражного» типа.



Рис. 5.3. Траектория поиска по методу конфигураций минимума функции Q(x) с «криволинейным» оврагом

Применение алгоритма F31оказывается эффективным при минимизации функций Q (х) с «прямолинейными оврагами». В этом случае экспериментально показано, что число испытаний, необходимое для локализации точки минимума х* с заданной точностью ε, прямо пропорционально числу переменных n.

Недостатком алгоритма является то, что в процессе проведения пробных движений направление дна оврага может быть пропущено, так как пробные шаги делаются только параллельно координатным осям. По этой же причине поиск может «остановиться» на дне оврага вдали от точки истинного минимума х*, если в базовой точке линии уровня минимизируемой функции (Q (х) = const) очень изогнуты.

Для устранения отмеченного недостатка метода конфигураций в алгоритме F32, реализующем метод вращающихся координат, предлагается вместо того, чтобы изменять каждую переменную xi независимо параллельно координатной оси, осуществлять на r-й итерации преобразование системы координат (х) таким образом, чтобы в новой системе координат (ξ) одна из осей совпадала с направлением дна оврага, а остальные были бы к ней ортогональны. После проведения одномерного поиска вдоль n взаимно ортогональных направлений строится новая система координат, и так до тех пор, пока точка минимума X* не будет локализована с заданной точностью ε.

Первая итерация в алгоритме F32 полностью совпадает с процедурой поиска по методу Гаусса — Зейделя F30. Вдоль направлений Ii, i = 1,2, …, n, параллельных координатным осям, поочередно решается одномерная задача оптимизации (5.97). На последующих итерациях одномерная задача оптимизации решается для каждого линейно-независимого взаимно ортогонального направления ξi, i = 1, 2, …, n. Начиная с базовой точки хr, определяется шаг λ1r вдоль направления ξ1r, при котором достигается min Q (хr + λ1ξ1r).


Оставить комментарий





Статистика

Рейтинг@Mail.ru