Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [ 65 ] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

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

Напоследок отметим, что введение разумных простых ограиичеини на переменные существенно сглаживает неприятные последствия неудачного выбора р.

8.1.3.8. Параметр штрафа для негладких задач. Негладкие задачи с 0раниченнями чаще всего решают методами, по.добнымп описанному в разд. 6.2.2.2. Обраи;аясь к соответствующей программе, пользователь должен определеть начальное значение параметра штрафа р. Как и в случае с модифицированной функцией .Лагранжа. обсуждавшемся выше, программа впоследствии может изменить это значение, причем допускаются поправки обоих знаков.

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

Опыт показывает, что на практике обычно подходит р~ -=тах{100, 100 F(Xi,)}. Как и дли методов модифицированных функций Лагранжа. надо выделить ситуации, когда известно хорошее начальное приближение Хс\ только теперь предпочтительны заниженные, а не завышенные значения р, скажем р=тах{1, F(Jf,)}. Снова следует отметить и положительное воздействие простых ограничений, в присутствии которых метод слабс-е реагирует на неудачные р. (Эти ограничения учитываются одинаково с общими, т. е. через соответствующие слагаемые в штрафном терне.)

8.1.4. ОШИБКИ В ПгеГРА.ЧМАХ ПОЛЬЗОВАТЕЛЯ

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

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

ментов, для которых верный ответ известен заранее, и посмотреть, что она выдаст. Это - хороший прием, но выбирать пробные точки надо аккуратно: просто удивительно, как часто берут х~0 и х=1 и как часто из-за специфики функций соответствующие тесты оказываются бессмысленными.

Особенно внимательно следует относиться к случаю, когда под-программе расчета функции нужны некоторые вспомогательные данные, передаваемые ей через массив-параметр или (в ФОРТРАНе) через С0Л1М0Ы-память. Иногда эти данные неумышленнио затираются, причем после того, как используются впервые; поэтому результат первого вычисления функции оказывается верным, а остальные - ошибочными. (Это одна из причин, по которой, присту-пая к решению задачи иа .MaiuHHe, имеет смысл для начала проделать короткий цикл «пробных итераций».)

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

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

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

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



пьЕтание, и пусть h - малое чисто, ар - случайный вектор единичной длины с одинаковыми по модулю компонентами. В нормальной ситуации должно выполняться приближенное равенство F(x+hp)-F(x)!hg(xVp. (8.1)

Если оно окажется нарушенным, то (i) либо градиент вычислен неверно, (ii) либо при подсчете F сильно сказываются ошибки округления, (iii) либо функция F плохо отмасштабирована (см. разд. 8.7.1). Последнюю нз трех перечислетшых альтернатив можно распознать с помощью соотношения

F (л-+hp)-F (х) x-(F{x + hp)-F (x-hp)). (8.2)

Справедливость (8.2) при нарушенном (8.1) является надежным признаком того, что в программе вычисления градиента допутдена ошибка. Еслн же (8.2) не выполняется, причем правые части (8.2) и (8.1) близки, ошибок, вероятнее всего, нет. Наконец, в случае, когда не соблюдается ни (8.1), ни (8.2) и правые части (8.1) и (8.2) существенно различны, надо посмотреть, что будет при увеличенном h. Коль скоро (8.1) остается нарушенным при любом разумном ft, программа вьгаиспения g, почти наверняка, неверна (поведение конечно-разностной аппроксимации производной в зависимости от b обсуждается в разд. 4.6.1 и 8.6),

Описанный способ тестировании в практическом отношении вполне эффективен для выятзлеиия больших ошибок при подсчете Л, но не позвапяет обнаруживать малые. В то же время и они могут стать причиной отказа алгоритма; как распознавать такие отказы, обсуждается в разд. 8.4.2.4.

Не сомневаясь в программе подсчета первых производных, правильность вычисления вторых можно проверять приемом, аналогичным описанному выше. Основой тестирования служит соотношение

hpG(x)p{g(x + hp)~g(x))rp. (8.3)

Если при первом пробном И оно нарушается, надо уве.личнть А и снова проверить его. Обозначим выбранные значения h через h, и ftj. Коль скоро (8.3) не выполняется при обоих и

К (£ (лг-f Л,р) -g(x)) р «й, (g (x + h.,p)-g{x))p. (8.4) то вторые производные, по-видимому, считаются неверно. Если же (8.4) тоже окажется нарушенным, то, как и в случае с первыми производными, надо повторить тест с другим значением h.

Небольшие погрешности при построении матрицы Гессе сходимости обычно не нарушают, но ее скорость может снизиться (см. разд. 8.3.1).

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

8.1.5. РАБОТА С ОГРАНИЧЕННЫМ МАТЕМАТИЧЕСКИМ ОБЕСПЕЧЕНИЕМ

fДалеко ие все существующие оптимизационные библиотеки столь полны, как хотелось бы, и нередко метод для решения своей задачи приходита выбирать из таких, среди которь]х нет специально приспособленного к ее типу. Об[цая рекомендация здесь может быть тадько одна - предпочтение надо отдать программе, эксплуатирующей максимум характерных особенностей задачи. Ниже мы обсудим некоторые конкретные случаи вынужденного применения не вполне подходящих средств.

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

Обозначим через J (л) матрицу Якоби системы функций, сумму квадратов которых надо минимизировать. Если в искомой точке все они близки к нулю, матрица Гессе этой суммы будет хорошо оцениваться произведением J (х) J {х). Значит, даже отказавшись от вычисления вторых производных, для задачи о наименьших квадратах все равно можно взять программу метода ньютоновского типа, «подменив» запрашиваемую ею процедуру построения матрицы Гессе процедурой расчета J (х)J (х); это лучше, чем обращаться к какому-нибудь o6uieMy методу первого порядка. Такой подход целесообразен и в случаях, ког.ла недоступны аналитические значения не только вторых, но и первых производных; здесь надо применить конечно-разностную аппроксимацию

Коль скоро невырожденность J (х) гарантировать нельзя, вместо J (х) J (х) предпочтительнее испо.льзовать какую-нибудь «похожую» на гюложительно определенную матрицу. Например, можно заменить J (х) J (х) на J (х) J (х)-\-а1, где о-малое положительное число (для хорошо отмасштабированной задачи подойдет а = Уъл1(\->г\Р(х)\)). Это избавит ньютоновский метод от затруднений, возникающих в случае, когда у матрицы системы для расчета направления поиска нет свойства существенной по- ложительной определенности.

8.I.S.2. Аппроксимация части производных. Подавляющее большинство стандартных программ минимизации составляют такие, которые, если уж прибегают к первым или вторым производным, требуют задания их всех без исключений. В то же время бывает, что доступны не все, а «почти все» производные. Тогда есть две



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

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

Д.ЧЯ аппроксимации части элементов матрицы Гессе по конечным разностям обычно прибегают к той самой программе подсчета первых производных, которая используется в блоке выбора направления поиска и строит градиент целиком. Если при этом брать в качестве конечно-разностных векторов единичные, то сэкономить усилия по сравнению со случаем с аппроксимацией всех вторых производных удастся лишь при условии, что какие-то столбцы матрицы Гессе известны [Юлиостыо. В то же время иногда лишнего счета можно избежать, даже если неизвестные э.тементы есть в каждом столбце. Д.пя этого надо подобрать специальные конечно-разностные векторь!, и здесь привлекагсгг технику, обсуждавшуюся в разд. 4.8.1 в связи с проблемой эффективного оценивания разреженных матриц Гессе. Следует, однако, отметить, что соответствующие приемы часто оказываются довольно сложными.

8.1.5.3. Решение задач с ограничениями программой безусловной минимизации. Если понадобилось найти минимум при нелинейных ограничениих, а в вашем распоряжении есть только программа безусловной минимизации, то на ее основе можно реализовать схему с модифицированной функцией Лагранжа (см. разд. 6.4) {Штрафными функциями лучше ни пользоваться; см. разд. 6.2.1.1.) При этом до-тжиы быть принять! определенные предосторожности, В общем случае модифицированная функция Лагранжа для ряда (а иногда и для всех) значений параметра штрафа оказывается неограниченной снизу. Поэтому необходимо как-то застраховать применяемый к ней метод от бессмысленного счета, например устанавливая относительно невысокую квоту на количество пробных точек нли занижая максимальную разрешенную ветчину шага (см. разд. 8.1.3.4 и 8.1.3.5). Если же имеется программа минимизации при простых ограничениях, то разумнее всего ввести таковые и использовать ее - это самый надежный способ решения проблем, связанных с неограниченностью.

8.1.5.4. Учет линейных и нелинейных ограничений. По многим соображениям теоретического и практического характера (см. гл. 5) линейные и нелинейные ограничения лучше учитывать по-

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

8.1.5.5. Нелинейные уравнении. Не располагая специальными программами решения систем нелинейны.ч уравнений, вместо них можно применять (обычно с тем же успехом) программы минимизации сумм квадратов. Коль скоро некоторые из уравнений линейны, лучше не включать нх в минимизируемую сумму, а учитывать не-посредствепно, т. е. взять метод для задач о наименьших квадратах с линейными ограничениями (пример задачи такого сорта рассмотрен в разд. 7.6.2).

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

Рассмотренные выше параметры настройки стандартных программ довольно типичньЕ, и, в часпюсти, характерны для библиотек, поставляемых Группой численных алгоритмов (NAG) и Национальной физической лабораторией. Эти библиотеки наряду с основными включают и различные сервисные программы.

Принципы разработки и рациональная структура фортранов-ского математического обеспечения для нужд оптимизации приведены в статье Ги-тла, Мюррея, Пиксна и Райт (1979). О процедурах выбора метода, реализованных в разных библиотеках и работающих по блок-схемам типа приведенной в разд. 8.1.1.1, можно прочесть, например, у Флетчера (1972с). Смита и др, (1974) и в «Руководстве-справочнике по ФОРТРАН-библиотеке» (1981).

Огандарт МРЗ-формала подробно описан в документе фирмы 1ВЛ1 за номером Н20-0476-2 («Система математического программирования 360, версия 2, линейное и сепарабельное программирование Руководство пальзователю», стр. 141 - 151). Более сжатое Описание и иллюстративные примеры читатель найдет в инструк-



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [ 65 ] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0015