YALMIP выводит «Неисполнимый» для простого, выполнимого SDP

matlab mathematical-optimization convex-optimization

681 просмотра

1 ответ

103 Репутация автора

Я хочу определить, является ли данная матрица 3x3 положительно-полуопределенной или нет. Для этого я пишу следующий SDP в YALMIP

v=0.2;
a=sdpvar(1);
b=sdpvar(1);
M=[1 a -v/4 ; b 1 0 ; -v/4 0 0.25];
x=sdpvar(1);
optimize([M+x*eye(3)>=0],x,sdpsettings('solver','sedumi'))

Эта программа выдает мне ошибку «Обнаружено двойное неосуществимое, первичное направление улучшения». Это происходит для любого значения v в интервале (0,1].

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

16*t^3 - 36*t^2 + (24 - 16*a*b - v^2)*t + (-4 + 4*a*b + v^2)

Численно вычисляя значения трех корней, я вижу, что три из них положительны для знака (а) = знак (б) (за исключением небольшой области в окрестности а, b = + - 1), для любого значения v. Следовательно, SDP должен работать без проблем и выводить отрицательное значение x без дальнейших осложнений.

Чтобы сделать вещи более интересными, я запустил тот же код со следующей матрицей

M=[1 a v/4 ; b 1 0 ; v/4 0 0.25];

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

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

РЕДАКТИРОВАТЬ: Я также попробовал решатель SDPT3, и результаты очень похожи. На самом деле, программа работает гладко для случая + v, но когда я ставлю знак минус, я получаю следующую ошибку

'Unknown problem in solver (Turn on 'debug' in sdpsettings) (Error using  & …'

Кроме того, когда я добавляю некоторые ограничения к переменным, т.е. я запускаю следующую команду

optimize([total+w*eye(3)>=0,-1<=a<=1,-1<=b<=1],w,sdpsettings('solver','sdpt3'))

Тогда ошибка превращается в ошибку «Неисправимая проблема».

Автор: Alex Источник Размещён: 18.07.2016 06:26

Ответы (1)


1 плюс

328 Репутация автора

Решение

Поздний ответ, но все равно. Указанная вами матрица не является симметричной. Полуопределенное программирование - это оптимизация по множеству симметричных положительных полуопределенных матриц.

Когда вы определяете это несимметричное матричное ограничение в YALMIP, оно просто интерпретируется как набор из 9 линейных поэлементных ограничений, и для этой линейной программы оптимальный x не ограничен.

Автор: Johan Löfberg Размещён: 13.09.2016 12:29
Вопросы из категории :
32x32