Сравнительные численные исследования системы квазиньютоновской оптимизации Profminihp-2004 и подсистем оптимизации Matlab 6, Mathematica 4, MathCAD 8

Автор: Яновский Тимур Александрович

Журнал: Вестник Волгоградского государственного университета. Серия 9: Исследования молодых ученых @yrw-jvolsu

Рубрика: Физико-математические науки

Статья в выпуске: 4-2, 2005 года.

Бесплатный доступ

Короткий адрес: https://sciup.org/14967577

IDR: 14967577

Текст статьи Сравнительные численные исследования системы квазиньютоновской оптимизации Profminihp-2004 и подсистем оптимизации Matlab 6, Mathematica 4, MathCAD 8

1. Программная система квазиньютоновской оптимизации

ProfMiniHP-2004

Новая программная система ProfMiniHP-2004 предназначена для решения задач оптимизации с высокой точностью. Система построена в соответствии с технологией реализации программных модулей по восходящей схеме и с так называемой защитой от ошибок, что позволило добиться исключительной «прозрачности» всех вычислительных процессов1. Она включает 77 программных модулей, расположенных на 7 уровнях вложенности и представленных 3455 операторными строками языка высокого уровня Borland C++ v5.02.

Система ProfMiniHP-2004 содержит следующие подсистемы программных модулей:

- расчета вектор-градиентов на основе адаптивных правой (RD) и центральной (CD) конечно-разностных аппроксимаций, а также экстраполяции Ричардсона (ER)²;
- начального задания обратной матрицы Гессе на основе единичной матрицы (I) или модификаций Денниса-Шнабеля-Фрэнка (IDSHF) и Шанно-Фуа (SHF)³;
- рекуррентной оценки обратных квази-ньютоновских матриц методами Дави-дона-Флетчера-Пауэлла (DFP), проективного Ньютона-Рафсона (PNR), Бройдена (BR), Пирсона 2 и 3 (PIR2, PIR3)⁴;
- численного анализа обратной квазиньютоновской матрицы на основе сингулярного разложения (SVD) и оценки ее обусловленности (HANAL), используемой для выбора уровня регуляризации обратной квазиньютоновской матрицы (HREGUL) и ее реализации на основе нового подхода, опирающегося на результаты Гершгорина⁵;
- одномерной оптимизации на основе методов модифицированного золотого сечения (MGS), параболической аппроксимации Мэтьюза-Финка (PAMF), а также регуляризованных методов Брента-Форсайта-Малькольма-Моулера (BFMM) и Дэвиса-Свенна-Кемпи-Па-уэлла (DSKP)⁶;
- многоаспектной проверки условий останова на основе регуляризованных критериальных функций, опирающихся на относительную машинную точность вычислений;
- масштабирования пространства независимых переменных и значений функции.

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

Тест-функция Вуда :

Ее минимум: f ( x * ) = 0 при x * = (1;1;1; 1) . Функция была построена специально для того, чтобы «загнать» в неоптимальную стационарную точку большинство известных алгоритмов, и имеет важные особенности. Как отмечают Фиакко и Мак-Кормик⁸, обычный спуск и метод Ньютона оказались бессильными решить эту задачу: последовательность точек сходилась примерно к точке ( - 1,07;1,16; - 0,86; 0,76), в которой f ® + 7,89 , кроме того: «Где-то в этой области градиент функции / стремится к нулю. Матрица вторых частных производных, однако, имеет здесь отрицательное собственное значение...».

Тест-функция Флетчера-Пауэлла :

Ее минимум: f ( x * ) = 0 при

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

Для объективной оценки качества, то есть точности и надежности минимизации тест-функций Вуда и Флетчера-Пауэлла системой ProfMiniHP-2004, использовались «параллельные» результаты минимизации тех же функций известными системами10 Mathcad 8, Mathematica 4, MATLAB 6. Здесь под надежностью метода или системы оптимизации понимается сходимость численных результатов к решению в принципе, то есть безотносительно к точности.

4. Результаты численных исследований

Для тонкой настройки системы ProfMiniHP-2004 на особенности (порядок, многомерность, «овражность», вырожденность матрицы Гессе в стационарной точке) выбранных тест-функций использовались следующие основные параметры: METHODAPPROXHESSINVERT -для выбора метода рекуррентной оценки обратной квазиньютоновской матрицы из методов DFP, PNR, BR, PIR2 и PIR3; METHODLINESEARCH - для выбора метода одномерной минимизации из методов MGS, PAMF, DSKP и BFMM; METHODAPPROXGRADIENT - для выбора адаптивного конечно-разностного метода RD, CD, ER METHODQUASIIDENTIFYHESSINVERT -для выбора метода задания начальной аппроксимации обратной матрицы Гессе в фор ме I, IDSHF, ISH; RIGHTDIGITS - для выбора числа достоверных десятичных разрядов оценивания целевой функции , которое во всех экспериментах полагалось равным 6.

Поскольку одной из главных целей ис следования являлась сопоставимость результатов, полученных с помощью системы ProfMiniHP-2004 и систем Mathcad 8, Mathematica 4 и MATLAB 6, имеющиеся в ProfMiniHP-2004 и весьма важные для точ ности и надежности минимизации подсистемы анализа и основанной на нем «плавной» регуляризации обратной матрицы Гессе, а также масштабирования целевой функции и переменных не применялись. Кроме того, далее учтем, что приводимые результаты оптимизации имеют в системе ProfMiniHP-2004 одинарную машинную точность, в то время как результаты, полученные с помощью систем Mathcad 8, Mathematica 4 и MATLAB 6, имеют двойную точность.

Для численного исследования новой системы квазиньютоновской оптимизации высокой точности ProfMiniHP-2004 на тест-фун-кциях Вуда и Флетчера-Пауэлла было выполнено более трехсот численных экспериментов, частично представленных в таблицах 1-8.

Фрагменты результатов исследований систем ProfMiniHP-2004, Mathcad 8, Mathematica 4 и MATLAB 6 для тест-функ-ции Вуда приведены в таблицах 1-4, причем в таблицах 1 и 2 отражены результаты оптимизации, производимой из начальной точки x ₀ = ( - 3; - 1; - 3; - 1) , а в таблицах 3 и 4 - из точки .

Фрагменты результатов исследований для тест-функции Флетчера-Пауэлла приведены в таблицах 5-8, причем в таблицах 5 и 6 отражены результаты оптимизации, производимой из начальной точки , а в таблицах 7 и 8 - из точки .

Таблица 1

№	Наименования систем оптимизации	Оптимальные значения x и f ( x )
№	Наименования систем оптимизации	* x 1^*	* x 2	* x 3	* x 4^*	f ( x ^* )
1	MATLAB	-1,3640	1,9055	-0,0110	-0,0246	7,3825000000
2	Mathematica	1,09189	1,19584	0,921632	0,846415	0,0467560000
3	MathCAD	0,992	0,984	1,007	1,011	0,0011540000

Таблица 2

№	Методы системы ProfMiniHP				Оптимальные значения x и f ( x )
№	_H ˆ _k - 1	^А g k	α k	_H ˆ₀ - 1	* x 1	* x 2	* x 3	* x 4	f ( x ^* )
1	DFP	ER	DSKP	I	1,000116	1,000234	0,999882	0,999765	0,0000000495
2	BR	ER	BFMM	I	1,000145	1,000286	0,999859	0,999714	0,0000000772
3	BR	RD	BFMM	I	1,000192	1,000382	0,999795	0,999592	0,0000001482
4	BR	ER	MGS	I	1,000185	1,000371	0,999813	0,999624	0,0000001256
5	PIR3	CD	BFMM	I	1,000076	1,000153	0,999928	0,999856	0,0000000206
6	PIR3	CD	MGS	I	1,000129	1,000259	0,999873	0,999744	0,0000000596
7	PIR3	ER	BFMM	I	1,000136	1,000274	0,999864	0,999729	0,0000000670

Таблица 3

№	Наименования систем оптимизации	Оптимальные значения x и f ( x )
№	Наименования систем оптимизации	* x 1	* x 2	* x 3	* x 4	f ( x ^* )
1	MATLAB	1,0000	1,0000	1,0000	1,0000	0,0000000030
2	Mathematica	-0,0238	0,0069	1,4371	2,0646	1,7183200000
3	MathCAD	1	1	1	1	0,0000000020

Таблица 4

№	Методы системы ProfMiniHP				Оптимальные значения x и f ( x )
№	_H ˆ _k - 1	^А g k	α k	_H ˆ₀ - 1	* x 1	* x 2	* x 3	* x 4	f ( x ^* )
1	DFP	ER	MGS	I	0,999758	0,999514	1,000244	1,000490	0,0000002140
2	BR	ER	DSKP	I	0,999861	0,999721	1,000156	1,000313	0,0000000901
3	PNR	ER	DSKP	I	0,999975	0,999948	1,000041	1,000081	0,0000000128
4	PIR3	CD	DSKP	I	0,999881	0,999761	1,000117	1,000235	0,0000000506
5	PNR	CD	DSKP	I	0,999694	0,999386	1,000305	1,000612	0,0000003377
6	PNR	CD	MGS	I	0,999702	0,999401	1,000295	1,000592	0,0000003191
7	DFP	ER	DSKP	I	0,999759	0,999516	1,000247	1,000496	0,0000002171

Таблица 5

№	Наименования систем оптимизации	Оптимальные значения x и f ( x )
№	Наименования систем оптимизации	* x 1	* x 2	* x 3	* x 4	f ( x ^*)
1	MATLAB	0,0251	-0,0025	0,0116	0,0116	0,0000010000
2	Mathematica	0,000000	-0,00000	0,000000	0,000000	0,000000
3	MathCAD	0,057	-0,057	0,023	0,023	0,0000210000

Таблица 6

№	Методы системы ProfMiniHP				Оптимальные значения x и f ( x )
№	^А 1 _H ˆ _k - 1	g k	α k	^А 1 _H ˆ₀ - 1	* x 1	* x 2	* x 3	* x 4	f ( x ^*)
1	DFP	CD	DSKP	IDSHF	0,01173	-0,00117	0,00323	0,00321	0,0000000591
2	DFP	ER	MGS	I	0,00710	-0,00071	-0,00526	-0,00526	0,0000002434
3	DFP	ER	MGS	IDSHF	0,01500	-0,00150	0,008623	0,008631	0,0000001403
4	DFP	ER	DSKP	IDSHF	0,01557	-0,00155	0,007003	0,007006	0,0000001127
5	PIR3	ER	MGS	IDSHF	0,01574	-0,00157	0,003633	0,003639	0,0000002215
6	PIR3	ER	BFM	IDSHF	0,01547	-0,00154	0,005735	0,005759	0,0000001210
7	PIR3	ER	BFM	I	0,00896	-0,00089	0,005156	0,005154	0,0000000180

Таблица 7

№	Наименования систем оптимизации	Оптимальные значения x и f ( x )
№	Наименования систем оптимизации	* x 1	* x 2	* x 3	* x 4	f ( x ^* )
1	MATLAB	-0,0350	0,0035	-0,0134	-0,0135	0,0000060000
2	Mathematica	1	1	1	1	122
3	MathCAD	0,059	-0,0063	0,027	0,034	0,0003170000

Таблица 8

№	Методы системы ProfMiniHP				Оптимальные значения x и f ( x )
№	^А 1 _H ˆ _k - 1	^А g_k	α _k	^А 1 _H ˆ₀ - 1	* x ₁	* x ₂	* x ₃	* x ₄	f ( x ^*)
1	DFP	RD	MGS	I	-0,00160	0,00015	0,00868	0,008679	0,0000001994
2	DFP	RD	DSKP	I	0,00592	-0,00059	0,00121	0,001211	0,0000000050
3	DFP	CD	MGS	IDSHF	-0,00158	0,00015	0,00219	0,002190	0,0000000024
4	DFP	CD	DSKP	I	0,00726	-0,00072	-0,00026	-0,00027	0,0000000337
5	DFP	ER	DSKP	IDSHF	0,01442	-0,00144	0,00643	0,006436	0,0000000827
6	BR	RD	MGS	I	0,00061	-0,00006	0,00623	0,006198	0,0000000420
7	BR	ER	DSKP	IDSHF	0,00193	-0,00019	0,00098	0,000991	0,0000000009

6. Выводы

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

Рейтинг (здесь и далее: от лучшего к худшему) методов_аппроксимации обратной матрицы Гессе О: DFP, BR, PNR, PIR3, PIR2. Из них лучший по точности сходимости — метод DFP. Результаты, полученные с помощью методов BR, PNR и PIR3, незначительно отличаются друг от друга. Метод Пирсона 2 оказался худшим не только по точности сходимости, но и, что еще более важно, по надежности, систематически демонстрируя расходимость результатов.

Рейтинг методов численного дифференцирования: ER, CD, RD.

Рейтинг методов одномерного поиска: DSKP, BFMM и MGS, MF. Отметим хорошее качество работы метода DSKP и близких к нему по результатам методов BFMM и MGS.

Рейтинг методов аппроксимации начальной обратной матрицы Гессе : IDSHF, I, ISH. Лучший — метод IDSHF, причем модификация Шанно-Фуа выглядит откровенно слабо.

Представляется, что с достаточно высокой вероятностью добиться весьма точного результата при решении задачи оптимизации можно, аппроксимируя обратную матрицу Гессе методом DFP или PNR, аппроксимируя градиент методом экстраполяции Ричардсона, наконец, проводя одномерный поиск методом DSKP или MGS.

Результаты работы пакетов оптимизации систем MATLAB и Mathematica показали, что с их помощью не всегда можно добиться корректного решения задачи оптимизации. Так, при минимизации функции Вуда из начальной точки (-3; -1; -3; -1) пакет оптимизации системы MATLAB не смог найти точку глобального минимума, указав точку, близкую к псевдорешению. Пакет оптимизации системы Mathematica не достиг верного решения в задаче с той же функцией из начальной точки (2; -1; -3; -1) и, более того, не смог даже начать решать задачу минимизации функции Флетчера-Пауэлла для начальной точки (1; 1; 1; 1).

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

Таким образом, результаты данного сравнительного исследования позволяют оценить систему оптимизации ProfMiniHP-2004 как предпочтительную по сравнению с па- кетами оптимизации систем Mathcad 8, Mathematica 4, MATLAB 6.

Список литературы Сравнительные численные исследования системы квазиньютоновской оптимизации Profminihp-2004 и подсистем оптимизации Matlab 6, Mathematica 4, MathCAD 8

Соммервилл И. Инженерия программного обеспечения: Пер. с англ. 6-е изд. М.: Изд. дом «Вильяме», 2002. 624 с: ил.
Мэтьюз Дж.Г., Финк К.Д. Численные методы. М.: Изд. дом «Вильяме», 2001.
Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988;
Shanno D.F. Conditioning of quasi-Newton methods for function minimization//Mathematics of Computation. 1970. № 24.
Fletcher R., Powell MJ.D. A rapidly convergent descent method for minimization//Computer J. 1963. № 6;
Pearson J.D.//Computer J. 1969. № 13.
Дэннис Дж., Шнабель Р. Указ. соч.;
Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. 279 с;
Хорн Р., Джонсон Ч. Матричный анализ: Пер. с англ. М.: Мир, 1989. 655 с.
Мэтьюз Дж.Г., Финк К.Д. Указ. соч.;
Форсайт Дж., Малькольм М., Моулер К. Указ. соч.;
Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение: Пер. с англ. Изд. второе, стереотип. М.: Мир, 2001. 575 с: ил.;
Brent R.P. Algorithms for Minimization without Derivatives, Prentice-Hall, Inc., Englewood Cliffs. New Jersey, 1973;
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 509 с;
Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. 534 с.
Дэннис Дж., Шнабель Р. Указ. соч.;
Fletcher R, Powell MJ.D. Op. cit;
Фиакко А, Мак-Кормик Г. Нелинейное программирование. М.: Мир, 1972. 240 с;
Гилл Ф., Мюррей У., Райт М. Указ. соч.;
Химмельблау Д. Указ. соч.; Fletcher R. Practical Optimization (2-nd Edition)//John Wiley & Sons. N. Y., 1987.
Фиакко А, Мак-Кормик Г. Указ. соч.
Fletcher R., Powell MJ.D. Op. cit.; Химмельблау Д. Указ. соч.; Fletcher R. Practical Optimization...
Дьяконов В., Круглов В. Математические пакеты расширения MATLAB: Спец. справ. СПб.: Питер, 2001. 480 с: ил.

Еще

Статья