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

Метод покоординатного спуска (метод Гаусса-Зейделя) является одним из простейших методов этой группы. Сущность метода состоит в последовательной минимизации целевой функции по отдельным переменным. Сначала отыскивается минимум по первой компоненте, при этом считается, что остальные фиксированы, затем по второй (при этом первая компонента принимается равной найденной) и т.д. Метод в общем случае не обеспечивает отыскания минимума функции за один цикл поиска, т. е. после изменения всех переменных. Необходимо многократное повторение таких циклов.

Метод обладает рядом существенных недостатков. Сходимость метода существенно зависит от выбора системы координат, что наглядно отображено на рис. 5.9 и 5.10. Допустим, что линии уровня минимизируемой функции построены в системе координат O . В этой системе координат с помощью  метода покоординатного спуска требуется проведение нескольких циклов поиска для определения искомого минимума. Однако, если повернуть исходные координатные оси как показано на рис. 5.10, получим новую систему координат Ox₁ x₂, в которой метод обеспечивает сходимость за один цикл поиска.

Рис.	5.9	Сходимость метода покоординатного спуска при неудачном выборе системы координат

 

Рис.	5.10	Сходимость метода покоординатного спуска при удачном выборе системы координат

 

Метод может оказаться вообще непригодным при наличии ограничений (см. рис.5.11). Вах! При чем тут ограничения? Забегаем вперед?

Рис.	5.11	Неработоспособность метода покоординатного спуска при наличии ограничений

 

Рис.	5.12	Влияние эффекта овражности на сходимость метода покоординатного спуска

 

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

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

Метод конфигураций является более перспективным для задач большой размерности. В соответствии с этим методом вначале происходит обследование окрестности некоторой точки х⁰ (например, путем изменения значений одной или нескольких компонент вектора х⁰). После отыскания приемлемого направления производятся вычисления целевой функции при постепенно увеличивающемся шаге (тем самым устанавливается конфигурация поиска). Увеличение шага продолжается до тех пор, пока поиск в этом направлении приводит к уменьшению функции. Если уменьшения функции не происходит, то шаг уменьшают. После нескольких неудач при сокращении шага от принятой конфигурации отказываются и переходят к новому обследованию окрестности. Таким образом, согласно этому методу делаются попытки найти наилучшее направление поиска с тем, чтобы двигаться вдоль него. Метод прост в реализации. (Где она? пробовали – не вышло )Но и для этого метода характерна возможность (хотя и в меньшей степени) заедания вблизи локального минимума или явно выраженного оврага. По своей сути метод конфигураций является достаточно общим методом прямого поиска. Большинство методов этой группы может рассматриваться как его конкретизация.

Метод линейной аппроксимации

Общий вид алгоритма поиска имеет вид

xk+1 = xk – hksk,

где s^k – вектор, определяющий направления поиска,   h^k – рабочий шаг поиска.

Возможны различные способа определения направления поиска. Наиболее часто для этого используются следующие формулы ( это же »градиенты. На фига мозги-то пудрить? )

либо при симметричной аппроксимации

здесь a ^k – длина пробного шага, n _i – вектор направления пробного шага.

В зависимости от способа задания вектора направления пробного шага и величины пробного шага можно получить различные варианты методов поиска. Так, задавая n _i = e_i, где e_i – единичный орт, и, считая a ^k достаточно малым, получаем разностную аппроксимацию градиентных методов, например, в симметричном виде

Рабочий шаг поиска h^k целесообразно выбирать оптимальным в направлении поиска

⇐ Предыдущая1234567Следующая ⇒

Поделиться: