Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



Методы нелинейного программирования могут быть охарактеризованы как многошаговые методы или методы последовательного улучшения начального решения. Для этого используют идею движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния х(к) осуществляется переход в следующее состояние х(к+1) изменением вектора х(к) на величину Δх(к), называемую шагом х(к+1) = х(к) + Δх(к). Очевидно, что для случая поиска минимума целевой функции f(х) должно выполняться условие f(х(к)) < f(х(к+1)), иначе перевод в состояние х(к+1) нецелесообразен.

Значительное число методов нелинейного программирования в соответствии со способом определения шага (к) (направления поиска) можно отнести к одному из трех основных классов:

1. Градиентные методы;

2. Безградиентные методы детерминированного поиска;

3. Методы случайного поиска.

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

Согласно этому методу направления спуска выбираются параллельно координатным осям. Совершается цикл: производится спуск вдоль первой оси ОХ1, затем вдоль оси ОХ2 и т.д. до последней оси ОХn. Под циклом понимается тот момент, когда проварьированы все переменные. Эти действия повторяются в цикле вплоть до достижения оптимума. Одним из вариантов этого метода является спуск по координате с решением задачи одномерной оптимизации на каждом шаге.

На рисунке 1 показан один шаг итерации, состоящий из двух этапов. Сначала фиксируется значение координаты х2 и решается задача одномерной оптимизации по координате х1. То есть определяется минимум одномерной функции, изображенной на выносном графике слева. Далее фиксируется значение координаты х1, сообщающее минимум этой функции, и отыскивается минимум однопараметрической функции, график которой показан на выносном элементе внизу.

Для реализации этого метода в таблице Excel одномерная оптимизация может быть реализована варьированием значений xi в диапазоне [аi, bi] с малым постоянным шагом αi. По мере сходимости задачи оптимизации к решению шаг αi целесообразно уменьшать.

Заметим, что не для всех гладких функций применение этого метода гарантирует сходимость, велика вероятность "застревания" поиска на дне оврага вдали от точки экстремума. Оврагом называют часть пространства управляемых параметров, в которой наблюдаются слабые изменения производных целевой функции по одним направлениям и значительные изменения с переменой знака – по некоторым другим направлениям.



 

 


Рисунок 1 – Схема сходимости метода циклического покоординатного спуска с решением задачи одномерной оптимизации на каждом шаге

 

В то же время при благоприятной ориентации дна оврага, а именно при положении одной из координатных осей, близком к параллельности с дном оврага, поиск оказывается весьма быстрым. Эта ситуация показана на рисунке 2.

 

Рисунок 2 – Схема сходимости при благоприятной ориентации осей оврага

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!