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

[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]

8.4.2.2. Плохие масштабы. Иногда условия (8.18), (8.19) и (8.20) оказываются несовместными по одной из причин, которые можно считать проявлениями того, что функция выигрыша «плохо отмасштабирована» относительно направления р.

Пожалуй, самый типичный дефект рассматриваемого тнпа- нес-балансированносгь нзмененийФ„ и х при движении вдоль р. Если Фд! почти не реагирует даже на большие вариации х (это случается прн несбалансированных производных; см. разд. 8.7.1.3), то трудно обеспечить одновременное соблюдение неравенств (8.18) и (8.20). Обратная картина - сильная реакция Фд на незначительные изменения X - столь же нежелательна. Здесь, когда производная от Фд вдоль направления pj становится настолько большой, что определяется не первой, а второй нз величин в правой части (8.21), могут оказаться противоречивыми условия (8.18) и (8.19).

Угроза аварийного останова в процедуре одномерного поиска возникает также при отсутствии баланса между компонентами Хц и Pt. Допустим, например, что Xj = (IO", 1), Pt = (0, 1) и расчеты ведутся на машине с 6=10-". Тогда, хотя первая компонента Xj при движет™ вдоль сохраняется, т. е. на нее не надо было бы обращать внимания, именно из-за ее большой величины формула (8.21) даст 6ц порядка Ю", что, вообще говоря, многовато для минимальной длины шага по второй компоненте. Поэтому вполне может оказаться, что при к, подчиняющихся (8.19), неравенству (8.18) удовлетворить не удастся.

Коль скоро процедура выбора шага отказала по одной из перечисленных причин, а последняя в свою очередь объясняется некачественностью Рь, поиск, возможно, удастся продолжить после небольшой корректировки данных. В частности, ньютоновские направления бьрвают «плохо отмасштабнрованнымн» в точках хл, где градиент функции Ф„ достаточно велик и при этом ее матрица Гессе близка к вырождению («на ск.чоие длинного узкого оврага»), В случае соответствующего останова ньютоновский алгоритм надо запустить еще раз, задав в качестве начального приближения какую-нибудь точку, слегка отличающуюся от полученной к моменту прерывания. В квазнньютоновских алгоритмах неудачные направления чаще получаются в х, лежащих «ка дне оврага», причем тогда, когда оценки матрншл Гессе существенно неточны. Стало быть, если речь идет о повторном запуске квазиньютоновского метода, то следует изменить оценку матрицы Гессе (например, воспользоваться конечно-разностной аппроксимацией), а точку варьировать не надо. Когда неясно, чем объяснить отказ процедуры одномерного поиска - случайным выбором неудачного направления нли тем, что задача вообще плохо отмасштабиропана, полезно попробовать спуститься по антиградненту. Безрезультатность этой попытки (невыполнение условий «существенного убывания») будет признаком необходимости заново отмасштабнровать задачу каким-нибудь из способов, описанных в разд. 8.7.

8.4.2.3. Чрезмерно жесткие критерии останова. Слишком сильные требования к окончательному приближению (см. разд. 8.2) тоже нередко приводят к аварийному останову в блоке выбора шага. Это бывает, когда точка х оказывается настолько близкой к х*, что разница между значениями Фд в х и х* соразмерима с ошибкой вычислений. Тогда, даже если теоретическая возможность удовлетворить условию «существенного убывания» при спуске из х имеется, практическая вполне может отсутствовать. Именно поэтому алгоритмы иногда выдают признак отказа, хотя в действительности найдено хорошее решение.

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

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

Во-первых, вблизи точки безусловного минимума Ф;„ ни одна нз простых конечно-разностных формул хорошей оценки градиента не даст (см. разд. 8.6.1), и там отказ процедуры одномерного поиска будет нечем иным, как признаком достижения предельной точности.

Во-вторых, если взять неудачные конечно-разностные интервалы, оценка градиента g может оказаться очень плохой и в точке х, далекой от оптимальной. Тогда не исключено, что та самая формула расчета р, которая при использовании точных значений первых производных генерирует только направления спуска (см. разд. 8.4.6), из-за замены uag„ даст «направление подъема»; немедленное следствие-аварийный останов в блоке выбора шага. В такой ситуации надо построить более подходящий набор конечно-разностных интервалов (предназначенный для этого метод описан в разд. 8.6.2).

Неточность численного дифференцирования, послужившая причиной отказа процедуры одномерного поиска, может объясняться и малыми разрывами функции Ф,1 (сильные разрывы обычно проявляются более просто). На вероятность их существования укажут большие (по модулю) компоненты приближения градиента. Один из способов выяснить, действительно ли такие компоненты появились из-за разрывности Ф„,- посмотреть, к каким последствиям приведет увеличение соответствующих конечно-разностных интервалов. Допустим, к примеру, что интервал h, равен 10"* и между х и x+hiCi



есть точка, где скачком меняется на Ю"». Тогда оценка i-й производной будет иметь порядок т. Оценка той же производной при Л=10- окажется величиной порядка IO". Если бы не разрыв, такое изменение h, вряд ли привело бы к столь резкому различию в оценках.

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

8.4.3. УСТОЙЧИВО МЕДЛЕННЫЙ ПРОГРЕСС

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

Замедление прогресса бывает связано и с тем, что поиск привел в область, где функция плохо отмасштабирована. Здесь упомянутые выше приемы могут оказаться безрезультатными, и тогда необходимо либо заново стыасштабировать задачу (см. разд. 8.7), либо вообще переформулировать ее.

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

Аварийный останов по сформулированному признаку обычно объясняется тем, что, попав в вырожденную вершину допустимого множества, алгоритм не может выделить подходящий нсбор из п линейно независимых активных ограничений (см. разд. 5.82). Когда общее чисто активных ограничений невелико, есть смысл попытаться сделать это аналитическим путем. Если же их много и вырождение значительно, надо действовать иначе. Во-первых, для поиска

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

Серия нулевых шагов бывает также следствием обращения в нуль множителей Лагранжа некоторых активных неравенств. В данном случае оиа возникает в результате бесплодных «стараний» алгоритма найти такое подашожество линейно независитлых активных ограничений, которому отвечала бы положительно определенная спроектированная матрица Гессе (см. разд. 5.8.3). Как и в ситуации с вырожденной вершиной, здесь встает комбинаторная проблема. Правда, существует немалая вероятность, что точка останова на самом деле окажется приемлемым решением (ведь нулевые множители Лагранжа становятся помехой лишь при условии, что спроектированный градиент 6.11изок к нулю; см, разд. 5.8.3). Коль скоро на этог счет есть сомнение, можно попытаться подобрать подходящий рабочий спнсок из соображений аналитического плана, а если такой путь исключается, стоит попробовать вывести алгоритм из тупика с помощью небольших вариаций правых частей ограничений.

8.4.3.3. Оптимизация прн нелинейных ограничениях. Алгоритмы решения задач с нелинейными ограничениями могут «застревать» вдали от оптимума по нескольким причинам. В частности, говоря о схемах с подзадачами безусловной минимизации или минимизации при линейных ограничениях, надо указать на трудности, обсуждавшиеся в разд. 8.4.3,1 и 8.4.3.2. Однако отсутствие ощутимого прогресса во время поиска минимума при нелинейных ограничениях возможно и в силу иных обстоятельств.

Трудности идентификации правильного активного набора. Методы, опирающиеся на функции Лагранжа, иногда отказывают потому, что нз-за специфики задачи не могут выделить правильный активный набор. Допустим, для некоторых неактивных в х:* ограничений Г(л*) = й, где ЦвЦ-очень малая величина. Даже хорошему алгоритму вряд ли удастся отличать такие ограничения ог активных, пока не будет достигнуто неравенство с(;1С)<6, а это обычно требует большого числа итераций. Прогресс на таких итерациях оказывается незначительным, т.е. здесь возможен аварийный останов, причем тогда на точность полученного решения рассчитывать не приходится.

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



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

Трудности идентификации активного набора довольно характерны для задач /„ и (см. разд. 4.2.3), возникающих в контексте настройки математических моделей на данные наблюдений. Настройка осуществляется по опорным точкам, среди которых есть «критические», определяющие правильный активный набор; однако наряду с ними часто есть «почти» критические точки и соответственно «почти» активные в решении ограничения.

8.4.4. ВЫПОЛНЕНИЕ МАКСИЛИЛЬНОГО ЧИСЛА ИТЕРАЦИЙ ИЛИ ОБРАЩЕНИЙ К ПРОЦЕДУРЕ ВЫЧИСЛЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ

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

В частности, выход на верхнюю границу числа итераций иногда обьясняется тем, что у задачи есть неограниченное решение (см. также разд. 8.4.1). Бывает и так, что он обусловлен замелиением сходимости в силу какого-нибудь из обстоятельств, рассмотренных в разд. 8.4.3; тогда надо следовать приведенным там рекомендациям.

8.4.5. ОТСУТСТВИЕ ОЖИДАЕМОЙ СКОРОСТИ СХОДИМОСТИ

Когда пользователь рассчитывает на высокую скорость сходимости алгоритма, а она не проявилась, он может расценить это как признак «отказа». Однако, прежде чем перейти к обсуждению соответствующих причин, мы хотели бы подчеркнуть, что об отказе здесь можно говорить лишь в случае, если надежды, возлагаемые на алгоритм, имели твердую основу. Что же касается методов оценивания достигнутой скорости сходимости, то о них кратко сказано в разд. 8,3.1.

Чаще всего «отказы» рассматриваемого сорта случаются с ньютоновскими методами, от которых в согласии с теорией ожидают квадратичной сходимости. Существуют три основные причины, по которым ньютоновский метод может сходиться медленнее. Первая, самая распространенная - ошибки в программе вычисления матрицы Гессе.

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

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

Наконец, третья возможная причина - плохая обуслов-ченность (илн вырожденность) матрицы Гессе. Для квадратичной сходимости классического метода Ньютона требуется, чтобы в решении эта матрица была невырожденной, причем, чем больше число ее обусловленности, тем меньше область сходимости. Поэтому любой метод ньютоновского типа неизбежно потеряет быстродействие, если это число окажется очень большим. Когда все объясняется плохой от-масштабированностью задачи, дело можно попытаться поправить с помощью приемов, описанных в разд. 8.7.

Вырожденность матрицы Гессе в ре1пении, как правило, указывает на то, что точка минимума определена неоднозначно (для квадратичных форм этот момент обсуждался в разд. 3.2.3). Иногда неоднозначность оказывается следствием нечеткости формулировки задачи (соответствующий пример описан в разд. 7.6.1).

8.4.6. НЕУДАЧНОЕ НАПРАВ.ПЕНИЕ ПОИСКА

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

р[\ФтЫ<0 (8-22)

(когда Хп - нестационарная точка). Нарушение этого неравенства считается признаком отказа алгоритма.

Вектор обьино вычисляется как решение некоторой линейной системы вида

Мр, = -уФ«(Хд). (8.23)

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



[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.001