Содержание к диссертации
Введение
Глава 1. Системный анализ и обзор методов оптимизации 12
1.1.Системный анализ проблемы оптимизации 12
1.2.Задачи постановочного характера и точность средств измерений 16
1.3. Машинная арифметика и анализ точности операций и процессов 23
1.4.Масштабирование переменных, целевой функции и градиента 34
1.5.Оценивание квазиньютоновского направления 42
1.6.Одномерная оптимизация 83
1.7,Оценивание точности решения и критерии останова 99
Глава 2. Постановка задачи построения системы квазиньютоновской оптимизации высокой точности ProfMiniHP 106
2.1.Математическая постановка задачи квазиньютоновскои оптимизации высокой точности 106
2.2. Алгоритмически-программная постановка задачи оптимизации высокой точности 107
2.3.Постановка задачи исследования системы оптимизации высокой точности 109
Глава 3. Решение задачи построения системы квазиньютоновскои оптимизации высокой точности 110
3.1.Математическое решение 110
3.2. Алгоритмическое решение 151
3.3.Программное решение 173
Глава 4. Численные исследования программной системы ProfMiniHP квазиньютоновскои оптимизации высокой точности 193
4.1.Тест-функции численного исследования 193
4.2. Численные исследования подсистемы дифференцирования GradientSearch 196
4.3.Численные исследования подсистемы RegulHessInvert регуляризации обратной квазиньютоновскои матрицы Гессе 201
4.4.Численные исследования подсистемы LineSearch оценивания шага одномерного поиска 207
4.5.Численные исследования системы квазиньютоновской оптимизации высокой точности в целом 218
Заключение 241
Библиографический список
- Машинная арифметика и анализ точности операций и процессов
- Алгоритмически-программная постановка задачи оптимизации высокой точности
- Алгоритмическое решение
- Численные исследования подсистемы дифференцирования GradientSearch
Введение к работе
Современные методы численной оптимизации традиционно широко применяются во многих областях человеческого знания. В последние десятилетия интерес к этим методам резко возрос в связи с серьезной математизацией теоретической и прикладной экономики. Содержание работ нобелевских лауреатов по экономике(финансам) в 90-е годы 20-го столетия, например, знаменитая теория оптимизации инвестиционного портфеля Марковитца[202], хорошо подтверждают это. Известны глубокие и интересные примеры решения сложных оптимизационных задач в технике[154], электронике[12], системах управления с участием человека[93], химической технологии[8, 62, 35], медицине[5], авиации и космонавтике[22] и т.д.
Важный аспект оптимизации связан с повышением точности ее решений. Именно это обстоятельство определяет значительный и все увеличивающийся интерес к квазиньютоновским методам, которые, как считается, могут позволить это сделать.
Эти соображения определили основные цели данной диссертационной работы, ее структуру и содержание.
В первой главе приведены результаты аналитического обзора современного состояния численных методов квазиньютоновской оптимизации, в частности, методов Давидона[142], Флетчера, Пауэлла[162], Бройдена[126], Пирсона[227], а также смежных методов адаптивного численного дифференцирования[54], одномерной оптимизации[123, 77], векторного и матричного анализом[82, 90, 18, 19], применения машинной арифметики конечной точности[86, 81, 134, 193].
Во второй главе дана постановка задачи синтеза диалоговой системы оптимизации высокой точности. Определены основные требования к создаваемой системе оптимизации, как по составу включаемых методов, так и по их программной реализации.
В третьей главе рассматривается решение поставленной задачи, охватывающее основные математические, алгоритмические и программные
аспекты реализации программной системы оптимизации.
Четвертая глава посвящена численным исследованиям реализованной программной системы. В качестве тест-функции выбраны известные функции Вуда[257] и Пауэлла[233а], имеющие важные и необходимые для целей тестирования особенности. Все приводимые фрагменты результатов численных исследований представлены таблично, детально прокомментированы и завершены рейтингами как используемых квазиныотоновских, так и их сопровождающих, численных методов дифференцирования, одномерного поиска и аппроксимации начальной обратной матрицы Гессе.
Для объективного оценивания полученных результатов проведено их сравнение с результатами минимизации выбранных тест-функций известными пакетами оптимизации, входящими в состав широко распространенных коммерческих систем компьютерной математики MathCAD 8[24], MATLAB 6, Mathematica4[25].
В заключении дана краткая характеристика проделанной работы и основных, полученных при ее выполнении, результатов.
Актуальность темы исследований. Ускоряющийся рост как общемирового, так и российского производства при все возрастающих потребностях в энергии, материалах, трудовых, информационных и интеллектуальных ресурсах, а также в условиях их все большего дефицита, весьма остро ставит проблему их оптимального использования. При этом ясно, что важнейшим аспектом оптимального решения становится его точность. Однако такой взгляд на проблему оптимизации начинает реально влиять на практику, а значит, и теорию оптимизации только в 90-е годы 20 века. Этому есть объективные причины. Действительно, прикладная оптимизация как важное научно-прикладное направление начала развиваться, по существу, после появления и относительно широкого распространения средств вычислительной техники в 50-70-х годах. При этом низкая производительность компьютеров первых поколений обусловила общепринятое понимание эффективности алгоритмов оптимизации как флоп-минимальных. Такая
трактовка эффективности во многом сохраняется и сейчас, но, в основном, в приложении к задачам оптимизации большой(тысячи) и очень большой(десятки и сотни тысяч) размерности пространства независимых переменных. Вместе с тем, уже в 60-е годы начинают появляться первые теоретические[14, 39, 79, ...] и прикладные[256, 86, ...] работы, в которых акцентируется вопрос о устойчивости и точности алгоритмов оптимизации. Влияние этих и многих других работ[36, 47, 51, 83, 88, 108, 131, 134, 142, 162, 167, ...] привело в 80-90-х годах не только к появлению суперкомпьютеров с длиной машинного слова в 48, 64 и 128 двоичных разрядов, но и к разработке IEEE-стандарта двоичной арифметики[113, 114], в настоящее время реализованного в рабочих станциях Sun, DEC, HP и IBM, а также во всех персональных компьютерах. Платформа IEEE-арифметики в приложении к задачам оптимизации высокой точности только начинает осваиваться. Основное направление этого развития - "силовое", т.е. разработка алгоритмов, использующих как IEEE-арифметику двойной, реже, расширенной двойной точности, реализованную в компьютерах Intel Pentium, так и близкую к IEEE-стандарту арифметику двойной и дважды двойной (учетверенной, использующей переменные real* 16) точности, программно моделируемую на компьютерах Cray серий С90, J90, T3D и ТЗЕ, DEC Vax, DEC Alpha, NEC SX-4, Sun Spark и IBM RS6000[19, 32].
Однако даже акцентированного использования IEEE-арифметики недостаточно для получения оптимальных решений высокой точности. Рациональное повышение точности решений должно также опираться на системный анализ всех важнейших аспектов оптимизации, учитывая не только качество математических методов, используемых во внешней и внутренней среде проблемы[17, 38, 45, 48, 66, 108, 174, 193, 245], но и качество их алгоритмической и программной реализации[120, 121, 144, 151, 152, 190, 197, 214, 234], включая создание дружественного пользователю интерфейса.
Таким образом, системный анализ проблемы квазиныотоновской оптимизации и разработка на его основе и с применением возможностей IEEE-
арифметики математического, алгоритмического и программного обеспечения новой высокоточной системы квазиньютоновской оптимизации ProfMiniHP, представляется актуальной научно-прикладной задачей.
Цель работы. На основе системного анализа проблемы оптимизации и возможностей IEEE-арифметики одинарной точности, разработать математическое, алгоритмическое и программное обеспечение системы квазиныотоновской оптимизации высокой точности ProfMiniHP.
Задачи работы определялись результатами выполненного системного анализа проблемы оптимизации, из которых следует:
определить основные задачи внешней среды проблемы оптимизации с акцентом на подготовку оптимизируемой задачи к решению и конкретизацию требований к точности ее численного решения, учитывающую неустранимые погрешности в априорной информации;
выделить основные задачи и методы внутренней среды оптимизации, позволяющие обеспечить высокую надежность и точность оценивания квазиньютоновского направления Р и шага одномерного поиска а в направлении Р, а также момента останова процесса оптимизации;
используя возможности IEEE-арифметики, модифицировать выделенные известные и разработать новые математические методы, реально обеспечивающие машинно возможную точность соответствующих вычислительных процессов и критериев принятия решений;
на основе структурно-модульного подхода, разработать и протестировать алгоритмическое и программное обеспечение системы ProfMiniHP;
спланировать и реализовать машинные эксперименты, позволяющие объективно оценить точность решения выбранных задач оптимизации.
Общие методы исследований включали системный, математический и статистический анализ, анализ ошибок процесса вычислений в ІЕЕЕ-стандарте, численные методы, в том числе векторно-матричного анализа, методы численной одномерной минимизации унимодальных функций, методы планирования машинных экспериментов и машинного моделирования,
табличный и графический анализ численных результатов.
Общая методика проведения исследований содержала вербальную постановку необходимых задач и аналитический обзор соответствующей литературы; обобщение результатов обзора и формализацию постановки; выбор математических методов и алгоритмов ее решения; изучение условий применимости выбранных методов и необходимости их модификаций или разработки; алгоритмическую и программную реализацию методов, их тестирование и отладку; проведение машинных экспериментов, позволяющих объективно оценить качество решения каждой поставленной задачи.
Научная новизна. На основе IEEE-арифметики разработаны инструменты обеспечения высокой точности вычислений:
"гладкий" квадратичный "регуляризатор" regui(x), нивелирующий машинный нуль числа хє/г1;
"разрешение" геф(х) машинного числа xeR], являющееся абсолютной погрешностью представления х в компьютере и опирающееся на машинное эпсилон єт [Форсайт и др.(М., 1980); Гольдберг(1991); Деммель(М.,2001)];
регуляризованное разрешение resiv(x) = resiv(regui(x)) машинного числах;
регуляризованное разрешение resiv{x,f) скалярной функции /./?'-*#' относительно аргумента х;
регуляризованные разрешения векторно-матричных операций, включая внешнее(скалярное) и внутреннее произведения векторов, векторную
операцию saxpy(a,X, Y):R" -^R",aeRl,X, Yg R" и 1-нормы матрицы.
Эти re$lv{-)-инструменты обобщены на случай d-точности представления
числах, где \
оценивания квазиныотоновского направления минимизации Р:
о при разработке методов адаптивного дифференцирования;
о при разработке методов SVD-анализа обусловленности и
9 положительной определенности обратной квазиныотоновской
матрицы (далее - обратной квазиматрицы) Гессе Н~1 и принятия решений о ее переоценивании или регуляризации;
о при разработке методов помехоустойчивого переоценивания Н~1;
о при разработке методов регуляризации матрицы //"' по Холесскому;
оценивания длины шага а в квазиньютоновском направлении Р:
о при разработке нового метода обобщенной одномерной
оптимизации; о при разработке новых методов трихотомии и стохастической
одномерной оптимизации, поразрядного цифрового сканирования;
оценивания момента останова квазиныотоновского процесса:
о при разработке булевых частных критериев сходимости, опирающихся на меры относительной близости соответствующих оценок F,P,X,VF;
о при разработке нового обобщенного критерия останова. Практическая ценность. На основе IEEE-стандарта двоичной
арифметики разработаны ^f/v(') -инструменты обеспечения машинной
надежности и ^-точности вычислений, которые, как представляется, полезно использовать не только при построении методов оптимизации, но и в других численных методах, например, матричном анализе, решении систем линейных алгебраических уравнений или методе наименьших квадратов... .
Разработанные новые и модифицированные известные методы численного дифференцирования, оценивания квазиныотоновского направления Р и длины шага а в направлении Р, реализованы в виде программных модулей и подсистем, что позволяет их использовать в других системах численного анализа и оптимизации.
Одна из главных целей работы - программная система ProfMiniHP, -прошла этапы автономного и детального комплексного тестироваЕшя и отладки
и может реально применяться для d-(npu d=l — высоко-)точного решения сложных прикладных задач оптимизации. Предложение о некоммерческом применении системы ProfMiniHP размещено на сайте кафедры САПРиПК ВолгГТУ ().
Отдельные положения и результаты работы используются при преподавании общего курса "Методы оптимизации" и спецкурсов "Идентификация стохастических систем", "Управление стохастическими системами" на кафедре ТВиОУ математического факультета ВолГУ.
Достоверность результатов. Подтверждена в более чем 400 машинных экспериментах, в которых, в частности, сравнивалась точность решений, полученных системой ProfMiniHP и оптимизационными пакетами коммерческих систем Mathematica 4, MathCAD 8SE и MATLAB 6.
Объективность и содержательность результатов обеспечивалась выбором:
ряда наиболее известных тест-функций[89, 20, 233а, 257] различной размерности и сложности, включая вырожденность квазиматрицы Гессе в оптимальных точках и наличие стационарных неоптимальных точек;
многочисленных различных начальных точек оптимизации;
по возможности, идентичных квазиныотоновских и иных методов.
В результате было установлено, что среди коммерчески поставляемых систем более высокой оказалась точность решения квазиныотоновской оптимизации пакета Optimization Toolbox системы MATLAB 6. Вместе с тем, этот пакет, несмотря на реализацию в IEEE-арифметике двойной точности, показал в целом худшую, часто - на порядки, точность решений, чем решения реализованной в одинарной точности системы ProfMiniHP. Важно, что для этого не потребовалась тонкая настройка применяемых методов системы ProfMiniHP.
Публикации. По результатам диссертации опубликовано 10 печатных работ.
Апробация работы. Основные положения и результаты диссертационных исследований докладывались и обсуждались на международных и областных
научно-технических конференциях:
Информационные технологии в образовании, технике и медицине(Волгоград, 2004);
X Международная конференция и Российская научная школа. Системные проблемы надежности, качества, информационных и электронных технологий(Инноватика - 2005)(Сочи, 2005);
Ежегодная XVII Международная Интернет-конференция молодых ученых и студентов по современным проблемам машиноведения (МИКМУС-2005) (Москва, 2005);
Инфокоммуникационные технологии в науке, производстве и образовании (Инфоком-2)(Кисловодск, 2006);
IX и X межвузовские конференции студентов и молодых ученых г. Волгограда и Волгоградской области(Волгоград, 2004-2005гг.);
профессорско-преподавательского состава и студентов ВолГУ (Волгоград, 2003-2006гг);
и постоянно действующих семинарах:
Нелинейный анализ. Математический факультет ВолГУ. Рук. проф., д.ф.-м.н. Миклюков В.М., 2003-2006 гг.;
Системный анализ и САПР: исследования и приложения. Кафедра САПРиПК ВолгГТУ. Рук. проф., д.т.н. Камаев В.А., 2003-2006 гг.
Структура работы и объем. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 259 названий и насчитывает 282 страницы, в том числе 242 страницы основного текста и 3 приложения.
Машинная арифметика и анализ точности операций и процессов
При постановке задачи оптимизации точностные характеристики используемых СИ, могут применяться по двум направлениям. Первое, связанное с выбором двусторонних ограничений на X,, может первоначально опираться на фаницы рабочего диапазона DP СИ. Конечно, границы рабочего диапазона СИ при постановке задачи оптимизации целесообразно уточнить, например, на основе имеющегося технологического регламента. Однако при решении задачи оптимизации выбор в качестве ограничений на компоненты Xt граничных значений DP может иметь определенный смысл, т.к. оптимальное решение может лежать вне технологического "коридора" и это может иметь важное содержание. Тем более, что в этом случае знание границ рабочего диапазона сопровождается ГОСТ-гарантированным знанием относительной погрешности измерений у(х), не превосходящей соответствующего заданного значения, например, равного 6; 2,5 или 1%. Второе направление, затронутое выше, связано с тем, что погрешность оценки независимых переменных может решаться на основе знания класса точности используемых СИ. А из этого следует, что установление реальных погрешностей данных не только показывает верхнюю границу точности будущих оценок оптимального решения, но и должно использоваться при определении объективно обусловленных требований к точности оптимального решения.
Подчеркнем, что точность оценивания оптимального решения X прямо зависит от выбора вида и порядка целевой функции, что обычно недопонимается и не учитывается, приводя к неоправданно жестким критериям останова и вытекающим из них соответствующим численным проблемам, из которых зацикливание метода оптимизации является еще наиболее простым.
Таким образом, знание метрологических характеристик СИ, используемых для получения исходных данных на этапе постановки задачи оптимизации, позволяет не только приближенно определить верхние границы изменения независимых переменных, но и является объективной основой для формирования требований к выбору параметров критерия останова, адаптирующих его к конкретной задаче оптимизации. Все "компьютерные" числа на внутреннем, т.е. машинном уровне, представимы в двоичной системе счисления. Однако, для удобства пользователя внешнеее представление чисел является десятичным.
Дальнейшее изложение опирается на стандарт IEEE Floating Point Standard [113, 134, 174, 193] для 32 разрядных компьютеров, обеспечивающий "действительно надежную арифметику с плавающей точкой" [32, с.36]. Машинные целые числа имеют конечное число разрядов. В компьютерах на платформе Intel, поддерживающих стандарт IEEE и распространенных в РФ, а также в рабочих станциях Sun, DEC, HP и IBM, для хранения целого числа отводится 32 двоичных разряда — бита, причем первый разряд отводится под знак числа. Наибольшее целое число таких компьютеров равно 231 -1 = 2147483647, а наименьшее по модулю - 2"31 [32, с.34]. Множество F1PS машинной системы представления действительных чисел с плавающей точкой, следуя общепринятой системе обозначений[18, с.65; 54, с.32; 85, с.22; 174, с. 156], заметим, несколько отличающийся от используемой в стандарте [113, с.З, 4], характеризуется основанием(базой) /? системы исчисления компьютера, точностью (числом цифр в мантиссе) /, минимальным и максимальным значениями показателя степени /min и /max, т.е. четверкой чисел {/?, /, /mjn, /max} и содержит все числа fip вида: ( d \ fir=± S- 7 =± i 2- //?/,0 / -1, , 0,/min / /max, (1.9) \i=\P J а также число 0. Отметим, что для каждого fip Ф 0 имеем m \fip\ М,т = J3l -\M = /З1" (1 -/Г ). (1.10)
Для компьютеров с 32 битами число с обычной точностью поддерживается 24 битами (включая 1 бит под знак) для мантиссы и 8 битами для порядка. Следовательно, в компьютерах представимы действительные числа fip : \f,p\ є [2.938736с-39,1.701412 + 38], (1.11) т.е. от 2 128 до 2127, с шестью десятичными знаками точности.
Далее все действительные числа представляются, следуя "научному обозначению"[54, с.32] посредством сдвига десятичной точки в положение после первой ненулевой цифры мантиссы и присвоения соответствующей степени основанию 10, например: 0.00012 = 1.2х 10 5, 3141592 = 3.141592х 106 или в форме 0.00012=1.2е-05, 3141592=3.141592е+06
Алгоритмически-программная постановка задачи оптимизации высокой точности
На основе структурно-модульного программирования с использованием языка высокого уровня Borland C++ v5 построить интерактивную программную систему кваз и ньютон о вс кой оптимизации ProfMiniHP путем проектирования, алгоритмически-программной разработки, тестирования и отладки программных подсистем:
BaseSearch( ), содержащей и поддерживающей параметры системы ProfMiniHP, в том числе и предоставляемые пользователю при выборе методов оценивания направления и шага поиска, их внутренних параметров; конфигурации обобщенного критерия останова; уровня визуализации вычислительных процессов, а также состава и формы представления начальной, текущей и финальной информации о состояниях квазиньютоновского процесса и его результатах; DirectSearch(-), позволяющей пользователю выбрать метод оценивания квазиныотоновского направления поиска /-точности П к, М,Л )) = й 1 ( к. /Д ))х ( VF(Xk, Я Д-))), (2.11) где к — номер итерации процесса оптимизации, из соответствующего набора методов адаптивной конечно-разностной аппроксимации вектор-градиента VF(Ar ,r /v(-)) и оценивания матрицы H l(Xk,rfslv(-)) на основе сингулярного анализа ее хорошей обусловленности и 108 положительной определенности, используемых при решении вопроса о регуляризации матрицы Н \Хк { ,rlv(-)), либо ее переоценивании одним из 8 квазиньютоновских методов;
LineSearch(-), позволяющей пользователю выбрать метод оценивания максимальной длины шага /-точности -к .d к d k(.()) = а(Х ,Р\ r«lv()) = argminF(X + aP{XK, r ,tf())) (2.12) a 0 из набора 6 эффективных, в том числе регуляризованных, методов одномерного поиска; A-I UF=M(F(XK),F(X )) sF(r"( StopSearch(-), оценивающей состояние сходимости квазиныотоновского процесса на основании обобщенного критерия останова, включающего управляемый частных регуляризованных критериев сходимости вида хк )), к-\ ЦР=Ц{Р{Х )) 8Р(Г«{ Xі -к vk-\ Ъ jup=ju{X\X ) sx{ slv{ Xі )), к-\ //VF = M{VF(X )) sVF( slv{ XK )), (2.13) (2.14) (2.15) (2.16) где пары (///г,ЕР()),...,(/jyF,SyF(-)),ecTb пары: мера отклонения + ее критическое значение, а норма 1\,12 или 4о; подчеркнем, что все критерии опосредованно проверяют "малость" относительных ошибок; ControlMiniHP(-), реализующей следующую обобщенную 4-х шаговую схему квазиньютоновского процесса минимизации F{X): имея текущее приближение X оптимальной точки X , на очередной к-й итерации выполнить операции: шаг 1. проверить выполнение подсистемой StopSearch(-) критерия останова и при его выполнении вычисления окончить, взяв \Xk, F(Xk)j в качестве оценки решения, иначе перейти к шагу 2; 109 шаг 2. используя подсистему DirectSearch(-), оценить вектор квазиньютоновского направления Р(Хк, r slv(-)) высокой точности; шаг 3. используя подсистему LineSearch(-), оценить длину шага ак ( /v(0) = а(хк» рк» rlv(-)) высокой точности; шаг4. вычислить Xk+l = Хк +ак(Р (-))х Р(Хк, Я (-)) и, положив А: = А: + 1, вернуться к шагу 1. 2.3.Постановка задачи исследования системы оптимизации высокой точности
Для исследования системы оптимизации ProfMiniHP следует: выполнить развернутое численное исследование системы, выбрав известные тест-функции, имеющие важные для многомерной оптимизации особенности: выраженную овражную структуру, плохую обусловленность матрицы Н (X ) в оптимальной точке, наличие глобальных и локальных минимумов; сравнить результаты оптимизации, полученные на выбранных тест функциях системой ProfMiniHP и пакетами оптимизации систем компьютерной математики MathCAD 8 SE, Mathematica 4.0.0.0, MATLAB 6.0.0.88. Release 12. Текстографическое оформление диссертационной работы и ее презентационной версии выполнить с использованием текстового редактора Word и программы аудиовизуальных презентаций PowerPoint пакета Microsoft Office.
Алгоритмическое решение
Целью алгоритмического решения является разработка алгоритмов решения всех, необходимых для построения системы квазиныотоновской оптимизации высокой точности, задач. Отметим, что в работе под алгоритмом понимается "...точное предписание, которое задает вычислительный процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемого этим исходным данным результата"[Математическая энциклопедия, М., 1977, с.202].
Основной состав математических задач, требующих алгоритмического решения, частично представлен в разделе 3.1. Вместе с тем, ясно, что эти задачи следует дополнить задачами системной увязки как алгоритмических модулей, обеспечивающих решения отдельных задач, так и объединяющих их подсистем, а также подсистем еще более высокого уровня. Кроме этого, некоторые "технические детали" математических решений являются настолько сложными, что также требуют алгоритмической поддержки. В результате, общее число алгоритмов, включая второстепенные, оказалось существенно большим ста. Однако с учетом того обстоятельства, что одной из задач диссертационной работы является описание только наиболее важных и научно содержательных алгоритмов, они и представлены далее.
Поскольку состав и содержание наиболее важных математических задач были определены в результате предшествующих системного анализа и математического решения, то проектирование алгоритмического решения системы ProfMiniHP осуществлялось по восходящей схеме[30, с. 125-126]. Следуя восходящей схеме, первоначально алгоритмизировались основные математические задачи, которые затем информационно и функционально увязывались в алгоритмические блоки, а затем и подсистемы все более высокого уровня. Состав основных алгоритмов системы ProfMiniHP приведен в таблице 3.1.
При разработке алгоритмов, представленных на Рис.3.4-3.20, большое внимание уделялось их структурной целостности и ясности. Поэтому было решено пожертвовать их чрезмерной деталировкой, что позволило сделать алгоритмы, по существу, самодокументируемыми, а значит и избежать нередко запутывающих подробных описаний. Вместе с тем, в приведенных алгоритмах имеется важные особенности, которые заслуживают отдельных комментариев. В алгоритм управления системой ProfMiniHP(Pnc.3.20) введены две процедуры масштабирования: XFXScaling и XFXReScaling. Первая из них, представленная на Рис.3.5, имеет своей целью перевод решения задачи оптимизации в новое, например, условно нормированное, пространство с I выровненным относительным масштабом изменения компонент вектора X и хорошо(порядка 1) отмасштабированными значениями целевой функции F(X). Цель такого перехода: снизить ранее упоминавшиеся[72, с.220] "вычислительные трудности" решения, как правило, плохо отмасштабированных оптимизационных задач[15, с.367]. Второй алгоритм: XFXReScaling, — предназначен для демасштабирования оптимальных оценок X и F(X) и предоставления их пользователю в реальном масштабе измерений. Алгоритм адаптивного масштабирования, входящий в алгоритм XFXScaling, реализует новую идею применения теории планирования эксперимента для масштабирования F(X), масштаб измерения(и изменения) которой неизвестен. С этой целью алгоритм содержит блок формирования и реализации центрального композиционного плана Бокса[87, с. 143] второго порядка, основное назначение которого заключается в реальном, хотя и далеком от детального, численного исследования топологии целевой функции.
Оцениваемые при этом статистики изменения F(X): математическое ожидание и стандартное отклонение, - и используются для масштабирования F{X). Алгоритм же демасштабирования XFXReScaling настолько прост, что не требует какого-либо графического или вербального описания.
Алгоритм регуляризации RegulHessInvert, представленный на Рис.3.9, помимо весьма сложного варианта с разложением по Холесскому, содержит и два относительно простых варианта регуляризации, в которых использованы результаты Гершгорина о сильном диагональном преобладании. Заметим, что все три варианта существенно опираются на разработанные f esiv( ) -инструменты точности. "Левый" вариант регуляризации по Гершгорину пополняет до надежного "преобладания" те диагональные элементы матрицы Я-1, для которых такое преобладание отсутствует. Ясно, что в этом случае объем вмешательства в —і структуру регуляризуемой матрицы И минимальный. "Правый" вариант обеспечивает увеличение всех диагональных элементов матрицы Я-1 на величину dmax, которая соответствует максимальному пополнению, среди необходимых. Здесь изменение структуры регуляризуемой матрицы Н более сильное.
В систему ProfMiniHP введен алгоритм квазиглобалыюго поиска. Он реализует идею решения отдельных задач оптимизации для начальных точек, являющихся вершинами правильного симплекса Бокса, расположенного внутри гиперкуба допустимой области изменения вектора X.
В связи с этим было разработано два алгоритма. Первый: SingleQNminiHP, приведенный на Рис.3.15, - решает задачу квазиныотоновской оптимизации для одной начальной точки, например, задаваемой пользователем.
Численные исследования подсистемы дифференцирования GradientSearch
Для исследования включенных в систему пяти методов численного дифференцирования: правых и центральных разностей с фиксированным и адаптивным шагом приращения конечно-разностных схем, — были спланированы и реализованы представительные машинные имитационные эксперименты. Варьируемыми параметрами экспериментов являлись: тест-функции F(X), точки оценивания X, начальные шаги приращения компонент
X и коэффициенты их уменьшения в адаптивной схеме. Также проводились эксперименты по варьированию внутренних параметров методов, с целью их оптимальной настройки. Точки эксперимента X выбирались вдали от точек экстремума, вблизи и в них самих, поскольку было важно оценить точность оценивания VF(A\ r6 /v(-)) как на относительно "крутых" участках изменения функции, так и на относительно "пологих" участках вблизи точки экстремума. Отметим, что это существенно важно для так называемых овражных функций.
В адаптивных схемах коэффициент /3 уменьшения шага приращения выбирался как равный 10[54, с.353], так и равным 2, что, несмотря на замедление процесса оценивания, как представлялось, должно дать более точные оценки производных. Это и подтвердилось в первых экспериментах, поэтому дальнейшие исследования выполнялись с J3 = 2.
Далее приведены фрагменты численных исследований с функциями Химмельблау №2 и Вуда. Отметим, что также проводились исследования и с функциями Химмельблау №1, Дэнниса, Шнабеля и Пауэлла, однако полные результаты этих исследований, частично отраженные в работе Яновского и др.[104], вследствие их объемности, здесь не приводятся. 4.2.2.Исследования с тест-функцией Химмельблау №2
Из этих результатов следует, что лучшим по точности оказался адаптивный метод экстраполяции Ричардсона. Он и адаптивный метод центральных разностей существенно превосходят по точности остальные методы. Так, относительные ошибки метода экстраполяции Ричардсона для всех пяти точек не превышают 0.000001. Это хорошие результаты.
Метод центральных разностей с шагом по Дэннису, Шнабелю[20, с.384], немного точнее адаптивного метода правых разностей и регулярно превосходит его по относительной ошибке оценивания как минимум на порядок в точках, близких к экстремальной. Существенно хуже точность метода правых разностей с фиксированным по Дэннису, Шнабелю шагом. Для этого метода по мере приближения к точке экстремума точность оценок частных производных ухудшается. Так, в точке Xі =(3.584430,-1.848130) производные оценены явно плохо: относительная ошибка оценивания по одной из переменных составляет почти 112, а по другой - 51.5, — как это видно из соответствующего фрагмента таблицы относительных ошибок. Частично это объясняется выраженно овражным характером тест-функции, но в основном связано с, видимо, плохим правилом оценивания фиксированного шага приращения разностных схем, предложенным Дэннисом, Шнабелем[20, с.382, 384]. 4.2.3.Исследования с тест-функцией Вуда
Анализ результатов для этой весьма сложной овражной функции показывает неплохую точность оценивания вектор-градиентов. Однако отличие методов существенное. Высокая точность оценивания присуща только двум методам: центральным разностям и экстраполяции Ричардсона, - при предпочтительности метода Ричардсона. Правые разностные схемы, видимо, следует считать требованиям высокой точности не удовлетворяющими. Исследование пяти процедур численного дифференцирования на основе тест-функций разного уровня овражности и сложности, условно разделенных на 2 класса, а также фиксированных и адаптивных схем с /?=10 и /?=2, позволило сделать следующие выводы.
Для класса относительно гладких тест-функций 2-го порядка достаточно простого вида рейтинг методов оценивания вектор-градиентов VF(X, rflv()) следующий: метод экстраполяции Ричардсона, центральные разности с адаптивным выбором шага, центральные разности с фиксированным по Дэннису-Шнабелю шагом, правые разности с адаптивным выбором шага, правые разности с фиксированным по Дэннису-Шнабелю шагом.
Для класса довольно сложных овражных тест-функций 4-го порядка метод Ричардсона не всегда показывал надежно точные результаты. Асимметричность правой разностной схемы, несмотря на метод оценивания шага, негативно сказывалась на результатах оценивания VF(X, ,(-)) когда точка находилась в "овраге" с крутыми склонами разной степени кривизны. Причем адаптивная правая разностная схема оказывалась даже хуже центральной разностной схемы с плохим правилом Дэнниса, Шнабеля выбора фиксированного шага.
В целом, адаптивный метод центральных разностей с коэффициентом уменьшения шага приращения /?=2 оказался лучшим с позиций точности оценивания и надежности его применения.