Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.3. Методы возможных направлений. Условия выбора вычислительной схемы

Идея методов возможных направлений проста: из начальной допустимой (по условиям задачи) точки Х0 осуществляется переход к новой допустимой точке, в которой значение целевой функции 2 лучше, чем в Х0; этот процесс продолжается до тех пор, пока сохраняется возможность улучшения z.

Каждый шаг решения основан здесь на двух операциях-выборе подходящего направления, двигаясь в котором можно достичь лучших z (пусть на достаточно малом перемещении), не выходя за пределы области U, и оценке требуемой величины перемещения. По такой схеме работает большое количество численных методов, причем результатом обычно является указание точки Х, подозрительной на экстремум. Если определена очередная точка Хk, то переход к следующей точке осуществляется в соответствии с формулой

Хk+1 = Хk±akrk, (4.2)

где ak - величина k-го шага; rk - единичный вектор, в направлении которого производится этот шаг. Интерпретации названных условий даны ниже; для простоты сначала предполагается отсутствие ограничений на выбор X (т. е. U≡Rn).

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

В основе метода наискорейшего спуска лежат следующие утверждения:

-в качестве rk всегда выбирается вектор градиента


-величина аk определяется либо условием


либо


Преимущества такой схемы поиска X* заключаются в возможности получать максимальные приращения |z| при переходах от одной точки X к другой (см. также гл. 6). Рассматриваемый метод является одним из наиболее рапространенных численных методов; в его названии отражена идея скорейшего достижения точки минимума z.

Для доказательства сходимости введем следующие предположения:

1) рассматривается задача на отыскание безусловного минимума f(X), причем множество {X*} не пусто;

2) f(X) является выпуклой вниз и дифференцируемой функцией, т. е. (∇f(X1), X1-X2)≥f(X1)-f(X2) при Х1≠Х2, Х1, Х2∈Rn; в частности, (∇f(Xk), Xk-X*)≥f(Xk)-f(X*) > 0;

3) множество {X} точек X, обладающих свойством f(X)≤f(X1), ограничено, т. е. diam{X} = D<∞ (здесь Х1 - начальная точка поиска);

4) для любых Xk, Xl отличных от X*, выполнено условие


Использование этих замечаний позволяет получить оценку изменения разностей f(Xk)-f(X*),k = 1,2,..., и тем самым дать ответ на традиционный вопрос о скорости сходимости процесса поиска X*, что является косвенным подтверждением замкнутости W(Xk).

Из очевидного равенства


и замечания 2) следует


или


Если f(Хk)-f(Xk+1)>0 (подобное требование является общим для поисковых методов, см. теорему 11), то приведенное выше неравенство легко представить в виде tk-tk+1≥bkt2k, bk>0, tk>tk+1 его решением служит


k≥1 (чтобы убедиться в этом, достаточно записать рассматриваемое неравенство как ti/ti+1-1≥bit2i/ti+1 или l/ti+1-1/ti≥biti/ti≥bi и провести суммирование по номерам t). Таким образом,

(4.3)

Теперь проблема оценки разностей f(Xk)-f(X*) сводится к анализу свойств слагаемых, собранных под знаком суммы в знаменателе (4.3). Для исследуемого случая


где âk - величина шага, найденная в результате минимизации f(Xk-akrk) (см. замечание 1)); а - произвольное неотрицательное значение параметра аk. Согласно условию 4) имеем a∇f(Xk) - f(Xk-a∇f(Xk))≥(∇f(Xk), a∇f (Хk)) - β/2||a∇/(Xk) ||2 = a|| ∇f(Xk) ||2-a2β/2|| - a2β/2||∇f(Xk) ||2. Положив в последнем неравенстве а = 1/р, получаем f(Xk)- f(Xk+1)≥||∇f(Xk) ||2/2β. Далее, согласно неравенству Коши - Буняковского


поэтому


Замена каждого слагаемого суммы


в (4.3) на 1/2βD2 только усилит отношение (4.3), следовательно,

(4.4)

Нетрудно видеть, что f(Хk)→f(Х*) при k→∞, т. е. имеет место сходимость (в данном случае - слабая) метода наискорейшего спуска.

Решающую роль в получении оценки (4.4) играли предположения 1)-4). Далеко не всегда исследователь имеет в своем распоряжении столь обширные сведения

6 особенностях функции f(X), и проблема обеспечения сходимости остается одной из центральных проблем разработки эффективных методов поиска оптимума.

Обобщенный метод Ньютона

Активное использование только первых производных df/dxj в ходе определения Хk+1, k = 1, 2, ..., может оказаться недостаточным в заключительной фазе поиска X*, z* из-за необходимости более точной аппроксимации f(X). Это приводит к идее учета производных высших порядков (прежде всего - второго порядка) для улучшения показателей вычислительного процесса (например, скорости сходимости вблизи X*).

Обобщенный метод Ньютона базируется на представлении f(Хk+1) в виде


где H(Xk)-матрица вторых частных производных функции f(X) в точке Хk (гессиан). Из необходимого условия эстремума ∇f(X*) = 0 следует ∇f(Хk) + H(Хk) (Х*k) = 0, поэтому (при обратимой матрице H) имеем (X*k) = -H-1k) ∇f(Хk). Направление -H-1k) ∇f(Xk) используется при организации переходов; величина ад определяется уже встречавшимся требованием


Сходимость метода Ньютона доказывается в тех же предположениях относительно свойств f(X), которые были сделаны при описании метода наискорейшего спуска; необходимые коррективы связаны с существованием и обратимостью H(Хk).

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

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

Пусть заданы n единичных векторов е1 ,..., еn, направления которых совпадают с положительными направлениями соответствующих координатных осей. Предлагается оптимизировать f(X) поочередно по каждому из указанных направлений; после того как завершится исследование направления еn, происходит возврат к e1 и процесс (цикл) повторяется. Если Xk - очередная точка, куда совершен переход, a ej - вектор, определяющий направление дальнейшего "движения" (1≤j≤n), то Хk+1 находится из условия


Хk+2 - из условия


т.д. (случай max z); здесь k-множество допустимых аk.

Сходимость метода обеспечивается в предположениях, что f(X) имеет непрерывные первые производные df/dxj (j = 1,....,n) и для любого Xk на направлении произвольно взятого еj (1≤j≤n) существует единственное значение ak=âk, доставляющее максимум f (Xk + akej).

Очевидно, можно разрабатывать и другие алгоритмы поиска оптимума, объединяемые идеей выбора допустимых направлений rk. В частности, стремление учесть не только необходимые, но и достаточные условия экстремума приводит к так называемым методам второго порядка (здесь определяющими являются особенности матрицы H); стремление объединить полезные свойства разных методов реализуется в методе сопряженных градиентов и т. д. Важно заметить, что разнообразие подходов к проблеме выбора возможного направления перемещений от Xk к Xk+1 не затрагивает принципа получения Хk+1 при известном rk (оптимизация по пара-

метру аk). Следовательно, алгоритмическое отображение W(Xk) характеризующее рассматриваемую группу методов, всегда представимо как W(Xk) = WIWII, где WI - отображение, определяющее рациональное аk = âk, WII - отображение, определяющее нужное направление rk.

Рис. 4.1
Рис. 4.1

Сравнительная простота условий сходимости алгоритмов, основанных на использовании формулы (4.2), объясняется двумя причинами - наличием удобных свойств функции f(X) (гладкость, единственность âk и т. п.) и отсутствием ограничений на выбор Хk. Это затрудняет практическое применение методов возможных направлений в том виде, как они были даны выше; возникает необходимость дополнительных исследований с целью внести коррективы, учитывающие ограниченность области U.

Главным осложнением, связанным с требованием учета границ U, является возможная не замкнутость отображения WI; следствием этого бывает нарушение сходимости метода (так называемое заклинивание). Оно выражается в том, что применяемый алгоритм начинает вырабатывать последовательность {Хk}, сходящуюся к Х≠Х*. Пример подобного отклонения дан на рис. 4.1, где изображена область U, границами которой служат прямые I, II и сопряженная с ними дуга окружности III. Если принять одну из точек окружности за начальную точку X1 и на каждом шаге использовать (в качестве заданного) направление хорды, соединяющей Xk с серединой дуги (α, Хk), то можно ожидать возникновения последовательности {Хk}, сходящейся к Х = α (для этого достаточно, чтобы вектор ∇f был постоянно направлен так, как показано на рис. 4.1); очевидно, направление тк перейдет в пределе (при k→∞) в r = (αβ). Рассматривая теперь последовательность {Xk+1}, k = 1, 2, ..., приходим к заключению: в принятых предположениях ее предельная точка X∞+1 совпадает с Х = α, хотя правило переходов требует (а свойства ∇f допускают) выбрать X∞+1 = β; следовательно, X∉WI(X, r), отображение WI незамкнуто в Х, и Х≠Х*.

Полезно обратить внимание и на следующее обстоятельство: как и ранее, WI при имеющихся Хk, rk указывает точку Хk+1 доставляющую экстремум (для определенности-максимум) функции f(X) на прямой, выходящей из Xk в направлении rk, однако в задаче с ограничениями дополнительно требуется, чтобы отрезок, соединяющий Xk с Xk+1, целиком принадлежал U (это особенно важно учитывать тогда, когда область U невыпукла). Таким образом, проблема анализа сходимости заметно усложняется. В ряде случаев ее успешному решению способствует использование результатов теоремы сходимости (13), приводимой здесь без доказательства: если при поиске экстремума непрерывно дифференцируемой целевой функции f(X) метод возможных направлений дает последовательность {Xk}, k = 1, 2, содержащую подпоследовательности, которые имеют предельными X, r значения Х, r, допускают выполнение неравенства (∇f(X), r)>0 и обеспечивают принадлежность всех Хu + аuru области U при любом аu ∈ [0, δ], δ>0, то пределом любой сходящейся подпоследовательности будет точка X*.

Рассматриваемые условия не только обеспечивают улучшение z при перемещениях вдоль rk, но и учитывают возможное появление препятствий в виде границ области U. Вводится регулирование длины шага (параметр δ) на случай, когда какая-то из точек Xk окажется вблизи границы; все указанные особенности должны сохраняться и при предельном переходе (k→∞).

На практике опасность неудачного выбора rk может быть устранена запоминанием точек и участков границы. к которым приводит используемая вычислительная процедура, а также внесением других аналогичных корректив в логическую схему алгоритма поиска X*, z*. Это часто вызывает существенные изменения в подходах к решению задачи.

Метод ε-возмущений

Обратимся к задаче математического программирования: найти Х→max{z = f(Х)} при φi(Х)≥0, i = 1,...., m. Считая f (X) и все φi(Х) непрерывно дифференцируемыми, определим в некоторой допустимой точке Xk множество Jε номеров i, для которых φi*)≤ε (здесь ε - неотрицательное число, указывающее степень близости Хk к границе фφi = 0, i∈J; при ε = 0 точка Xk попадает на рассматриваемую границу; с увеличением ε состав множества Jε расширяется). Если теперь выбирать с учетом условий φi(Xk)≤ε(i∈Jε), то опасность выхода на соответствующие границы исключается или отдаляется настолько, что ею можно пренебречь. Подобные соображения лежат в основе метода ε-возмущений.

Пусть Xk и ε с заданы; пусть далее σ-параметр, имеющий смысл производной по направлению. Ставится цель найти направление rk=r*k, доставляющее шах а при (∇f(Xk), rk)-σ≥0, (∇φi(Xk), rk)-σ≥0 (i∈Jε), σ≥0 (увеличение а означает, с одной стороны, попытку сблизить положения rk и ∇f, а с другой стороны, отдалиться от границ φi = 0, i∈Jε; достижимый компромисс характеризуется здесь получаемым значением max σ = = σ*, зависящим от Хk, ε). Если окажется σ*k, ε)>0, то рекомендованное выше правило выбора rk = r*k обеспечит выполнение неравенств (∇f(Xk), rk) > 0, (Δφik), rk) >0, (i∈Jε) и шаг (пусть небольшой) в направлении r*k позволит улучшить 2 с одновременным сохранением допустимости Xk+1. Другим важным моментом является то, что при ε = 0 и σ*k, 0) = 0 в точке Хk выполняются условия Куна - Таккера.

Алгоритм метода ε-возмущений представляется теперь в следующем виде:

а) выбирается допустимая начальная точка X1 и принимается ε1>0;

б) решается вспомогательная задача определения r*1, σ*1, ε1);

в) вычисляется Х2 согласно требованию Х2∈WI(X1, r*1);

г) принимается ε2≤ε1 и процедуры б), в) повторяются сначала для Х2, ε2, а затем для остальных Xk, εk(k = 3, 4, ...);

д) поиск экстремума завершается, если очередная точка Хи удовлетворяет условиям Куна - Таккера.

Доказательство сходимости (при k→∞) рассмотренного алгоритма основывается в значительной степени на оценках поведения последовательности εk (это нужно для выполнения условий теоремы (13)).

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"