(8.60)

Если в качестве у/ берется Л из (8.54), то для хорошо отмасштабированной функции такое изменение должно иметь порядок е. Исходя из данной установки (после отбрасывания в (8.59) остаточного члена) можно выписать для dj уравнение, решением которого будет

А т/l + \F(x)\ •l V 2]C„ix)\

Этот масштабирующий множитель хорош и в ситуации, когда производная gi(x) отлична от нуля, ио настолько мала по модулю, что прн шаге h второе слагаемое справа в (8.57) доминирует.

Итак, решив отмасштабировать переменные по значениям производных, надо еще понять, какой из формул (8.58) или (8.60) воспользоваться. Неверный выбор может существенно осложнить последующую минимизацию. Если, например, взять формулу (8.58), хотя в действительности квадратичным членом тейлоровского разложения пренебрегать не следовало бы, то полученное значение dj может оказаться намного больше того, которое требуется на самом деле. Тогда функция будет «слишком нелинейной», и это затруднит работу любого алгоритма, ориентированного на линеаризацию.

Масштабирование, основанное на оценке оптимального конечно-разностиого интервала. Проблема выбора между (8.58)-(8.60) отпадает, если при масштабировании Опираться не на значения производных, а на численную оценку конечно-разностиого интервала, минимизирующего сумму ошибок усповии и отбрасывания при аппроксимации gj (х) (см. разд. 8.6).

Пусть fij-вычисленная оценка «оптимального» интерва.та для аппроксимации первой производной целегюй функции по /-Й исходной переменной (см, разд. 4.6.1.3 и 8.6.2), Возмущение х на Л/ эквивалентно возмущению j/ нз (8.56) па yy = /i/dy, причем для хороию отмасштабированной функции оптимальный интервал равен ft из (8.54). Таким образом, логично взять

(8.61)

Пример нормировки производных. Рассмотрим вычисление конечно-разностной оценки первой компоненты градиента функшщ из примера 8.5 после того, как первая переменная отмасштабирована в соответствии с (8.58) и (8.61). Формула (8.58) дает d, = .56x10". Значение sF (jz-f-ftfii) оказывается равным ,221792x10; при шаге А меняются три из шести шестнадца-теричных цнфр мантиссы, т. е. масштабирование приводит к желаемому результату. Однако оценка первой компоненты градиента, вычисленная но правой конечно-разностной формуле с интервалом ft, все же получается не слишком точной. Она равна -. 105062 х Ю,

в то время как истинным значением является -.110999x10. Ощутимое различие объясняется большой ошибкой отбрасывания -вторая производная при масштабировании увеличилась в 3.1x10 раз.

Величина dj, вычисленная в рассматриваемом случае по формуле (8.61), равна . 106х10«Соответствующим значением f"(j/--ftei) будет ,221956x10, Шаг ft и при таком di приводит к изменению трех из шести шестнадцатеричных цифр мантиссы. Правая коиечно-раз-ностная формула с ннтерва,10.м h теперь дает оценку производтюй, равную-.209920x10», Точным значением является .211682x10", Как и можно было ожидать, относительная погрешность конеч. но-разностиой аппроксимации при использовании (8,61) оказалась меньше, чем при использовании (8.58).

8.7.2. МАСШТАБИРОВЛНИЕ ЗНАЧЕНИЙ ЦЕЛЕВОЙ ФУНКЦИИ

Иногда считают, что масштаб значений целевой функции не играет никакой роли. Теоретически это действительно так, поскольку ни умножение F{x) иа положительную константу, нн дополнение F{x) постоянным слагаемым на решении не сказываются. (Заметим, что при умножении F на число пропоршюиально изменяется и все производные; сложение F с числом производных не меняет.) Однако отсюда еще ие следует, что такие операции не отразятся на работе алгортма поиска минимума.

Желательно, чтобы в окрестности искомой точки модули значений целевой функции были величинами порядка единицы или меньше. Этого всегда можно добиться, поделив F на подходящую константу. Например, если в исходном определении функция F(x) имеет порядок 10», то в оптимизационной профамме имеет смысл умножать ее и ее производные на 10"».

Шохо, когда целевая функция всюду близка к нулю. Как отмечалось в нескольких иэ предыдущих разделов, в правила останова реальных алгоритмов всегда включают не только тесты, оперирующие относительными величинами, но также альтернативный тест на близость к нулю некой абсолютной величины. Поэтому, хотя в теории умножение F, скажем, иа Ю"™ решения задачи не изменит, на практике оно приведет к тому, что алгоритм будет объявлять любую начальную точку оптимальной (нз-за того что норма градиента везде исчезающе мала).

Когда F содержит большую постоянную составляющую, переменная часть F отражается в вычисляемых значениях F с пониженной точностью. Поэтому рекомендуется избавляться от постоянных слагаемых, и лучше, например, определить F {х) как xj-f-x, чем как xf-f-xj-f 1000 (даже h3xj-)-xi-f-l единицу стоит убрать).

8.7.3. МАСШТАБИРОВАНИЕ ОГРАНИЧЕНИЙ

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

8.7.3.1, Некоторые следствия масштабирования ограничений.

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

В методах активного набора нормировка ограничений проявляется также в моменты сокращений рабочего списка вблизи условно стационарных точек jc. Вектор множителей Лагранжа Х„ в jCj определяется как решение совместной системы уравнений

Умножение ограничений на различные веса изменит строки Л„ и соотвегственно значения \, В частности, умножение /-го ограничения иа о)у приводит к делению на Шу компоненты У. с j-ы номером. При этом в большинстве алгоритмов из рабочего списка выводится то ограничение, которому отвечает максимальная по модулю оценка множителя. Значит, «взвешивание» ограничений может приводить к изменению последовательности точек, генерируемых алгоритмом.

Пример 8.10. Рассмотрим задачу с двумя переменными. Предположим, что скалярное произведение а\х представляет собой концентрацию растворенного в воде кислорода (характерное значение этой величины -одна миллионная), а скалярное произведение ofx-скорость течения (характерное значение-пять миль в час). Допустим, что они должны удовлетворять двусторонним неравенствам

0<оГх<8х10-«, 3<оГл:<10

и что 2х2-матрица А со строками йГ и оГ выглядит так:

/10-" -10-"\ = (, , ). (8.62)

Если при решении задачи будет получена точка, где оба левых неравенства обращаются в равенства и оба множителя Лаграижа отрицательны, то почти наверняка модуль первого множителя окажется намного больше модуля второго и из рабочего списка будет выве.цено первое ограничение.

В приведенном примере верхнее неравенство следует ушю-жить на Ю". После такой нормировки матрица Л преобразуется в

(8.63)

и становится очень хорошо обусловленной (столбцы (8.63) взаимно ортогональны).

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

8,7.3.2, Методы масштабирования линейных ограничений. Для

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

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

Алгоритм SC (масштабирование линейных ограничений) SC1. [Подсчет максимального отношения модулей для двух элементов одного столбца.] Вычислить

р„ = тах mzs.{\a,ila,i\\,

просматривая только те пары s, /, для которых а/фО.

SC2. [Нормировка строк.] При каждом i поделить i-ю строку матрицы А на ((min-1 а,у )(гаах а,.у )) где минимум берется только по тем i, для которых а,/фО.

SC3. [Нормировка столбцов.] При каждом / поделить /-Й столбец матрицы А на ((min,-1 а,., )(тах,. fly где минимум берется только по тем i, для которых о,.у0.

SC4. [Подсчет максимального отношения модулей для двух элементов одного столбца.] Вычислить

р = шахтах{ a,y/ajy},

просматривая только те пары s, /, для которых а/фО. SC5. [Проверка соблюдения условий останова.] Если р-р„)> >10-1р„, вернуться к шагу SC1. В противном случае - остановиться.

На шаге SC5 можно использовать и другие условия останова. Например, можно прерывать счет после выполнения определенного числа (скажем, пяти) итераций.

Если алгоритм SC применить к (8.62), то хорошо обусловленная матрица (8.63) будет получена на первой итерации.

8.7.3.3. Методы масштабирования нелинейных ограничений.

Для оценки точности, с которой численное решение задачи с линейными ограничениями должно (и будет) удовлетворять тем из них, что окажутся активными, достаточно результатов из вычислительной линейной алгебры. При правильной нормировке соответствующие невязки обычно оказываются величинами порядка в„. Что же касаегся нелинейных ограничоиий, го для них приемлемые значения иевязок могу г быть обоснованно оценены лишь при усповии, что известны достижимые точности (Ьа) подсчета функций Ci(x). Не располагая такой информацией, стандартный алгоритм будет стремиться обеспечить такие невязки ограничений, которые подходили бы под «естественное» определение «малых». Однако даже малые невязки, как правило, окажутся существенно различными (например, Ci(x*)=10-»», с,(л;*)==-10-« и т. д.).

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

даче из разд. 1.1 веса ограничений по объему и длине носового конуса надо подобрать так, чтобы правые части стали единичными.

Для нелинейных функций ограничений в принципе можно использовать методы масштабирования из разд. 8.7.1. К сожалению, это не просто, поскольку для разных функций потребуются разные преобразования переменных. Коль скоро задачу предполагается решать методом с использованием функции Лагранжа (см. разд. 6.4, 6.5 и 6.6), достаточно было бы от.часштабировать переменные относительно нее. Однако обычно сделать это ие удается, поскольку нет хороших априорных оценок компонент Я*.

Многие методы оптимизации при нелинейных ограничениях включают вычисления с матрицей Якоби для функций ограничений из рабочего списка. Ради повышения устойчивости таких методов при их реализации можно предусматривать предварительную «балансировку» матрицы Якоби по каждой итерации с помощью какой-нибудь процедуры типа алгоритма SC; впрочем, это работа разработчика, а не пользователя.

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

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

Пример 8.1 предложен Муртафом и Сондерсом (1977). Схема масштабирования по геометрическим средним успешно применяется в линейном программировании много лет; см., например, Бенишу и др. (1977). В той форме, в которой она изложена здесь, ее применял Фоурер (1979). О других схемах масштабирования линейных ограничений можно прочесть у Хэмминга (1971), Фалкерсона и Вулфа (1962), Кёртиса и Раида (1972). Результаты численных экспериментов с несколькими схемами представлены Томлином (1975b).