Метод Зойтендейка (стр. 2 из 4)

Если , то остановиться; х_k—точка Куна—Таккера, В противном случае перейти к шагу 2.

Шаг 2. Положить равным оптимальному решению еле-., дующей задачи линейного поиска:

где определяется в соответствии с (1). Положить, определить новое множество активных ограничений в и переопределить А₁ и А₂. Заменить k на k+1 и перейти к шагу 1.

Заметим, что . Решим задачу методом Зойтендейка, взяв в качестве начальной точки . Каждая итерация алгоритма содержит решение подзадачи, определенной в описании шага 1, для нахождения направления, а затем линейный поиск вдоль этого направления.

Итерация 1

Поиск направления. В точке имеем . Кроме того, в точке x₁ активными являются только ограничения неотрицательности переменных, так что l = {3,4}. Задача для нахождения направления имеет вид

Рис. 2

Эту задачу можно решить симплекс методом для решения задач линейного программирования. На рисунке 2 показана допустимая область этой задачи.

Линейный поиск. Теперь, двигаясь из точки (0, 0) вдоль направления (1, 1), нужно найти точку, в которой значение целевой функции минимально. Любая точка может быть записана в виде , а целевая функция в этой точке принимает вид . Максимальное значение коэффициента l, для которого точка допустима, вычисляется по формулам и равно

Следовательно, если —новая точка, то значение получается из решения следующей задачи одномерной минимизации:

минимизировать —10+2

при условии 0££ .

Очевидно, что решением является , так что

Итерация 2

Поиск, направления. В точке имеем .

Рис 3.

Кроме того, множество активных ограниче ний в точке х₂ равно l={2}, так что направление движения получается из решения следующей задачи:

минимизировать

при условии

Читатель может проверить на рис. 3, что оптимальным решением этой задачи линейного программирования является точка, а соответствующее значение целевой функции равно .

Линейный поиск. При начальной точке х₂ любая точка в направлении d₂ может быть представлена в виде Соответствующее ей значение целевой функции равно

Максимальноезначение l для которого точка Х₂+ld₂ остается допустимой, определяется в соответствия с (1) следующим образом:

Таким образом, в качестве ^ берется оптимальное решение следующей задачи:

минимизировать

при условии

Оптимальным решением этой задачи является ,так что

Рис 4.

Итерация 3

Поиск направления. Вточкех₃= имеем Кроме того, множество активных ограничений в точке х_з равно l ={2}, так что направление движения получается из решения следующей задачи:

Можно легко проверить по рис. 4. что действительно является решением этой задачи линейного программирования. Соответствующее значение целевой функции равно нулю, и процедура заканчивается. Более того, точка является точкой Куна—Таккера.

В этой конкретной задаче функция f выпукла, и по теореме 4.3.7 точка х является оптимальным решением.

Таблица 1

Результаты вычислений по методу Зойтендейка для случая линейных ограничений

Рис. 5. Поиск решения методом Зойтендейка (случай линейных ограничений).

В табл. 1 приведены результаты вычислений для рассмотренной задачи. На рис. 10.5 изображен процесс поиска решения в соответствии с описанным алгоритмом.

Задачи с нелинейными ограничениями-неравенствами

Теперь рассмотрим задачу, в которой допустимая область задается системой ограничений-неравенств не обязательно линейных:

минимизировать f(х)

при условиях g_i(х)£0,i=1, ...,m.

В теореме формулируются достаточные условия, при которых вектор d является возможным направлением спуска.

ТЕОРЕМА. Рассмотрим задачу минимизации f(х) при условиях g_i (х)£0,i=1, ...,m.. Пусть х—допустимая точка, а I—множество индексов активных в этой точке ограничений, т. е.. Предположим, кроме того, что функции f и g_i для дифференцируемы в х, а функции g_iдля непрерывны в этой точке. Если при , то вектор d является возможным направлением спуска.

Рис. 6. Совокупность возможных направлений спуска в задаче с нелинейными ограничениями. 1— 1-е ограничение; 2—3-е ограничение; 3—4-е ограничение; 4— 2-е ограничение; 5— возможные направления спуска; 6— линии уровня целевой функции.

Доказательство. Пусть вектор и удовлетворяет неравенствам и при . Для выполняютсянеравенства , и так как g_i непрерывны в точке х, то для достаточно малых . В силу дифференцируемости функций g_i при имеем

где при . Так как , то при достаточно малых . Следовательно, при i = 1, ...,m, т.е. точка допустимая для достаточно малых положительных значений . Аналогично из следует, что для достаточно малых > 0 имеем . Следовательно, вектор и является возможным направлением спуска.

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

Чтобы найти вектор d, удовлетворяющий неравенствам для , естественно минимизировать максимум из и для . Обозначим этот максимум через z. Вводя нормирующие ограничения Для каждого j, получим следующую задачу для нахождения направления.

Пусть (z, d)—оптимальное решение этой задачи линейного программирования. Если z<0, то очевидно, что d—возможное направление спуска. Если же z= 0, то, как показано ниже, текущая точка является точкой Ф. Джона.

ТЕОРЕМА.. Рассмотрим задачу минимизации f(х) при условиях g_i(х)£0, i = 1,..., m. Пусть х—допустимая точка, а. Рассмотрим следующую задачу нахождения направления:

Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.

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

Это и есть условие Ф. Джона.