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

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н.ТУПОЛЕВА

В.Р. Хайруллин

Лабораторный практикум по курсу « Методы оптимального упрпвления»

Казань 2014

Лабораторная работа №1.

Минимизация функции многих переменных прямыми методами.

Цель работы:знакомство с задачей минимизации функции многихпеременныхметодами, не требующими вычисления градиента функции. К ним относятся метод покоординатного спуска, метод деформированного многогранника.

Введение. Данная задача формулируется как задача безусловной оптимизации, сутью которой является поиск минимума функции многих переменных на всем пространстве соответствующей размерности. Функцию многих переменных будем рассматривать как функцию, заданную в точках X n-мерного эвклидова пространства Eⁿ.

Рассмотрим основные методы решения задач безусловной минимизации вида:

где (1.1.)

Если функция дважды дифференцируема, то данную задачу можно решить аналитически, используя необходимые и достаточные условия безусловного экстремума. Записав необходимые условия:

или (1.2)

находим все стационарные точки функции . Среди них, используя достаточные условия, находим точки локального минимума, в которых матрица вторых производных положительно определена. Сравнивая значения в этих точках, находим точку глобально минимума.

Однако аналитически решить систему уравнений (1.2) не всегда возможно. Кроме того, функция может быть не только недифференцируемой, но даже не аналитически заданной. Поэтому аналитический метод имеет ограниченное применение и для решения задачи (1.1) на практике чаще используют приближенные численные методы.

Простейшие из них, называемые прямыми методами, не требуют вычисления производных функций , а используют только вычисленное значение функции .

В этих методах, после задания начальной точки последовательно ищутся точки такие, чтобы выполнялось неравенство вида:

(1.3)

Новая точка ищется с помощью итерационной процедуры вида:

(1.4),

в которой выбор нового приближения к точке минимума определяется сравнением значений функции в нескольких точках пространства Eⁿ.

Постановка задачи.

Дана функция y=f(X) . Требуется найти минимум функции, используя метод покоординатного спуска или метод деформированного многогранника.

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

При оптимизации по данному методу траектория поиска экстремума функции выбирается в виде ломаной линии, отдельные отрезки которой параллельны координатным осям пространства оптимизируемых параметров .

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

Рис. 1

Опишем данный метод.

После выбора некоторого начального приближения ищется при фиксированных значениях . Таким образом, движение из точки происходит по прямой, параллельной оси в сторону убывания функции . Затем поиск идет вдоль оси из точки с координатами , то есть ищется . Описанная процедура последовательно повторяется для всех .

По завершению поиска по всем получаем точку . Процесс поиска повторяется аналогично вышеизложенному, и в результате имеем точку и так далее. Итерационный процесс поиска заканчивается, когда изменение аргумента X мало влияет на изменение функции , то есть выполняется следующее неравенство вида:

(1.5),

где -заданная точность вычислений.

Примечание. При поиске минимума функции по направлению вдоль оси , переход от начальной точки к точке происходит в соответствии с формулой:

(1.6),

где параметр может принимать значение 1 или -1, а -величина шага в данном направлении. При отыскании коэффициент меняется от начального значения до минимально возможного .