Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 45
Текст из файла (страница 45)
Вот одна из реализаций лаврентьевского примера. Пример [Лаврентьева), ,1«(х()) = Я вЂ” х ) х~д! пцп; х(О) = О,х(1) = 1 з Функция ! с х(1) = »СЕ допустима, она абсолютно непрерывна (т. е. при наллежит И', (1)) и в этом пространстве достигает глобального минимума. Но в пространстве функций, удовлетворяющих условию Липшица (И" (1)), минимум функционала положителен. Доказательство опирается на следующую лемму.
1сгз 1пз И' = (х( ) О И" ([а, Л[); — < х(Е) < — ч! Е [а, )з[, 4 2 пз нл 1з х(а) = —, х(Л) = 1(х()) = / (! — *'(!))'*'(!) д!» О. ь Действительно, в силу того, что —, <;(с), получаем; «Лс) р 1(х(),а,)з): = / (! — х'(1))'х*(!) да = » р р з х'(1)х' ь сб 9 ° ь = / ! (! — — ) й (!) д! > — / !зх (!) д1. (сс) 1 1б,/ » и 275 274 Глава 6. Общяя теория зкстршиальвых задач р Задача ) г~х~(з) гп - пнп; х(о) = е, х(Д) = йш легко пеша~~, » ~~ е 4 ' 2 в ней б 4, Алворзпъгы огпшмиэации 4.!.
Алгоритмы мнннмнзвцнн квадратичной функции Задача (З/5)з(,/2)б(1 — 1/2( /15)"')' 3' (гз/)?)згз)з 522гз Лемма доказана. Остальное просто. Если х( ) удовлетворяет условию Лившица, тогда, если 1 меньше некоторого йг, то х(1) < — ', О < 8 < 6г, а если ,цз 1 — 62 < 1 < 1 (при некотором 62), тогда х(1) > г— . значит, существуют 2 ' такие а и 12, как в лемме, и тогда У«(х()) > з(х(),а,)з) > со, что и требовалось.
Метод принудительного ограничения здесь к цели не приводит. Не исключено, что ситуация примера Лаврентьева имеет место в некоем «общем положении». Но может ли она встретиться в реально интересных задачах? И что делать, если ответ окажется утвердительным? На эти вопросы пока нет отчетливого ответа. Проблемы существования решения задачи особенно остро стоят в многомерных задачах вариацнонного исчисления, ибо там почти нет «явных решений», и необходимо гарантировать себе возможность получить приближенное решение, применив какой-либо метод финитизации. 4 4.
Алгоритмы оптимизации таким образом, дело сашипся к решению лептой задачи: даны дае точки А и С и ирозоляшая ме:кау ними горизонтальная орамая ОВ; требуется найти иа ашй прямой точку В, чтобы иугь АВС был иаискорейшим. Лейбниц (Вз аасьме и. Бед«уз«и 3! цю«я 1бзб г. ио ля«еду бГьгз«смоиюиы) Алгоритмы решения экстремальных задач делятся на прямые (т.е.
методы, не использующие необходимых условий экстремума) и «непрямые». В словах Лейбница, взятых нами в качестве эпиграфа, содержится первый намек на прямой метод в варнационном исчислении; задачу о брахистохроне Лейбниц решает. заменив кривую ломаной, исследуя конечномерную задачу и переходя к пределу. Прямые алгоритмы основываются, в основном, на идеях цвлесообразноло спуска, а также методах отсечения и штрафа.
Расскажем о некоторых из них. К(х) = — (Ах,х) — (Ь,х) — с- ппп; х Е ш, А > О, (Рг) ! л 2 где А — поло:кительно определенная матрица размера А х 6, безусловно принадлежит к числу простейших и актуальнейших проблем минимизации. Она коэрцитивна и конечномерна, и потому решение задачи х существует. По теореме Ферма должно удовлетворяться уравнение К'(х) = О сз Ах = Ь, и дело сводится, таким образом, к решениюлинейной системы.
Это — залача линейной алгебры. Ей посвящена огромная литература, не относящаяся к оптимизации. Одним из основных методов решения является метод Гаусса последовательного исключения неизвестных. Он прост по вычислительной схеме и устойчив по отношению «3 к ошибкам округления.
Этот метод требует — умножений (несмотря на значительные усилия последних лет существенное сокращение этого числа не удается). Многие методы минимизации функции К( ) реализуют идею целесообразного спуска. Таков, в частности, метод сонрлзкенныд градиентов (или сопрллсснныл направлений; направления у и у' называются сопрязсенными относительно симметрической матрицы А, если Ау ортогоначьно у'). Метод состоит в следующем. Берется произвольная точка хо и из нее спускаются в нижнюю точку функции К(.) вдоль луча 1ш исходящего из хо в направлении «минус градиента» уо — — -К'(хо). Находится точка х,, где функция К(.) достигает минимума на этом луче.
Далее рассматривается двумерное аффинное многообразие Ао, проходящее через точку х„с приложенными к ней векторами ус и К'(х,). Линия уровня ограничения функции К() на зто многообразие есть эллипс, касающийся луча 1,. Затем находится (сопряженное) направление у,, ведущее в центр эллипса. Вдоль этого направления снова ищется минимум квадратичной функции, в результате чего мы попадаем в центр эллипса хз.
тогда берется аффинное многообразие Аз, проходящее через хз, с приложенными к ней векторами уг и К'(хз) и все повторяется. Через не более, чем 6 шагов достигается искомый минимум 4.2. Метод центрнровйнных сечений и метод эллнцсондов Рассмотрим следующую проблему: найти минимум выпуклой диффсренцируемой функции / на выпуклом конечномсрном компактном теле А С ш": /(х) — ппп; х б А.
(Рз) Это — общая проблема выпуклой конечномерной оптимизации. 277 27б Глава 6. Общая теория экстремальных задач $4 Алгоритмы оптимизации Метод цеитрироваиных сечений В серелине шестидесятых голов А, Левин из России н Д. Ньюман из США предложили метод поиска минимума в задаче (Р2), базирующийся на теореме Грюнбаума — Хаммера, относящейся к выпуклой геометрии. Согласно этой теореме, если через центр тяжести некоторого выпуклого тела А в д-мерном пространстве провести гнперплоскость, то она разобьет тело на два множества А' и А н прн этом объем любого из этих пщ2множеств не превосходит величины (1 — —,) объема множества А. Сам метод (называемый методом цеитриравалпых сечений) состоит в следующем.
Обозначим А через Ае. Найдем точку хе — — дгАе центр тяжести Ае. Вычислим у'(хе). Если этот вектор — нулевой, задача решена; минимум уже найден, а если этот вектор отличен от нуля, можно отбросить часть Ае, лежащую в полупространстве Пе. = (х ! (У'(хе),х — х~) > 0) (ибо, как мы помним, для любой выпуклой функции выполнено неравенство Г(х) — 7'(4) > (2"(О,х — 4), и, значит, если х Е Ае П П~е, то у(х) > у(х~) > ш1п у.) Оставшуюся после отбрасывания А О П~а часть обозначим А, и повторим всю процедуру снова. И так далее. На я-том шаге выберем такую точку Е„среди (хн., ., х„), в которой значение у не больше, чем любое из значений [у(х,): 1 < 2 ( и).
Докажем, что Щ„) сходится к у и со скоростью геометрической прогрессии. Действительно, не ограничив себя в общности, можно считать, что 0 Е А и это — точка минимума в задаче (Р2), пусть а > (««л ) > —, (»«ЬЛ) - 2' (Уо1лС вЂ” объем д-мерного множества С). Тогда по определению Уо!л(аА) > Уо1«А„, т. е. найдется элемент х Е аА ! А„, Из конструкции алгоритма следует, что раз элемент х был отброшен, значит, у(х) > у(х,) лля некоторого в, а значит, 7(х) > У(Е„). Но й Е аА, следовательно, й = аЕ, Е Е А и значит по теореме Грюнбаума — Хаммера, (через Уагу обозначена максимальная разность у(х) — 2 (0), х Е А): Я ) < У(х) = У(аС+0(1 — а)) < а,Г(()+(1 — а)Г(О) = = У(0) + а(У(0 2(0))) < 2(0) + аУагу < Уо!лА» Оа < У(0) + ( ) Чат) < г(0) + (1 — е )"2~Чаг$. Уо1лАо Метод аписаиимх эллипсоидав Немировского — Юдина — Шара Метод описанных эллипсоидов основан на комбинации двух идей— яшее отсечения, о которой говорилось ранее, и на таком геометрическом факте: половину зллипсаида махгиа паиеслгить в эллипсоид абаеиа меньшего, челг изначальный эллипсоид! При этом, во-первых, отношение объема эллипсонда, содержащего полуэллипсоид к объему самого эллипсоида меньше единицы, и центр нового эллипсоила можно вычислить по полуэллипсонлу с затратой порядка д~ операций.
Построим описанный элли псоид. В силу аффинности задачи можно считать, что изначальный эллил псоид — это шар 2, 'х2 < 1, а полушар состоит из точек этого шара ь=! с неотрицательной последней координатой. Поместим центр описанного эллипсонда в точку Е с координатами (О,...,О, 1/(д+ 1)) и определим эллипсоид неравенством — 2(, 2 ) ( 7(д+ 1))2(д+ 1)2 д2 дз ( 2=! Объем построенного зллипсонда равен произведению полуосей на объем единичного шара, н делить потом надо на объем единичного шара, так что интересуюшая нас величина равна Без труда доказывается, что а(д) < 1 для любого натурального д > 2. А теперь можно описать и сам алгоритм. Обозначим через Ее некоторый эллипсоид, содержащий в себе множество А. Если его центр о2 не прннадле:кит А, проведем через се гиперплоскость, не содержащую точек из А и отбросим половину эллипсоида, не пересекающуюся с А. Если же се Е А, вычислим у'(се), произведем отсечение «по Левину — Ньюмену» и снова мы получим половину эллипсоида, которую обозначим Еа.
А теперь опишем вокруг Ее эллипсоид меньшего объема, чем объем Ее, обозначим новый эллипсоид Е~ и начнем все сначала. Это также приводит к стремлению по функционалу со скоростью геометрической прогрессии. К числу наиболее известных алгоритмов выпуклой оптимизации относится симплекс-метод.
Симплекс-метод, изложенный в гл. П, сыграл исключительную роль в истории численных методов оптимизации. Многие убеждены в том, что именно на решение задач симлекс-методом было затрачено наибольшее машинное время в сравнении с другими методами оптимизации. В течение многих десятилетий было неизвестно, принадлежат или нег задачи линейного программирования к числу так называемых неполиномиальных (т.е. «2рудных») задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
