Об упрощении задачи полуопределенного программирования

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

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-113025
record_format	dspace
spelling	irk-123456789-1130252017-02-01T03:02:46Z Об упрощении задачи полуопределенного программирования Базилевич, Ю.Н. Рассматривается метод, позволяющий привести несколько симметрических матриц к одинаковому блочно-диагональному виду, либо установить, что для данных матриц такое приведение невозможно. Это может быть полезно при решении задач полуопределенного программирования. Учитывается требование – матрица преобразования должна быть ортогональной. Розглядається метод, що дозволяє привести кілька симетричних матриць до однакового блочно-діагонального вигляду, або встановити, що для даних матриць таке приведення неможливе. Це може бути корисно при вирішенні задач напіввизначеного програмування. Враховується вимога – матриця перетворення має бути ортогональною. The method, which allows to reducing some symmetric matrices to the same block-diagonal form, either to establishing that such a reduction is impossible for these matrices, is considered. This can be useful in solving semidefinite programming problems. We taken into account the demand — the transformation matrix must be orthogonal. 2016 Article Об упрощении задачи полуопределенного программирования / Ю.Н. Базилевич // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 103-107. — Бібліогр.: 10 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/113025 519.61: 519.85 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается метод, позволяющий привести несколько симметрических матриц к одинаковому блочно-диагональному виду, либо установить, что для данных матриц такое приведение невозможно. Это может быть полезно при решении задач полуопределенного программирования. Учитывается требование – матрица преобразования должна быть ортогональной.
format	Article
author	Базилевич, Ю.Н.
spellingShingle	Базилевич, Ю.Н. Об упрощении задачи полуопределенного программирования Теорія оптимальних рішень
author_facet	Базилевич, Ю.Н.
author_sort	Базилевич, Ю.Н.
title	Об упрощении задачи полуопределенного программирования
title_short	Об упрощении задачи полуопределенного программирования
title_full	Об упрощении задачи полуопределенного программирования
title_fullStr	Об упрощении задачи полуопределенного программирования
title_full_unstemmed	Об упрощении задачи полуопределенного программирования
title_sort	об упрощении задачи полуопределенного программирования
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
url	http://dspace.nbuv.gov.ua/handle/123456789/113025
citation_txt	Об упрощении задачи полуопределенного программирования / Ю.Н. Базилевич // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 103-107. — Бібліогр.: 10 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT bazilevičûn obuproŝeniizadačipoluopredelennogoprogrammirovaniâ
first_indexed	2025-07-08T05:04:09Z
last_indexed	2025-07-08T05:04:09Z
_version_	1837053825683292160
fulltext	Теорія оптимальних рішень. 2016 103 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматривается метод, позво- ляющий привести несколько сим- метрических матриц к одинако- вому блочно-диагональному виду, либо установить, что для данных матриц такое приведение невоз- можно. Это может быть полез- но при решении задач полуопреде- ленного программирования. Учи- тывается требование – матрица преобразования должна быть ортогональной.  Ю.Н. Базилевич, 2016 УДК 519.61: 519.85 Ю.Н. БАЗИЛЕВИЧ ОБ УПРОЩЕНИИ ЗАДАЧИ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ Введение. В настоящее время активно раз- вивается полуопределенное программирова- ние [1 – 3]. К этой постановке задачи приво- дится ряд нелинейных задач оптимизации. Для упрощения задач предложены методы при- ведения матриц коэффициентов к блочно- диагональному виду [4, 5]. В настоящей ра- боте предлагаются менее громоздкие методы упрощения задачи оптимизации. Пусть nS обозначает пространство симме- трических вещественных матриц порядка n, nS – подмножество ,nS состоящее из неот- рицательно определенных (положительно полуопределенных) матриц. Скалярное (внутреннее) произведение между двумя квадратными матрицами L и M порядка n определяется как след матрицы L M и обо- значается , 1 tr( ) , n ij ij i j L M L M l m      где ijl и ijm – (ij)-элементы соответственно матриц L и M . Задача полуопределенного программиро- вания заключается в следующем [3, 5]: даны матрицы ( 0, )n pA S p m  и столбец  1 2, , ..., ,n nb b b   b нужно найти матрицу nX S , удовлетворяющую следующим условиям 0min ,A X , 1, .i iA X b i m   (1) Ю.Н. БАЗИЛЕВИЧ 104 Теорія оптимальних рішень. 2016 Рассмотрим проблему уменьшения числа неизвестных в (1). 1. Постановка задачи. Если сделать замену переменных в (1): ТX H XH (H – вещественная ортогональная матрица преобразования, X – новая неиз- вестная матрица порядка n) и преобразовать матрицы ( 0, )pA p m с помо- щью той же матрицы преобразования: ,Т p pA H A H то получим опять задачу полуопределенного программирования. Действительно: симметричность матриц при таком преобразовании не нарушится, кроме того, это преобразование явля- ется преобразованием подобия и, следовательно, оставляет неизменными соб- ственные числа матрицы X, сохраняя, таким образом, полуопределенность неиз- вестной матрицы. Допустим, что матрицы pA приобрели одинаковый блочно-диагональный вид: (1) (2) 0 , 0 pТ p p p A A HA H A          (2) где 1(1) n pA S , 2(2) n pA S и 1 2 .n n n  В этом случае задача (1) приводится к следующему виду [5]:    1 2(1) (2) 0 0min ,A X A X     1 2(1) (2) 1, .i i iA X A X b i m    (3) Здесь 1(1) n pX S и 2(2) n pX S – диагональные блоки матрицы .X Заметим, что число переменных в (3) меньше, чем в (1). Еще лучше получить выражение, аналогичное (2), с максимально возможным количеством блоков. Итак, нужно для данных матриц ( 0, )pA p m найти такую матрицу H, при которой матрицы Ò p pA HA H будут иметь наилучший блочно-диагональный вид, либо убедиться в том, что для заданных матриц такое приведение невоз- можно. Слово «наилучший» может означать максимальное количество блоков либо минимальное суммарное количество переменных в диагональных блоках матрицы .X Далее изложено решение этой проблемы и показано, что оба кри- терия приводят к одному и тому же результату. Предварительным этапом решения задачи о преобразовании матриц являет- ся использование априорной информации о симметрии с помощью теории групп. Здесь группы симметрии не рассматриваются потому, что существует хорошо разработанная методика таких расчетов [6]. Она используется при рас- четах колебаний молекул, кристаллов и т. п. 2. Метод коммутирующей матрицы. О возможности применения ком- мутирующей матрицы для расщепления систем уравнений можно ознакомиться ОБ УПРОЩЕНИИ ЗАДАЧИ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ Теорія оптимальних рішень. 2016 105 в учебниках по квантовой механике. Метод коммутирующей матрицы предложен одновременно А.К. Лопатиным и Е.Д. Якубович. Рассмотрим множество Λ(B) всех матриц, коммутирующих с данными матрицами B1, B2, …, Bg . Это множество является алгеброй над полем комплексных чисел и называется централизатором матриц {B}. Теорема 1. Пусть матрицы А и T коммутируют AT = TA, матрица T имеет блочно-диагональный вид: T = diag ,kT причем спектры блоков kT попарно не пересекаются. Тогда матрица А также имеет блочно- диагональный вид А = diag kА . Эта теорема приведена в [7] – гл. VIII, теорема 3 (см., также [8] § 2.5 и [9]). Следствие. Если существует матрица T  Λ(B), имеющая хотя бы два различных собственных числа, то преобразование подобия 1 ,B H B H   где H – матрица, столбцами которой являются векторы канонического базиса матрицы T, приводит обе матрицы к блочно-диагональному виду с двумя (как минимум) блоками на главной диагонали. Теорема 2. Если матрицы B приводятся преобразованием подобия к блоч- но-диагональному виду с двумя (как минимум) блоками на главной диагонали, то существует матрица T  Λ(B), имеющая хотя бы два различных собственных числа. Итак, для возможности одновременного приведения двух матриц к блочно- диагональному виду необходимо и достаточно чтобы централизатор содержал матрицу T с неодинаковыми собственными числами. Для нахождения централизатора (точнее говоря – его базиса) можно объявить все элементы матрицы T неизвестными и составить систему линейных однородных алгебраических уравнений, соответствующую матричным уравнениям , 1, .B T TB g    Получим gn2 уравнений с n2 неизвестными. Общее решение такой системы уравнений (при небольшом n) можно получить известными методами. Вычислительный метод преодоления проблем, связанных с большим n, изложен в [10]. Обозначим базис централизатора Λ(B) через W1, W2, …, Wr. Если размерность r централизатора равна 1, то весь централизатор состоит из матриц кратных единичной матрице. В этом случае приведение матриц B к блочно- диагональному виду невозможно. Если r > 1, то в качестве матрицы T, используемой для нахождения преобразования (следствие к теореме 1), выбираем матрицу базиса Wk, имеющую хотя бы два различных собственных Ю.Н. БАЗИЛЕВИЧ 106 Теорія оптимальних рішень. 2016 числа. Векторы ее канонического базиса являются столбцами искомой матрицы преобразования подобия. 3. Приведение симметрических матриц. Особенность решаемой проблемы в том, что преобразованные матрицы должны быть симметрическими, и новая матрица неизвестных X должна оставаться положительно полуопределенной. Эти условия будут выполняться, если матрица преобразования H будет ортогональной. Для этого из множества коммутирующих матриц нужно выбирать симметрическую матрицу T. Следует обратить внимание на тот факт, что вместе с каждой матрицей T в централизатор множества симметрических матриц входит и транспонирован- ная матрица T . Действительно, из равенства CjT = TCj вытекает Т Т Т Т j jT C C T , а поскольку матрица Cj симметрическая, то и .Т Т j jT C C T Это и означает, что ТT принадлежит централизатору. Поэтому, вместо несимметрических (вообще говоря) матриц T нужно использовать заведомо симметрические матри- цы ТV TT или .ТV T T  Для симметрической матрицы всегда существует базис, состоящий из ортогональных нормированных собственных векторов. Из таких векторов и составляем ортогональную матрицу преобразования H. Особый случай, когда r > 1, но все матрицы базиса не имеют различных собственных чисел, при симметрических матрицах исключен. Действительно: симметрические матрицы имеют диагональную жорданову форму. Если все числа такой диагональной формы одинаковы, то матрица T кратна единичной и может быть лишь одним элементом базиса. Иначе – матрица T имеет раз- личные собственные числа. Приведение к блокам минимального порядка осуществляется путем после- довательного применения метода коммутирующей матрицы сначала к исходным матрицам ,kС затем к получающимся блокам до нахождения нерасщепляющих- ся блоков. Теорема единственности ([8], теорема 6.5) подтверждает, что это и есть наилучшее приведение. Другими словами, получив нерасщепляющиеся да- лее блоки, мы имеет и максимально возможное число подсистем, и минималь- ное количество неизвестных в матрице .Х Выводы. Разработан метод одновременного приведения нескольких сим- метрических матриц к блочно-диагональному виду. Используются такие вычис- лительные методы, которые позволяют получить результат при сравнительно высоких порядках исходных матриц. Метод предназначен для упрощения задач полуопределенного программирования. Он же может быть полезен для деком- ОБ УПРОЩЕНИИ ЗАДАЧИ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ Теорія оптимальних рішень. 2016 107 позиции «традиционных» колебательных систем, т. е. таких, где нет гироскопи- ческих добавок и нет позиционных неконсервативных сил, обусловленных вза- имодействием с внешней средой. Ю.М. Базилевич ПРО СПРОЩЕННЯ ЗАДАЧІ НАПІВВИЗНАЧЕНОГО ПРОГРАМУВАННЯ Розглядається метод, що дозволяє привести кілька симетричних матриць до однакового блочно-діагонального вигляду, або встановити, що для даних матриць таке приведення неможливе. Це може бути корисно при вирішенні задач напіввизначеного програмування. Враховується вимога – матриця перетворення має бути ортогональною. Yu.N. Bazilevich ON THE REDUCING OF SEMIDEFINITE PROGRAMMING PROBLEM The method, which allows to reducing some symmetric matrices to the same block-diagonal form, either to establishing that such a reduction is impossible for these matrices, is considered. This can be useful in solving semidefinite programming problems. We taken into account the demand — the transformation matrix must be orthogonal. 1. Todd M.J. Semidefinite optimization // Acta Numerica. – 2001. – N 10. – Р. 515 – 560. 2. Перетятько А.С. Напіввизначена оптимізація для розв’язування загальних квадратичних задач: Автореф. дис. ... канд. фіз.-мат наук: «Математичне моделювання та обчислювальні методи». – Харків, 2015 – 22 с. 3. Жадан В.Г. Об одном варианте допустимого аффинно-масштабирующего метода для полуопределенного программирования // Тр. ИММ УрО РАН. – 2014. – Т. 20, № 2. – С. 145 – 160. 4. de Klerk E., Dobre C., P˙asechnik D V. Numerical block diagonalization of matrix -algebras with application to semidefinite // Math. Program. – 2011. – Ser. B. – 129: 91 – 111. 5. Murota K., Kanno Y., Kojima M., Kojima S. A numerical algorithm for block-diagonal decomposition of matrix -algebras with application to semidefinite programming // Japan J. Indust. Appl. Math. (2010) 27: 125 – 160. 6. Любарский Г.Я. Теория групп и ее применение в физике: Курс лекций для физиков- теоретиков. Изд. 2. – М.; 2016. – 360 с. 7. Гантмахер Ф.Р. Теория матриц. – М.: Наука, 1967. – 576 с. 8. Базилевич Ю.Н. Численные методы декомпозиции в линейных задачах механики. – Киев: Наук. думка, 1987. – 156 с. 9. Bazilevich Yu.N. The Simultaneous Reduction of Matrices to the Block-Triangular Form [E-resource] // Physics Journal. – 2015. – Vol. 1, N 2. – Р. 54 – 61. Access to the resource: http://files.aiscience.org/journal/article/html/70400061.html. 10. Базилевич Ю.Н., Булдович А.Л. Алгоритм нахождения общего решения системы линейных однородных алгебраических уравнений в случае сверхбольшой разреженной матрицы коэффициентов // Математические модели и современные технологии. Киев: Ин-т математики, 1998. – С. 12 – 13. Ю.Н. БАЗИЛЕВИЧ 108 Теорія оптимальних рішень. 2016 Получено 20.04.2016

Об упрощении задачи полуопределенного программирования

Репозитарії

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