УПРАЖНЕНИЕ 21.2.5

1. Решите следующую задачу методом линейных комбинаций.

Минимизировать /(X) = х3 + х3 -Зх,х,

при ограничениях

Зх, +х2<3, 5х, - Зх2 < 5, х х2 > 0.

21.2.6. Алгоритм последовательной безусловной максимизации

В этом разделе приводится описание градиентного метода более общего вида. Предполагается, что целевая функция f(X) является вогнутой, а каждая функция ограничений g/X) - выпуклой. Кроме того, допустимая область задачи должна содержать внутренние точки. Это исключает как явное, так и неявное использование ограничений в виде равенств.

Алгоритм последовательной безусловной максимизации основан на преобразовании исходной задачи с ограничениями в эквивалентную задачу без ограничений. Процедура в некоторой степени подобна применению метода множителей Лагранжа. Преобразованная задача затем может быть решена методом наискорейшего подъема (раздел 21.1.2).

Введем новую целевую функцию

p(x ) = /(x)+/(x-7iFT-I-L .

Ui*,(X) >i*J

где t - неотрицательный параметр. Наличие второй суммы обусловлено учетом требований неотрицательности переменных исходной задачи, которые следует записать в виде -х<0 для их согласования с остальными ограничениями вида £ (Х)<0. Поскольку функция g/X) является выпуклой, 1/gX.) будет вогнутой. Отсюда следует, что р(Х, t) является вогнутой функцией от переменных X. Следовательно, функция р(Х, t) имеет единственный максимум. Поэтому решение исходной оптимизационной задачи с ограничениями эквивалентно максимизации функции р(Х, t).

Выполнение алгоритма начинается с произвольного выбора начального неотрицательного значения t. Начальная точка Х° выбирается в качестве первого пробного решения. Эта точка должна быть внутренней точкой области допустимых решений, т.е. не должна находиться на ее границе. При заданном значении t оптимальное решение (точка максимума) функции р(Х, t) находится методом наискорейшего подъема.

Точка, представляющая новое решение, всегда будет внутренней, ибо если решение находится близко к границе области, то по крайней мере одна из функций l/gt(X) или -1/Xj примет очень большое отрицательное значение. Поскольку рассматривается задача максимизации р(Х, t), то такие решения автоматически исключаются. Основной результат состоит в том, что последовательно получаемые решения всегда будут внутренними точками допустимой области. Следовательно, исходная задача может всегда рассматриваться как задача без ограничений.

Когда получено оптимальное решение, соответствующее заданному значению t, выбирается новое значение t, и процесс вычислений (методом наискорейшего подъема) повторяется. Если t - текущее значение t, то следующее значение t необходимо выбирать так, чтобы выполнялись неравенства 0 < /* < t.

Литература

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

Практическая реализация алгоритма последовательной безусловной максимизации имеет ряд нюансов, которые здесь не рассматриваются. В частности, существенным фактором является выбор начального значения параметра t, который может повлиять на скорость сходимости алгоритма. Далее для определения начальной внутренней точки области допустимых решений могут потребоваться специальные алгоритмы. Соответствующие детали можно найти в книге [3].

ЛИТЕРАТУРА

1. Bazaraa М., Sherall Н. and Shetty С. Nonlinear Programming, Theory and Algorithms, 2nd ed.,Wiley, New York, 1993. (Русский перевод первого издания: Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. - М.:Мир, 1982.)

2. Beightler С, Phillips D. and Wilde D. Foundations of Optimization, 2nd ed., Prentice Hall, Upper Saddle River, N. J., 1979.

3. Fiacco A. and McCormick G. Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968. (Русский перевод: Фиакко A., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. - М.: Мир, 1972.)

4. Rardin D. Optimization in Operations Research, Prentice Hall, Upper Saddle River, N. J., 1998.

Литература, добавленная при переводе

1. Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.

2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. - М.: Мир, 1985.

3. Зангвилл У. И. Нелинейное программирование. - М.: Сов. радио, 1973.

4. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. - М.: Наука, 1986.

5. Химмельблау Д. Прикладное нелинейное программирование. - М.: Мир, 1975.

ПРИЛОЖЕНИЕ А

КРАТКИЙ ОБЗОР ТЕОРИИ МАТРИЦ

А.1. ВЕКТОРЫ

А.1.1. Определение вектора

Пусть pv р2, рп - произвольные действительные числа. Обозначим через Р упорядоченное множество этих чисел: Р = (р}, рг, ...,р ). В этом случае Р называется 71-мерным вектором (или просто вектором), apt - t-м элементом вектора Р. Например, Р = (2, 4) - 2-мерный вектор, у которогор, = 2 ир2 = 4.

А.1.2. Сложение и вычитание векторов

Пусть Р = (р1,р2, ...,р ) и Q = (grI, q2,qn) - два n-мерных вектора. Тогда элементы вектора R = (ri; г2, г ), равного R = Р ± Q, определяются соотношениями г, =р, ± q,.

В общем случае для любых векторов Р, Q и S, имеющих одинаковую размерность, выполняются следующие соотношения.

А.1.3. Умножение вектора на скаляр

Для произвольного вектора Р и скаляра 6 (произвольного действительного числа) произведение вектора Р на скаляр 6 определяет новый вектор Q, задаваемый соотношением

В общем случае для любых векторов Р и S, имеющих одинаковую размерность, и произвольных скалярных величин в и у выполняются следующие соотношения. 6(Р + S) = 6Р + 6S (свойство дистрибутивности)

P±Q=Q±P

(Р + Q) + S - Р + (Q + S)

Р + (-Р) = О

(свойство коммутативности) (свойство ассоциативности) (существование нулевого вектора)

Q = eP = (ePl,ep2, ...,6р ).

6(уР) = (ву)Р

(свойство ассоциативности)