Решение слау методом покоординатного спуска

Решение слау методом покоординатного спуска

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

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

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

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

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

Точка описывает начальное приближение. Проводя спуск по координате , попадем в точку . Далее, двигаясь параллельно оси ординат, придем в точку и т.д.

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

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

Метод координатного спуска является простым в реализации методом оптимизации. Главным недостатком метода является его ограниченная применимость.

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

Здесь — значение, полученное после — го шага оптимизации, — наперед заданное положительное число.

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

Читайте также:  Программа для дизайна макетов

Применим метод покоординатного спуска для решения системы

C помощью метода покоординатного спуска решение этой системы

получается за четыре итерации.

const double EPS = 1e-7;

double f (double X, vector values, int pos) <

return sqr (fabs(13 * values[0] + 14 * values[1] — 11)) + sqr (fabs(14* values[0] — 13* values[1] — 15)) + sqr (fabs(15 * values[2] — 19));

// дихотомия для одномерной оптимизации

void binarySearch (vector &values, int now) <

double l = — (1 EPS;) <

if (f(m1, values, now) — f (m2, values, now) > EPS) <

void Coords (vector &answer) <

double prevValue = f (answer[0], answer, 0) + 100, nextValue = f (answer[0], answer, 0);

while (fabs(nextValue — prevValue) > EPS) <

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной (рис. 3.6).

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

(– новые точки приближения к экстремуму)

Ищем экстремум функции f(х1). Положим, экстремум функции в точке х1 1 .

В результате выполнения n шагов найдена новая точка приближения к экстремуму .

Далее проверяем критерий окончания счета (3.15):

если – решение найдено, в противном случае выполняем еще один цикл.

= (0, 0),  = 0,1.

Любым известным методом находим экстремум: x1 1 = 3,25.

= (3,2; 1,625)

3. Проверка критерия окончания счета:

Как видим, , следовательно, требуется выполнить еще хотя бы один цикл.

= (1, 1),  = 0,01.

Любым известным методом находим экстремум:

= (0,5; 0,3).

3. Проверка критерия окончания счета:

Видим, , следовательно, требуется выполнить еще хотя бы один цикл.

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

Поиск экстремума ведется шагами в направлении градиента (max) или антиградиента (min). На каждом шаге в направлении градиента (антиградиента) движение осуществляется до тех пор, пока функция возрастает (убывает).

Этот метод имеет лучшую сходимость, чем предыдущий.

Допустим, требуется найти минимум функции.

. (3.16)

тогда

2. Делаем шаг в направлении антиградиента. Выражения для нахождения координат новой точки приближения к экстремуму выглядят следующим образом:

(3.17)

где  1 – величина шага в направлении антиградиента при 1-ой итерации.

3. Нахождение величины шага.

В направлении антиградиента движемся до тех пор, пока функция убывает. Следовательно, шаг выбирается из условия минимума функции f( 1 ).

Для этого в функцию f(х1, х2хn) подставляем выражения для координат новой точки (3.17).

В результате получим функцию одной переменной f( 1 ). Минимум f( 1 ) находим любым известным методом поиска экстремума функции одной переменной.

4. Полученное значение  1 подставляется в формулы (3.17). В результате получаем точку X1 = (x1 1 ,,xn 1 ).

5. Проверка критерия окончания счета.

Если , то решение в точке, иначе – требуется сделать еще шаг.

f(x1, x2) = x1 2 – 7x1 + x2 2 – 4x2x1x2 + 35, = (1, 1), = 0,5.

Читайте также:  Одно и тоже значение

1. = 2x1 – 7 – x2, a1 = 21 –7 –1 = –6.

= 2x2 – 4 – x1, a2 = 21 –4 –1 = –3.

(6; 3,5)

4. , следовательно, нужен еще шаг.

Найти безусловный экстремум методом наискорейшего спуска

1. = 10x1 – 4x2, – 1, a1 = 101 – 41 – 1= 5,

= –4x1 +10x1 – 1, a2 = –41 + 101 – 1 = 5.

(1)

с n эквивалентна задаче минимизации функции

(2)

или какой-либо другой возрастающей функции от абсолютных величин | fi | невязок (ошибок) , . Задача отыскания минимума (или максимума) функции n переменных и сама по себе имеет большое практическое значение.

Для решения этой задачи итерационными методами начинают с произвольных значений и строят последовательные приближения:

(3)

которые сходятся к некоторому решению при .

Различные методы отличаются выбором «направления» для очередного шага, т.е. выбором отношений

.

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ [j] , минимизирующим величину как функцию от λ [j] . Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ [j] . Последний метод применим для отыскания max и min таблично заданной функции F(x1,x2. xn) .

Градиентные методы

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где λ [j] выбирается

  • постоянной, в этом случае метод может расходиться;
  • дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
  • наискорейшим спуском:

Метод наискорейшего спуска (метод градиента)

Выбирают , где все производные вычисляются при , и уменьшают длину шага λ [j] по мере приближения к минимуму функции F .

Для аналитических функций F и малых значений fi тейлоровское разложение F(λ [j] ) позволяет выбрать оптимальную величину шага

(5)

где все производные вычисляются при . Параболическая интерполяция функции F(λ [j] ) может оказаться более удобной.

Алгоритм

  1. Задаются начальное приближение и точность расчёта
  2. Рассчитывают , где
  3. Проверяют условие останова:
    • Если , то j = j + 1 и переход к шагу 2.
    • Иначе и останов.

    Метод покоординатного спуска (Гаусса—Зейделя)

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

    Алгоритм

    1. Задаются начальное приближение и точность расчёта
    2. Рассчитывают , где
    3. Проверяют условие останова:
      • Если , то и переход к шагу 2.
      • Иначе и останов.

      Метод сопряжённых градиентов

      Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.

      Применение метода к квадратичным функциям в определяет минимум за n шагов.

      Алгоритм

      1. Задаются начальным приближением и погрешностью:
      2. Рассчитывают начальное направление:
        • Если или , то и останов.
        • Иначе
          • если (j + 1) , то j = j + 1 и переход к 3;
          • иначе и переход к 2.

          Литература

          1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
          2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
          3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
          4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
          5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
          6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
          Читайте также:  Как сделать смайлик в ворде

          Ссылки

          • Интерполяционные формулы
          • Математическое программирование
          • Метод градиента
          • Метод сопряжённых градиентов
          • Прямые методы
        • Формула Тейлора
        • Внешние ссылки

          См. также

          Wikimedia Foundation . 2010 .

          Смотреть что такое "Метод покоординатного спуска" в других словарях:

          Метод градиентного спуска — Градиентный спуск метод нахождения локального минимума (максимума) функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также… … Википедия

          Метод наискорейшего спуска — Градиентный спуск метод нахождения локального минимума (максимума) функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также… … Википедия

          ПОКООРДИНАТНОГО СПУСКА МЕТОД — один из методов минимизации функций многих переменных, использующий лишь значения минимизируемой функции. П. с. м. применяется в тех случаях, когда минимизируемая функция недифференцируема или вычисление ее производных требует большого объема… … Математическая энциклопедия

          Метод Гаусса — Зейделя — У этого термина существуют и другие значения, см. метод покоординатного спуска. Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод … Википедия

          Метод Нелдера — Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв … Википедия

          Метод Гаусса-Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия

          Метод Гаусса—Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия

          Метод Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия

          Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани … Википедия

          Метод сопряжённых направлений — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани … Википедия

          Ссылка на основную публикацию
          Регулятор громкости для автомагнитолы
          Бывший хозяин видимо пытаясь снять магнитолу за рукоятку громкости, сломал её. В результате громкость не регулировалась, а отпаявшиеся контакты энкодера...
          Работа с far manager
          Фар менеджер - один из самых удобных файловых менеджеров, рассчитанный на работу с файлами и папками на дисках, прежде всего,...
          Работа с классами python
          Серия контента: Этот контент является частью # из серии # статей: Этот контент является частью серии: Следите за выходом новых...
          Регулярные выражения perl примеры
          Regular expressions, или регулярные выражения - способ определения символьной маски для последующего сравнения с ней строки символов или для обработки...
          Adblock detector