Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 46
Текст из файла (страница 46)
Построим описанный элли псоид. В силу аффинности задачи можно считать, что изначальный эллил псоид — это шар 2, 'х2 < 1, а полушар состоит из точек этого шара о=! с неотрицательной последней координатой. Поместим центр описанного эллипсонда в точку Е с координатами (О,...,О, 1/(д+ 1)) и определим эллипсоид неравенством — 2(, 2 ) ( У(д+ 1))2(д+ 1)2 д2 дз ( о=! Объем построенного эллипсонда равен произведению полуосей на объем единичного шара, н делить потом надо на объем единичного шара, так что интересуюшая нас величина равна Без труда доказывается, что а(д) < 1 для любого натурального д > 2.
А теперь можно описать и сам алгоритм. Обозначим через Ео некоторый эллипсоид, содержащий в себе множество А. Если его центр со не прннадле:кит А, проведем через со гиперплоскость, не содержащую точек из А и отбросим половину эллипсоида, не пересекающуюся с А. Если же со Е А, вычислим У'(со), произведем отсечение «по Левину — Ньюмену» и снова мы получим половину эллипсоида, которую обозначим Ео. А теперь опишем вокруг Ео эллипсоид меньшего объема, чем объем Ео, обозначим новый эллипсоид Е~ и начнем все сначала.
Это также приводит к стремлению по функционалу со скоростью геометрической прогрессии. К числу наиболее известных алгоритмов выпуклой оптимизации относится симплекс-метод. Симплекс-метод, изложенный в гл. П, сыграл исключительную роль в истории численных методов оптимизации. Многие убеждены в том, что именно на решение задач симлекс-методом было затрачено наибольшее машинное время в сравнении с другими методами оптимизации. В течение многих десятилетий было неизвестно, принадлежат или нег задачи линейного программирования к числу так называемых неполиномиальных (т.е. «2рудных») задач. В 1970 году Кли и Минти построили примеры, показывающие, что симплекс-метод в некоторых ситуациях требует экспоненциального числа шагов.
Многие математики (в том числе и сам Данциг) не раз говорили, что воспринимают, как чудо пятидесятилетнюю триумфальную службу» симплекс-метода в бесчисленных 278 Глава 6. Общая теория экстремальных задач исследованиях прикладного характера (Данциг сказал: «Т1зе пешепдоца ровсег оу Фе эппр!ех шегпос! Ы а сопжап! аоцзпзе го ше»).
И лишь недавно были построены полнномнальные алгоритмы, сопоставимые с симлекс-методом по эффективности. Важный шаг был сделан Хачияном, который применил к решению задач линейного программирования метод зллипсондов. Но метод Хачияна на практике уступал симплекс-методу. Однако вскоре появились новые методы, которые во многих случаях оказались предпочтительнее симплекс-метода. Один из таких методов, получивших широкое распространение, стал метод, изобретенный индийским математиком Кармаркаром.
Но потом выяснилось, что за много лет до работы Кармаркара ту же основную идею построения адгорнтма, основанного на методе штрафа, выдвинул российский математик Дикин. Нет возможности здесь описать алгоритм Кармаркара — Дикнна (обо всех затронутых проблемах выпуклой оптимизации см. Шор (1989)). Алгоритмы рещеяиа задач классического вариаиивиного исчисления и оптимального управления Одними из важнейших при решении задач вариационного исчисления являются методы, редуцирующие задачу к конечномерной. Впервые такой метод применил, как было уже сказано, Лейбниц, заменивший искомую кривую ломаной.
Затем эту же идею разрабатывал Эйлер (метод ломаных Эйлера). Метод Бубнова — Галеркииа Необходимость решения задач вариационного исчисления, связанных с инженерными проблемами, стала особенно актуальной в начале века. Среди конкретных алгоритмов, реализующих идею редукции бесконечномерной задачи к конечномерной, выделяется метод Ритца (1908), развитый Галеркиным (!915). Поясним суть метолов Ритца и Галеркина на примере простейшей (вообще говоря — многомерной) задачи. Пусть требуется найти минимум функционала ) Х (1, х(!), й(!)) !!1, при условии, что на границе области П о функция х(.) принимает заданные значения.
Для нахождения функции близкой к минимальной, Ритц предложил рассматривать семейство фУнкций, зависащих от нескольких паРаметРов Ф(за), а = (б!,...,ая) такое, что при всех значениях параметра в граничные условия удовлетворяются. Галеркин, конкретизируя эту идею, для решения уравнения Эйлера рассматриваемой задачи, предлагал выбирать некоторое линейное пространство функций.
Приведем пример применения метода Галеркина нахождения минимума квадратичной задачи классического вариационного уравнения, приводящее к приближенному решению уравнения Штурма — Лиувилля. д 5. Приход!ения общей те!Янаи к решению коикречимх задач 279 Рассмотрим залачу: ( )) ( (йэ(!) 9(!)гсэ(!)) ги + 2((!)я(!) г!! — шш; о я(0) =а(Т) =0 (9) О) Уравнение Эйлера в этой задаче — одно из самых популярных в матема- тике и ее приложениях — уравнение Штурма — Лиувилля: й+ дх = /, я(0) = х(Т) = О.
Метод Галеркина (который конкретизировал идею Бубнова) состоит в том, что задавшись системой (сй())й !* сй() Е С ((О,!)) линейно- независимых функций, удовлетворяющих йулевым условиям на концах, ищем решение, минимизирующее функцию многих переменных: ш(х) = д(2 ' яйсй()), х = (х!,...,х„). Подставляя выражение аа() = 2, хйсй() й=! й=! в минимизируемый интеграл, получаем: с а .У(я ()) = ~~! ай!хйх! + 2~ Ьйхй, й,!= ! й=! т т где а = и = )'(гй(!)уг(!) — 9ЯдйЯ~гЯ) !!г, ьй — — э' 1(!)сй(!)ги. задача о свелась к конечномерной квадратичной задаче, которая обсуждалась выше.
Упражнение. Вычислить по методу Галеркина приближенное решение рассматриваемой задачи при Т = д(!) = У(!) = 1, яэ(Ф) = !(1-Ю)(а!+аэ ). ф 5. Приложения обшей теории к решению конкретных задач Ыатсматнкн прошлого сюдстнв со страстным рвением отдавались рсшснню отдсаьных трудных задач.
Я напомню только поставаснную Иоганном бсрнудвн шддчу о браанстоаронс. Гнаьбсрт Сасдусг поставнть парад собоа падь нзмсвать способ рсвшннв асса швач... овнам н пр!пон простым способом. ,!Ьыанбср О роли отдельных задач в истории нашей науки замечательно сказал Гильберт в словах, приведенных нами выше (и прн этом в качестве примера он привел задачу на экстремум!). Существует огромное число точно Глава 6. Общая теория экстремальных задач 280 решенных экстремальных задач — в классическом анализе, геометрии, алгебре...
С точно решенными задачами на экстремум связаны имена многих крупнейших математиков всех времен. В этом параграфе приводится свыше сорока задач, поставленных и решенных в разные времена, начиная с классической изопериметрической задачи, обсуждавшейся в 1У веке до нашей эры (решение ее было предложено Зенодором) и кончая некоторыми задачами, ставшими актуальными в самые последние годы.
Решения этих задач связаны с именами Архимеда, Евклила, Ферма, Кеплера, Ньютона, Лейбница, братьев Бернулли, Лагранжа, Эйлера, Чебышева, Бернштейна, Гильберта, Ландау, Адамара, Юнга, Блашке, Харди, Литглвула, Пойа, Наля, Колмогорова, Вейля и многих других.
Нам представляется важным подчеркнуть, что все эти задачи (как и подавляющее большинство других, которые могут быть решены «явно») допускают решения, полученные по единому методу, обсугкдавшемуся в этой части — методу Лагранжа. А именно, всюду можно поступать единообразно и «просто» (как, собственно, и рекомендовал поступать Даламбер). Сначала следует формализовать задачу, затем применять принцип Лагранжа, далее решать (или исслеловать) получающиеся уравнения. В итоге нахолятся функции. подозреваемые на экстремум, и наконец (с помощью достаточных условий) слелует доказывать, что получено именно решение задачи.
Не все задачи решаются здесь с полной подробностью, во многих случаях мы просто ссылаемся на решения, детально разобранные в книгах [ИТ[, [АТФ[, [АГГ[, [Т[, [ГТ[ или статье [МИ-Т], (а в ряде случаев— в первой части этой книги). Этот параграф книги не предназначен лля легкого чтения. Почти каждая из предлагаемых задач — это отдельная тема, которая далеко не исчерпывается ее решением.
Сами же решения могут слукить комментарием к методу Лагранжа, к полезности изучения теории экстремума, к истории математики, и могут быть использованы на лекциях, семинарских занятиях, а также на занятиях различных математических кружков Но вместе с тем большинство задач были в той или иной мере опробованы на семинарских занятиях или кружках (в частности, задачи 2, 6, 42 и 46 были прелложены студентам для решения вместо сдачи экзамена, они справились с заданием, и их решения были использованы в этом параграфе), так что все задачи б 5 интересны и доступны.
Старинные задачи и ях обобщения 1. Классическая изоперимегрическая задача Среди плоских кривых заданной длины найти кривую, охватывающую наибольшую площадь. Зто — одна из стариннейших задач на экстремум. Считается, что ответ в этой задаче был известен Аристотелю (1У век до н. э.). Об истории $ 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
