Алгоритм сплайновой экстраполяции при решении задач полубесконечной оптимизации

Размещено на http://www.allbest.ru/

Самарский государственный технический университет,

АЛГОРИТМ СПЛАЙНОВОЙ ЭКСТРАПОЛЯЦИИ ПРИ РЕШЕНИИ ЗАДАЧ ПОЛУБЕСКОНЕЧНОЙ ОПТИМИЗАЦИИ

А.П. Ефимов

Аннотация

алгоритм полубесконечный экстраполирование итерация

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

Ключевые слова: полубесконечная оптимизация, численные методы, итерации, сходимость, экстраполяция, D^m-сплайны, псевдокубические сплайны.

Введение

Исследованию задач полубесконечной оптимизации и разработке методов их решения посвящено огромное количество работ. Это обусловлено тем, что задачи полубесконечной оптимизации часто возникают при исследовании и оптимизации различных реальных систем, процессов, объектов. Например, это задачи нагрева изделий в индукционной печи с заданной или максимальной точностью [1, 2].

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

,

. (1)

Величина в (1) является максимально достижимой точностью минимизируемого поля при управлении .

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

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

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

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

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

Так как экстраполянт, естественно, не только должен приближать поле в уже исследованных областях, но и в какой-то степени предсказывать поведение вне этих областей, ряд требований должен предъявляться к поведению экстраполянта на удалении от исследованных областей. В частности, экстраполянт не должен вести себя на удалении от исследованных областей «слишком резко». Можно предположить ограничение изменения экстраполянта первой или второй степенью от расстояния до исследованной области.

Все эти требования в значительной степени можно удовлетворить при использовании интерполяционных D^m-сплайнов и псевдополиномиальных, в первую очередь, псевдокубических сплайнов на хаотических сетках. Интерполяционные D^m-сплайны и псевдополиномиальные сплайны основаны на вариационном подходе к построению сплайн-функций, имеют вполне конкретную физическую и геометрическую интерпретацию и в настоящее время достаточно хорошо изучены ([3-7] и др.).

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

Рассмотрим более подробно алгоритм, реализующий подход с использованием такой экстраполяции.

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

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

Основной этап состоит из ряда циклически повторяющихся шагов.

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

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

Шаг 3. Решение оптимальной задачи для построенного на предыдущем шаге приближения:

,

. (2)

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

Шаг 4. Обращение к модели и получение значения поля в точке, полученной на предыдущем шаге. Эта точка включается в число базовых точек.

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

Сходимость. Критерий останова алгоритма

Для любого итерационного алгоритма крайне важными являются вопрос об условиях сходимости и тесно связанный с ним вопрос о критерии останова алгоритма. Решение этих вопросов обычно базируется на понятии расстояния между двумя приближениями.

Пусть есть решение задачи (1). Тогда можно выделить [2, 8] локальные экстремумы функции , т.е. объединения концевых точек и точек, в которых

, , .

Пронумеруем эти точки в порядке невозрастания значений функции в них: для любых . Тогда для первых штук этих точек () выполняется условие

, (3)

а для остальных последующих

. (4)

В работах [1, 2, 8] достаточно всесторонне изучены свойства локальных экстремумов. Показано, что в большинстве практически важных случаев для (3) выполняется условие альтернанса . Показано, что выполнение условия альтернанса позволяет свести исходную задачу (1) к задаче математического программирования.

В общем случае условие (3) не является достаточным признаком решения. Общий достаточный признак строгого локального экстремума в точке состоит в строгой положительности производной от функции в этой точке по всем допустимым направлениям из конуса допустимых направлений [2, 8]: , или

, (5)

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

Таким образом, если вместо функции используется её приближение , совпадающее с на некотором множестве базовых точек , , в том числе в базовой точке , в которой для приближения выполняется условие, аналогичное (5):

, (6)

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

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

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

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

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

, , (7)

где - значение максимального отклонения в точке решения. Вычитая из каждого уравнения системы (7), например, последнее, получаем систему для нахождения :

, , (8)

где - якобиан системы (8).

Для поиска следующего приближения согласно разработанному алгоритму функция заменяется на приближённую, восстановленную по ранее вычисленным точкам функцию . Соответственно, вместо задачи (8) рассматривается задача

, , (9)

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

Сравнение линейных систем (8) и (9) позволяет получить [9] при некоторых дополнительных требованиях, предъявляемым к матрицам и , оценку сверху относительной погрешности получаемого приближенного решения в какой-либо векторной норме:

, (10)

где есть число обусловленности матрицы системы (8), - относительное отклонение приближённого якобиана от точного в норме, согласованной с выбранной векторной нормой. Выражение (10) не может быть использовано для оценки точности полученного приближения, но оно позволяет предъявить дополнительные требования к используемому приближению . В частности видно, что сходимость определяется точностью матрицы первых производных в окрестностях опорных точек. Для сходимости достаточно, чтобы выражение, стоящее в правой части (10), было меньше единицы. Этого можно добиваться как получением и использованием более точных приближений матрицы , так и, в какой-то степени, снижением числа обусловленности этой матрицы. Кроме того, видно, что если очередная итерация основного этапа алгоритма требует большого шага, при котором может быть получено большое значение ошибки , то возможны два следующих решения: искусственное уменьшение величины шага до разумного приемлемого значения или выполнение шага требуемой величины. В первом случае происходит продвижение алгоритма в нужном направлении, уточнение приближения и, возможно, улучшение решения. Во втором случае происходит уточнение приближения в большей области с меньшей гарантией получить улучшенное решение.

Согласно исследуемому алгоритму, следующим шагом будет обращение к модели и получение точного значения функции . Значения , соответствуют точному решению системы (7). Соответственно, вектор с компонентами , является невязкой решения системы (7). Тогда справедлива оценка в какой-либо векторной норме [9]

, (11)

где матрица есть матрица коэффициентов при неизвестных в левой части системы (7), вектор есть вектор правой части системы (7), матричная норма является согласованной с выбранной векторной нормой.

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

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

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

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

Библиографический список

1. Рапопорт Э.Я. Оптимизация процессов индукционного нагрева металла. М.: Металлургия, 1993. 279 с.

2. Рапопорт Э.Я. Альтернансный метод в прикладных задачах оптимизации. М.: Наука, 2000. 336 с.

3. Duchon J. Splines minimizing rotation-invariant semi-norms in Sobolev spaces // Constructive theory of functions of several variables. Berlin, 1977. P. 85-100.

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

5. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. Новосибирск: Наука, 1983.215 c.

6. Ашкеназы В.О. Сплайн-поверхности: Основы теории и вычислительные алгоритмы - Тверь: Тверской гос. ун-т, 2003. 82 с.

7. Arcangйli R., Lуpez de Silanes M.C., Torrens J.J. Multidimensional Minimizing Splines: Theory and Applications. Boston: Kluwer Academic Publishers, 2004. 280 p.

8. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М: Наука, 1972. 368 с.

9. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1985-1989. 655 с.

Размещено на Allbest.ru