Численная эффективность методов полуопределенной оптимизации

Розглянуто задачі напіввизначеної оптимізації та методи їх розв’язання. Запропоновано новий узагальнений симлекс-метод для розв’язання задач напіввизначеної оптимізації на основі апроксимації конуса напіввизначених матриць сумою матриць рангу одиниця. Порівняльні чисельні експерименти підтверджують...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автори:	Косолап, А.И., Перетятько, А.С.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207792
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Численная эффективность методов полуопределенной оптимизации / А.И. Косолап, А.С. Перетятько // Проблемы управления и информатики. — 2014. — № 2. — С. 56-64. — Бібліогр.: 16 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207792
record_format	dspace
spelling	irk-123456789-2077922025-10-14T00:09:40Z Численная эффективность методов полуопределенной оптимизации Чисельна ефективність методів напіввизначеної оптимізації Numerical efficiency of semidefinite optimization methods Косолап, А.И. Перетятько, А.С. Оптимальное управление и методы оптимизации Розглянуто задачі напіввизначеної оптимізації та методи їх розв’язання. Запропоновано новий узагальнений симлекс-метод для розв’язання задач напіввизначеної оптимізації на основі апроксимації конуса напіввизначених матриць сумою матриць рангу одиниця. Порівняльні чисельні експерименти підтверджують ефективність напіввизначеного симплекс-методу. The problems of semidefinite optimization and modern methods of their solution are considered. The new semidefinite simplex-method for the solution of problems of semidefinite optimization on the basis of approximation of a cone of semidefinite matrixes by the sum of matrixes of a rank unit is offered. Comparative numerical experiments have confirmed the efficiency of the semidefinite simplex-method. 2014 Article Численная эффективность методов полуопределенной оптимизации / А.И. Косолап, А.С. Перетятько // Проблемы управления и информатики. — 2014. — № 2. — С. 56-64. — Бібліогр.: 16 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207792 519.853 10.1615/JAutomatInfScien.v46.i4.20 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Косолап, А.И. Перетятько, А.С. Численная эффективность методов полуопределенной оптимизации Проблемы управления и информатики
description	Розглянуто задачі напіввизначеної оптимізації та методи їх розв’язання. Запропоновано новий узагальнений симлекс-метод для розв’язання задач напіввизначеної оптимізації на основі апроксимації конуса напіввизначених матриць сумою матриць рангу одиниця. Порівняльні чисельні експерименти підтверджують ефективність напіввизначеного симплекс-методу.
format	Article
author	Косолап, А.И. Перетятько, А.С.
author_facet	Косолап, А.И. Перетятько, А.С.
author_sort	Косолап, А.И.
title	Численная эффективность методов полуопределенной оптимизации
title_short	Численная эффективность методов полуопределенной оптимизации
title_full	Численная эффективность методов полуопределенной оптимизации
title_fullStr	Численная эффективность методов полуопределенной оптимизации
title_full_unstemmed	Численная эффективность методов полуопределенной оптимизации
title_sort	численная эффективность методов полуопределенной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207792
citation_txt	Численная эффективность методов полуопределенной оптимизации / А.И. Косолап, А.С. Перетятько // Проблемы управления и информатики. — 2014. — № 2. — С. 56-64. — Бібліогр.: 16 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT kosolapai čislennaâéffektivnostʹmetodovpoluopredelennojoptimizacii AT peretâtʹkoas čislennaâéffektivnostʹmetodovpoluopredelennojoptimizacii AT kosolapai čiselʹnaefektivnístʹmetodívnapívviznačenoíoptimízacíí AT peretâtʹkoas čiselʹnaefektivnístʹmetodívnapívviznačenoíoptimízacíí AT kosolapai numericalefficiencyofsemidefiniteoptimizationmethods AT peretâtʹkoas numericalefficiencyofsemidefiniteoptimizationmethods
first_indexed	2025-10-14T01:11:21Z
last_indexed	2025-10-15T01:09:56Z
_version_	1846008187408351232
fulltext	© А.И. КОСОЛАП, А.С. ПЕРЕТЯТЬКО 2014 56 ISSN 0572-2691 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.853 А.И. Косолап, А.С. Перетятько ЧИСЛЕННАЯ ЭФФЕКТИВНОСТЬ МЕТОДОВ ПОЛУОПРЕДЕЛЕННОЙ ОПТИМИЗАЦИИ Введение. В последние пятнадцать лет полуопределенная оптимизация (Semidefinite Programming — SDP) является одной из наиболее важных тем теоре- тических и прикладных исследований. Многие сложные прикладные задачи вы- числительной геометрии, квадратичной, комбинаторной и полиномиальной опти- мизации, теории сетей и оптимального управления могут эффективно решаться посредством полуопределенной релаксации [1]. Область приложения полуопределенной оптимизации постоянно расширяет- ся [13]. Разработаны методы для решения этого класса задач. Широко использует- ся прямодвойственный метод внутренней точки [4, 5]. Однако поиск более эффек- тивных методов для решения задач полуопределенной оптимизации продолжает- ся [6–8]. В работе [9] предложен новый полуопределенный симплекс-метод для решения этого класса задач. Найдены оценки эффективности методов посредст- вом проведения большого количества численных экспериментов. Их результаты отражены в настоящей работе. Искомой точкой минимума в задаче полуопределенной оптимизации является положительно-полуопределенная матрица. Множество таких матриц образует вы- пуклый конус в пространстве всех матриц. Если целевая функция и ограничения за- дачи полуопределенной оптимизации линейны, то такая задача будет выпуклой, так как конус полуопределенных матриц выпуклый. Однако условие положительной полуопределенности матрицы может быть получено только алгоритмически, что усложняет разработку эффективных алгоритмов полуопределенной оптимизации. Определение положительной полуопределенности матрицы требует поиска мини- мального собственного значения искомой матрицы либо определителей всех ее ми- норов, либо поиска минимума отношения Релея .\|\|\|\|/ 2T zXzz Заметим, что количе- ство миноров матрицы растет экспоненциально от размерности матрицы, и для матрицы порядка n число миноров равно .12 n Образующими конуса полуопределенных матриц являются матрицы ранга единица, число которых бесконечно, причем каждые две из них соседние (сумма образующих опять образующая). Это затрудняет построение аппроксимации по- луопределенного конуса эллипсоидальным конусом, у которого сумма образую- щих не является образующей. Ниже построена локальная аппроксимация конуса полуопределенных матриц многогранным конусом. Постановка задачи SDP и решение прямодвойственным методом внут- ренней точки. В задаче полуопределенного программирования требуется найти },...,,1,0,\|min{ miXbXAXC ii   (1) Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 2 57 где X — полуопределенная матрица размерности ),( nn C и все iA — симмет- ричные матрицы, а  ijij xcXC будем называть скалярным произведением матриц. Двойственной к (1) является задача ,0,\|max 1 T           ZCZyAyb m i i (2) где матрица Z также положительно-полуопределенная. Необходимые условия экстремума для задач (1), (2) имеют вид [3] .0 ;0, ;0,...,,1, 1 T      XZ ZCZyA XmibXA m i i ii   (3) Нелинейная система (3) имеет mnn  )1( переменных и 22/)1( nnnm  уравнений (из равенства 0 ZX следует равенство 0XZ для полуопреде- ленных матриц, причем матрица ZX не является симметрической). Система (3) без условий 0,0  ZX имеет неединственное решение (например, для задачи min{ x1  x2\|2x1  x2 1, x  0} система уравнений 2x1  x2 1, 2y1  z1   1, y2  z2   1, z1x1  0, z2x2  0 имеет два решения: (0,5, 0,  0,5,  1, 0, 0) и ( 0,01633, 1,032669,  0,5,  1, 0, 0)), поэтому используют штраф ),ln(det XXC  кото- рый определен только для .0X Необходимые условия оптимальности для задачи со штрафом приводят к сле- дующей нелинейной системе уравнений: , ; ;...,,1, 1 T IXZ CZyA mibXA m i i ii      (4) которая при фиксированном 0 и начальном 0X имеет единственное реше- ние [10]. Система (4) решается методом Ньютона для фиксированного значения параметра ,0 затем пересчитываетcя значение  так, чтобы .0 На каж- дой итерации метода Ньютона решается линейная система (скобками заменим индексы ),(XAXAi  ),,1 mi  , );()( );()( TT XZIZXXZ yAZCyAZ XAbXA    (5) где искомыми являются матрицы ZX  , и вектор .y Найдем сначала вектор y из второго уравнения системы (5): ,)( 2 T ZFyA  (6) где ).(T 2 yAZCF  Умножив обе части уравнения (6) слева на X и справа на 1Z и результат слева — скалярно на матрицу ,A получим ).()())(( 11 2 1T   ZZXAZXFAZyXAA (7) Из последнего уравнения системы (5) находим ,XZXZIZX  58 ISSN 0572-2691 подставив его в уравнение (7), получим ))(()())(( 11 2 1T   ZXZZXIAZXFAZyXAA или ).()()()())(( 11 2 1T XAXAZAZXFAZyXAA   Учитывая, что )()( XAbXA  (см. (5)), последнее уравнение равносильно сле- дующему: .)()())(( 11 2 1T bZAZXFAZyXAA   (8) Уравнение (8) содержит только один неизвестный вектор — .y После его опре- деления из системы (5), (6) находим искомые матрицы )(T 2 yAFZ  и .11 XZZXZX   Результатом проведенных операций может быть несимметрическая матри- ца .X Ее необходимо преобразовать к симметрической таким образом: .2/)( TXXX  Переход в новую точку осуществляется следующей итерационной процедурой: ;XXX p ;yyy d ,ZZZ d где константы p и d принадлежат отрезку ].1,0( Параметр  на каждой ите- рации пересчитывается по формуле nXZ [3]. Рассмотренная формула симметризации матрицы X может нарушить сходи- мость метода Ньютона, поэтому предложены различные модификации уравнения .IZX  В работе [10] применяется оператор ,][ 2 1 )( TTTT1 IPXZPPXZPXZHP   который изменяет третье уравнение системы Ньютона (4) на )()( XZHIZXXZH Pp  или .)()()()( TT1TT1 PZXPPXZPIPZXXZPPZXXZP   Предложены различные виды матрицы P. Наиболее эффективна матрица P, определяемая формулой NP [11]: ,))(( 2/12/12/12/12/12/1  XZXXXP для кото- рой оценка числа итераций метода внутренней точки равна 223 5,03 nmmn  [11]. Рассмотренный метод внутренней точки для решения задачи (1) эффективен для задач полуопределенного программирования средней размерности [8]. Кроме того, он применим только в том случае, если разрыв двойственности равен нулю. В отличие от задачи линейного программирования, здесь разрыв двойственности может быть больше нуля даже тогда, когда прямая и двойственная задача SDP имеют решение. Для того чтобы разрыв двойственности в задачах (1), (2) равнял- ся нулю, достаточно выполнения условия Слейтера (существует допустимое ре- шение 0X для задачи (1)). Полуопределенный симплекс-метод для решения задач полуопределен- ной оптимизации. Рассмотрим прямую задачу полуопределенного программиро- вания (1), где необходимо найти полуопределенную матрицу .X Известно, что любая полуопределенная матрица может быть разложена на сумму матриц ранга единица [12, c. 542], которые представимы в виде .Txx Таким образом, матрицы ранга единица определяются векторами ).,,( 1 j n jj xxx  Эти матрицы являются Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 2 59 крайними лучами (образующими) конуса полуопределенных матриц K. Число таких образующих бесконечно, но существует их конечный набор, содержащий решение задачи (1). В качестве начальных образующих достаточно выбрать любую незави- симую систему векторов. При программной реализации метода выбирались векто- ры с компонентами, равными ),0...,0,1,0...,,0(jx ),0...,,0,1,1,0...,,0( jx ).1...,1,1...,1( jx Число таких матриц (образующих) равно .13 n Обозначим эти матрицы ,T jjj xxX  а соответствующий многогранный конус — .0K Будем искать решение задачи (1) в виде ,  j jj XX где число слагаемых равно ,13 n а .0 Тогда задача (1) преобразуется к виду         0,...,,1,min mibXAXC ij jjij jj или .0,...,,1,min         mibXAXC ij jijj jj (9) Решение задачи (9)  позволяет найти полуопределенную матрицу ,*   j jj XX которая будет решением задачи (1), если .0 * KX  В противном случае конус 0K необходимо увеличить добавлением новых образующих. Задача (9) является задачей линейного программирования, которую решим симплекс-методом или прямодвойственным методом внутренней точки. В симп- лекс-методе на каждой итерации находится базисное решение и преобразуется строка целевой функции так, чтобы при базисных переменных коэффициенты це- левой функции (оценки) равнялись нулю. В новое базисное решение включается столбец матрицы ограничений с минимальным значением коэффициента преобра- зованной целевой функции. Это базисное решение уменьшает значение целевой функции, если оценка в строке целевой функции отрицательна. Для полуопреде- ленного симплекс-метода новый столбец матрицы ограничений необходимо по- строить. Обозначим Ki многогранные конусы, на которых ищется решение зада- чи (9), i — количество добавленных столбцов в матрицу ограничений. Для этих конусов справедливо соотношение ., iKK ii  Искомый столбец матрицы ограничений задачи (9) будем определять произ- вольной матрицей ранга единица .T kk xx Для этого столбца оценка в преобразо- ванной строке целевой функции будет минимальной. Найдем эту оценку. Пусть B — матрица базисных элементов оптимального решения задачи (9). Тогда эле- менты нового k-го столбца матрицы ограничений задачи (9) будут равны: ),...,,,( TT 2 T 1 1 kkmkkkk xxAxxAxxAB  а строку целевой функции преобразуем по формуле      i kkj m j ijiikk xxAbxxCxxC T 1 1TT или ,T1 1 T kkjij m j iii xxAbxxCC              где суммирование проводится по всем базисным столбцам матрицы ограничений за- дачи (9), а 1 ijb — элементы матрицы .1B Обозначим , 1 1T     j j m j ijii AbxxCCQ 60 ISSN 0572-2691 тогда kkkk QxxxxQ TT  будет требуемой оценкой, необходимо найти такое kx , чтобы оценка kk QxxT была минимальной. Если ,0T kk Qxx то ввод k -го столбца в базис приведет к уменьшению целевой функции задачи (9) [13, с. 101]. Если же матрица Q положительно-полуопределенная, то ,,0T xQxx  и значение целевой функции задачи (9) не может быть уменьшено. В этом случае текущее решение оптимально для задачи (1) (см. теорему 1). Для нахождения kx решим задачу квадратичной оптимизации }.1\|\|\|\|\|min{ 2T xQxx (10) Хорошо известно, что задача (10) эффективно разрешима [14]. Очевидно, что ре- шение задачи (10) совпадает с решением задачи }.1\|\|\|\|\|)1\|\|(\|\|min{ 22T  xxrQxx Выберем 0r таким, чтобы матрица rIQQ * была положительно-опреде- ленной. Для этого достаточно, чтобы ,\|,\| ** iqq ji ijii    где * ijq — элементы мат- рицы .Q Таким образом, решение задачи (10) сведено к поиску собственного вектора матрицы ,Q соответствующему ее минимальному собственному значе- нию. Это равносильно решению задачи }1\|\|\|\|\|min{ 2T xxQx или }.1\|\|\|max{\|\| T2 xQxx (11) При надлежащем выборе начального значения kx0 -е приближение решения зада- чи (11) может быть найдено в явном виде (используя метод множителей Лагранжа для последовательности задач ...),1,0},1\|)max{( TT  kxQxxxk . )( )( 0)12(0 0* xQx xQ x k k k    Значение kx отличается от решения, полученного степенным методом, норми- ровкой вектора kx на каждой итерации. Учитывая, что задача (11) квадратичная, на каждой итерации будем строить сопряженные направления. Положим 1kz kk xx  1 и параметр  выберем из условия сопряженности векторов kx и :1kz ,0)()()()()( T1T1T1T   kkkkkkkkk xQxxQxxxQxzQx откуда . )( )( T 1T kk kk xQx xQx   Полагаем ,11   kk xz и процесс поиска собственного вектора (решения зада- чи (11)) продолжается. Искомый собственный вектор будет достигнут, если вы- полнить условие ,\|\| 1  kk xx где 0 — заданная точность вычислений. Численные эксперименты показали, что сходимость метода сопряженных направ- лений, в среднем в 1,5 раза выше степенного метода со сдвигом Релея вклю- чительно [15]. В качестве начального приближения 0x достаточно взять точку (вектор), не ортогональную искомому собственному вектору. Этому условию Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 2 61 удовлетворяет точка касания эллипсоида грани описанного прямоугольного па- раллелепипеда ,/)( 110         iiqeQx где ),1...,,1(e а 1 iiq — i-й диагональный элемент матрицы ,)( 1 Q значение i выбирается из условия максимума .\|\|\|\| 0x Если x — решение задачи (11), то матрица Q — положительно-полу- определенная при условии .0T Qxx В этом случае задача (1) решена, в про- тивном случае поиск решения задачи (1) симплекс-методом будет продолжен. Это утверждение вытекает из следующей теоремы. Теорема 1. Если существует решение задачи (1) с меньшим значением целе- вой функции, чем в точке   j jj X ( — решение задачи (9) на конусе ),iK то тогда существует матрица kX ранга единица, что для решения задачи (9) на ко- нусе 1iK справедливо неравенство .        j jjkkj jj XCXXC Доказательство. Пусть X — решение задачи (1), тогда ,*  i iXX где * iX — матрицы ранга единица. Добавим к ограничениям задачи (9) новые столб- цы, содержащие матрицы :* iX .......... ......................................................................................................... ,......... ** 111 1 * 1 * 111111 mrmrmkmmmm rrkmm bXAXAXAXA bXAXAXAXA   Пусть столбцы этой матрицы ограничений определяют многогранный конус ,rK тогда решение задачи (9) при этих ограничениях определит матрицу ,X так как . rKX  Таким образом, значение целевой функции будет уменьшено. Это воз- можно только тогда, когда, по крайней мере, одна оценка в преобразованной строке целевой функции, соответствующая добавленным столбцам, будет отрица- тельной ),0,( *  iXQi так как в противном случае текущее решение задачи (9) будет оптимальным. Добавление одного из таких столбцов с отрицательной оцен- кой в матрицу ограничений задачи (9) приведет к убыванию ее целевой функции (см. теорему 4 в [12], с. 101), что доказывает теорему. Из теоремы 1 следует, что убывание целевой функции задачи (9) на кону- сах ,...,1, iKi будет до тех пор, пока .* iKX  Для доказательства сходимости полуопределенного симплекс-метода необ- ходимо следующее утверждение. Теорема 2. Предельная точка последовательности }{ kx принадлежит -ок- рестности точки минимума x непрерывной функции )(xf на компактном до- пустимом множестве, если: a) )(xf ограничена снизу и убывает на допустимом множестве; б) существует такое 0 (— точность вычислений), для которого спра- ведливо неравенство kxfxf kk  ,)()( 1 вне  -окрестности точки .x Доказательство. Если последовательность )( kxf убывает и ограничена снизу, то она сходится к некоторому значению ),( mxf когда ,mk xx  что озна- чает .,)()( 0kkxfxf mk  Если точка mx не принадлежит  -окрестности точки ,x то .)()( 1  kk xfxf Из последних двух неравенств следует ),()( 1 mk xfxf  но тогда )( mxf не может быть пределом )( kxf , так как )( kxf убывающая. Полученное противоречие доказывает, что mx принадлежит  -окрестности точки .x Теорема доказана. 62 ISSN 0572-2691 Непосредственно из теорем 1, 2 следует сходимость полуопределенного сим- плекс-метода. Следствие. Пусть решение задачи (9) определяет матрицу ,kX для которой выполняется условие ,0*  XCXC k тогда предельная точка X по- следовательности }{ kX принадлежит )(B ( )(B — окрестность решения *X задачи (1)). Достаточно показать, что существует такое ,0 для которого выполня- ется неравенство   kk XCXC 1 вне окрестности )(B (убывание kXC  доказано в теореме 1). Из теоремы 4 [12] следует, что ,0T1   rk r kk kk a b QxxXCXC где r — ведущая строка симплекс-метода, а kx — решение задачи (10). Выберем ,0 где, TT  kk rk r kk Qxx a b Qxx для которого выполняется неравенство ,1   kk XCXC тогда если 0rb (решение задачи (9) невырожденное), то условия теоремы 2 выполняются. Если предположить, что ,,0 kbr  то значения целевой функции задачи (9) при добавлении новых столбцов в матрицу ограниче- ний не будут убывать, что противоречит условиям теоремы 1. Таким образом, ).( BX Если допустимое множество задачи (9) пусто, то для нахождения начального базиса используем метод искусственного базиса (столбцы искусственного базиса будут определяться матрицами произвольного ранга). Минимизируем сумму пе- ременных k для столбцов искусственной матрицы. Если задача (1) имеет реше- ние, то все k обратятся в нуль и будет найден начальный базис, состоящий из матриц ранга единица. Рассмотрим пример задачи (1): . 1 3 4 , 001 010 100 , 100 000 000 , 000 000 001 , 111 111 111 321                                                 bAAAC Начальная матрица для задачи (9) равна (одинаковые столбцы программой удаляются) 312211010 111110100 111101001  Полуопределенным симплекс-методом добавлено пять столбцов: 4,59E02 0,561676 0,429775 7,88E02 0,319177 4,59E02 0,124838 0,122866 1,31E02 5,59E02 1 0,21611 1,22E-02 0,972314 0,357683. За шесть итераций найдено решение задачи (1): 4 2,61987 2,913056 2,61987 6,826113 0,210867 2,91306 0,21087 3 со значением целевой функции .313702,25 XC Методом внутренней точки за 22-е итерации получено решение 3,99999727 2,62082 2,91425 2,6208194 6,828507 0,20752 2,9142529 0,20752 2,999999 с погрешностью 1,0Е06 в ограничениях и значением целевой функции .313697,25 XC Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 2 63 Рассмотренный полуопределенный симплекс-метод имеет ряд преимуществ по сравнению с методом внутренней точки. 1. Размерность задачи, решаемой полуопределенным симплекс-методом, рав- на ,13 kn  где k — число итераций метода, а для внутренней точки — .)1( nnm  Еще больше различие по числу ограничений: m и 22/)1( nnnm  соответственно. 2. Область задач, решаемых полуопределенным симплекс-методом, шире, так как не требуется равенства целевых функций прямой и двойственной задач. 3. Полуопределенный симплекс-метод нечувствительный к выбору началь- ной точки, в то время как в методе внутренней точки начальная точка должна быть допустимой (существуют версии этого метода для недопустимой начальной точки [16]). Сравнительные численные эксперименты. Разработаны программы полуоп- редленного симплекс-метода и метода внутренней точки interior point method (IPM). Сравнительные численные эксперименты проводились для задач SDP (1) раз- личной размерности. Полуопределенный симплекс-метод не требует начальной допустимой точки (матрицы). В программе IMP в качестве начальной использо- валась единичная матрица. За критерии определения эффективности методов бра- лись точность и время решения, а также точность выполнения ограничений. Экс- перименты показали преимущества полуопределенного симплекс-метода как по скорости решения задач, так и по точности выполнения ограничений. Сравни- тельные эксперименты проводились на компьютере с двухъядерным процессором Intel Core i5 c частотой 2,5 ГГц. При точности вычислений 810 метод внутрен- ней точки иногда давал погрешность в ограничениях порядка 0,001, а полуопре- деленный симплекс-метод позволял находить решения, которые удовлетворяли ограничениям с машинной точностью. Затем были проведены эксперименты с существующими программными пакета- ми. Результаты этих экспериментов приведены в таблице. Полужирным шрифтом от- мечены лучшие результаты; e — задание числа в экспоненциальной форме. Задачи полуопределенной оптимизации решались пакетами CSDP, PENSDP, SDPA, SDPT3, SEDUMI с использованием NEOS-сервера (http://neos-server. org/neos/), для их решения полуопределенным симплекс-методом была разработа- на программа на VBA для Excel. Также на VBA для Excel была разработана про- грамма рассмотренного метода внутренней точки [15]. Таблица n m Критерий Программный пакет Симплекс-метод CSDP PENSDP SDPA SDPT3 SEDUMI 10 10 решение 198,97 199,03 199,03 199,03 199,03 199,03 время 6,45е-02 6,65е03 2е02 4,51е03 1,3 8е01 11 14 решение 74,97 75,02 75,02 75,02 75,02 75,02 время 2,29е01 9,24е03 4е02 8,51е03 1,2 8,3е01 20 3 решение 873,3804 873,3806 873,3806 873,3806 873,3806 873,3806 время 3,93е02 1,073е02 4е02 1,26е01 1,5 8,6е01 30 1 решение 5852,52 5852,52 5852,52 5852,52 5852,52 5852,52 время 2,23е02 1,41е02 5е02 9,84е03 1,3 6,9е01 50 2 решение 3675,12 3675,12 3675,12 3675,12 3675,12 3675,12 время 1,71e01 5,06е-02 1,4е01 5,57е02 1,7 1,06 100 2 решение 57408,05259 57408,053 57408,053 57408,053 57408,053 57408,053 время 5,6e01 3,31е01 6,2е01 2,53е01 3,1 3,63 25 4 решение 112232,2602 112232,26 112232,26 112232,26 112232,26 112232,26 время 1,48e01 1,49е02 8е02 1,38е02 1,5 9е01 13 6 решение 9,194 8,99 9 8,99 8,99 8,99 время 5,79е03 1,83е02 3е02 3,3е02 1,6 7,7е01 http://neos-server/ 64 ISSN 0572-2691 Таким образом, из результатов таблицы можно сделать вывод, что полуопре- деленный симплекс-метод не уступает методам внутренней точки даже при том, что его программная реализация не является оптимальной. Заключение. В настоящей работе рассмотрены современные методы реше- ния задач полуопределенной оптимизации. В частности, приведено обоснование нового полуопределенного симплекс-метода. Многочисленные эксперименты подтверждают высокую эффективность предложенного метода. А.І. Косолап, А.С. Перетятько ЧИСЕЛЬНА ЕФЕКТИВНІСТЬ МЕТОДІВ НАПІВВИЗНАЧЕНОЇ ОПТИМІЗАЦІЇ Розглянуто задачі напіввизначеної оптимізації та методи їх розв’язання. Запро- поновано новий узагальнений симлекс-метод для розв’язання задач напіввиз- наченої оптимізації на основі апроксимації конуса напіввизначених матриць сумою матриць рангу одиниця. Порівняльні чисельні експерименти підтвер- джують ефективність напіввизначеного симплекс-методу. A.I. Kosolap, A.S. Peretyatko NUMERICAL EFFICIENCY OF SEMIDEFINITE OPTIMIZATION METHODS The problems of semidefinite optimization and modern methods of their solution are considered. The new semidefinite simplex-method for the solution of problems of semidefinite optimization on the basis of approximation of a cone of semidefinite matrixes by the sum of matrixes of a rank unit is offered. Comparative numerical ex- periments have confirmed the efficiency of the semidefinite simplex-method. 1. Vandenberghe L., Boyd S. Semidefinite programming // SIAM Review. — 1996. — 38. — P. 49–95. 2. Шор Н.З. Методы минимизации негладких функций и матричные задачи оптимизации. — Кишинев : Эврика, 2009. — 240 с. 3. Freund R.M. Introduction to semidefinite programming. — Massachusetts Institute of Techno- logy, 2004. — 54 p. 4. Alizadeh F. Interior point methods in semidefinite programming with applications to combinato- rial optimization // SIAM Journal on Optimization. — 1995. — 5. — Р. 13–51. 5. Nesterov Yu., Nemirovskii A.S. Interior point polynomial algorithms in convex programming // SIAM Studies in Applied Mathematics. — 1994. — 13. — 405 р. 6. Todd M.J. Semidefinite optimization // Acta Numerica. — 2001. — 10. — P. 515–560. 7. Malick J., Povh J., Rendl F., Wiegele A. Regularization methods for semidefinite programming / // SIAM Journal on Optimisation — 2009. — 20, N 1. — P. 336–356. 8. Helmberg C., Rendl F. A spectral bundle method for semidefinite programming // Ibid. — 2000. — 10, N 3. — P. 673–696. 9. Косолап А.И. Обобщение симплекс-метода для решения задач полуопределенной оптими- зации // Математичне та комп’ютерне моделювання. — 2010. — C. 99–106. 10. Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming // SIAM Journal Optimixation — 1998. — 8, N 2. — P. 365–386. 11. Todd M.J., Toh K.C., Tutuncu R.H. On the Nesterov–Todd direction in semidefinite programming // Ibid. — 1998. — 8, N 3. — P. 769–796. 12. Хорн Р., Джонсон Ч. Матричный анализ. — М. : Мир, — 1989. — 656 с. 13. Данциг Дж. Линейное программирование, его обобщение и применение — М. : Прогресс, 1966. — 600 с. 14. Fortin C. Computing the local minimizers of a large and sparse trust-region subproblem. — Mon- treal : McGill University, 2004. — 149 p. 15. Парлетт Б. Симметричная проблема собственных значений. Численные методы. — М. : Мир, 1983. — 384 с. 16. Roumili H., Keraghel A., Yassine A. Infeasible interior point method for semidefinite programs // Applied Mathematical Sciences. — 2007. — 10 p. Получено 22.07.2011 После доработки 30.10.2013

Численная эффективность методов полуопределенной оптимизации

Репозитарії

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