Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
32 32.07438 0.9 0.15 0 0.35 0.38 264
33 32.45504 0.17 0.6 0 -0.084 -0.044 282
41 32.36572 0.01 0.07 0 -0.011 -0.0023 366
42 32.36345 6Е — 3 0.017 0 -6.9Е-3 -6.2Е-3 372
43 32.35725 4Е — 4 0.017 0 -3.8Е-3 — 3.1 E — 3 378
51 32.34916 2Е — 5 5Е-3 0 -1.9Е-5 - 12Е - 2 426
52 32.34894 4Е-5 4Е-3 0 -83Е-5 -70Е-5 432
61 32.34879 IE-6 9Е-4 0 -6Е-6 -5Е-6 510
65 32.34869 IE-7 6Е-4 0
БЭСМ-6, причем половина этого времени тратится на вычисление / и их производных, половина — на решение задач линейного программирования. Решением является точка
х = {0, 0, 5.17278 , 0, 3.06138, 11.83698 , 0, 0, 0.10337, 0,
0.30007, 0.33342, 0.40013, 0.42823, 0.22397}.
430
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
Задачи негладкой оптимизации. Выше были рассмотрены алгоритмы, ориентированные на гладкие задачи в том смысле, что все функции /‘ предполагались достаточно простыми, гладкими. Кстати, что это значит? Ответ не так прост, как может показаться. Мы используем аппроксимацию функций f‘(x) линейными или квадратичными выражениями. Эффективность алгоритмов существенно зависит от того, как соотносятся между собой два числа: 5 — расстояние, на котором используемая аппроксимация описывает изменение функций с некоторой (10 %-ной, допустим) погрешностью, и L — расстояние от начального приближения Jt0 до искомой точки минимума х\ Грубо говоря, число шагов можно ориентировочно оценивать величиной L/S. Это отношение есть естественная мера гладкости функции. Читателю не должно казаться странным, что эта характеристика функцйи зависит от начального приближения, т.е. от априорной информации о расположении искомой точки х*.
Если говорить просто о классе негладких функций, то он включает в себя необозримое множество слишком разных функций. Универсальные алгоритмы поиска минимума таких функций строить можно, но они крайне неэффективны и особого интереса для практики не представляют. К счастью, обычно в практической работе возникают негладкие функции специфического типа, для которых можно разрабатывать специальные достаточно эффективные алгоритмы минимизации. В частности, одним из наиболее важных источников задач негладкой оптимизации является задача следующего типа (иногда ее называют чебышевской задачей):
min/°(jt), где f°(x) = max f°’j(x), х Є Rn. (12)
* j В задачу могут входить условия (2), и каждая из функций f‘(x) может
иметь форму (12). Важно подчеркнуть, что каждую из функций /0 ^ мы будем предполагать гладкой в том смысле, который выше мы придали этому термину. Функция f°(x) вида (12) принадлежит важному классу функций, дифференцируемых лишь по направлениям.
Определение 2. Функция f(x) называется дифференцируемой в точке х по направлениям, если для любого направления е (ІИІ = 1) существует предел
D(Xt е)=1 im?L*+JflrJlil'
s- +0 *
(Здесь s — скалярный параметр, всегда положительный!) Величина D(x, е) называется производной / в точке х по направлению е. При
гладких f°'J функция (12) почти во всех точках является просто дифференцируемой. Вычисляется эта производная очень просто.
Пусть j(x) — тот, пока единственный индекс, на котором достигается максимум в (12), т.е. f°(x} = f°'j(x\x), и это соотношение (в си-
§ 26]
ПОИСК МИНИМУМА
431
л у непрерывности) остается справедливым в некоторой окрестности точки х. Тогда /°(х) дифференцируема и D(x, е) = (f0' j<-^(x), е). Осложнения возникают в том случае, когда максимум в (12) достигается при двух (и более) индексах. Обозначим множество таких индексов j(x) = arg max /°- J(x). В этом случае
D(x, е) = max(f°'J(x), е).
JSj(X)
Конечно, множество точек х, в которых в j(x) входит больше одного индекса, имеет «нулевую меру», но при решении задач минимизации таких функций приходится иметь дело именно с точками из этого множества. Более того, если J больше размерности х, то типичной является ситуация, когда в точке минимума f°(x) в /(V) входит N + 1 индексов. Для построения минимизирующей последовательности точек X важно уметь находить направление е, вдоль которого f°(x) убывает. Это направление должно быть направлением убывания для всех функций f°'J (j Є j(x)), т.е. речь идет о выпуклом конусе, образованном пересечением подпространств:
(f°x’j(x), е) < 0, j Є j(x). (13)
По мере роста числа индексов в j(x) конус (13) становится все уже. В общем положении (т.е. если нет каких-то случайных совпадений) этот конус не пуст до тех пор, пока число индексов в j(x) не больше N. Ho как только это число станет хотя бы на единицу больше, конус (13) оказывается пустым.
Сложность задачи негладкой оптимизации связана со следующим обстоятельством. Когда функция /°(х) является гладкой, перемещение точки х по лучу x(s) = X + se (где s — скалярный параметр, е — почти любой вектор) приводит к убыванию /(.X + Se), если не при росте s, то при его убывании. В случае функции /° вида (12) ситуация иная. Для большинства векторов е такое движение по лучу сопровождается ростом /°: функция /°(х + se) аналогична |s|. Исключение составляют лишь векторы конуса (13). Обобщение метода линеаризации на задачи с /° типа (12) проходит почти автоматически: несколько изменяется лишь форма задачи линейного программирования для определения вариации 6х, а именно, вместо (10) имеем, очевидно,
