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