Глава 8. НЕКОТОРЫЕ МЕТОДЫ ДЛЯ ЗАДАЧ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

Задача нелинейного программирования (НЛП) с линейными ограничениями может быть сформулирована в виде

где А — матрица размера -мерный вектор, а -мерный вектор. Среди различных задач НЛП

задачи с линейными ограничениями встречаются часто и, вообще говоря, решить их легче, чем задачи с нелинейными ограничениями.

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

8.1. МЕТОД ЛИНЕЙНОЙ АППРОКСИМАЦИИ

Возможно, наиболее прямой подход к решению задачи (8.1) заключается в линейной аппроксимации. Для данной допустимой точки будет решением задачи линейного программирования (ЛП), которая имеет такие же ограничения, как и задача (8.1), и целевая функция которой представляет линейную аппроксимацию в точке Тогда направление является хорошим направлением для поиска большего значения

В любой допустимой точке линейной аппроксимацией является где

Алгоритм при данном и фиксированном находит решение следующей подзадачи:

при

Но так как некоторые члены целевой функции постоянны, то алгоритм фактически решает более простую, но эквивалентную подзадачу ЛП

где х — фиксированная допустимая точка, а у — переменная.

Далее с помощью направления мы получаем следующую точку Здесь Следует обратить внимание на то, что как так и допустимы. Поэтому при любая точка

допустима, так что также допустимая точка. Теперь дадим строгую формулировку алгоритма.

Алгоритмическое отображение. Алгоритм представляется в виде где а отображение получают, полагая, что

где — решение задачи (8.3) для допустимой точки

Назовем допустимую точку х подходящей, если для решения у подзадачи (8.3) при

Остается доказать, что в подходящей точке выполняются условия Куна — Таккера (см. упр. 1). Если окажется подходящей, то алгоритм завершает свою работу. Для того, чтобы алгоритм начал работать, должна быть задана исходная точка

Доказательство сходимости. Чтобы доказать сходимость, предположим, что непрерывно дифференцируема. Предположив, что допустимая область компактна, мы обеспечим выполнение условия (1) теоремы сходимости А, так как благодаря допустимости данной точки все точки должны быть допустимыми.

Условие 2. Пусть Ясно, что условие 26 выполняется. Чтобы доказать выполнение условия 2а, допустим, что х не является подходящей. Тогда, полагая, что у решает задачу (8.3) при получаем

и поскольку то

Условие 3. Наконец, нужно доказать замкнутость отображения А. Сначала исследуем Пусть Тогда

Чтобы доказать замкнутость достаточно установить, что — решение задачи (8.3) при Тогда поскольку Так как все допустимы, то также допустимо. При этом по определению

Рис. 8.1. Алгоритм линейной аппроксимации:

для любого допустимого у. Функция непрерывно дифференцируема, поэтому, переходя к пределу в (8.9), приходим к соотношению

Но тогда, так как точка допустима, а выражение (8.10) имеет место для всех допустимых — решение подзадачи при . Следовательно, замкнуто. (Другое доказательство замкнутости см. в упр. 4.)

Вследствие того, что все допустимы, а значит, входят в компактное множество, все также находятся в компактном множестве. При замкнутых и следствие 4.2.1 доказывает, что А замкнуто. Поэтому процедура удовлетворяет условиям теоремы сходимости А.

Графическое изображение поведения этого алгоритма представлено на рис. 8.1. Точка а представляет собой абсолютный максимум а овалы — это линии уровня функции Допустимая область представлена прямоугольником . Подробно описана процедура получения Обратите внимание на то, что последовательность сходится к точке к точке решения. Следует также обратить внимание на то, что точка дает зигзагообразное движение к точке решения Такое зигзагообразное движение часто замедляет сходимость.