Глава семнадцатая. Нелинейное программирование

17-1. Классификация методов нелинейного программирования

Нелинейное программирование включает в себя методы определения минимума функции n переменных F(х), где х = || x₁, x₂, x₃ || при m + n ограничивающих условиях

т. е.

Соотношения (17-2) следует понимать таким образом, что каждая компонента векторов ψ и x них не менее нуля. Иногда сокращенно соотношения (17-1) и (17-2) записывают в виде

или

где область G задается условиями

В нелинейном программировании допускаются в общем случае любые соотношения между n и m, т. е. n>m, n = m, m<m.

В задачах нелинейного программирования, так же как и в задачах линейного программирования, могут встречаться другие формы написания условий. Но все возможные формы могут быть сведены к виду (17-1), который в дальнейшем будем называть нормальным [Л. 89, 96].

В общем случае функции F(х) и ψ_i(х) бывают произвольными и, в частности, линейными. Нетрудно убедиться, что задачи, решаемые прямыми методами поиска, являются частными случаями задач вида (17-1), (17-2).

Задачи поиска экстремума функции при наличии ограничений можно решать с помощью классических методов, но они рассматривают только случаи, когда неравенства имеют вид строгих равенств:

При этом не требуется не отрицательности переменных x_j, m<n, а функции F(х) и ψ_i(х) непрерывны и имеют частные производные, по крайней мере до второго порядка. Для нелинейного программирования классические методы имеют большое теоретическое значение, так как основополагающая теорема Куна - Таккера в выпуклом программировании обобщает теорему Лагранжа для классических задач. Поэтому в начале главы будут рассмотрены классические методы отыскания экстремума функции с ограничениями.

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

Теоретически нелинейное программирование разработано только для одного частного случая выпуклых функций F(х) и ψ_i(х), и соответственно этот раздел назван выпуклым программированием (рис. 17-1).

Функция f(х)n переменных ||x₁,...,x_n|| = x ∈ G называется выпуклой функцией в выпуклой области G, если для любых двух точек из G выполняется соотношение

где 0<λ<1. Функция будет строго выпуклой, если здесь знак «≤» можно заменить на «<». Соотношение (17-3) означает, что выпуклая функция не может принимать больших значений, чем линейная функция, интерполирующая значения f(х¹) и f(х²). На рис. 17-2 приведен пример выпуклой функции одной переменной.

Рис. 17-1. Классификация методов нелинейного программирования

Соответственно функция f(х) называется вогнутой (или строго вогнутой), если функция - f(х) выпукла (строго выпукла).

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

Рис. 17-2. К определению выпуклой функции

Метод считается теоретически разработанным, если найдены соотношения, являющиеся необходимыми и достаточными условиями оптимума, и алгоритмы поиска экстремума с доказательством их сходимости. Этим требованиям, строго говоря, удовлетворяют только методы, рассматриваемые в разделе квадратичного программирования, частично методы решения задач с сепарабельными функциями и в значительно меньшей степени прямые методы. Функция f(х) = f(x₁, ...,x_n) называется сепарабельной, если она представлена в виде

В общем случае эти функции не являются выпуклыми. Однако если каждая из функций f_j(x_j) выпуклая и коэффициенты c_j неотрицательны, то функция f(х) тоже выпуклая. Методы решения задач с сепарабельными функциями, основанные на замене нелинейных функций ломаными кривыми, составленными из отрезков прямых, ищут локальный экстремум и не гарантируют отыскание глобального экстремума [Л. 89].

Теоретически наиболее широко и детально в нелинейном программировании разработан раздел выпуклого программирования, называемый Квадратичным, в котором функции представляются в виде суммы линейной и квадратичной форм и имеют вид:

Для выпуклости необходимо, чтобы матрица C = [| c_jk || представляла собой симметричную положительную полуопределенную матрицу, т. е. чтобы для любых x выполнялись условия симметрии c_jk = c_kj и положительной полуопределенности хСх≥0.

Однако и этот достаточно узкий раздел не представляет единого целого, а состоит из набора методов, справедливых для более частных видов функции (17-5) и отличающихся разной эффективностью, для которой пока еще нет удобных способов сравнительной оценки.

Методы квадратичного программирования можно разделить на три группы: алгоритмы, использующие симплекс-метод; градиентные и прочие специальные методы (см. рис. 17-1).

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