source: proiecte/pmake3d/make3d_original/Make3dSingleImageStanford_version0.1/third_party/opt/yalmip/htmldata/ranksdp.htm @ 37

Last change on this file since 37 was 37, checked in by (none), 14 years ago

Added original make3d
File size: 7.6 KB
Line 
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];
48B = [0 0 1 0]';
49C = [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);
59Y = 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')';
69Cp = null(C)';
70W  = eye(3)*1e-6;</pre>
71                <pre>F = set(Bp*(A*X+X*A')*Bp' &lt; -W) + set(Cp*(Y*A+A'*Y)*Cp' &lt; -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] &gt;= 0);   % not needed, see below
83F = F + set(rank([X eye(4);eye(4) Y]) &lt;= 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.&nbsp; 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>
Note: See TracBrowser for help on using the repository browser.