Cтраница 4
Сама по себе она, может быть, и не слишком интересна, но научившись решать ее, мы сможем, применяя технику перебора активных ограничений, строить методы поиска минимума в задачах с неравенствами. [46]
Ньютоновский вектор p ( ft) по-прежнему можно интерпретировать как направление обобщенного наискорейшего спуска, только теперь он выбирается из множества векторов, ортогональных нормалям активных ограничений. [47]
Чтобы избежать зигзага, не выводите ограничения, повторно появившегося в активном наборе, до тех пор, пока не будет найден минимум на пересечении гиперплоскостей активных ограничений, либо предусмотрите возможность вернуться к старому базису, когда полученный после вывода выигрыш окажется существенно меньше ожидаемого. [48]
В чистом виде алгоритмы Гольдфарба и Муртага - Саджен-та численно неустойчивы: направления, вычисляемые в них, из-за ошибок округления могут оказаться существенно не ортогональными нормалям активных ограничений и, значит, недопустимыми. Допустимость p ( ft обусловлена равенствами A ( ftrHo о Для метода Гольдфарба и д ( 4) т ( О для метода Муртага - Саджента, которые теоретически должны выполняться на всех итерациях. К несчастью - только теоретически, ибо, если состав активного набора сохраняется достаточно долго, ошибки, накапливаемые при пересчетах матриц Но и V ( fe), могут привести к большим невязкам в этих равенствах. Отсутствие непосредственного контроля за соблюдением соотношения между элементами столбцов матриц Но и V (, гарантирующих параллельность направления спуска гиперплоскостям активных ограничений, чревато вполне реальными неприятностями. Когда матрицы Но и V ft вычисляются только по значениям Но, V и р, даже небольшая потеря ортогональности на каком-нибудь шаге, распространяясь на все последующие шаги, способна быстро перерасти в серьезную ошибку. Сказанное легко проиллюстрировать, рассмотрев одну итерацию метода Гольдфарба. Предположим, что А ( 1) A ( ft) А и при пересчете Но на й-й итерации по DFP-формуле не возникает никаких новых ошибок. [49]
Следующая лемма утверждает, что если d - возможное направление в х или d D ( x), то Vgi ( x) td 0 для любого активного ограничения. [50]
Все множество X можно теперь разбить на непустые попарно непересекающиеся открытые грани, объединив в одну грань те точки множества, которым соответствует один и тот же набор активных ограничений. [51]
Как показывает накопленный вычислительный опыт, самое надежное средство против зигзага - стратегия Зойтендейка, только при применении ее на практике надо минимизировать целевую функцию на пересечении гиперплоскостей активных ограничений не точно, а приближенно, в рамках довольно свободного допуска. Если окажется, что в приближенном решении все множители Лагранжа положительны, надо уменьшить допуск и продолжить минимизацию. [52]
В случае выпуклости множества X х: / г ( х) 0, г 1 т условия линейной независимости векторов / г ( х), соответствующих активным ограничениям, в предыдущей теореме можно заменить более просто проверяемым, а именно так называемым условием регулярности. Существуют различные условия регулярности ограничений; здесь будут рассмотрены следующие условия. [53]