feasp

Вычислительное решение данной системы LMI

Синтаксис

[tmin,xfeas] = feasp(lmisys,options,target)

Описание

[tmin,xfeas] = feasp(lmisys,options,target) вычисляет решение xfeas (при наличии) системы LMI, описанной lmisys. Векторная xfeas является конкретным значением переменных принятия решений, для которых удовлетворены все LMI.

Учитывая систему LMI

N^{T} L x N \leq M^{T} R (x) M,

(1)

xfeas вычисляется решением вспомогательной выпуклой программы:

Минимизируйте t в зависимости от N^TL (x) N -M^TR (x) M ≤ tI.

Глобальный минимум этой программы является скалярным значением tmin возвращен как первый выходной аргумент по feasp. Ограничения LMI допустимы, если tmin ≤ 0 и строго допустимо, если tmin < 0. Если проблема является выполнимой, но не строго выполнимой, tmin положительный и очень маленький. В таком случае может потребоваться какой-либо последующий анализ, чтобы решить, xfeas ли достаточно близко, чтобы это возможно.

Необязательный аргумент target задает целевое значение для tmin. Код оптимизации заканчивается, как только достигается значение t ниже этой цели. Значение по умолчанию target = 0.

Обратите внимание, что xfeas является решением с точки зрения переменных принятия решений, а не с точки зрения матричных переменных задачи. Использовать dec2mat для вывода допустимых значений матричных переменных из xfeas.

Параметры управления

Необязательный аргумент options предоставляет доступ к определенным параметрам управления для алгоритма оптимизации. Этот вектор с пятью входами организован следующим образом:

options(1) не используется.
options(2) устанавливает максимальное количество итераций, разрешенное для выполнения процедурой оптимизации (100 по умолчанию).
options(3) устанавливает радиус допустимости. Настройка options(3) к значению R > 0 дополнительно ограничивает вектор принятия решений x = (x 1,..., xN) лежать в мяч
$\sum_{i = 1}^{N} x_{i}^{2} < R^{2}$
Другими словами, евклидова норма xfeas не должен превышать R. Радиус выполнимости является простыми способами получения управления величиной решений. После расторжения, feasp отображает насыщение f-радиуса, то есть норму решения в процентах от R радиуса допустимости.
Значение по умолчанию R = 109. Настройка options(3) отрицательное значение активирует режим «гибкой привязки». В этом режиме радиус выполнимости первоначально устанавливается равным 108 и увеличивается, если необходимо, в ходе оптимизации
options(4) помогает ускорить завершение. При установке целочисленного значения J > 0 код завершается, если t не уменьшился более чем на один процент в относительных терминах во время последних итераций J. Значение по умолчанию является 10. Этот параметр сходится со скоростью по сравнению с точностью. Если установлено небольшое значение (< 10), код завершается быстро, но без гарантии точности. Напротив, большое значение приводит к естественному сходению за счет, возможно, большого количества итераций.
options(5) = 1 отключает трассировку выполнения процедуры оптимизации. Сброс options(5) к нулю (значение по умолчанию) включает его обратно.

Настройка option(i) Значение нуля эквивалентно установке соответствующего параметра управления на его значение по умолчанию. Следовательно, нет необходимости переопределять весь вектор при изменении всего одного параметра управления. Чтобы задать максимальное количество итераций равное 10, для образца достаточно ввести

options=zeros(1,5)       % default value for all parameters 
options(2)=10

Проблемы с памятью

Когда задача наименьших квадратов, решенная при каждой итерации, становится плохо обусловленной, feasp решатель переключается с линейной алгебры на основе Холецкого на QR (для получения дополнительной информации см. «Задачи памяти»). Поскольку QR-режим обычно требует гораздо большей памяти, MATLAB^® может иссякнуть память и отобразить сообщение

??? Error using ==> feaslv 
Out of memory. Type HELP MEMORY for your options.

Затем необходимо попросить системного менеджера увеличить пространство свопов или, если нет дополнительного пространства свопов, задать options(4) = 1. Это предотвратит переключение на QR и feasp завершится, когда Холецкий не справится из-за численных нестабильностей.

Примеры

свернуть все

Решающая система LMI

Открыть Live Script

Рассмотрим задачу нахождения P > I такой, что:

$A_{1}^{T} P + P A_{1} < 0,$

$A_{2}^{T} P + P A_{2} < 0,$

$A_{3}^{T} P + P A_{3} < 0,$

с данными

$A_{1} = (\begin{array}{c} - 1 & 2 \\ 1 & - 3 \end{array}), A_{2} = (\begin{array}{c} - 0.8 & 1.5 \\ 1.3 & - 2.7 \end{array}), A_{3} = (\begin{array}{c} - 1.4 & 0.9 \\ 0.7 & - 2.0 \end{array}) .$

Эта проблема возникает при изучении квадратичной устойчивости многогранника матриц, $C o {A_{1}, A_{2}, A_{3}}$ .

Оценка выполнимости с помощью feaspсначала введите LMI.

setlmis([]) 
p = lmivar(1,[2 1]);

A1 = [-1 2;1 -3];
A2 = [-0.8 1.5; 1.3 -2.7];
A3 = [-1.4 0.9;0.7 -2.0];

lmiterm([1 1 1 p],1,A1,'s');     % LMI #1 
lmiterm([2 1 1 p],1,A2,'s');     % LMI #2 
lmiterm([3 1 1 p],1,A3,'s');     % LMI #3 
lmiterm([-4 1 1 p],1,1);         % LMI #4: P 
lmiterm([4 1 1 0],1);            % LMI #4: I 
lmis = getlmis;

Функции feasp для поиска допустимого вектора принятия решений.

[tmin,xfeas] = feasp(lmis);

 Solver for LMI feasibility problems L(x) < R(x)
    This solver minimizes  t  subject to  L(x) < R(x) + t*I
    The best value of t should be negative for feasibility

 Iteration   :    Best value of t so far 
 
     1                        0.972718
     2                        0.870460
     3                       -3.136305

 Result:  best value of t:    -3.136305
          f-radius saturation:  0.000% of R =  1.00e+09

Результат tmin = -3.1363 означает, что проблема является допустимой. Поэтому динамическая система $x_{}^{˙} = A (t) x$ квадратично стабилен для $A (t) \in C o {A_{1}, A_{2}, A_{3}} .$

Для получения матрицы Ляпунова P доказывая квадратичную стабильность, используйте dec2mat.

P = dec2mat(lmis,xfeas,p)

P = 2×2

  270.8553  126.3999
  126.3999  155.1336

Возможно добавить дополнительные ограничения для этой задачи выполнимости. Для образца следующая команда ограничивает норму Фробениуса P по 10 во время запроса tmin быть меньше или равным -1.

options = [0,0,10,0,0];
[tmin,xfeas] = feasp(lmis,options,-1);

 Solver for LMI feasibility problems L(x) < R(x)
    This solver minimizes  t  subject to  L(x) < R(x) + t*I
    The best value of t should be negative for feasibility

 Iteration   :    Best value of t so far 
 
     1                        0.988505
     2                        0.872239
     3                       -0.476638
     4                       -0.920574
     5                       -0.920574
***                 new lower bound:    -3.726964
     6                       -1.011130
***                 new lower bound:    -1.602398

 Result:  best value of t:    -1.011130
          f-radius saturation:  91.385% of R =  1.00e+01

Третья запись options устанавливает радиус выполнимости равным 10, в то время как третий аргумент равен feasp, -1, устанавливает целевое значение для tmin. Это ограничение приводит к tmin = -1.011 и матричный P с самым большим собственным значением $λ_{m a x} (P)$ = 8.4653.

P = dec2mat(lmis,xfeas,p);
e = eig(P)

Ссылки

Решатель выполнимости feasp основан на проективном методе Нестерова и Немировского, описанном в:

Нестеров Я. и А. Немировски, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, 1994.

Немировски, А. и П. Гахинет, «Проективный метод решения линейных матричных неравенств», прок. Amer. Contr. Конф., 1994, Балтимор, Мэриленд, с. 840-844.

Оптимизацию выполняет файл MEX на C feaslv.mex.

См. также

dec2mat | gevp | mincx

Представлено до R2006a

Документация