- •ВВЕДЕНИЕ
- •1. ПРИМЕРЫ И КЛАССИФИКАЦИЯ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ. ОБЗОР МЕТОДОВ
- •2. ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ
- •2.1. Основные понятия
- •2.2. Порядок решения экстремальных задач
- •3. ДИНАМИЧЕСКИЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ
- •3.1. Постановка задачи оптимального управления
- •3.2. Функционал, его свойства, необходимые и достаточные условия достижения экстремума
- •3.3. Вариационные задачи на безусловный экстремум
- •3.4. Вариационные задачи на условный экстремум
- •3.5. Каноническая форма уравнений Эйлера. Принцип максимума
- •3.6. Практические примеры применения принципа максимума
- •3.6.1. Синтез программы управления мягкой посадкой космического летательного аппарата
- •3.6.2. Синтез системы стабилизации, оптимальной по быстродействию
- •3.6.3. Расчетный пример
- •4. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
- •4.1. Линейное программирование: постановка задачи, основные понятия, графическая интерпретация
- •4.2. Симплекс-метод
- •4.2.1. Алгебраический вариант
- •4.2.2. Табличный вариант
- •4.3. Решение задач дискретного линейного программирования
- •4.4. Двойственная задача линейного программирования
- •4.5. Нелинейное программирование
- •4.5.1. Обобщенный метод множителей Лагранжа, условия Куна-Таккера
- •4.5.2. Численный метод зондирования пространства параметров
- •4.5.3. Методы безусловной оптимизации
- •4.5.4. Методы безусловной оптимизации первого и второго порядка
- •4.5.5. Прямые методы условной оптимизации
- •4.5.6. Непрямые методы условной оптимизации
- •4.5.7. Применение симплекс-метода для решения целочисленных задач нелинейного программирования
- •5. СТРАТЕГИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ
- •5.1. Основные термины и допущения. Формализация задачи. Принципы поиска решения
- •5.2. Общие методы решения стратегических матричных игр
- •5.2.2. Способы упрощения стратегических матричных игр
- •5.2.3. Решение стратегических матричных игр методом линейного программирования
- •5.2.4. Итерационный алгоритм Брауна-Робинсон
- •5.3. Примеры решения стратегических матричных игр
- •6. СТАТИСТИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ
- •Библиографический список
- •ОГЛАВЛЕНИЕ
На рис. 30 X[1] – исходная точка, n=2. На первой итерации поиск производится последовательно вдоль осей x1, x2, x1. Точки X[1], X[2], X[3] – точки минимума, найденные при последовательных одномерных поисках вдоль исходных направлений. На второй итерации одномерный поиск должен производиться из точки X[3] последовательно вдоль направлений x2, x1, а также вдоль направления, совпадающего с вектором X[1]–X[3], и так далее.
Известно, что данный метод наиболее эффективен для минимизации функций, близких к квадратичным по крайней мере вблизи точки минимума. В идеальном случае для квадратичной
функции n переменных точка минимума X находится точно за n итераций.
4.5.4. Методы безусловной оптимизации первого и второго порядка
Градиентом дифференцируемой функции f(X) в точке X [k] называется n-мерный вектор f(X[k]), компоненты которого являются частными производными функции f(X), вычисленными в точке X[k]. Этот вектор перпендикулярен плоскости, проведенной через точку X[k], и касательной к поверхности уровня функции f(X), проходящей через точку X[k] (рис.31).
Рис. 31
102
Вектор-градиент направлен в сторону наискорейшего возрас-
тания функции в данной точке. Вектор – f(X[k]), противоположный градиенту, называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы поиска первого порядка, называемые также градиентными методами минимизации.
Очевидно, что если нет дополнительной информации, то из точки X[k] разумно перейти в точку X[k+1], лежащую в направлении антиградиента. Это приводит к итерационному процессу вида
X[k+1]=X[k]–ak . f(X[k]), где a>0 – шаг, k=0,1,2,...
В координатной форме этот процесс записывается следующим образом:
x |
[k +1]= x [k]− a |
|
|
∂f |
X = X[k] |
, i=0,1,...,n; k=0,1,2,... |
|
∂x |
|||||
i |
i |
k |
|
|
||
|
|
|
|
i |
|
|
В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента
X[k +1]− X k ≤ ε , либо выполнение условия малости градиента
f (X[k +1]) ≤ γ . Здесь ε и γ – заданные малые величины. Возмо-
жен и комбинированный критерий, состоящий в одновременном выполнении указанных условий.
Градиентные методы отличаются друг от друга способами выбора величины шага ak .
Достаточно малый постоянный шаг ak обеспечит убывание целевой функции, однако при этом может потребоваться неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума. Из-за сложности получения необходимой информации для выбора величины шага, методы с постоянным шагом применяются на практике редко.
Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется.
Наиболее простым в реализации и в то же время вполне эффективным является метод наискорейшего спуска.
103
Метод наискорейшего спуска. В соответствии с этим методом величина шага ak на каждой итерации выбирается из условия минимума функции f(X) в направлении антиградиента:
f (X[k]− ak f (X[k]))= min(f (X[k]− a f (X[k]))).
a >0
Общий алгоритм метода состоит в следующем:
1.Задают координаты начальной точки X[0], k=0.
2.Вычисляют значение градиента f(X[k]).
3. Выполняют одномерную минимизацию по a функции f(X[k]–a. f(X[k])).
4. Вычисляют координаты точки X[k+1].
5. Проверяют условие останова итерационного процесса. Если оно выполняется, вычисления прекращают. В противном случае продолжают вычисления с п. 2 при k=k+1.
Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций, так как вектор антиградиента для таких функций, как правило, направлен в окрестность точки минимума (рис. 32). У таких функций наибольшее М и наименьшее m собст-
венные значения матрицы Гессе |
H = |
∂2 f |
|
(см. подразд. 2.2) |
||
∂x |
∂x |
j |
||||
|
|
|
||||
|
|
i |
|
|
мало отличаются друг от друга (матрица Н хорошо обусловлена).
Рис. 32
104
Напомним, что собственными значениями матрицы являются
корни характеристического уравнения ∆n =0, где определитель ∆n находится в соответствии с формулой (1).
Однако в случае минимизации овражных функций скорость сходимости градиентных методов значительно снижается, так как направление вектора антиградиента существенно отклоняется от направления в точку минимума (рис. 33). Обнаружить такую ситуацию можно путем оценки обусловленности матрицы Гессе минимизируемой функции. Для овражной функции матрица Н плохо обусловлена (m/М<<1).
Рис. 33
Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы иногда используются в комбинации с другими методами. На начальной стадии решения задачи, когда точки X[k] находятся далеко от точки минимума, шаги в направлении антиградиента позволяют достигать существенного убывания функции. Вблизи же точки минимума переходят к другому методу, эффективному для овражных функций.
Метод безусловной оптимизации второго порядка (метод Ньютона). Необходимое условие экстремума функции многих
105
переменных f(X) в точке X = (x1, x2 ,...xn ) может быть записано для ее градиента в этой точке f (X)= 0 .
Разложение f(X) в окрестности некоторой точки X[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде
f (X)= f (X[k])+ H (X[k])(X − X[k])= 0 ,
где Н(X) – матрица вторых производных (матрица Гессе) минимизируемой функции. Решение уравнения дает соотношение, кото-
рое может быть положено в основу поиска точки X :
X[k +1]= X[k]− H −1(X[k]) f (X[k]),
где H-1 – обратная матрица для матрицы Гессе, а H −1(X[k]) f (X[k])= p[k] – направление спуска. Отметим, что для
квадратичной функции f(X) рассматриваемая точность разложения в ряд Тейлора достаточна для достижения минимума за один шаг. Для других функций полученное выражение может быть основой итерационного процесса поиска минимума.
Величина шага вдоль направления р[k] полагается равной единице или может определяться аналогично рассмотренному выше варианту метода наискорейшего спуска путем одномерной минимизации вдоль данного направления.
Установлено, что последовательность X[k] сходится в точке X только в том случае, когда матрица Гессе целевой функции является положительно определенной на каждой итерации. Это условие может не выполняться как на начальных итерациях, если минимизируемая функция вблизи начальной точки X[0] существенно отличается от квадратичной зависимости, так и на конечных итерациях за счет накопления ошибок. Поэтому выполнение условия положительной определенности (критерия Сильвестра, подразд. 2.2) должно проверяться на каждой итерации. Если на k-м шаге матрица H не окажется положительно определенной или не удастся получить H -1, в большинстве модификаций данного метода H -1 заменяют единичной матрицей. Соответственно получается
р[k]= f(X[k]), и на рассматриваемом шаге метод Ньютона вырождается в метод наискорейшего спуска.
Количество вычислений на итерации методом Ньютона, как правило, значительно больше, чем в градиентных методах первого порядка. Это объясняется необходимостью вычисления и обраще-
106