1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> |
---|
2 | <html> |
---|
3 | |
---|
4 | <head> |
---|
5 | <meta http-equiv="Content-Language" content="en-us"> |
---|
6 | <title>YALMIP Example : Rank constrained LMIs</title> |
---|
7 | <meta http-equiv="Content-Type" content="text/html; charset=windows-1251"> |
---|
8 | <meta content="Microsoft FrontPage 6.0" name="GENERATOR"> |
---|
9 | <meta name="ProgId" content="FrontPage.Editor.Document"> |
---|
10 | <link href="yalmip.css" type="text/css" rel="stylesheet"> |
---|
11 | <base target="_self"> |
---|
12 | </head> |
---|
13 | |
---|
14 | <body leftMargin="0" topMargin="0"> |
---|
15 | |
---|
16 | <div align="left"> |
---|
17 | |
---|
18 | <table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%"> |
---|
19 | <tr> |
---|
20 | <td width="100%" align="left" height="100%" valign="top"> |
---|
21 | <h2>Rank constrained LMIs</h2> |
---|
22 | <hr noShade SIZE="1"> |
---|
23 | <p> |
---|
24 | <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16">This |
---|
25 | example requires the solver <a href="solvers.htm#lmirank">LMIRank</a> (and a |
---|
26 | semidefinite solver)</p> |
---|
27 | <p>A lot of problems, in particular in control theory, can be |
---|
28 | addressed using rank constraints. Unfortunately, adding a |
---|
29 | simple rank constraint to a matrix in a standard LMI problem leads |
---|
30 | to an NP-hard optimization problem. Nevertheless, with a reasonable |
---|
31 | initial guess, a local search can be efficient for finding a |
---|
32 | low-rank solution in some cases. The solver <a href="solvers.htm#lmirank">LMIRank</a> |
---|
33 | performs such a local search and is interfaced by YALMIP. Details on |
---|
34 | the algorithm <a href="solvers.htm#lmirank">LMIRank</a> |
---|
35 | can be found in |
---|
36 | <a href="readmore.htm#ORSI">[Orsi et. al.]</a>.</p> |
---|
37 | <h3>Dynamic controller design using rank constraints</h3> |
---|
38 | <p>To illustrate rank constraints in YALMIP, and how to use |
---|
39 | the solver <a href="solvers.htm#lmirank">LMIRank</a>, we solve one |
---|
40 | of the examples in |
---|
41 | <a href="readmore.htm#ORSI">[Orsi et. al.]</a>. The problem is to design a |
---|
42 | dynamic output feedback controller for the system <strong>x' = Ax+Bu, |
---|
43 | y=Cx</strong></p> |
---|
44 | <table cellPadding="10" width="100%"> |
---|
45 | <tr> |
---|
46 | <td class="xmpcode"> |
---|
47 | <pre>A = [0.2 0 1 0;0 0.2 0 1;-1 1 0.2 0;1 -1 0 0.2]; |
---|
48 | B = [0 0 1 0]'; |
---|
49 | C = [0 1 0 0];</pre> |
---|
50 | </td> |
---|
51 | </tr> |
---|
52 | </table> |
---|
53 | <p>Define matrices <b>X</b> and <b>Y</b> (essentially modeling a Lyapunov |
---|
54 | matrix and its inverse) </p> |
---|
55 | <table cellPadding="10" width="100%"> |
---|
56 | <tr> |
---|
57 | <td class="xmpcode"> |
---|
58 | <pre>X = sdpvar(4,4); |
---|
59 | Y = sdpvar(4,4);</pre> |
---|
60 | </td> |
---|
61 | </tr> |
---|
62 | </table> |
---|
63 | <p>Without going into the theoretical background, the following LMI |
---|
64 | constraints are necessary for the existence of a controller. </p> |
---|
65 | <table cellPadding="10" width="100%"> |
---|
66 | <tr> |
---|
67 | <td class="xmpcode"> |
---|
68 | <pre>Bp = null(B')'; |
---|
69 | Cp = null(C)'; |
---|
70 | W = eye(3)*1e-6;</pre> |
---|
71 | <pre>F = set(Bp*(A*X+X*A')*Bp' < -W) + set(Cp*(Y*A+A'*Y)*Cp' < -W);</pre> |
---|
72 | </td> |
---|
73 | </tr> |
---|
74 | </table> |
---|
75 | <p>The rank constraint enter when we want to couple the matrices X |
---|
76 | and Y, and ensure the existence of a dynamic controller with at most 2 |
---|
77 | states. Once again stating the equations without any theoretical |
---|
78 | justification, the resulting constraints are</p> |
---|
79 | <table cellPadding="10" width="100%" id="table1"> |
---|
80 | <tr> |
---|
81 | <td class="xmpcode"> |
---|
82 | <pre>F = F + set([X eye(4);eye(4) Y] >= 0); % not needed, see below |
---|
83 | F = F + set(rank([X eye(4);eye(4) Y]) <= 4+2);</pre> |
---|
84 | </td> |
---|
85 | </tr> |
---|
86 | </table> |
---|
87 | <p>In the current implementation in YALMIP, a rank constraint |
---|
88 | automatically appends a positive semidefiniteness constraint on the |
---|
89 | involved matrix (i.e. a non-strict constraint, so these appended cones are |
---|
90 | not affected by the option <code>shift</code>.) Hence, the first constraint in the previous piece |
---|
91 | of code can (and should) be removed. Also note the use of a |
---|
92 | non-strict rank constraint. A strict inequality can be used, but will |
---|
93 | currently be interpreted as non-strict, hence it should not be used |
---|
94 | in order to avoid confusion. At the moment, the rank operator is |
---|
95 | implemented rather straightforwardly using a <a href="extoperators.htm">nonlinear operator</a>, |
---|
96 | but requires some dedicated code internally (read hack) to work when |
---|
97 | actually calling a solver. Hence, it should be emphasized that the current |
---|
98 | implementation is experimental and can be subject to changes in |
---|
99 | order to make the operator better integrated.</p> |
---|
100 | <p>At this point, we are ready to solve the problem. The solver <a href="solvers.htm#lmirank">LMIRank</a> |
---|
101 | needs an initial guess, and this can be supplied either by the user |
---|
102 | (by initializing variables and using the <code>'usex0'</code> option |
---|
103 | in standard fashion) or |
---|
104 | automatically by YALMIP. YALMIP computes an initial guess by |
---|
105 | removing the rank constraint and minimizing the trace of the rank |
---|
106 | constrained matrix (or sum of traces of all rank constrained |
---|
107 | matrices). Note that <a href="solvers.htm#lmirank">LMIRank</a> does not |
---|
108 | support objective functions, but only solves feasibility problems. |
---|
109 | If you want to optimize an objective function, you need to, e.g., |
---|
110 | perform a bisection. The following call will automatically select an |
---|
111 | SDP solver to find the initial guess, solve the initial problem, and |
---|
112 | then call <a href="solvers.htm#lmirank">LMIRank</a> (if installed) to search for a |
---|
113 | low-rank solution.</p> |
---|
114 | <table cellPadding="10" width="100%" id="table2"> |
---|
115 | <tr> |
---|
116 | <td class="xmpcode"> |
---|
117 | <pre>solvesdp(F);</pre> |
---|
118 | </td> |
---|
119 | </tr> |
---|
120 | </table> |
---|
121 | <p>The following call ensures that the solver for the initial guess |
---|
122 | is <a href="solvers.htm#sedumi">SeDuMi</a>, and uses an accuracy recommended by the author of <a href="solvers.htm#lmirank">LMIRank</a>.</p> |
---|
123 | <table cellPadding="10" width="100%" id="table7"> |
---|
124 | <tr> |
---|
125 | <td class="xmpcode"> |
---|
126 | <pre>solvesdp(F,[],sdpsettings('lmirank.solver','sedumi','sedumi.eps',0))</pre> |
---|
127 | </td> |
---|
128 | </tr> |
---|
129 | </table> |
---|
130 | <p>Note that these computations only give a feasible pair <b>X</b> |
---|
131 | and <b>Y</b>. To actually compute the controller (called reconstruction) requires some additional steps. </p> |
---|
132 | <p>If we compute the eigenvalues of our rank |
---|
133 | constrained matrix, we immediately see that we effectively have a |
---|
134 | rank of 6.</p> |
---|
135 | <table cellPadding="10" width="100%" id="table4"> |
---|
136 | <tr> |
---|
137 | <td class="xmpcode"> |
---|
138 | <pre>eig(double([X eye(4);eye(4) Y]))</pre> |
---|
139 | <pre><font color="#000000">ans = |
---|
140 | -0.0000 |
---|
141 | -0.0000 |
---|
142 | 1.6780 |
---|
143 | 2.5342 |
---|
144 | 2.7754 |
---|
145 | 2.9674 |
---|
146 | 6.2289 |
---|
147 | 6.8932</font></pre> |
---|
148 | </td> |
---|
149 | </tr> |
---|
150 | </table> |
---|
151 | <p>indeed, this is the rank reported by YALMIP.</p> |
---|
152 | <table cellPadding="10" width="100%" id="table5"> |
---|
153 | <tr> |
---|
154 | <td class="xmpcode"> |
---|
155 | <pre>rank([X eye(4);eye(4) Y]) |
---|
156 | <font color="#000000">Linear scalar (real, derived, 1 variables, current value : 6)</font></pre> |
---|
157 | </td> |
---|
158 | </tr> |
---|
159 | </table> |
---|
160 | <p>Note that rank computations are inherently hard from a numerical |
---|
161 | point of view, hence it may easily happen that the reported rank is |
---|
162 | higher than the desired rank, even though <a href="solvers.htm#lmirank">LMIRank</a> |
---|
163 | claimed feasibility. In such cases, a more detailed analysis using |
---|
164 | tolerances might be necessary (YALMIP always uses the default |
---|
165 | tolerance.)</p> |
---|
166 | <table cellPadding="10" width="100%" id="table6"> |
---|
167 | <tr> |
---|
168 | <td class="xmpcode"> |
---|
169 | <pre>rank(double([X eye(4);eye(4) Y]))</pre> |
---|
170 | <pre><font color="#000000">ans = |
---|
171 | 6</font></pre> |
---|
172 | <pre>rank(double([X eye(4);eye(4) Y]),1e-6)</pre> |
---|
173 | <pre><font color="#000000">ans = |
---|
174 | 6</font></pre> |
---|
175 | </td> |
---|
176 | </tr> |
---|
177 | </table> |
---|
178 | </td> |
---|
179 | </tr> |
---|
180 | </table> |
---|
181 | |
---|
182 | </div> |
---|
183 | |
---|
184 | </body> |
---|
185 | |
---|
186 | </html> |
---|