Файл: Методы оптимизации в статистических задачах управления..pdf

которая лежит внутри области D, определяемой системой огра­ ничений (283)

и выбираем некоторое положительное число 8lt с помощью кото­ рого разобьем всю систему ограничений (286) на две группы. К первой группе относятся ограничения, удовлетворяющие ус­ ловию

и ко второй группе относятся ограничения

FI (х°) + б1 > 0.

Ограничения первой группы выполняются с достаточным за­ пасом и поэтому не будут учитываться в выборе направления дви­ жения на первом шаге.

Задаемся далее положительным значением к г и выбираем на­

для ограничений второй группы при произвольном положитель­ ном t.

Из условий (287)—(289) видно, что задача выбора направле­ ния движения 5+ является задачей линейного программирования и может быть решена одним из разработанных алгоритмов, на­ пример симплекс-методом [26, 116]. После ее решения могут пред­ ставиться три случая:

1) S F p C - A ;

В первом случае точка х1, получаемая в результате осуществле­

122

где положительный скаляр t вычисляется из условия принадлеж­ ности точки хх границе области I. Иначе говоря, скаляр t выби­ рается как максимальное значение, при котором еще х1 удовлетво­ ряет системе ограничений (283).

Во втором случае, как и в первом, строится точка х1, но при осуществлении следующей итерации вместо значений бх и Хг используются параметры ÖJ2 и XJ2. Это означает, что точка х° находится недалеко от точки минимума.

Третий случай указывает на отсутствие направления £, удо­ влетворяющего условиям (288) и (289), при которых функция бF0 убывает. Из этого следует, что если значения Sj и ^ достаточно малы, то точка х° оптимальна. В противном случае необходимо

Все последующие итерации осуществляются аналогично пер­ вой. Итерационная процедура заканчивается при достижении

неравенств (283). Это предположение не вызывает существенных затруднений, так как обычно, вникнув в сущность решаемой экстремальной задачи, бывает нетрудно найти точку x0£ D . В то же время эта задача может быть решена и формальным ма­ тематическим методом, например на основе использования того же метода возможных направлений.

Действительно, предположим, что для точки у0, которая была выбрана в качестве начального приближения, не удовлетворяется некоторое k-e ограничение из системы .

Fk (у0) > 0.

Тогда рассмотрим задачу минимизации Fk (х) при условии вы­ полнения тех неравенств из системы (283), для которых F{ (у0) < 0. Эта задача может решаться, например, методом возможных на­ правлений при сведении ее к каноническому виду общим примером, изложенному в настоящем параграфе, или методом линеаризации функции. Процедура минимизации продолжается до тех пор, пока значение Fk (у) не станет отрицательным. Далее аналогич­ ным приемом добиваемся выполнения и всех других неравенств из системы (283).

NКак видно из изложения, метод возможных направлений яв­ ляется достаточно сложным в реализации. В то же время, как по­ казывает практика, он во многих случаях дает хорошую сходи­ мость и поэтому широко используется. Одним из недостатков метода является невозможность его применения для случая огра­ ничений типа равенств.

123

9. Методы решения задачи нелинейного программирования, основанные на использовании линейного программирования

Рассмотрение этой группы методов начнем с метода отсека­ ющих плоскостей [135]. Пусть требуется решить задачу выпуклого нелинейного программирования, записанную в канонической форме:

Метод отсекающих плоскостей основан на следующем свойстве

Действительно, используя неравенство (292), а также тот факт, что функция Fi (х) выпукла, легко показать, что если точка г принадлежит области D, т. е. удовлетворяет системе ограниче­ ний (291), то г также удовлетворяет системе ограничений (293).

Алгоритм метода заключается в следующем. Задаемся некото­ рой совокупностью точек х1, х2, . . ., хти строим систему ограни­ чений (293). Далее решаем задачу линейного программирования, которая состоит в минимизации F0 (х) на области 5 Г. При этом в процессе выбора точек х1, х2, . . хт необходимо позаботиться о том, чтобы задача линейного программирования имела бы конеч­ ное решение. Пусть решением задачи линейного программиро­ вания является точка хт+1.

Если хт+1 £ D, то очевидно, что хг+1 является точным опти­ мальным решением исходной задачи (291). Если хт+1 $ D, т. е.

124

если некоторые неравенства в (291) не удовлетворяются, то к си­ стеме ограничений (293) добавляются ограничения

на каждом шаге удобно решать двойственным симплекс-методом, так как этот метод хорошо приспособлен к решению задачи ли­ нейного программирования с растущим числом ограничений

[26, 116].

В процессе реализации метода бывает полезно с целью эконо­ мии памяти ЦВМ предусмотреть процедуру отбрасывания некото­ рых неравенств, которые добавлялись на предыдущих шагах.

Метод допускает простое обобщение в тех случаях, когда функции F{ (х) не дифференцируемые, однако требование вы­ пуклости является необходимым.

Недостатком метода отсекающих плоскостей является то, что практически для любой итерации результирующая точка не при­ надлежит требуемой области D. Кроме того, отсутствует правило окончания итерационной процедуры.

Близким по идее, но свободным от указанных недостатков является метод аппроксимации границ области, предложенной В. П. Булатовым [72]. Алгоритм метода состоит в следующем. Предположим, что требуется решить задачу нелинейного выпук­ лого программирования в канонической форме. Пусть х° точка есть внутренняя точка в области D. Построим некоторый много­ гранник S lt включающий в себя множество D. Простейшим много­

На первом шаге решим задачу минимизации функции F0 (х) на многограннике S x. Решение задачи обозначим q1. Это решение, как и в предыдущем методе, удобно определять двойственным симплекс-методом. Затем соединим точки х° и q1 отрезом прямой линии и определим точку х1 пересечения этого отрезка с границей области D:

X1 = х° + Ц (q1— х°).

Параметр Ц выбирается как наименьшая положительная ве­ личина, для которой удовлетворяется одно из уравнений

125

На следующем шаге строится новый многогранник <S2, который задается совместно системой неравенств (295) и неравенством, определяемым касательной плоскостью к границе области в точке X1. Это неравенство имеет вид

Очевидно, что к системе неравенств (295) нужно добавить не­ сколько неравенств (296), если равенство (297) выполняется одно­ временно для нескольких значений г. При определении точки х2,

Недостатком метода аппроксимации границ области является необходимость определения внутренней точки х°, а также необ­ ходимость решения на каждой итерации уравнений (297).

10. Задача минимизации функций в условиях помех

Раньше при изложении численных методов минимизации пред­ полагалось, что в процессе вычисления или измерения значений функции, градиента и т. д. ошибки отсутствуют. Однако в некото­ рых случаях, например, когда значение минимизируемой функции вычисляется методом статистического моделирования или опреде­ ляется путем прямых измерений, ошибки измерения оказываются значительными и их необходимо учитывать. К настоящему времени имеется значительное число работ, посвященных анализу влияния случайных возмущений на сходимость и точность детерминиро­ ванных методов оптимизации [66, 100, 102]. С другой стороны,

126