2.6.2.5 АЛГОРИТМЫ СКАЛЯРНОЙ ОПТИМИЗАЦИИ

Задача скалярной оптимизации решалась в программной среде Excel 7.0 средствами модуля Solver.xla.

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

Чтобы найти оптимум (для определенности - максимум) критерия F(X), нужно выбрать последовательность точек Хi (i = 1, ..., n), для которых будут выполнены условия:

< F^2) < ... < F^i) < F^n). (49)

Как только в этой последовательности появится вектор Xn + 1, такой, что F(Xn) > F(Xn + 1), это будет означать, что при Xn < X < Xn + 1, функция F(A ) достигает максимума.

Xt + i = Х- + aP. (50)

где aj - скаляр, определяющий длину шага вдоль этого направления (при поиске минимума в формуле - минус); Р- - вектор, задающий направление поиска.

Для определения вектора Р, используется понятие градиента. Градиент F '(Х) скалярной функции векторного аргумента F(X) в точке Хi - вектор, направленный в сторону наискорейшего возрастания функции и ортогональной поверхности уровня [поверхности постоянного значения функции F(X)], проходящей через точку Х^. Выражение (52) можно записать в координатной форме:

Xji + 1 = Xji + aiGj(Xi); j = 1, 2, к, (51)

где Gj - j-я компонента вектора градиента. Графическая интерпретация градиентного метода представлена на рис. 1.

Поскольку явный вид функции F(^ неизвестен, вычислительный процесс градиентного поиска строят следующим образом. Произвольно выбирают начальную точку Х-i и в этой точке вычисляют значение функции F^j). Всем компонентам вектораХ1 дают малые приращения Dхj (j = 1, 2, ..., к) и формируют вектор Х2 = Х1 + DX. Затем выполняют пробный шаг, т.е.? F(Xi) < F(X2), то пробный шаг признается удачным и вычисляются

= ^ {X2) - ^(х 1); . = ^ к (52)

AxJ

Если Е(Х1) > -Р(Х2), то пробный шаг неудачен. Поэтому знаки всех приращений Бх^ меняются на противоположные, меняется и направление вектора градиента. Найдя нужное направление, выбирают величину шага а, и продолжают процесс, выстраивая последовательность векторов {X}, удовлетворяющую условию (49).

вычисляют значение функции F(X2). Если компоненты вектора градиента:

Проблема выбора шага - важнейшая во всей процедуре. Именно способом выбора шага отличаются друг от друга различные градиентные методы. Дело в том, что при малом шаге поиск будет почти наверняка успешным, т.е.

Хк+1 = (1 - 2акЬ)хк .

Рис. 3 Проблема подмены глобального оптимума локальным Однако из графика видно, что оптимальная точка есть правая граница интервала, которую в такой ситуации называют глобальным (или истинным) оптимумом, в то время как найденная вершина - локальный оптимум. При поиске оптимума на многомерных поверхностях со сложной топологией всегда существует опасность «застрять» на локальном оптимуме и никогда не добраться до глобального. Способ избежать этого состоит в повторении поиска из различных стартовых точек. Если при повторах найденная точка оптимума и значение функции в ней сохранятся, можно с большой вероятностью считать, что найден глобальный оптимум.

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