Метод покоординатного спуска — это метод, который характерен выбором направления поиска поочередно вдоль всех координатных осей.
Сущность понятия «оптимизация»
Метод оптимизации известен уже достаточно давно. Оптимизация представляет собой осуществление выбора, то есть это то, чем люди вынуждены все время заниматься в своей повседневной деятельности. Термин «оптимизация» является обозначением процесса или последовательности действий, которые позволяют найти необходимое точное решение.
Хотя итоговой целью оптимизации считается определение самого лучшего, то есть, оптимального решения, на практике, как правило, можно довольствоваться улучшением существующих решений, а не модификацией их до абсолютного совершенства. По этой причине под оптимизацией скорее следует понимать стремление к совершенству, которое, вполне вероятно, может оказаться недостижимым.
Проблема поиска и принятия самых лучших решений является такой же старой, как и само человечество. Издавна люди, начиная осуществлять свои мероприятий, думали над их вероятными последствиями и должны были принять решение, оценивая тем или иным методом зависящие от него параметры, то есть, способы организации мероприятий. Но до определенного времени решения принимались без специализированного математического анализа, а только на базе имеющегося опыта и здравого смысла.
Рассмотрим конкретный пример. Человек вышел утром из дому с целью поехать на работу. При этом ему нужно было осуществить принятие целого ряда сопутствующих решений, типа, брать или не брать с собой зонт, где лучше всего перейти улицу, каким видом транспорта поехать, и тому подобное. Естественно, всю совокупность этих решений человек может принять и без реализации специальных расчетов, просто используя имеющийся у него опыт и здравый смысл.
Но есть и совсем другие примеры. Допустим, необходимо организовать работу городского транспорта. В распоряжении руководящих работников есть какое-нибудь количество транспортных средств. Нужно выработать и принять целый набор решений, а именно, какое количество и каких транспортных средств следует отправить по тому или иному маршруту, как менять частоту следования транспорта в зависимости от времени суток, где лучше всего расположить остановки, и так далее.
Данные решения выступают уже как гораздо более ответственные, чем решения из предыдущего примера. По причине сложности процесса последствия решений уже не представляются абсолютно ясными. Для представления этих последствий, необходимо выполнить некоторые расчетные операции. А самым главным является тот факт, что от данных решений гораздо больше зависит. В первом примере неоптимальный выбор решения может затронуть интересы только одного человека, а во втором примере неправильный выбор решения способен затронуть аспекты жизни людей целого города.
Метод покоординатного спуска
Самым сложным является случай принятия решений, когда речь идет о действиях, опыта, в проведении которых еще просто нет, и, соответственно, у здравого смысла отсутствует точка опоры, а интуиция способна и подвести. К примеру, формируется перспективный план развития вооружений на ближайшее десятилетие. Образцов вооружения, на которые можно рассчитывать, еще просто нет, как и нет никакого опыта их использования. При планировании специалисты вынуждены опираться на значительное количество данных, которые относятся не столько к прошлому опыту, сколько к предполагаемому будущему. Выработанное решение обязано по возможности предоставить гарантии отсутствия ошибок, которые связаны с вероятностью неточных прогнозов, и обладать достаточной эффективностью для обширного перечня условий. Для того чтобы обосновать такое решение, должна быть использована сложная система математических расчетов.
Рассмотрим метод покоординатного спуска. Предположим требуется определить самое маленькое значение целевой функции 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=x11, за которым начнется ее возрастание. Точку, имеющую координаты (x11, x, 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) за ее самое маленькое значение в исследуемой области.
Далее можно провести аналогичную минимизацию целевой функции по переменным x3, x4, . . ., xn. Когда будет достигнута переменной xn, следует вновь вернуться к x1 и продолжить процесс. Необходимо подчеркнуть, что данный метод позволяет свести задачу поиска самого маленького значения функции нескольких переменных к многократному решению одномерных задач оптимизации.
