оценивает V ие лучшим образом. Особенно же грубой эта оценка будет в том случае, когда итерации решения (fc-1)-й подзадачи прерываются раньше, чем вьнюлнятся условия оптимальности.

6.7.2. ИСПОЛЬЗОВАНИЕ КВАДРАТИЧНОЙ ПОДЗАДАЧИ

Ниже описаны методы решения (6.66) с квадратичными подзадачами вида (6.41). Лшейные ограничения из (6.65) в этих методах обрабатываются приемами гл. 5 и соответствешю выполняются в течение всего процесса поиска. Матрица в (6.41) будет включать А из (6.65), строки, отвечающие активным простым ограничениям на переменные, и градиенты функций {с,-(л:)} в х. Заметим, что от итерации к итерации может изменяться только часть коэффициентов Ак, а это надо использовать для экономной организации вычислений.

В ра.зд. 6.5.3 решение (6.41) было представлено через матрицы Y и 2 из LQ-разложения А (см. (6.42)). В случаях большой размерности тоже применяют подобные представления, ы рассмотрим одно из них, аналогичное полученному в разд. 5.6.2 для больших задач с линейными ограничениями (см. (5.73) и (5.74)).

Для удобства записи индекс k текущей итерации в дальнейшем опущен. Все исходные переменные разобьем на базтюные, супер-базисные и иебазисные (см. разд. 5.6.2). В соответствии с этим делением рассортируем столбцы А и компоненты векторов р и g. Поскольку небазнсные переменные фнкснрукгтся на своих граничных значениях, составляющая Рд вектора р будет нулевой (и ее можно опустить). Что же касается составляющих р„ и Ps, то ограничения (6.41) означают-, чю оии должны быть связаны равенством вида

где d - вектор, состоящий из нулей (они отвечают линейным ограничениям из (6.65)) и компонент вектора с, а В есть невырожденная квадратная <х<-матрица. Это равенство эквивалентно такому:

BpB=-d~Spe. (6.68)

На (6.68) можно смотреть как на систему уравнений с неизвестным Рл, решение которой при любом ps дает в комплекте с ps вектор, допустимый для (6.41) и для линейных ограничений исходной задачи.

Составляющая ps решетшя подзадачи (6.41) определяется безусловной минимизацией ее целевой функции после исключения с по-мотцью (6.68) переменной p,j. Выражение эт-ой функции через Рв и Ps ВЫ1-лядит так:

рнМвРв +PbHbsPs + \psHsPs + 81pb + 8sPs. (6.69)

где Нв, Hbs и 7/s - блоки матрицы

Hbs\

Подстановкой pB=B-d-Sps) в (6.69) получим квадратичную форму о Ps, условие минимальности которой сводится к аналогичному (6.44) равенству

zmZps = -Zg + ZH

(6.70)

с матрицей Z вида (5.75). Оно и задает искомый вектор ps.

"6.7.2.1. Представление матрицы, обратной к базисной. В данном разделе рассматривается техника представления матрицы B~ в методах решения задачи (6.65) с квадратичной подзадачей. Явно В" никогда не формируют, так что под «представлением В~Ч мы подразумеваем организацию вычисления решений уравнений типа (6.68) и, в частности, выбор способов разложения В и пересчета соответствующих факторов по хо;ту гюиска оптимума.

В дальнейшем используется следующее разбиение В на блоки:

ГВ. ВЛ\1,

Будем счтттать, что первые t, строк В (матрицы В, и В-г) отвечают линейным ограничениям (6.65), а последние строк (матрицы Вз и Bj) - нелинейным. Блоки Bi и В., квадратные.

От итерации к итерации в матрице В, во-первых, иногда (при сменах ба:)иса) заменяются столбцы и, во-вторых, всякий раз обновляются элементы нижних te строк. Из-за изменений второго типа проблема представления В" для (6.65) значительно сложнее, чем для задач с линейными отраннчеииями. Прн этом «кардинальные способы» ее разрешения вроде /.(/-разложения В заново на каждом шаге [le приемлемы (как чрезмерно трудоемкие); к треугольному разложению В «с нуля» прибегают лишь раз в несколько итераций ради повышения точности факторов н сокращения записи их представлений.

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

Разбиение на подматрицы. Поскольку матрица В, меняется только при сменах базиса, ее /. -разложение «поддерживать» ие-

трудно. Этим можно воспользоваться, организовав решение систем уравнений с В и В на основе разложений В, и матрицы размеров В: решение системы Вх=Ь представимо в виде

СП

где и,, «2 н Di определяется из уравнений

В1Щ = Ь, Dv = b,-~B,u, BiU, = -B,Vi. (6.72)

В ннх D=B-BsBBs, а bi и - составляющие разбиения вектора правых частей в соответствии с (6.71).

Вычисление В-Ь последовательным решением подсистем (6.72) фактически представляет собой процедуру блочного гауссова исключения с Bi в качестве первого блока. Иногда ее называют методом с разбиением В- на подматрицы. Известно несколько эффективных способов экономной реализации формул (6.72) с учетом специфики В.

Аппроксимация обратной матрицы; итеративное уточнение.

Один нз подходов к преодолению трудностей пересчета разложения матрицы В в связи с изменениями в ее nocjceflHux строках - выполнять его ие на каждой итерации. По сути дела это означает «шаг к методам» разд. 6.7.1, в которых параметры линеаризованных ограничений сохраняются постоянными, пока не будет иавдено решение подзадачи (6.66).

Возможны разные реализации рассматриваемого подхода. .Мы укажем на две из них. Пусть В"» - аппроксимирующап В матрица, которая соответствует той итерации, где разложение В было откорректировано в последний раз. Тогда, во-первых, можно вместо истинных решений систем типа Bx=b использовать векторы В~Ь (т. е. для ряда итераций заменять В на В), а, во-вторых, имея 6 и какое-то представление В"эти решения можно оценивать по схеме последовательного уточнения с В-Ь в роли начальных приближений.

ПредлагаОдМый способ огрубления методов с квадратичной подзадачей вполне допустим, так как в ннх точность аппроксимации нелинейных ограничений важна только вблизи х* (разд. 6.5.3.4). Что же касается удаленных от х* точек Xj, то здесь выбор параметров последних <2 ограничений в (6.67) достаточно произволен и важно лишь обеспечить существенное убывание функции выигрыша.

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

Точнее говоря, если в

BpB=d-SPs вместо Рв подставить решение рд системы

Bpu=d-Sps, то первые равенств не нарушаются.

*6.7.2.2. Расчет направления поиска в пространстве супербазисных переменных. После того как техника представления В" (а следовательно, и Z) оговорена, для 0[1ределения конкретного метода решения задачи (6.65) с использованием квадратичной подзадачи надо установить, как будет вычисляться ps из (6.70). Трудности здесь те же. что упоминались в разд. 5.6.2.1 при обсуждении больших задач с линейными ограничениями: может не хватать памяти для записи и требоваться слишком много вычислений для построения матриц ZHZ (и ZH). Матрица И размера пхп наверняка целиком ие поместится в памяти.

Зачастую заранее ясно, что размеры ZfiZ будут умеренными на всех итераш)ях, хотя число переменных п велико. Тогда строить ZHZ и решать (6.70) можно методами, которые используются для задач малой размерности. Например, в качестве ZHZ можно брать квазиньютоновскую аппроксимацию спроектированной матрицы Гессе функции Лагранжа. генерируемую (пересчшъшаемую от шага к шагу) какой-нибудь из процедур, анапогичиых тем, что применяются в случаях с линейными ограничениями. Вопросы, возникающие в связи с этим подходом, не являются характерными исключительно для больших задач и упоминались в замечаниях к разд. 6.5. Надо только отметить, что эффективный при небольшом числе переменных прием с вычислением конечных разностей вдоль столбцов Z теперь становится слишком трудоемким, так как формирование каждого из этих столбцов требует решения системы линейных уравнений с матрицей В. По той же причине, даже располагая матрицей W, приходится отказываться от построения ZWZ.

Если из-за ограничений по памяти или по трудоемкости явно представить ZHZ нельзя, но при этом удается эффективно вычислять произведения ZWZ иа вектор, то для определения ps можно применить линейный метод сопряженных градиентов с улучшением обусловленности (см. ра.зд. 4.8.6). Этот рецепт годится, например, когда матрица Гессе функции Лагранжа W является разреженной с известной структурой заполнения; в данном случае хорошо работает прием расчета ZU7Zw, описанный в разд. 5.1.2.5. Если же матрица W не разрежена (а, так как W компонуется нз нескольких матриц вторых производных, это бывает чаще, чем в задачах без ограничений), то не исключено, что положение удается спасти, используя в ZU/Zo вместо векторов WZv их оценки по конечным раз-

иостям градиентов функции Лагранжа вдоль Zv. Очевидно, такой выход приемлем лишь при условии, что вычисление упомянутых градиентов - относительно недорогая процедура.

Замечания и избранная библиография к разделу 6.7

Авторами рассмотренного в разд. 6.7.1 алгоритма являются Муртаф и Сондерс (1980). Он реализован в ФОРТРАН-пакете MINOS/AUGMENTED, который можно приобрести в Лаборатории оптимизации систем Станфордского университета. Розен (1978) предлагал использовать для больших задач типа (6.65) комбинированную схему, когда сначала процедурой «фазы 1» отыскивается неплохое приближение, а затем запускается алгоритм с подзадачами (6.37). В качестве средства решения последних рекомендовалась программа MINOS (см. разд. 5.6.2).

Очень часто к большим задачам применялась и применяется схема последовательного линейного программирования Гриффита и Стюарта (1961). Чем она привлекает, понятно - можно непосредственно использовать доступные коммерческие [1акеты решения больших линейных задач. Однако при этом возникает неприягная проблема выбора эвристических правил подгонки искусственных двусторонних ограничений на переменные подзадачи (см. замечания к разд. 6.5). Методы последовательного линейного программирования обсуждаются в работах Бейкера и Веиткера (1980), Бэтчелора и Била (1976), Била (1974, 1978).

Каждая итерация схемы обобщенных приведенных градиентов (см. разд. 6.3.1) фактически включает решение квадратичной подзадачи и может осуществляться теми же сренствами, которые используются в пакете MINOS. Джейи, Лэсдон и Сондерс (1976) описали соответствующую реализацию этой схемы, предназначенную для больших задач.

Вопросы оптимизации при нелинейных отраничениях и большом числе переменных с использованием квадратичных подзадач рассмотрены в работе Эскудеро (1980). Там же предлагается метод, основанный па квадратичной подзадаче с неравенствами. Идеи разд. 6.7.2 подробно изложены Гтшлом и др. (1981b). Схема с квадратичной подзадачей является более гибкой, чем схема-к подзадаче (6.66), но зато реализовать последнюю, располагая пакетом типа MINOS, намного проще.

Процедура (6.72) использует дополнения Шура, подробно рассматриваемые в статье Коттла (1974). Прочие ссылки по поводу методов решения разреженных линейных систем и пересчета представлений их матриц даны в замечаниях к разд. 5.6. Упомянутый в разд. 6.7.2.1 метод последовательного уточнения досконально разобран в книге Уилкинсоиа (1965).

6.8. ЗАДАЧИ СПЕЦИАЛЬНЫХ ТИПОВ

Среди существующих методов безусловной минимизации и ми-нимизац1[И при линейных или нелинейных ограничениях есть много специальных, рассчитанных на особые категории задач. Некоторые из них были представлены выше, напри\кр методы для задач линейного и квадратичного программирования (см. разд. 5.3.1, 5.3,2 и 5.6.1) и для безусловной задачи о наименьших квадратах (см. разд. 4.7). Говорилось также, хотя и без описания способов решения, о задачах безусловной минимизации негладких функций особой структуры.

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

6.8.1. СПЕЦИАЛЬНЫЕ З.АДЛЧИ МИНИМИЗАЦИИ НЕГЛАДКИХ ФУНКЦИЙ

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

найти min maxj/i (х), h{x)...../„ (х)], (6.73)

в которой {/i(x)) - гладкие функции. В данном случае прои-звод-ные от F терпят разрывы в точках, где fi=l]=F, Столь же просто характеризуются и точки разрывов F из (4.4): в каждой из них при некоторых i выполняются равенства /i=0.

Особый подкласс составляют задачи типа (6.73) и (4.4) с линсй-ны.ии {fi). При помощи преобразований, описанных в разд. 4.2.3, они сводятся к задачам линейного программирования и могут быть решены симплекс-методом. Применением техники последоватетьной линеаризации этот подход обобщается н иа (6.73), (4.4) с нелинейными {fi}, ио для них он не са.мый эффективный.

Современные методы решения нелинейных задач (4.4) и (6.73) работают по такому принципу: на каждой итерации (i) прогнозируется список равенств вида fi=fi=F (для (6.73)) или /(=0 (для