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

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К практическим занятиям по дисциплине

Оптимизация технологических процессов

общественного питания»

Направление подготовки магистра

19.04.04 Технология продукции и организация общественного питания

УФА 2015

Рекомендовано к изданию

методической комиссией факультета

пищевых технологий

(Протокол № 1 от «21» сентября 2015 г.)

Составитель: доцент Мартынов В.М.

Рецензент: доцент кафедры математики Лукманов Р.Л.

Ответственный за выпуск:

зав. кафедрой «Технологическое оборудование животноводческих

и перерабатывающих предприятий»

д.т.н., доцент Мартынов В.М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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