Основы теории оптимизации (стр. 28 )

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

На n-м вычислении n-ю точку следует поместить симметрично по отношению к (n — 1)-й точке. Положение этой последней точки в принципе зависит от нас. Для того чтобы получить наибольшее уменьшение интервала на данном этапе, следует разделить пополам предыдущий интервал. Тогда точка х будет совпадать с точкой хn-1. Однако при этом мы не получаем никакой новой информации. Обычно точки хn-1 и хn отстоят друг от друга на достаточном расстоянии, чтобы определить, в какой половине, левой или правой, находится интервал неопределенности. Они помещаются на расстоянии ε/2 по обе стороны от середины отрезка Ln-1; можно самим задать величину ε или выбрать эту величину равной минимально возможному расстоянию между двумя точками.

Интервал неопределенности будет иметь длину Ln, следовательно, Ln-1=2Ln - ε (рис. 11, нижняя часть). На предыдущем этапе точки хn-1 и хn-2 должны быть помещены симметрично внутри интервала Ln-2 на расстоянии Ln-2 от концов этого интервала. Следовательно, Ln-2 = Ln-1+Ln (pис. 11, средняя часть).

Рис. 11.

Замечание. Из рисунка ясно, что на предпоследнем этапе хn-2 остается в качестве внутренней точки.

Аналогично Ln-3=Ln-2+Ln-1 (pис. 11, верхняя часть)

В общем случае Lj-1=Lj + Lj+1 при 1<j<n.

Таким образом,

Если определить последовательность чисел Фибоначчи следующим образом: F0=1, F1=l, и Fk=Fk-1+Fk-2 для k = 2, 3,..., то

(7)

Если начальный интервал (a;b) имеет длину L = (b-а), то

(8)

Следовательно, произведя n вычислений функции, мы уменьшим начальный интервал неопределенности в l/Fn раз по сравнению с его начальной длиной (пренебрегая ε), и это - наилучший результат.

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

(9)

После того как найдено положение первой точки, числа Фибоначчи больше не нужны. Используемое значение ε может определяться из практических соображений. Оно должно быть меньше L1\Fn+x, в противном случае мы будем напрасно тратить время на вычисление функции.

Таким образом, поиск методом Фибоначчи, названный так ввиду появления при поиске чисел Фибоначчи, является итерационной процедурой. В процессе поиска интервала (x1; x2) с точкой х2, уже лежащей в этом интервале, следующая точка х2 всегда выбирается такой, что х3–х4 = х2–х1 или х4-х1 = х3-x2, т. е. x4=х1-х2+х3.

Если f(x2) = f2 и f(x4) = f4, то можно рассмотреть четыре случая (рис. 12).

Рис. 12.

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

При решении вопроса о выборе численного метода рекомендуется оценить поведение линий уровня целевой функции в окрестностях предполагаемой точки экстремума. Число m=L/l, где L и l - максимальное и минимальное собственные значения гессиана функции f в предполагаемой точке экстремума x0 (характеризующее разброс собственных значений оператора f(x)), называется числом обусловленности гессиана функции f в точке x0. Если m >> 1, то функция f называется плохо обусловленной или овражной. Овражность, то есть вытянутость линий уровня вдоль одного направления, приводит к тому, что градиентные методы поиска экстремума функции сходятся медленно.

В зависимости от наивысшего порядка частных производных функции f (x), используемых для формирования dk и tk, численные методы используют методы нулевого порядка, использующие информацию только о значениях функции f(x) (методы деформируемого многогранника, конфигураций). Эти методы могут применяться в тех случаях, когда функция задана неявно или не задана аналитически, но известен ряд значений функции или эти значения вычисляются непосредственно в ходе реализации алгоритма. Они также могут быть полезны в случаях, когда производные функции могут быть заданы аналитически, но их выражения очень громоздки.

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

1) исследование с циклическим изменением переменных и 2) ускорение поиска по образцам.

Исследующий поиск начинается в точке х0, называемой старым базисом. Направления поиска - координатные направления. По каждому направлению поочередно с шагом +t0 (-t0) проверяется выполнение условия и в качестве нового базиса берется точка с координатами, полученными в результате удачных шагов из начальной точки по каждому направлению. Направление от старого базиса к новому задает направление ускорения поиска: в качестве следующей точки минимизирующей последовательности проверяется точка y1=x0+(x1-x0). Здесь - ускоряющий множитель, задаваемый пользователем. Если полученная точка является удачной, то она берется в качестве следующей точки для исследования. В противном случае исследование ведется из точки x1.

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

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

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

где 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). (2)

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

max Δi < ε. (3)

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

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

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

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

1. Задается начальное приближение хr=х°.
2. Осуществляется циклический покоординатный спуск из точки
хr по формуле (1) с выбором длины шага λkr, из условия (4) для
всех 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*.