Метод покоординатного спуска С++,С#,Fotran,Delphi

Метод покоординатного спуска С++,С#,Fotran,Delphi

Пусть нужно найти наименьшее значение целевой функции u=f(M)=f(x1, x2, . . . ,xn). Здесь через М обозначена точка n-мерного пространства с координатами x1, x2, . . . ,xn: M=(x1, x2, . . . ,xn).Выберем какую-нибудь начальную точку М0=(x10, x20, . . . ,xn0) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x1, x20,x30, . . . ,xn0 ). Тогда она превратится в функцию одной переменной  x1 . Изменяя эту переменную, будем двигаться от начальной точки x1=x10  в сторону убывания функции, пока не дойдем до ее минимума при x1=x11, после которого она начинает возрастать. Точку с координатами ( x11, x20,x30, . . . ,xn0) обозначим через М1, при этом f(M0) >= f(M1).

Фиксируем теперь переменные: x1=x11, x3= x30, . . . ,xn=xn0 и рассмотрим функцию f как функцию одной переменной  x2: f(x11, x22, x30 . . . ,xn0). Изменяя  x2 , будем опять двигаться от начального значения x2=x20   в сторону убывания функции, пока не дойдем до минимума при x2=x21 .Точку с координатами {x11, x21, x30 . . . xn0} обозначим через М2, при этом   f(M1) >=f(M2). 

Проведем такую же минимизацию целевой функции по переменным   x3, x4,  . . . ,xn. Дойдя до переменной xn, снова вернемся к x1 и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М0,М1,М2, . . . , которой соответствует монотонная последовательность значений функцииf(M0) >= f (M1)>= f(M2) >=  ...    Обрывая ее на некотором шаге k можно приближенно принять  значение функции f(Mk) за ее наименьшее значение в рассматриваемой области.

Рис. 2. Поиск наименьшего значе- ния функции методом покоординат- ного спуска.

Отметим, что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция   f(x1, x2, ... ,xn)  задана явной формулой и является дифференцируемой, то мы можем вычисллить ее частные производные и использовать их для

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

На рис. 2 изображены линии уровня некоторой функции двух переменных             u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода. Когда мы приступаем к решению реальной задачи оптимизации, такого рисунка, содержащего в себе готовый ответ, у нас, конечно, нет.

 Пусть требуется решить задачу (2):

f(x) -->min,  х ОRn.                                      (2)

В двумерном пространтсве R2. Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме. 
Выбирают произвольно начальную точку х(0)   из   области определения функции f(х). Приближения х(k) определяются соотношениями (3): 
x(k+1)=x(k)+t(k)S(k)      (k=0,1,2, ...), 
где вектор направления спуска s(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если  S(k) параллелен х1, то S(k)= {1,0,0,...,0}, если он параллелен  x2, то S(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t(k)   является решением задачи одномерной минимизации: 
f(x(k)+ts(k)) -->  min,   t ОR1,    (k=0,1,2, ...), 
и может определяться, в частности, методом сканирования. 
Детальная реализация общей схемы в двумерном случае R2 дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х(k), х~(k),x(k+1)   (k=0, 1,  2,)       (рис.2).    При k=0, исходя  из начальной точки х(0)=(x1(0),x2(0)), находят точку х~(0)= (x1~(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом f(x~(0))<=f(x(0)).Затем находят точку минимума x(1)  функции f (x1~(0),x2) по второй  координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является  х(1).   Фиксируя вторую  координату   точки  х(1),   находят   точку   минимума х~(1)= (x1~(1),x2(1)), функции  f(x1,x2(1)) одной переменной x(1); при  этом f(x~(1))<=f(x(1))<=f(x(0)). Точку х(2)   получают, минимизируя целевую функцию f(x1~(1),x2), вновь по коорданате х2, фиксируя координату x1~(1) ,точки x(1) , и т.д. 
Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство 
||x(k+1) - x(k) ||<e           (4) 
  
Блок-схема поиска минимума функции двух переменных методом покоординатного спуска.