АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.2. Двойственный симплекс-метод.
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. Метод рассмотрения остатков от деления.
  8. I. Методические основы
  9. I. Методические основы оценки эффективности инвестиционных проектов
  10. I. Организационно-методический раздел
  11. I. Предмет и метод теоретической экономики
  12. I. Что изучает экономика. Предмет и метод экономики.

Метод циклического покоординатного спуска заключается в изменении каждый раз одной переменной, тогда как другие ос­таются постоянными. Опишем этот метод для задачи (2.1).


- некот

приближение, а а0- некото-

™ы * > 0 Обозначим е>= (0,.... 0,1, 0,..., 0) - единичный динатньГи вектор, у которого./-* координата равна 1, остальные равны нулю,./ =1,..., л. Положим

S*=eJ»Jk=k-n\-] + l, (2-13)

где Г* 1 - целая часть числа kin. Условие (2.13) обеспечивает цик-

L"J, „ „о = i

лический перебор координатных векторов е,...,е, т.е. Л е,...

Вычислим значение функции/С*) в точке Х= Хк+ akSk и про­верим неравенство

(2.14)

f(Xk+akSk)<f(Xk).

Если оно выполняется, то полагаем

Xk+x = Xk+akSk,akH=ak. (2.15)

В случае, если условие (2.14) не выполняется, вычисляем зна­чение функцииДХ) в точке Х- Хк - а^5* и проверяем неравенство

f(Xk-akSk)<f(Xk). (2-16)

При выполнении условия (2.16) полагаем

y*+i_ у* г, с* г, = г, (2 \Ъ

Л —Л — U.ki3, Ufc+|— <J.k. yi.,11)

Будем считать (к+\)-й этап удачным, если выполнилось хотя бы одно из условий (2.14) или (2.16). Если же ни одно из этих ус­ловий не выполнено, считаем (А;+1)-й этап неудачным и полагаем

 
18)

=п, хк = х''"+1; ак при/* ф п или хк ф хк~"*х или 0 < к < п - 1,

где Я.е(0;1) - фиксированное число, являющееся параметром ал­горитма. Условие (2.18) означает, что если за один цикл из п эта­пов при переборе направлений всех координатных векторов е,..., е" с шагом ак реализовался хотя бы один удачный этап, то


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

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

Заметим, что такой метод работает плохо, если в выраже­ние минимизируемой функции входят произведения х.х., т.е. если имеет место взаимодействие между x.,i=\,...,n.

Указанного недостатка можно избежать с помощью следу­ющей модификации метода покоординатного спуска, известной под названием метода Зейделя.

2.2.2. Метод Зейделя

Этот метод заключается в последовательной минимизации функции/^ по направлению каждого из координатных векто­ров e\j = 1,..., и, всегда начиная из самой последней точки пост­роенной последовательности. После завершения минимизации по направлению последнего координатного вектора е" цикл, назы­ваемый внешней итерацией, повторяется до тех пор, пока не вы­полнится одно из возможных условий окончания поиска:

|/(Х*)-/(А'*-")|<8ИЛи||Х4-Х*1<£, (2.19)

где е > 0 - заданный параметр точности.

Для приближенного решения вспомогательной задачи ми­нимизации

min{/-(A-*-aS*)|ae^} (2.20)

на каждом внутреннем шаге внешней итерации целесообразно использовать изученный ранее метод поразрядного поиска. Опи­шем алгоритм метода Зейделя.

ШагО. Задать параметр точности е > 0, выбрать точку на­
чального приближения Х°е Е", вычислить значение функции/
(А"°), положить к = 0. _

Шаг1. Положить jk=k- л["^1 +1, Sk = eJ, где |^J- целая часть числа kin.


Решить задачу одномерного поиска (2.20), т.е. определить оптимальную величину шага а = arg mm{f(Xk+aS)\aeR}. Найти новую точку последовательности Xk+l=Xk+akSk и вычислить зна­чение функции/(Х +).

Шаг 2. Если / < п, то положить к = к+\ и перейти к шагу 1, иначе -- перейти к шагу 3.

Шаг 3. Проверить условие достижения заданной точно­сти (2.19). Если оно выполняется, то перейти к шагу 4, иначе -к шагу 1, положив к= к+\.

Шаг 4. Завершить вычисления, положив X»IW, / =f(X '). Эффективность метода Зейдел'я существенно зависит от свойств целевой функции/^). Так, если линиями уровня целе­вой функции двух переменных являются концентрические окруж­ности, то очевидно, что два шага исчерпывающего спуска приве­дут в точку минимума из любой начальной точки, т.е. минимум такой функции удается с помощью описанного алгоритма найти точно за конечное число шагов.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)