Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля

We study the global optimization problem connected to finding of a minimum of homogeneous quadratic function of a special kind on Stiefel manifold. It's considered Lagrange dual bounds for three variants of this problem which differ with restrictions on components orthonormal vectors. It's...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2004
Автори:	Шор, Н.З., Стецюк, П.И., Березовский, О.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2004
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/84870
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля / Н.З. Шор, П.И. Стецюк, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 3-10. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84870
record_format	dspace
spelling	irk-123456789-848702015-07-17T03:02:25Z Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля Шор, Н.З. Стецюк, П.И. Березовский, О.А. We study the global optimization problem connected to finding of a minimum of homogeneous quadratic function of a special kind on Stiefel manifold. It's considered Lagrange dual bounds for three variants of this problem which differ with restrictions on components orthonormal vectors. It's shown on tests that they can effectively be used for finding of a global minimum. 2004 Article Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля / Н.З. Шор, П.И. Стецюк, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 3-10. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84870 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	We study the global optimization problem connected to finding of a minimum of homogeneous quadratic function of a special kind on Stiefel manifold. It's considered Lagrange dual bounds for three variants of this problem which differ with restrictions on components orthonormal vectors. It's shown on tests that they can effectively be used for finding of a global minimum.
format	Article
author	Шор, Н.З. Стецюк, П.И. Березовский, О.А.
spellingShingle	Шор, Н.З. Стецюк, П.И. Березовский, О.А. Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля Теорія оптимальних рішень
author_facet	Шор, Н.З. Стецюк, П.И. Березовский, О.А.
author_sort	Шор, Н.З.
title	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля
title_short	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля
title_full	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля
title_fullStr	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля
title_full_unstemmed	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля
title_sort	двойственные оценки для оптимизационной задачи квадратичного типа на многообразии штиффеля
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2004
url	http://dspace.nbuv.gov.ua/handle/123456789/84870
citation_txt	Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля / Н.З. Шор, П.И. Стецюк, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 3-10. — Бібліогр.: 7 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT šornz dvojstvennyeocenkidlâoptimizacionnojzadačikvadratičnogotipanamnogoobraziištiffelâ AT stecûkpi dvojstvennyeocenkidlâoptimizacionnojzadačikvadratičnogotipanamnogoobraziištiffelâ AT berezovskijoa dvojstvennyeocenkidlâoptimizacionnojzadačikvadratičnogotipanamnogoobraziištiffelâ
first_indexed	2025-07-06T11:59:40Z
last_indexed	2025-07-06T11:59:40Z
_version_	1836898772299284480
fulltext	Теорія оптимальних рішень. 2004, № 3 3 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается задача глобаль- ной оптимизации, связанная с на- хождением минимума квадратич- ной однородной функции спе- циального вида на многообразии Штиффеля. Рассмотрены лагран- жевые двойственные оценки для трех вариантов этой задачи, ко- торые различаются ограничения- ми на компоненты ортонормиро- ванных векторов. На тестовых примерах показано, что их можно эффективно использовать при на- хождении глобального минимума.  Н.З. Шор, П.И. Стецюк, О.А. Березовский, 2004 ÓÄÊ 519.8 Í.Ç. ØÎÐ, Ï.È. ÑÒÅÖÞÊ, Î.À. ÁÅÐÅÇÎÂÑÊÈÉ ÄÂÎÉÑÒÂÅÍÍÛÅ ÎÖÅÍÊÈ ÄËß ÑÏÅÖÈÀËÜÍÎÉ ÎÏÒÈÌÈÇÀÖÈÎÍÍÎÉ ÇÀÄÀ×È ÊÂÀÄÐÀÒÈ×ÍÎÃÎ ÒÈÏÀ ÍÀ ÌÍÎÃÎÎÁÐÀÇÈÈ ØÒÈÔÔÅËß Многобразие Штиффеля (Stiefel manifolds) состоит из всех ортонормированных систем векторов n k Rxxx ∈ rrr ,...,, 21 , где n R – n -мер- ное евклидово пространство и nk ≤ . В рабо- те [1] рассмотрена следующая оптимизаци- онная задача на многообразии Штиффеля:         =∑ = k i ii T ik xAxxxxf 1 21 ),...,,(min rrrrr (1) при ограничениях iji T i xx δ= rr , kji ≤≤ ,1 , (2) где iA , ki ,1= – заданные nn × веществен- ные симметричные матрицы, ijδ – символ Кронекера. Ограничения (2) задают много- образие Штиффеля, которое принято обозна- чать knM , . В зависимости от условий на компоненты векторов из knM , выделим следующие вари- анты задачи (1)–(2): (R) компоненты векторов ix r , ki ,1= , при- надлежат множеству действительных чисел. Этот вариант совпадает с постановкой задачи (1)–(3); (Z) компоненты векторов ix r , ki ,1= , при- надлежат множеству целых чисел. Для этого варианта векторы ix r , ki ,1= , содержат толь- ко компоненты либо 0, либо +1, либо –1; Н.З. ШОР, П.И. СТЕЦЮК, О.А. БЕРЕЗОВСКИЙ Теорія оптимальних рішень. 2004, № 3 4 (N) компоненты векторов ix r , ki ,1= , принадлежат множеству натуральных чисел, т. е. векторы ix r , ki ,1= , могут содержать только компоненты 0 или 1. Варианты (Z) и (N) определяются только диагональными коэффициентами матриц iA и не зависят от коэффициентов вне диагонали, что обусловлено спе- цификой целевой функции вида (1). Кроме того варианты (Z) и (N) близки в том смысле, что им соответствует одно и то же значение целевой функции в точках глобальных экстремумов. Отличие состоит лишь в числе глобальных экстрему- мов, т. е. если у варианта (N) их количество равно L , то у варианта (Z) их будет L k2 . В общем случае задача (1)–(2) для каждого из трех вариантов является мно- гоэкстремальной задачей нелинейного программирования (пусть даже и квадра- тичного типа), и ее решение представляет проблемы даже при небольших раз- мерностях 2=n и 3=n . Так, например, в [2] сообщается, что простой пример на 2,2M с диагональными коэффициентами матриц iA , 2,1=i требует трех мил- лионов вычислений значений функции при использовании программы GlobSol [3–4]. Однако, используя технику двойственных лагранжевых квадратичных оценок [5] нахождение глобального минимума задачи (1)–(2) можно значитель- но ускорить в ряде случаев. Рассмотрим оптимизационные задачи квадратичного типа, соответствую- щие каждому из указанных трех вариантов этой задачи, и лагранжевые двойст- венные оценки для каждой из задач. Для каждого ki ,1= обозначим коэффициенты симметричной nn × матрицы iA – ijla , nj ,1= , nl ,1= , а компоненты n -мерного вектора ix r – ijx , nj ,1= . Варианту (R) соответствует оптимизационная задача квадратичного типа: ∑∑∑ = = = = k i n j n l ilijijl xxaQ 1 1 1 * 1 min (3) при ограничениях 1 1 2 =∑ = n j ijx , ki ,1= , (4) 0 1 =∑ = n l jlil xx , 1,1 −= ki , kij ,1+= . (5) Задача (3)–(5) – переписанный с учетом расшифровки символа Кронекера ijδ аналог задачи (1)–(2). Здесь ограничения (4) задают условие нормированно- сти векторов ix r , ki ,1= , а ограничения (5) – условие их взаимной ортогонально- сти. Указанных ограничений достаточно для задания многообразия Штиффеля ДВОЙСТВЕННЫЕ ОЦЕНКИ ДЛЯ СПЕЦИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ … Теорія оптимальних рішень. 2004, № 3 5 knM , , состоящего из всех ортонормированных систем векторов n k Rxxx ∈ rrr ,...,, 21 ( nk ≤ ). Пусть m Ru ∈ , где 2/)1( += kkm – вектор множителей Лагранжа, состоя- щий из двух частей: { }kiuii ,1, = – множители Лагранжа, соответствующие огра- ничениям (4) и { }kijkiuij ,1,1,1, +=−= – множители Лагранжа, соответствую- щие ограничениям (5). Согласно [5] задаче (3)–(5) соответствует следующая двойственная лагранжева оценка: )(sup)( 1 0)(: * 1 * 1 uu uKu ψ=ψ=ψ ≥ , (6) где функция ∑ = −=ψ k i iiuu 1 1 )( , а 0)( ≥uK обозначает неотрицательную опреде- ленность семейства симметричных )( knkn × -матриц вида: ∑ ∑ ∑ = − = += +++= k i k i k ij jiijijiiii KKuKuKuK 1 1 1 1 0 )( 2 1 )( . Здесь матрицы 0K и ijK состоят из 2 k блоков размером nn × и задаются следующим образом. По диагонали матрицы 0K размещены блоки, заданные симметричными )( nn × -матрицами iA , ki ,1= , а все внедиагональные блоки матрицы 0K равны нулевым )( nn × -матрицам. ijK – матрица, ),( ji -й блок ко- торой равен единичной )( nn × -матрице, а все остальные блоки равны нулевым )( nn × -матрицам. Варианту (Z) поставим в соответствие следующую оптимизационную зада- чу квадратичного типа: ∑∑∑ = = = = k i n j n l ilijijl xxaQ 1 1 1 * 2 min (7) при ограничениях 1 1 2 =∑ = n j ijx , ki ,1= , (8) 0 1 =∑ = n l jlil xx , 1,1 −= ki , kij ,1+= , (9) 0=ilij xx , ki ,1= , 1,1 −= nj , njl ,1+= , (10) 0=ljij xx , kj ,1= , 1,1 −= ki , kil ,1+= , (11) Н.З. ШОР, П.И. СТЕЦЮК, О.А. БЕРЕЗОВСКИЙ Теорія оптимальних рішень. 2004, № 3 6 Здесь ограничения (8) и (9) такие же, как и в предыдущей задаче, т. е. зада- ют многообразие Штиффеля knM , на множестве вещественных чисел. Тот факт, что компоненты векторов должны принадлежать множеству целых чисел, уточ- няется посредством двух групп дополнительных ограничений. Так группа огра- ничений (10) обозначает, что для любой пары компонент вектора их произведе- ние должно равняться нулю. Это связано с тем фактом, что для варианта (Z) ка- ждый из векторов ix r содержит только одну ненулевую компоненту, равную +1, либо –1. Последнее следует из условий нормировки векторов ix r , ki ,1= , задан- ных ограничениями (8), и того, что компоненты векторов должны принадлежать множеству целых чисел. Ограничения (11) означают, что для двух различных векторов компоненты с одним и тем же номером не могут одновременно быть ненулевыми, т. е. 1± для разных векторов должны находиться на разных мес- тах. Последнее обусловлено уже не только ортонормированностью, но и взаим- ной ортогональностью векторов. Указанные группы ограничений идентифицируют вариант (Z) в том смысле, что множество допустимых решений системы (8)–(11) будет состоять только из целых чисел: 0, +1 и –1. Отметим, что последнее было бы справедливо и тогда, если рассмотреть для варианта (Z) задачу только с одной группой ограничений, т. е. либо (10), либо (11). Однако, согласно [5], включение в систему ограниче- ний функционально избыточных ограничений способствует улучшению нижней двойственной лагранжевой оценки. Задаче (7)–(11) соответствует двойственная лагранжева оценка: ),,(sup),,( 2 0),,(:,, *** 2 * 2 VvuVvu VvuKVvu ψ=ψ=ψ ≥ , (12) где ∑ = −=ψ=ψ k i iiuuVvu 1 12 )(),,( . Здесь m Ru ∈ – вектор множителей Лагранжа, соответствующих ограниче- ниям (8) и (9); 1m Rv∈ , 2 )1( 1 − = nn km – вектор множителей Лагранжа, соответ- ствующих ограничениям (10); 2m RV ∈ , 2 )1( 2 − = kk nm – вектор множителей Лагранжа, соответствующих ограничениям (11); 0),,( ≥VvuK обозначает неот- рицательную определенность семейства симметричных матриц ∑ ∑ ∑∑∑ ∑ − = += == − = += ++++= 1 1 1 11 1 1 1 ) ~~ ( 2 1 )( 2 1 )(),,( k i k il n j lijiljilj k i n j n jl iljijlijl KKVKKvuKVvuK , где ijlK – матрица размера nknk × , в i-м диагональном блоке которой содер- жится )( nn × -матрица с ),( lj -м коэффициентом, равным единице, и всеми ос- тальными коэффициентами, равными нулю; iljK ~ – матрица размера nknk × , для ДВОЙСТВЕННЫЕ ОЦЕНКИ ДЛЯ СПЕЦИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ … Теорія оптимальних рішень. 2004, № 3 7 которой блок ),( li содержит )( nn × -матрицу с j-м диагональным коэффициен- том, равным единице, и всеми остальными коэффициентами, равными нулю. Все остальные блоки матрицы iljK ~ равны нулевым )( nn × -матрицам. Как видим, функция ),,(2 Vvuψ имеет такой же вид как и функция )(1 uψ для первой задачи. Это обусловлено однородностью добавленных ограничений (10)–(11) и тем, что правая часть в этих ограничениях тождественно равна нулю. Далее рассмотрим вариант (N). Ему соответствует оптимизационная задача квадратичного типа: ∑∑∑ = = = = k i n j n l ilijijl xxaQ 1 1 1 * 3 min (13) при ограничениях 1 1 2 =∑ = n j ijx , ki ,1= , (14) 0 1 =∑ = n l jlil xx , 1,1 −= ki , kij ,1+= , (15) 0=ilij xx , ki ,1= , 1,1 −= nj , njl ,1+= , (16) 0=ljij xx , kj ,1= , 1,1 −= ki , kil ,1+= , (17) 02 =− ijij xx , ki ,1= , nj ,1= . (18) Задача (13)–(18) отличается от задачи (7)–(11) тем, что к последней добав- лены булевые ограничения (18) на неизвестные компоненты векторов ix r , ki ,1= . Эти ограничения исключают из множества допустимых точек knM , век- торы с компонентами, равными –1, и, соответственно, компоненты векторов мо- гут быть равны либо нулю, либо единице. Следовательно, среди допустимых решений системы ограничений (14)–(18) будут векторы, содержащие только од- ну компоненту равную единице, а уже какая конкретно компонента будет опре- деляться глобальным экстремумом задачи (13)–(18). Задача (13)–(18) существенно отличается от двух предыдущих. В обеих пре- дыдущих задачах квадратичные функции, задающие как функцию цели так и ограничения, были однородными и не содержали линейных членов. В последней же задаче булевые ограничения приводят к линейным членам. В силу этого на- хождение двойственной лагранжевой оценки для задачи (13)–(18) будет сложнее и потребует решения системы линейных уравнений. Пусть 3m Rw∈ , ( nkm =3 ) – вектор множителей Лагранжа, соответствующий ограничениям (18), а m Ru ∈ , 1m Rv∈ , 2m RV ∈ – векторы множителей Лагранжа для ограничений (14)–(15), (16) и (17), соответственно. Задаче (18)–(23) соответствует такая двойственная лагранжева оценка: Н.З. ШОР, П.И. СТЕЦЮК, О.А. БЕРЕЗОВСКИЙ Теорія оптимальних рішень. 2004, № 3 8 ),,,(sup 3 0),,,(:,,, * 3 wVvu wVvuKwVvu ψ=ψ ≥ , где ( )         −−=ψ ∑∑ ∑ = = =∈ k i n j k i iiijij Rx uxwxxwVvuKwVvu kn 1 1 1 3 ,),,,(inf),,,( . Здесь 0),,,( ≥wVvuK обозначает неотрицательную определенность семейства симметричных матриц { }knkn wwwwdiagVvuKwVvuK ,...,,...,,...,),,(),,,( 1111+= . Когда * 3ψ достигается внутри области положительной определенности се- мейства матриц ),,,( wVvuK (т. е. 0),,,( **** >wVvuK ), точку глобального экст- ремума * x для задачи (13)–(18) можно найти по следующей формуле ***1 1 * 1 * 11 * ),,,( 2 1 ),...,,...,,...,( wwVvuKxxxxx T knkn −== . В данном случае оценка * 3ψ будет точной нижней оценкой для * 3Q (т. е. * 3 * 3 Q=ψ ). Эффективность двойственных оценок * 1ψ , * 2ψ , * 3ψ исследовалась на ряде тестовых примеров (для их нахождения использовалась программа DSQTPR [6] с использованием модификации r-алгоритма [7]). Ниже приведем два из них. Пример 1. Рассмотрим задачу (1)–(2), где )3,2,1(1 −= diagA , )6,5,4(2 −= diagA , )9,8,7(3 −= diagA . Целевая функция имеет вид 2 33 2 32 2 31 2 23 2 22 2 21 2 13 2 12 2 11 98765432)( xxxxxxxxxxf −+++−+++−= , множество допустимых решений состоит из 328 = точек следующего вида: ))1,0,0(,)0,1,0(,)0,0,1((* TTT x ±±±= . Оптимальное значение целевой функции равно сумме отрицательных компонент матриц iA , т. е. 15)( ** −== xff . Сле- довательно, для вариантов (R) и (Z) имеем 15* 2 * 1 −== QQ . Для варианта (N) также 15* 3 −=Q , но решением будет единственная точка ))1,0,0(,)0,1,0(,)0,0,1((* TTT x = . Для первого примера все лагранжевые двойственные оценки являются точ- ными, т. е. * 1 * 1 15 Q=−=ψ , * 2 * 2 15 Q=−=ψ , * 3 * 3 15 Q=−=ψ . Кроме того, для вари- анта (N) программа DSQTPR обеспечивает нахождение точного оптимального решения задачи (18)–(23) по переменным * x . Для этого ей потребовалось 208 итераций r-алгоритма, и, следовательно, затраты на нахождение и строгое обос- ДВОЙСТВЕННЫЕ ОЦЕНКИ ДЛЯ СПЕЦИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ … Теорія оптимальних рішень. 2004, № 3 9 нование точки глобального минимума для варианта (N) небольшие (время счета ≈ 1 сек на компьютере IBM PC/AT/486DX/66MHz). Недостаток первого примера состоит в том, что глобальный минимум для варианта (N) однозначен и значение целевой функции в нем сильно отличается от значений целевой функции в других допустимых точках. Поэтому ниже опи- шем второй, более сложный пример, когда глобальный минимум для варианта (N) неоднозначен. Пример 2. Рассмотрим задачу (1)–(2) с матрицами )3,2,1(1 diagA = , )6,5,4(2 diagA = , )9,8,7(3 diagA = , т. е. целевая функция имеет вид 2 33 2 32 2 31 2 23 2 22 2 21 2 13 2 12 2 11 98765432)( xxxxxxxxxxf ++++++++= . Для данного примера 15* 3 * 2 * 1 === QQQ , а множество допустимых решений будет иметь следующий вид. Для варианта (N) имеем шесть допустимых реше- ний: ))1,0,0(,)0,1,0(,)0,0,1((* 1 TTT x = ; ))0,1,0(,)1,0,0(,)0,0,1((* 2 TTT x = ; ))1,0,0(,)0,0,1(,)0,1,0((* 3 TTT x = ; ))0,0,1(,)1,0,0(,)0,1,0((* 4 TTT x = ; ))0,1,0(,)0,0,1(,)1,0,0((* 5 TTT x = ; ))0,0,1(,)0,1,0(,)1,0,0((* 6 TTT x = . Для варианта (Z) количество допустимых решений будет равно 4826 3 =⋅ , где решения будут отличаться тем, что на соответствующих единице местах мо- гут находиться как единица, так и минус единица. Множество допустимых ре- шений для варианта (R) содержит бесконечное число точек. Для второго примера лагранжевые двойственные оценки 12* 1 =ψ и 12* 2 =ψ , и ни одна из них не является точной нижней оценкой для * 1Q и * 2Q . Заметим, что разрыв двойственности ** iii Q ψ−=∆ , 2,1=i , равен трем и есть достаточно большим ( %20≈ ). Оценка 15* 3 =ψ является точной. Из-за неоднозначности ре- шений программа DSQTPR не гарантирует нахождения оптимального решения задачи (18)–(23) по переменным * x . Для того, чтобы получить одно из решений требуется соответственно "возмутить" коэффициенты матриц iA , 3,2,1=i . Так, например, для "возмущенных" матриц )3,2,9999.0(1 diagA = , )6,9999.4,4(2 diagA = , )9,8,7(3 diagA = получим решение * 1x , а для "возмущен- ных" матриц )3,2,1(1 diagA = , )6,9999.4,4(2 diagA = , )9,8,9999.6(3 diagA = , по- лучим решение * 6x . Для этого программе DSQTPR потребовалось 499 итераций r-алгоритма в первом случае и 487 итераций во втором. В заключение отметим, что описанный в работе аппарат нахождения двой- ственных оценок с использованием функционально избыточных ограничений можно перенести на случай, когда квадратичная функция цели имеет общий вид (при этом ограничения остаются неизменными). То есть предлагаемый подход Н.З. ШОР, П.И. СТЕЦЮК, О.А. БЕРЕЗОВСКИЙ Теорія оптимальних рішень. 2004, № 3 10 для получения нижних оценок функционала (а в некоторых случаях и оптималь- ных значений компонент вектора переменных) возможно использовать для оце- нок NP-трудных задач, например, в квадратичной задаче о назначениях. Н.З. Шор, П.І. Стецюк, О.А. Березовський ДВОЇСТІ ОЦІНКИ ДЛЯ СПЕЦІАЛЬНОЇ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ КВАДРАТИЧНОГО ТИПУ НА МНОЖИНІ ШТИФФЕЛЯ Розглядається задача глобальної оптимізації, пов'язана з знаходженням мінімуму квадратич- ної однорідної функції спеціального вигляду на множині Штиффеля. Розглянуто лагранжеві двоїсті оцінки для трьох варіантів цієї задачі, які розрізняються обмеженнями на компоненти ортонормованих векторів. На тестових прикладах показано, що їх можна ефективно викорис- товувати при знаходженні глобального мінімуму. N.Z. Shor, P.I. Stetsyuk, O.A. Berezovskyi DUAL BOUNDS FOR SPECIAL OPTIMIZATION QUADRATIC TYPE PROBLEM ON STIEFEL MANIFOLDS We study the global optimization problem connected to finding of a minimum of homogeneous quadratic function of a special kind on Stiefel manifold. It's considered Lagrange dual bounds for three variants of this problem which differ with restrictions on components orthonormal vectors. It's shown on tests that they can effectively be used for finding of a global minimum. 1. Rapcsak T. On minimization on Stiefel manifold // European J. of Operational Research.– 2002. – 143. – P. 365–376. 2. Balogh J.,Csendes T.,Rapcsak T. Global optimization problems on Stiefel manifold // NMCM– 2002 Book of Abstracts, Miscolc, Hungary, 2002. – P. 19–21. 3. Corliss G.F., Kearfott R.B. Rigorous global search: Industrial applications // In T. Csendes (editor): Development in Reliable Computing, Kluwer, Dordrecht, 1999. – P. 1–16. 4. Kearfott R.B. Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, 1996. – 98 p. 5. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht, Kluwer, 1998. – 394 p. 6. Shor N.Z., Stetsyuk P.I. Dual Solution of Quadratic-Type Problems by r-algorithm (subroutine DSQTPr) // Abstracts of Second International Workshop "Recent Advances in Non- Differentiable Optimization", (October, 1-4, 2001, Kyiv, Ukraine). – P. 36. 7. Шор Н.З., Стецюк П.И. Использование модификации r-алгоритма для нахождения гло- бального минимума полиномиальных функций // Кибернетика и системный анализ. – 1997. – № 4. – C. 28–49. Получено 06.08.2004

Двойственные оценки для оптимизационной задачи квадратичного типа на многообразии Штиффеля

Репозитарії

Схожі ресурси