Применение функционального анализа в теории приближений. Тверь: ТвГУ, 1999. С. 19-30.

=========================================================

УДК 519.6 : 62.50

В.О.АШКЕНАЗЫ

Тверской государственный университет

-------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------

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

– явный вид целевой функции может быть неизвестен и определение ее значений в точках в процессе поиска экстремума производится либо путем дорогостоящих измерений на реальном объекте, либо в результате трудоемкого численного моделирования на ЭВМ;

– отсутствуют сведения о производных (векторе градиента) целевой функции;

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

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

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

Шаг 1. По имеющемуся множеству данных построить функцию , наилучшим образом аппроксимирующую неизвестную целевую функцию . Аппроксимация должна допускать явное представление с легко вычисляемыми производными.

Шаг 2. Найти точку как решение экстремальной задачи

Шаг 3. Если и выполняются некоторые условия завершения поиска экстремума (например, достаточно мало расстояние между минимумами и двух последовательно полученных приближений и и/или мала разность , то остановиться, считая и . В противном случае принять и определить значение в точке . Заменить на и вернуться к шагу 1.

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

Соответствующий вычислительный алгоритм оптимального восстановления гладкой функции двух переменных был впервые предложен в [1]. Математическая теория и вычислительные аспекты построения интерполяционных и сглаживающих сплайн-функций в многомерной области на хаотической сетке детально разрабатывались как в нашей стране, так и за рубежом (см., например, [2]-[5]).

Сглаживающий -сплайн (сплайн-поверхность) , обеспечивает минимизацию функционала

характеризует "гладкость" аппроксимации. Здесь

Если , а множество точек содержит подмножество точек , на которых можно построить единственный многочлен степени, то существует единственный непрерывный -сплайн вида

где - это различные одночлены степени меньшей или равной , а

Функция является фундаментальным решением (функцией Грина) полигармонического уравнения (см., например, [6]) и с точностью до положительного постоянного множителя имеет вид

Коэффициенты и находятся из решения линейной системы

Если есть гауссово случайное поле с нулевым средним и известной корреляционной функцией , а случайные ошибки , имеют нормальное распределение с нулевым средним и известной корреляционной матрицей , то минимаксная аппроксимация функции , имеет удобный для вычисления вид

Здесь

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

Достаточно реалистичным обычно является представление об однородности и изотропности случайного поля , с

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

где

Заметим, что при параметрическом представлении корреляционной функции, например, в виде

где - интервал пространственной корреляции случайного поля , можно попытаться оценивать значение параметра по исходным данным в точках поиска. Аналогичный подход использован в алгоритме аппроксимационного поиска экстремума, описанном в [10].

4. Рассмотренные в п.п. 2, 3 методы глобальной аппроксимации целевой функции могут быть положены в основу алгоритма аппроксимационного поиска экстремума дорогостоящей целевой функции по п. 1. Однако при практической реализации соответствующих вычислительных процедур возникает ряд нетривиальных проблем. К их числу можно отнести:

- построение множества начальных точек поиска;

- построение аппроксимирующей (интерполирующей или сглаживающей) сплайн-поверхности по данным о целевой функции в имеющемся множестве точек;

- отыскание экстремума аппроксимирующей функции;

- управление областью поиска и множеством текущих точек поиска;

- выбор критериев остановки процесса аппроксимационного поиска экстремума.

Рассмотрим некоторые возможные подходы к решению этих проблем.

а) Даже при решении задачи безусловной минимизации

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

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

Однако задача оптимального покрытия в общем случае конструктивно не решена.

При практической реализации процедуры размещения начальных точек можно предположить, что область начального поиска имеет вид

"Детерминированный" способ состоит в выборе точек в узлах кубической решетки. При этом целесообразно иметь , где есть некоторое натуральное число. Но с ростом размерности задачи () кубическая решетка быстро становится неэффективной для поиска экстремума и желательно использовать "квазистохастические" равномерно распределенные последовательности точек (см. [11]-[14]), в частности - последовательности [13] или последовательности Холтона [14]. Описанные в [13] и [14] алгоритмы построения таких последовательностей достаточно просты для реализации на компьютере.

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

в) Любая из описанных нами аппроксимирующих функций , моделирующих целевую функцию по ее значениям в точках , допускает явное представление функции градиента и производных более высоких порядков. Поэтому для решения задачи (3) отыскания экстремума (если нужно - глобального) аппроксимирующей функции на каждом шаге поиска, можно использовать любую подходящую вычислительную процедуру нелинейного программирования для гладких функций (см., например, [16]-[18]).

Число точек , по которым строится аппроксимация целевой функции, с каждым шагом поиска по алгоритму п. 1, вообще говоря, увеличивается. Необходимость ограничения множества этих точек обусловлена следующими обстоятельствами. Во-первых, при сложной структуре целевой функции не все уже пройденные точки поиска будут одинаково существенными для построения хорошей аппроксимации в окрестности искомой точки минимума : значения (или ) в удаленных точках менее важны, чем в ближних. Иными словами, при приближении поиска к аппроксимацию целесообразно делать все более "локальной". Поэтому при достижении некоторого максимального числа точек следует отбрасывать в первую очередь точки, наиболее удаленные от текущей области поиска . Кроме того, возможно управлять поиском, увеличивая допустимую невязку сглаживающих сплайн--поверхностей в удаленных точках. Оправданность такого подхода подтверждается и проведенными вычислительными экспериментами по аппроксимационному поиску экстремума на тестовых задачах.

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

Применительно к -сплайнам в [19] получена следующая асимптотическая оценка погрешности гладкого восполнения функции сплайн-поверхностью на сгущающейся сетке из точек.

Для в любой внутренности области справедлива оценка

Материалы исследований по тематике этой статьи докладывались на научной конференции, посвященной 25-летию ТвГУ [20].

СПИСОК ЛИТЕРАТУРЫ

2. Duchon J. Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces} // Constructive Theory of Functions of Several Variables. Berlin, 1977. P. 85-100.

3. Meinguet J. Multivariate Interpolation at Arbitrary Points Made Simple // ZAMP. 1979. V. 30, N 2. P. 292--304.

9. Kimmeldorf G.S., Wahba G. A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines // The Annals of Math. Statistics. 1970. V. 41, N 2. P. 495-502.

10. Shagen I.P. Stochastic Interpolating Functions - Applications in Optimization // J. Inst. Maths. Applics. 1980. V. 26, N 1. P. 93-101.

12. Niederreiter H. Quasi-Monte Carlo Methods and Pseudo-Random Numbers // Bull. Amer. Math. Soc. 1978. V. 84, N 6. P. 957-1041.

14. Halton J.H. On the Efficiency of Certain Quasy-Random Sequences in Evaluating Multi-Dimensional Integrals // Numer. Math. 1960. V. 2, N 2. P 84-90.

19. Dushon J. Sur l'erreur d'interpolation des fonctions de plusieurs variables par les -splines // R.A.I.R.O. Analyse numerique. 1978. V. 12, N 4. P. 325-334.

Поступила в редколлегию 15.12.98.