(1 I Л 3 3 3
111 2 4 4
111 ч5 5 5)
ЛИТЕРАТУРА
1. Derman С. Finite State Markovian Decision Process, Academic Press, New York, 1970.
2. Howard R. Dynamic Programming and Markov Processes, MIT Press, Cambridge, Mass., 1960. (Русский перевод: Ховард P. Динамическое программирование и марковские процессы. - М.: Сов. радио, 1964.)
Литература, добавленная при переводе
1. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. - М.: Наука, 1967.
2. Кемени Дж., Снелл Дж. Конечные цепи Маркова. - М.: Наука, 1970.
ГЛАВА 20
КЛАССИЧЕСКАЯ ТЕОРИЯ ОПТИМИЗАЦИИ
В классической теории оптимизации для поиска точек максимума и минимума (экстремальных точек) функций в условиях как отсутствия, так и наличия ограничений на переменные широко используется аппарат дифференциального исчисления. Получаемые при этом методы не всегда оказываются удобными при их численной реализации. Однако соответствующие теоретические результаты лежат в основе большинства алгоритмов решения задач нелинейного программирования (см. главу 21).
В этой главе изложены необходимые и достаточные условия существования экстремумов функций при отсутствии ограничений на переменные задачи, методы Якоба и Лагранжа для решения задач с ограничениями на переменные в форме равенств, а также условия Куна-Таккера для задач с ограничениями в виде неравенств.
20.1. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ БЕЗ ОГРАНИЧЕНИЙ
Экстремальная точка функции /(X) определяет либо ее максимальное, либо минимальное значение. С математической точки зрения точка Х.0 = (х1,xjyxj является точкой максимума функции /(X), если неравенство
/(X0 + h)</(X0)
выполняется для всех h = (А,, А;, Ап) таких, что Aj достаточно малы при всех j. Другими словами, точка Х0 является точкой максимума, если значения функции / в окрестности точки Х0 не превышают /(Х0). Аналогично точка Х0 является точкой минимума функции /(X), если для определенного выше вектора h имеет место неравенство
/(X0 + h)>/(X0).
На рис. 20.1 показаны точки максимума и минимума функции одной переменной f(x) на интервале [а, Ь]. Точки xv х2, х3, х4 и хв составляют множество экстремальных точек функции f(x). Здесь точки xv х3 и х6 являются точками максимума, а точки х2их4 - точками минимума функции f(x). Поскольку
f(x6) = max{/(t), f(x3), /(*„)}, значение f(x6) называется глобальным или абсолютным максимумом, а значения f{xx) и f(x3) - локальными или относительными максимумами. Подобным образом, значение f(x4) является локальным, a f(x2) - глобальным минимумом функции f(x).
а хх х2 хг х4 х5 х6 b х
Рас. 20.1. Экстремумы функции одной переменной
Заметим, что хотя точка х1 является точкой максимума функции f(x) (рис. 20.1), она отличается от остальных локальных максимумов f(x) тем, что по крайней мере в одной точке ее окрестности значение функции f(x) совпадает с f(x,). Точка х, по этой причине называется нестрогим (слабым) максимумом функции f(x), в отличие, например, от точки х3, которая является строгим максимумом f(x). Нестрогий максимум, следовательно, подразумевает наличие (бесконечного количества) различных точек, которым соответствует одно и то же максимальное значение функции. Аналогичные результаты имеют место в точке xt, где функция f(x) имеет нестрогий минимум. В общем случае Х0 является точкой нестрогого максимума функции f(x), если /(Х0 + h) < /(Х0), и точкой ее строгого максимума, если /(Х0 + h) < /(Х0), где h - вектор, определенный выше.
На рис. 20.1 легко заметить, что первая производная функции / (тангенс угла наклона касательной к графику функции) равна 0 во всех ее экстремальных точках. Однако это условие выполняется и в точках перегиба и седловых точках функции /, таких как точка хь. Если точка, в которой угол наклона касательной к графику функции (градиент функции) равен нулю, не является в то же время точкой экстремума (максимума или минимума), то она автоматически должна быть точкой перегиба или седловой точкой.
20.1.1. Необходимые и достаточные условия существования экстремума
В этом разделе излагаются необходимые и достаточные условия существования экстремумов функции п переменных /(X). При этом предполагается, что первые и вторые частные производные функции f(X) непрерывны в каждой точке X.
Теорема 20.1.1. Необходимым условием того, что точка Х0 является экстремальной точкой функции /(X), служит равенство
V/(X0) = 0.
Доказательство. Из теоремы Тейлора следует, что при 0 < в< 1 имеет место разложение функции f(X)
/(Х„ + h) -/(Х0) = V/(X0)h + ib/Hh Xi+0h,