[37] | 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> |
---|