Главная Методы условной оптимизации [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] Свобода и ограничение есть два аспекта необходимости. Антуан де Сент-Экзюперн, «La Citadelles (1948) В этой главе рассматриваются задачи мниимизации нелинейных функций нрн нелинейных ограинченнях. Они намного сложнее задач с линейными ограничениями, и арсенал применяемых к ним методов, естественно, отражает это. В нем нет того концептуального единства, которое присуще схемам предыдущей главы, причем дажи близкие по идее методы могут значительно различаться в деталях. Как и в гл. 4 и 5, здесь будут описаны лишь те мегоды, в эффективности которых авторы неоднократгю убедились иа собственном опыте, и ге, которые нужны для пояснения каких-то важных моментов или в качестве основы для последующего из.поження. Ссылки на литературу, где обсуждаются иные методы или содержатся более подробные сведения о представленных, вынесены в замечания, завершающие каждый большой раздел. Там же называются имена авторов различных схем и результатов. Чтобы упростить изложение, мы не станем касаться задач с условиями смешанного типа, а будем разбирать только два случая; первый - все ограничения являются равенствами и второй - все они неравенства. Так уже делалось в гл. 3 и 5. Мы надеемся, что способы адаптации предлагаемых схем к задачам со смесью нелинейных равенств и неравенств читателю будут понятны н без наших пояснений. В большей части этой главы все ограничения трактуются одинаково - как нелинейные. На самом же деле, еспи какие-то из равенств или иеравенссв конкретной задачи линейны, их почти наверняка стоит выделить и в оптимизационном процессе обрабатывать приемами предыдущей главы. Итак, в дальнейшем речь будет идти о ззтче с ограничениями-равенствами NEP найти min F (х) при ограничениях с,(х) = 0, 1 = 1, t, и о задаче с ограничениями-неравенствами N IP найти min F (х) при ограничениях с,(х)>:0, i=\, ..., т. Везде, где не оговорено иное, функции ограничении {с,( или {с,-} и целевая функция F считаются дважды непрерывно дифференцируемыми. Когда употребляется термин «функции задачи», имеются в виду и {с,.[ (или {с,.[), и F одновременно. Условия оптимальности для NEP и NIP получены в разд. 3.4. Напомним, что градиенты функций ограничений с, (х) (с,, (х)) принято обозначать через а,, (х) (а, (х)), а матрицы Гессе-через б,, (х) (С, (х)). Под А (х) {А (х)) понимается матрица, чья i-я строка есть а,{ху. 6.1. ОБЩИЕ ОПРЕДЕЛЕНИЯ 6.1,1, ФУНКЦИЯ ВЫИГРЫША При обсуждении условий оптимапьности для задач NEP и NIP было отмечено, что движение по прямой из допустимой точки, где некоторое нелинейное ограничение обращается в равенство, вообще говоря, приведет к нарушению этого равенства независимо от того, как направлена прямая (т. е.- в терминах разд. 3.3.2 - для нелинейного ограничения не существует удерживающих направлений). Это обсгоятельство сильно осложняет учет нелинейных ограничений и оказывается решающим при разработке алгоритмов. Возвращаясь к представленным в предыдущей главе методам решения задач, ограничения которых линейны, отметим, что все они исходят из принципа сохранения допустимости, т. е. после того, как с помощью процедуры первой фазы найдено допустимое начальное приближение, генерируют последовательности допустимых точек. Такой принцип берется в основу организации поиска, в частности, потому, что его воплощение не требует чрезмерных усилий; (i) ограничения из рабочего списка выдерживаются благодаря выбору подходящих направлений движения; (ii) возможность нарушить прочие ограничения исключается правилами расчета длин шагов. При этом качество приближений характеризуется только значениями в них целевой функции. Поддерживать допустимость приближений при решении задач, среди ограничений которых есть нелинейные, намного сложнее (а подчас и просто невозможно). Если же допустимость не обеспечивается, то для того, чтобы определить, является ли точка Хй+, «лучшей», чем Хь, ма.ло сравнить F(Xh + i) и f (х)- нужно как-то сопоставить и соответствующие невязки ограничений. Точнее говоря, нужна функция выигрыша, значения которой отражали бы (обычно конфликтующие) стреы.пеШ1я к уменьшению F и соб.пюде-вию ограничений и потому могли бы быть использованы как показатели качества. Некая функция выигрыша явно или неявно обязательно присугствует в каждом алгоритме для NEPh N1P, генфнрую- щем недопустимые точки. Как будет видно из содержания данной главы, разные алгоритмы используют существенно разные функции выигрыша. 6.1.2. КЛАССИФИКАЦИЯ ПОДЗАДАЧ 6.1.2.1. Адаптивные и детерминированные подзадачи. В оптимизационных методах последовательности приближений строятся на основе решения подзадач, каким-то образом связанных с исходной задачей. В частности, если говорить о методах безусловной минимизации и минимизации при линейных ограничениях, то можно выделить две определяющие итерацию подзадачи: подзадачу расчета направления поиска и подзадачу выбора длины шага. Первая обычно детерминирована в том смысле, что число требуемых для ее решения обращений к процедурам вычисления исходгюй целевой функции F и ее производных известно заранее и не зависит от получаемых значений функции. Так, например, для расчета направления поиска в дискретном методе Ньютона, рассчитанном на функции с плотной матрицей Гессе, всегда требуется вычислить ровно п конечных разностей градиентов, и больше никакие связанные с F величины не нужны. Что же касается подзадачи выбора длины шага, то она, как правило, является адаптивной. Это значит, что заранее не известно, сколько раз придется вычислить F (или производные F) по ходу ее решения, и все будет зависеть от того, как поведет себя F в пробных точках. (Здесь уместно напомнить о критериях «существенного убывания» (см. разд. 4.3.2.1), которые включают F и производные от F.) Среди методов решения задач с нелинеГшыми ограничениями тоже есть такие, в которых построение очередной точки сводится к детерминированному вычислению направления поиска и адаптивному выбору длины шага. Однако наряду с этими методами существуют н другие, со значительно более сложными подзадачами. К примеру, очередное приближение может определяться как точка безусловного минимума или минимума при линейных ограничениях функции общего вида. Разумеется, подзадача отыскания этой точки относится к категории адаптивных, причем ее решение требует серии итераций со своими адаптивными подзадачами. Таким образом, здесь имеются адаптивные подзадачи двух уровней - внешние и внутренние. В дальнейшем, разбирая методы с последовательной минимизацией функций общего вида (без ограничений или с линейными ограничениями), мы будем касаться вопроса о том, как эту минимизацию осуществлять, только тогда, когда это будет отража ься на основных определениях. Вообще же предпочтительный способ зависит or доступности производных исходных функций, размерности и т. д. 6.1.2.2. Нормальные и дефектные подзадачи. Второй признак классификации подзадач - их разрешимость. Дело в том, что в некоторых методах подзадачи могут не иметь удовлетворительных решений даже при условии, что исходная задана поставлена вполне корректно. Соответственно выделяют нормальные и дефектные подзадачи. К первым относят те подзадачи, решения которых существуют и хорошо определены (например, подзадачи расчета вектора, удовлетворяющего системе линейных уравнений с невырожденной матрицей): ко вторым - подзадачи, ие имеющие решений или имеющие бесконечные решения (например, подзадачи безусловной минимизации квадратичной функции со знаконеопределенной матрицей Гессе или решения несовместной системы уравнениГ)). Дефетсгные подзадачи - не редкость для многих методов минимизации при нелинейных ограничениях. Если они идентифицируемы, на случай их появления предусматривают какие-то замены в фор мулировках. Однако бывают и такие подзадачи, выявить дефект ность которых невозможно; к примеру, нет универсального способа, позволяющего устанавливать существование или отсутствие коиеч ного безусловного минимума у нелинейных функций общего вида Тогда приходится действовать по-другому, а именно ограничивать усилия на решение одной подзадачи, с тем чтобы не тратигь время попусту, если она окажется дефектной. Наконец, надо отметить, что дефектность подзадачи может быть следствием порочности исходной постановки. Заканчивая на этом обсуждение затронутых вопросов, мы надеемся, что у читателя создалось впечатление о том, какие трудности могут возникнуть при решении сложных нелинейных задач. 6.2. МЕТОДЫ ШТРАФНЫХ И БАРЬЕРНЫХ ФУНКЦИЙ Один из подходов к решению задачи с нелинейными ограничениями состоит в том, чтобы сконструировать функцию, безусловный минимум которой совпадает с х* или связан с х* определенным образом. Тогда к х* можно прийти, решив одну нли много подзадач безусловной минимизации. Целевые функции таких подзадач впредь будем обозначать через Ф. 6.2.1. МЕТОДЫ ГЛАДКИХ ШТРАФНЫХ И БАРЬЕРНЫХ ФУНКЦИЯ Методы, рассматриваемые в этом разделе, имеют не очень хорошую репутацию и, как правило, не столь эффективны, как те, о которых речь пойдет в дальнейшем. Однако идеи, лежащие в их основе, представляют интерес, поскольку находят и более удачные воплощения, а знание свойств этих методов важно для понимания родственных им эффективных алгоритмов. 10 Л-н 29В4 6.2.1.1. Квадратичная штрафная функция. Обычно точка безусловного минимума целевой функции F задачи с ограничениями лежит за пределами допустимого множесгва либо F вообще ие ограничена снизу. Поэтому рассчитьшать на сходимость последовательности решений вспомогательных задач безусловной м1]ии-мизации к X* можно лишь в том случае, если Ф, включает какой-то член, обеспечивающий в пределе допустимость. В частности, таким членом может быть дифференцируемая функция, чьи значения в недопустимой области положительны и имеют смысл «штрафов» за нарушение ограничений. Основные идеи рассматриваемого подхода мы обсудим на примере квадратичной штрафной функции Pq(x, Р)- = f (х)-Ь-е-с(х)3(х). (6.1) в этой записи с{Х) есть вектор .левых частей нарушенных в х ограничении. (Ограничения-равенства условимся считать нарушенными в любой точке.) Неотрицательное число р называют параметром штрафа, а скалярное произведение с(хУс(х) - штрафным термом. Штрафной терм в (6.1) является непрерывно дифференцируемой функщ1ей. Его вторые производные разрывны, приче.м разрывы возникают в тех точках, где хотя одно из неравенств исходаюй задачи обращается в равенство. Таким образом, если в искомом решепии X* какие-то из ограничений-равенств активны, это решение будет точкой разрывности вторых производных от Pq. Чтобы устранить этот дефект Pq, можно условиться считать неравенство Cj(x)0 нарушеннь[м, если (х)<е для некоторого малого положительного е. При таком определении «нарушенных ограничений» нн в точке х*. ни Б некоторой ее окрестности разрывов вторых производных не будет. (Хотя есть сколько угодно неквадратичных штрафных термов, имеющих в X* непрерьтвные вторые производные, такими термами не пользуются, поскольку ни теоретически, нн практически это не дает никаких преимуществ.) При очень слабых предположениях удается доказать, что для достаточно больших р существует зависимость х* (р), определяющая точки безусловных минимумов по X функций (6.1) и обладающая тем свойством, что lira х(р) = х*. (6.2) Важно отметить, что для доказательства (6.2) регулярности ограничений в X* (см. разд. 3.4.1) не требуется. Проиллюстрируем результаты штрафного преобразования (6.1) на простом примере Пример 6.1. Рассмотрим одномерную задачу вида иайти min х при ограничении х-1=0. Для нее Pq{x. р) = х=---(х-1)> Графики F(x) и Pq(x, р) при р= 10 изображены штриховой и сплошной линиями соответственно на рис. 6а. Ясно, что lim x* (р) = х* = 1 Глядя на соотношение (6.2), можно подумать, что естественным способом поиска хорошего приближения х* бьшо бы взять очень большое (заведомо достаточное) значение параметра штрафа и один раз решить задачу безусловной минимизации Pq. Однако делать так н£ рекомендуется. Причина в том, что если г.о количество / ограничений, активных в X*, лежит в диапазоне 0<f<n, то число обусловленности матрицы 1.0 Гессе Р(х,р) вточкех*(р) растет с увеличением р и в пределе становится бесконечным. Значит, прн очень большом р мы получим очень тяжелую задачу 1.3 x Рис. 6а. Штриховая линия - график целевой безусловной минимизации, функции к, примера 6.1. f ():)-=х;силошная- В двумерном случае линии РФ" "РТв °? фунтаии (х. уровня плохо обусловлен- ) x-t {х ной штрафной функции в окрестности X* будут «почти параллельными». Пример 6.2. Рассмотрим задачу, которая еще не раз послужит для целей иллюстрации в будущем; найти min х,х «е9!= при ограничении 2-xf-XgO, Ее единственное ограничение активно в решении х*=(-0.81650, - 1.1547) и имеет множитель Лагранжа Я*=0.81650 (все величины округлены до пяти значащих цифр). [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.0011 |