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

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

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

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

Проблема ошибок вычисления функций .задачи подробнее рассматривается в разд. 8.5.

О методах интерполяции и аппроксимации данных гладкими функциями можно прочесть в сборнике под редакцией Хайеса (1970) и в статье Пауэлла (1977а). Современный (иа уровне 1977 г.) обзор и обширная библиография по этим методам даиы Коксом (1977).

Основные квадратурные формулы и описание их свойств приводятся в любом учебнике по численному анализу, например у Дальквиста и Бьёрка (1974). За более полными сведениями рекомендуем обратиться к работе Лайнесса (1977b). Подробное обсуждение трудностей, связанных с определением целевой функции задачи оптимизапин по адаптивной квадратурной схеме, читатель найдет в другой статье того же автора (Лайиесс (1976)).

7.4. ПРЕОБРАЗОВАНИЯ ЗАДАЧ

7.4.1. УПРОЩЕНИЕ ИЛИ ИСКЛЮЧЕНИЕ ОГРАНИЧЕНИЙ

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

7.4.1.1. Исключение простых ограничений. Любое преобразование :!адачн следует применять с большой осторожностью. В частности, некоторые «народные средства» облегчения поиска оптимума MOrjT на самом деле усложнять его. В качестве примера рассмотрим одни из самых «древних» способов преобразования оптимизационных постановок, предназначенный для задач вида

иайти min F (х)

при ограничениях х,>0, i=l,2.....п.

Идея состоит в том, что заменять их задачами без ограничений найтн min ¥ (ш),

где f (ш) получается из F(x) подстановкой вместо Х; квадрата новой переменной Wi, т.е. Хг=аи.

Пример 7.1. Возьмем в качестве первого объекта приложения рассматриваемой замены переменных квадратичную задачу вида

иайтн min(x, + l)= + (x,+ l)»

при ограничении х,

Градиент и матрица Гессе ее целевой функции равны /2(х,-(- 1)\ /2 0\

W=V2(x,-l-l)) lo 2J-

Решением является точка (О, -1). В любом методе минимизации прн простых ограничениях тнпа описанного в разд. 5.5.1 переменная X, в конце концов будет зафиксирована на нуле и после этого быстро определится минимум от (Xj-bl)" по Xj.

Замена х±, Ха на т\, соответственно приводит к следующей задаче:

найти min (ш, + 1) + {w+ 1)».

Первые н вторые производные ее целевой функции таковы!

fiw,(, + l)\ 4(Зш;-Ь1) О-

(») =

и к ней можно применить любой метод безусловной минимизации.

Хотя функция f несколько «более нелинейна», чем F, у нее есть только одна стационарная точка - там достигается искомый минимум и матрица Гессе хорошо обусловлена

Примеры, подобные приведенному, служат рекламой «квадратичного» преобразования, и именно благодаря им оно приобрело популярность. Однако далеко ие всегда получается столь удачная функция ¥.

Пример 7.2. Возьмем слегка отличную от предьщущей задачу: найти min (Xj - I)"-)-(Хг-Ь 1)

прн ограиичеини х, >0.

Ее решением является точка (1, -1), так что условие иа Xi теперь не является ограничительным. Отметим, что матрица Гессе [1елевой функции всюду положительно определена. Градиент и матрица Гессе преобразованной целевой функции выглядят следующим об-



разом:

(ю) =

Очевиден дефект - у есть седловая точка (О, -1). Это значит, что, применив к W алгоритм безусловной минимизации, гарантирующий лишь стационарность предела поиска (а таковыми являются все методы, кроме модифицированных ньютоновских), можно получить ложный оптимум, в то же время при решении исходной .задачи алгоритмом минимизации при простых ограничениях подобная неприятность исключена: если он и придет в точку (О, -1), то по знаку множителя Лагранжа в ней выяснится, что переменную х, следует считать свободной, и затем поиск будет осуществляться гю обеим переменным. Таким образом, комбинаторная проблема определения правильного рабочего списка, возникающая в методах активного набора, квадратичным преобразованием, вообще говоря, не снимается, а заменяется тоже комбинаторной и даже более сложной проблемой отбраковки неоптимальных стационарных точек. К сожалению, описанная трудность не единственна.

Пример 7.3. Рассмотрим задачу

найтн min х/» -- (х --1)»

при ограничении х, > О, имеющую решение (О, -1). Ее преобразованный аналог таков: найти min (ш5)"Ч-(iBj-I-1)".

Прежде всего следует отметить, что нельзя вычислять S как и*? + (Щ + 1)% поскольку в этом случае минимума в = О, = 1 не будет (на самом деле у представленного полинома вообще нет конечных минимумов). Обязательно надо сначала возводить ю, в квадрат, а уже затем брать корень-тогда ш, =0, т = -\ оказывается экстремальной (и единственной стационарной) точкой f". При этом, однако, матрица Гессе функции W равна

/20 (mQ" ON

т. е. в (О, -1) вырождена. Последнее отрицательно отразится на скорости сходимости любого алгоритма безусловной минимизации, предназначенного для функций с гладкими производными (см. разд. 8.3.1). Если же не преобразовывать исходную задачу, а применить к ней метод минимизации при простых ограничениях, никаких трудностей не возникает, так как переменная х, будет зафиксирована на граничном значении и соответственно исключена пз спроектированных градиентов и матриц Гессе.

7.4.1.2. Исключение неравенств. В настоящее время общепринята точка зрения, что задачи с ограничениями-неравенствами тяжелее задач с равенствами. Ее трудно оспаривать, но отсюда вовсе не следует, что искусственным преобразованием неравенств в равенства всегда можно упростить дело. К примеру, популярная замена ограничений вида t,-(x)>0 на c,{x)-yi=0, где {/(-специально вводимая вспомогательная переменная, вряд ли тюмогла многим, так как обладает теми же недостатками, что и преобразование, рассмотренное в предыдущем разделе. Если уж заменять неравенства равенствами, то лучше всего делать это введением новой переменной, подчиняемой условию неотрицательности, т. е. вместо с,-(х)>0 испачьзовать пару ограничений Ci(x)j/,.=0, J/i>0.

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

(a) по недосмотру утрачивается свойство экстрема.тьности искомой точки;

(b) существенно возрастает степень нелинейности пеленой функции;

(c) ухудшается с6а.тансированность задачи;

((1) у новой целевой функции появляются особенности, которых не было у исходной;

(e) теряется гладкость;

(f) матрица Гессе получается вырожденной или плохо обусловленной в решении;

(g) возникают дополнительные стационарные и локально экстремальные точки;

(h) зависимость целевой функции от новых переменных оказывается периодической.

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

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

Fljy+ja.,ei)=F{y), /=±1, ±2. ... , где е, есть i-й единичный вектор и немодифицированный алгоритм для очередной точки у дает шаг р, то в качестве следующего значе-



НИЯ 1-й переменной брать j/i+Pi с р,, получающимся увеличением нли уменьшением pi иа величину, кратную а, и подбираемую так, "чтобы было IPiKOi. Второй способ - вводить подходящие простые ограничения. Например, если yi имеет смысл некоторого угла, то . естественно потребовать соблюдения неравенств 0i/i2?i и использовать для минимизации алгоритм типа описанного в разд. 5.5.1.

Другие трудности, которые могут возникать прн нелинейных заменах переменных, проиллюстрированы на следующем простом примере.

Пример 7.4. Рассмотрим задачу

найти mill F (к) (7.3а)

прн ограничении 2 х1 = 1 Если «>1, определено преобразование

(7.3b)

JC, =sinj ... sinj/„ j, X,- =cos J,,., sin,... sin4-„ „ 1 = 2,

X„ = C031/„.j.

«теГбы (..ЗЬ) автомат.

(7.3b) вектор X выражаетсГчерез у Тякм Допустимый для

замена переменных дает зквГл„,1~-/едлагаемая

НЯЙти min дг/..i

найти min

у em-

(7.4)

т. е. позволяет избавиться от нелинейного ограничения. Однако у (7.4) есть нежелательные свойства. Помимо очевидной периодичности новая целевая функция плоха тем, что при близком к нулю значении (01) практически не зависит от у,, ... , ста.по

быть, задача (7.4) оказывается очень плохо отмасштабированной.

Иной способ автоматически удовлетворить ограничению (7.3b) - воспользоваться таким преобразованием:

c = ±(l+Sj,!J , (7.5)

, п-\

Оно приводит к задаче вида

(7.6) (7.7)

где Fp(j/I - функция, отвечающая верхнему знаку в (7.5), а f „((/) - нижнему.

Если заранее известно, что некоторая переменная Xt из (7.3) в решении будет иметь определенный знак, то замена ее, в не х„ по аналогичной (7.7) формуле позволит избавиться от необходимости введения двух функций. Среди нескольких Xi известного знака «в роли Хп» лучше использовать ту, оптимальное значение которой сильнее отличается ог нуля: при близкой к нулю правой части (7.7) новые переменные будут плохо отмасштабированы.

7.4.1.4. Тригонометрические преобразования. Несмотря на свои недостатки, замены переменных с использованием тригонометрических функций иногда все же целесообразны. Рассмотрим, например, задачу, в которой надо оптимизировать расположение k точек трехмерного пространства на сферической поверхности заданного радиуса. Формально она ставится так:

найти min F (х, у, г)

.у.е-"" (7.8)

прн ограничениях x;--i/(-f 4 = г", 1 = 1,2.....к.

в ней 3k переменных и k ограничений.

Правильное исключение ( независимых ограничений-равенств из задачи с п неизвестными должно приводить к понижению размерности до (п-О (см. разд. 6.3). В частности, чтобы обеспечить автоматическое соблюдение (7.8), достаточно перейти к 2k угловым kq-ординатам {6, т,], связанным с исходными следующим образом:

= г sin е,. cos vf „ {/,- = rsine, sint,-, г, = ссо8е,.. (7.9)

Для нейтрализации неприятных следствий периодичности получающейся в результате целевой функции, ее лучше минимизировать при простых ограничениях 0<6(<2л и 0<;<2п. В конкретной задаче эти ограничения, возможно, удастся усилить из каких-то априорных соображений. Всегда надо стремиться к тому, чтобы нижние границы были как можно ближе к верхним.

Переход к угловым координатам полезен и тогда, когда минимизацию требуется осуществлять на шаре радиуса г. В данном случае можно ввести k вспомогательных переменных {rfj}, имеющих смысл расстояний точек от нуля, что позволит записать условия их принадлежности шару парами соотношений вида

xt+y\+A=t,

Верхние удовлетворяются заменой переменных Xi=diSm 6(0051,-, i/i=diSin 6i sin ?,-=dfCOs 6j, т.е. в координатах {di, Oj, i} задача сводится к минимизации при простых ограничениях нв {di>.

(7.10)



[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