graphics: bug 9270 fixed - The contour function was broken.
[scilab.git] / scilab_doc / lmitool / lmidoc.tex
1 % Copyright INRIA
2
3 \documentclass{article}
4
5 \usepackage{psfig}
6
7 \textwidth=6.65in
8 \textheight=9.5in 
9 \oddsidemargin=-.08in
10 \evensidemargin=0in
11 \topmargin=-.6in
12 \parskip.1cm
13
14 \begin{document}
15 \def\lmitool{{\tt LMITOOL}}
16 \def\dsp{\displaystyle}
17 \def\reals{{\bf R}}
18 \def\BEQ{\begin{equation}}
19 \def\EEQ{\end{equation}}
20 \def\eg{{\em e.g.}}
21 \def\ie{{\em i.e.}}
22 \def\Tr{{\mathop{\bf Tr}}}
23 \def\diag{{\mathop{\bf diag}}}
24 \def\eqbydef{\mathrel{\stackrel{\Delta}{=}}}
25
26 \title{\lmitool:
27 a Package \\ for LMI Optimization in Scilab\\[0.5in]
28 User's Guide}
29 \date{}
30 \author{R. Nikoukhah\thanks{{\tt Ramine.Nikoukhah@inria.fr}}
31 \and
32 F. Delebecque\thanks{\tt Francois.Delebecque@inria.fr}.  
33 \and
34 L. El Ghaoui\thanks{ENSTA, 32, Bvd. Victor, 75739 Paris, France.
35 Internet: {\tt elghaoui@ensta.fr}.  Research supported in part by DRET
36 under contract  92017-BC14.}
37 }
38
39 \maketitle
40
41 \begin{abstract}
42 This report describes a user-friendly Scilab package, and in
43 particular its two main functions {\tt lmisolver} and
44 {\tt lmitool} for solving
45 Linear Matrix Inequalities problems.  This package
46 uses Scilab function {\tt semidef}, an interface to the program 
47 Semidefinite Programming {\bf SP} (Copyright \copyright 1994 by Lieven
48 Vandenberghe and Stephen Boyd) distributed with Scilab. 
49 \end{abstract}
50
51 \tableofcontents
52
53 \newpage
54
55 \section{Purpose}
56 Many problems in systems and control can be formulated as follows 
57 (see \cite{BEFB:94}): 
58 \[
59 \Sigma : \;\; \left\{
60 \begin{array}{ll}
61 \mbox{minimize}    &  f(X_1,\ldots,X_M) \\
62 \mbox{subject to}  & \left\{ \begin{array}{l}
63                G_i(X_1,\ldots,X_M) = 0, \;\;i=1,2,...,p,\\
64                 H_j(X_1,\ldots,X_M) \geq 0, \;\;j=1,2,..,q. 
65                               \end{array} \right.
66 \end{array}
67 \right.
68 \]
69 where 
70 \begin{itemize}
71 \item
72 $X_1,\ldots,X_M$ are unknown real matrices, referred to as the {\em
73 unknown matrices,} 
74 \item
75 $f$ is a real linear scalar function of the entries of the unknown
76 matrices $X_1,\ldots,X_M$; it is referred to as the {\em objective function},
77 \item
78 $G_i$'s are real matrices with entries which are affine functions of the 
79 entries of the unknown matrices, $X_1,\ldots,X_M$;
80 they are referred to as  ``Linear Matrix Equality'' (LME) functions, 
81 \item
82 $H_j$'s are real symmetric matrices with entries which are affine functions
83 of the entries of the unknown matrices $X_1,\ldots,X_M$; they are referred to as  
84 ``Linear Matrix Inequality'' (LMI) functions.  (In this report, 
85 the  $V \geq 0$ stands for $V$ positive semi-definite unless stated otherwise).  
86 \end{itemize}
87 The purpose of \lmitool\ is to solve problem $\Sigma$ in a user-friendly manner
88 in Scilab, using the code SP \cite{sp}. This code is intended for
89 small and medium-sized problems (say, up to a few hundred variables).
90
91 \section{Function {\tt lmisolver}}
92
93 \lmitool\ is built around the Scilab function {\tt lmisolver}.  This
94 function computes the solution $X_1,\ldots,X_M$ of
95 problem~$\Sigma$, given functions $f$, $G_i$ and $H_j$. To solve
96 $\Sigma$, user must provide an evaluation function which 
97 ``evaluates'' $f$, $G_i$ and $H_j$ as a function the unknown matrices,
98 as well as an initial guess on the values of the unknown matrices.  User can either 
99 invoke {\tt lmisolver} directly, by providing the necessary information in a
100 special format or he can use the interactive
101 function {\tt lmitool} described in Section~\ref{s_lmitool}.
102
103 \subsection{Syntax} 
104 \begin{verbatim}
105 [XLISTF[,OPT]] = lmisolver(XLIST0,EVALFUNC[,options])
106 \end{verbatim}
107 where
108 \begin{itemize}
109
110 \item {\tt XLIST0:} a list structure including matrices and/or list of matrices.
111 It contains initial guess on the values of the unknown matrices. In general, the
112 ith element of {\tt XLIST0} is the initial guess on the value of the
113 unknown matrix $X_i$. In some cases
114 however it is more convenient to define one or more elements of
115 {\tt XLIST0} to be lists (of unknown matrices) themselves. This is a
116 useful feature when the number of unknown matrices is not fixed a priori
117 (see Example of Section~\ref{ex2}).
118
119 The values of the matrices in {\tt XLIST0}, if compatible with the LME functions, 
120 are used as intial condition for the optimization algorithm; they are
121 ignored otherwise. The size and structure of {\tt XLIST0} are used to
122 set up the problem and determine the size and structure of the output {\tt XLISTF}.
123
124 \item
125 {\tt EVALFUNC:} a Scilab function called {\em evaluation function}
126 (supplied by the user)
127 which evaluates the LME, LMI and objective functions, given the values of the
128 unknown matrices. The syntax is:
129 \begin{verbatim}
130 [LME,LMI,OBJ]=EVALFUNC(XLIST)
131 \end{verbatim}
132 where
133 \begin{itemize}
134 \item {\tt XLIST:} a list, identical in size and structure to {\tt XLIST0}.
135
136 \item {\tt LME:} a list of matrices containing values of the LME
137 functions $G_i$'s
138 for $X$ values in {\tt XLIST}. {\tt LME} can be a matrix in case
139 there is only one LME function to be evaluated (instead of a list
140 containing this matrix as unique element). It can also be a list
141 of a mixture of matrices and lists which in turn contain values of
142 LME's, and so on.
143
144 \item {\tt LMI:} a list of matrices containing the values of the LMI
145 functions $H_j$'s
146 for $X$ values in {\tt XLIST}. {\tt LMI} can also be a matrix (in case
147 there is only one LMI function to be evaluated). It can also be a list
148 of a mixture of matrices and lists which in turn contain values of
149 of LMI's, and so on.
150
151 \item {\tt OBJ:} a scalar equal to the value of the objective function $f$
152 for $X$ values in {\tt XLIST}.
153 \end{itemize}
154 If the $\Sigma$ problem has no equality constraints then {\tt LME}
155 should be {\tt []}. Similarly for {\tt LMI} and {\tt OBJ}.
156
157 \item
158 {\tt options:} a $5 \times 1$ vector containing optimization
159 parameters {\tt Mbound}, {\tt abstol}, {\tt nu}, {\tt maxiters},
160 and {\tt reltol}, see  manual page for {\tt semidef} for details ({\tt Mbound}
161 is a multiplicative coefficient for {\tt M}). This argument is optional,
162 if omitted, default parameters are used.
163
164
165 \item {\tt XLISTF:} a list, identical in size and structure to {\tt XLIST0}
166 containing the solution of the problem (optimal values of the unknown matrices).
167
168 \item {\tt OPT:} a scalar corresponding to the optimal value of the minimization
169 problem $\Sigma$.
170 \end{itemize}
171
172 \subsection{Examples}
173 \subsubsection{State-feedback with control saturation constraint}
174 \label{ex1}
175 Consider the linear system
176 \[
177 \dot{x}=Ax+Bu   
178 \]
179 where $A$ is an $n\times n$ and $B$, an $n \times n_u$ matrix.
180 There exists a stabilizing state feedback $K$ 
181 such that for every initial condition $x(0)$ with $\| x(0)\| \leq 1$,
182 the resulting control satisfies $\| u(t)\|$ for all $t\geq 0$, if and only if
183 there exist an $n\times n$ matrix $Q$ and an
184 $n_u \times n$ matrix $Y$ satisfying the equality constraint
185 \[
186 Q-Q^T=0
187 \]
188 and the inequality constraints
189 \begin{eqnarray*}
190 Q&\geq&0\\
191 -AQ-QA^T-BY-Y^TB^T &>& 0 \\
192 \left( \begin{array} {cc}  u_{max}^2I &Y\\Y^T & Q \end{array} \right) &\geq & 0
193 \end{eqnarray*}
194 in which case one such $K$ can be constructed as $K=YQ^{-1}$.
195
196 To solve this problem using {\tt lmisolver},  we first need to construct
197 the evaluation function.
198 \begin{verbatim}
199 function [LME,LMI,OBJ]=sf_sat_eval(XLIST)
200  [Q,Y]=XLIST(:)
201  LME=Q-Q'
202  LMI=list(-A*Q-Q*A'-B*Y-Y'*B',[umax^2*eye(Y*Y'),Y;Y',Q],Q-eye())
203  OBJ=[]
204 \end{verbatim}
205 Note that {\tt OBJ=[]} indicates that
206 the problem considered is a feasibility problem, i.e., we are only
207 interested in finding a set of $X$'s that satisfy LME and LMI functions.
208
209
210 Assuming {\tt A}, {\tt B} and {\tt umax}
211 already exist in the environment, we can call {\tt lmisolver}, and
212 reconstruct the solution in Scilab, as follows:
213 \begin{verbatim}
214 --> Q_init=zeros(A);
215 --> Y_init=zeros(B');
216 --> XLIST0=list(Q_init,Y_init);
217 --> XLIST=lmisolver(XLIST0,sf_sat_eval);
218 --> [Q,Y]=XLIST(:)
219 \end{verbatim}
220 These Scilab commands can of course be encapsulated in
221 a Scilab function, say {\tt sf{\_}sat}. Then, To solve this problem,
222 all we need to do is type:
223 \begin{verbatim}
224 --> [Q,Y]=sf_sat(A,B,umax) 
225 \end{verbatim}
226 We call {\tt sf{\_}sat} the {\em solver function} for this problem.
227
228
229
230 \subsubsection{Control of jump linear systems}
231 \label{ex2}
232 We are given a linear system 
233 \[
234 \dot{x} = A(r(t))x+B(r(t))u,
235 \]
236 where $A$ is $n \times n$ and $B$ is $n \times n_u$.   The scalar
237 parameter $r(t)$ is a continuous-time Markov process taking values in
238 a finite set $\{1,\ldots,N\}$. 
239
240 The transition probabilities of the process $r$ are defined by a
241 ``transition matrix'' $\Pi = (\pi_{ij})$, where $\pi_{ij}$'s are the 
242 transition probability rates from
243 the $i$-th mode to the $j$-th.  Such systems, referred to as ``jump
244 linear systems'', can be used to model linear systems subject to
245 failures.
246
247 We seek a state-feedback control law such that the resulting
248 closed-loop system is mean-square stable.  That is, for every initial
249 condition $x(0)$, the resulting trajectory of the closed-loop system
250 satisfies $\lim_{t \rightarrow \infty} \mbox{\bf E} \| x(t) \| ^2 = 0$.
251
252 The control law we look for is a mode-dependent linear state-feedback,
253 \ie\ it has the form $u(t) = K(r(t))x(t)$; $K(i)$'s are $n_u \times n$ matrices (the
254 unknowns of our control problem). 
255
256 It can be shown that this problem has a solution if and only if
257 there exist $n \times n$ matrices  $Q(1),\ldots,Q(N)$, and $n_u \times n$
258 matrices $Y(1),\ldots,Y(N)$, such that  
259 \begin{eqnarray*}
260 Q(i)- Q(i)^T&=& 0 , \\
261 \Tr Q(1)+ \ldots +\Tr Q(N) -1 &=& 0.
262 \end{eqnarray*}
263 and
264 \begin{eqnarray*}
265 \left[ \begin{array}{cc} Q(i) & Y(i)^T \\ Y(i) & I \end{array}\right] &>&0, \\
266 - \left[ A(i)Q(i)+Q(i)A(i)^{T} + B(i)Y(i)+Y(i)^TB(i)^{T}+
267 \dsp\sum_{j=1}^{N}\pi_{ji}Q(j) \right] &>& 0, \;\; i = 1,\ldots,N, \\
268 \end{eqnarray*}
269 If such matrices exist, a stabilizing
270 state-feedback is given by $K(i) = Y(i)Q(i)^{-1}$, $i=1,\ldots,N$.
271
272 In the above problem, the data matrices are $A(1),\ldots,A(N)$,
273 $B(1),\ldots,B(N)$ and the transition matrix $\Pi$.  The unknown 
274 matrices are $Q(i)$'s (which are symmetric $n \times n$ matrices) and
275 $Y(i)$'s (which are $n_u \times n$ matrices). In this case, both
276 the number of the data matrices and that of the unknown matrices
277 are a-priori unknown. 
278
279 The above problem is obviously a $\Sigma$ problem.  In this case,
280 we can let {\tt XLIST} be a list of two lists: one representing
281 the $Q$'s and the other, the $Y$'s.
282
283 The evaluation function required for invoking {\tt lmisolver} can be constructed as
284 follows:
285 \begin{verbatim}
286  function [LME,LMI,OBJ]=jump_sf_eval(XLIST)
287  [Q,Y]=XLIST(:)
288  N=size(A); [n,nu]=size(B(1))
289  LME=list(); LMI1=list(); LMI2=list()
290  tr=0
291  for i=1:N
292     tr=tr+trace(Q(i))
293     LME(i)=Q(i)-Q(i)'
294     LMI1(i)=[Q(i),Y(i)';Y(i),eye(nu,nu)]
295     SUM=zeros(n,n)
296     for j=1:N
297       SUM=SUM+PI(j,i)*Q(j)
298     end
299     LMI2(i)= A(i)*Q(i)+Q(i)*A(i)'+B(i)*Y(i)+Y(i)'*B(i)'+SUM
300  end
301  LMI=list(LMI1,LMI2)
302  LME(N+1)=tr-1
303  OBJ=[]
304 \end{verbatim}
305 Note that {\tt LMI} is also a list of lists containing the values
306 of the LMI matrices. This is just a matter of convenience.
307
308 Now, we can solve the problem in
309 Scilab as follows (assuming lists {\tt A} and {\tt B}, and  matrix
310 {\tt PI} have already been defined).
311
312 First we should initialize {\tt Q} and {\tt Y}. 
313 \begin{verbatim}
314 --> N=size(A);  [n,nu]=size(B(1)); Q_init=list(); Y_init=list();
315 --> for i=1:N, Q_init(i)=zeros(n,n);Y_init(i)=zeros(nu,n);end
316 \end{verbatim}
317 Then, we can use {\tt lmisolver} as follows:
318 \begin{verbatim}
319 --> XLIST0=list(Q_init,Y_init)
320 --> XLISTF=lmisolver(XLIST0,jump_sf_eval)
321 --> [Q,Y]=XLISTF(:);
322 \end{verbatim}
323
324 The above commands can be encapsulated in a solver function, say 
325 {\tt jump{\_}sf},
326 in which case we simply need to type:
327 \begin{verbatim}
328 --> [Q,Y]=jump_sf(A,B,PI)         
329 \end{verbatim}
330 to obtain the solution.
331
332
333 \subsubsection{Descriptor Lyapunov inequalities}
334 \label{ex3}
335 In the study of descriptor systems, it is sometimes 
336 necessary to find (or find out that it does not exist)
337 an $n\times n$ matrix $X$ satisfying
338 \begin{eqnarray*}
339 E^TX=X^TE&\geq&0\\
340 A^TX+X^TA+I&\leq&0
341 \end{eqnarray*}
342 where $E$ and $A$ are $n\times n$ matrices such that ${E,A}$ is a regular pencil.
343 In this problem, which clearly is a $\Sigma$ problem,
344 the LME functions play important role. The evaluation function
345 can be written as follows
346 \begin{verbatim}
347 function [LME,LMI,OBJ]=dscr_lyap_eval(XLIST)
348 X=XLIST(:)
349 LME=E'*X-X'*E
350 LMI=list(-A'*X-X'*A-eye(),E'*X)
351 OBJ=[]
352 \end{verbatim}
353 and the problem can be solved by (assuming $E$ and $A$ are
354 already defined)
355 \begin{verbatim}
356 --> XLIST0=list(zeros(A))
357 --> XLISTF=lmisolver(XLIST0,dscr_lyap_eval)
358 --> X=XLISTF(:)
359 \end{verbatim}
360
361 \subsubsection{Mixed $H_2/H_{\infty}$ Control}
362 Consider the linear system
363 \begin{eqnarray*}
364 \dot{x}&=&Ax+B_1w+B_2u\\
365 z_1&=&C_1x+D_{11}w+D_{12}u\\
366 z_2&=&C_2x+D_{22}u
367 \end{eqnarray*}
368 The mixed $H_2/H_{\infty}$ control problem consists in finding
369 a stabilizing feedback which yields $\|T_{z_1w}\|_{\infty}<\gamma$ and
370 minimizes $\|T_{z_2w}\|_2$ where $\|T_{z_1w}\|_{\infty}$ and
371 $\|T_{z_2w}\|_2$ denote respectively the closed-loop transfer
372 functions from $w$ to $z_1$ and $z_2$. In \cite{khargo}, it is
373 shown that the solution to this problem can be expressed as
374 $K=LX^{-1}$ where $X$ and $L$ are obtained from the problem of
375 minimizing Trace($Y$) subject to:
376 \[
377 X-X^T=0,\;\; Y-Y^T=0,
378 \]
379 and
380 \begin{eqnarray*}
381 -\left( \begin{array} {cc}
382 AX+B_2L+(AX+B_2L)^T+B_1B_1^T & XC_1^T+L^TD_{12}^T+B_1D_{11}^T \\
383 C_1X+D_{12}L+D_{11}B_1^T & -\gamma^2 I + D_{11}D_{11}^T
384 \end{array} \right) & > & 0 \\
385 \left( \begin{array} {cc}Y & C_2X+D_{22}L\\(C_2X+D_{22}L)^T&X
386 \end{array} \right) & > & 0
387 \end{eqnarray*}
388
389 To solve this problem with {\tt lmisolver}, we define the 
390 evaluation function:
391 \begin{verbatim}
392  function [LME,LMI,OBJ]=h2hinf_eval(XLIST)
393  [X,Y,L]=XLIST(:)
394  LME=list(X-X',Y-Y');
395  LMI=list(-[A*X+B2*L+(A*X+B2*L)'+B1*B1',X*C1'+L'*D12'+B1*D11';...
396                (X*C1'+L'*D12'+B1*D11')',-gamma^2*eye()+D11*D11'],...
397                                   [Y,C2*X+D22*L;(C2*X+D22*L)',X])
398  OBJ=trace(Y);
399 \end{verbatim}
400 and use it as follows:
401 \begin{verbatim}
402 --> X_init=zeros(A); Y_init=zeros(C2*C2'); L_init=zeros(B2')
403 --> XLIST0=list(X_init,Y_init,L_init);
404 --> XLISTF=lmisolver(XLIST0,h2hinf_eval);
405 --> [X,Y,L]=XLISTF(:)
406 \end{verbatim}
407
408
409 \subsubsection{Descriptor Riccati equations}
410 In Kalman filtering for descriptor system
411 \begin{eqnarray*}
412 Ex(k+1)& = & Ax(k) + u(k) \\
413 y(k+1)&=& Cx(k+1) + r(k)
414 \end{eqnarray*}
415 where $u$ and $r$ are zero-mean, white Gaussian noise sequences with 
416 covariance $Q$ and $R$ respectively, one needs to obtain the positive
417 solution to the descriptor Riccati equation (see \cite{ramine})
418 \[
419 P=-\left( \begin{array}{ccc} 0 & 0 & I \end{array} \right)
420 \left( \begin{array}{ccc} APA^T + Q & 0 & E \\
421                            0   & R & C \\
422                             E^T  & C^T & 0 \end{array} \right)^{-1}
423 \left( \begin{array}{c} 0 \\ 0 \\ I \end{array} \right) .
424 \]
425
426 It can be shown that this problem can be formulated as a $\Sigma$
427 problem as follows: maximize Trace(P) under constraints
428 \[
429 P-P^T=0
430 \]
431 and 
432 \[
433 \left( \begin{array}{ccc} APA^T + Q & 0 & EP \\
434                            0   & R & CP \\
435                           P^TE^T  & P^TC^T & P \end{array} \right)
436 \geq 0 .
437 \]
438
439 The evaluation function is:
440 \begin{verbatim}
441  function [LME,LMI,OBJ]=ric_dscr_eval(XLIST)
442  LME=P-P'
443  LMI=[A*P*A'+Q,zeros(A*C'),E*P;zeros(C*A'),R,C*P;P*E',P*C',P]
444  OBJ=-trace(P)
445 \end{verbatim}
446 which can be used as follows (asuming $E$, $A$, $C$, $Q$ and $R$ are
447 defined and have compatible sizes--note that $E$ and $A$ need not be
448 square).
449 \begin{verbatim}
450 --> P_init=zeros(A'*A)
451 --> P=lmisolver(XLIST0,ric_dscr_eval)
452 \end{verbatim}
453
454 \subsubsection{Linear programming with equality constraints}
455 \label{ex4}
456 Consider the following classical optimization problem
457 \[
458 \begin{array}{cc}
459 \mbox{minimize} & e^Tx \\
460 \mbox{subject to} & Ax + b \geq 0, \\
461 & Cx+d = 0.
462 \end{array}
463 \]
464 where $A$ and $C$ are matrices and $e$, $b$ and $d$ are vectors with
465 appropriate dimensions. Here the sign $\geq$ is to be understood elementwise.
466
467 This problem can be formulated in LMITOOL as follows:
468 \begin{verbatim}
469 function [LME,LMI,OBJ]=linprog_eval(XLIST)
470  [x]=XLIST(:)
471  [m,n]=size(A)
472  LME=C*x+d
473  LMI=list()
474  tmp=A*x+b 
475  for i=1:m
476     LMI(i)=tmp(i)
477  end
478  OBJ=e'*x
479 \end{verbatim}
480 and solved in Scilab by (assuming $A$, $C$, $e$, $b$ and $d$ and
481 an initial guess x0 exist in the environment):
482 \begin{verbatim}
483 --> x=lmisolver(x0,linprog_eval)
484 \end{verbatim}
485
486 \subsubsection{Sylvester Equation}
487 \label{ex5}
488 The problem of finding matrix $X$ satisfying
489 \[
490 AX+XB = C
491 \]
492 or 
493 \[
494 AXB = C
495 \]
496 where $A$ and $B$ are square matrices (of possibly different sizes) is
497 a well-known problem. We refer to the first equation as the continuous
498 Sylvester equation and the second, the discrete Sylvester equation.
499
500 These two problems can easily be formulated as $\Sigma$ problems as
501 follows:
502 \begin{verbatim}
503  function [LME,LMI,OBJ]=sylvester_eval(XLIST)
504  [X]=XLIST(:)
505  if flag=='c' then 
506    LME=A*X+X*B-C
507  else 
508    LME=A*X*B-C
509  end                                               
510  LMI=[]                                                          
511  OBJ=[]                                                          
512 \end{verbatim}
513 with a solver function such as:
514 \begin{verbatim}
515  function [X]=sylvester(A,B,C,flag)
516  [na,ma]=size(A);[nb,mb]=size(B);[nc,mc]=size(C);                                
517  if ma<>na|mb<>nb|nc<>na|mc<>nb then error("invalid dimensions");end           
518  XLISTF=lmisolver(zeros(nc,mc),sylvester_eval)
519  X=XLISTF(:)
520 \end{verbatim}
521 Then, to solve the problem, all we need to do is to (assuming $A$, $B$
522 and $C$ are defined)
523 \begin{verbatim}
524 --> X=sylvester(A,B,C,'c')
525 \end{verbatim}
526 for the continuous problem and 
527 \begin{verbatim}
528 --> X=sylvester(A,B,C,'d')
529 \end{verbatim}
530 for the discrete problem.
531
532
533 \newpage
534
535 \section{Function {\tt LMITOOL}}
536 \label{s_lmitool}
537 The purpose of \lmitool\ is to automate most of the steps required before
538 invoking {\tt lmisolver}.  In particular, it generates a *.sci
539 file including the solver function and the evaluation function or at
540 least their skeleton. The solver function is used to define the
541 initial guess and to modify optimization parameters (if needed).
542
543 {\tt lmitool} can be invoked with zero, one or three arguments.
544
545 \subsection{Non-interactive mode}
546 {\tt lmitool} can be invoked with three input arguments as follows:
547
548 \subsubsection{Syntax}
549 \begin{verbatim}
550 txt=lmitool(probname,varlist,datalist)
551 \end{verbatim}
552 where
553 \begin{itemize}
554 \item
555 {\tt probname}: a string containing the name of the problem,
556 \item
557 {\tt xlist}: a string containing the names of the unknown matrices
558 (separated by commas if there are more than one).
559 \item
560 {\tt dlist}: a string containing the names of  data matrices (separated
561 by commas if there are more than one). 
562 \item
563 {\tt txt}: a string providing information on what the user should do
564 next.
565 \end{itemize}
566
567 In this mode, {\tt lmitool} generates a file in the current
568 directory. The name of this file is obtained by adding ``.sci''
569 to the end of {\tt probname}. This file is the skeleton of
570 a solver function and the corresponding evaluation function.
571
572 \subsubsection{Example}\
573 Suppose we want to use {\tt lmitool} to solve the problem
574 presented in Section~\ref{ex1}. Invoking
575 \begin{verbatim}
576 -->txt=lmitool('sf_sat','Q,Y','A,B,umax')
577 \end{verbatim}
578 yields the output
579 \begin{verbatim}
580
581 --> txt  = 
582  
583 !    To solve your problem, you need to                         !
584 !                                                               !
585 !1- edit file /usr/home/DrScilab/sf_sat.sci                     !
586 !                                                               !
587 !2- load (and compile) your functions:                          !
588 !                                                               !
589 !   getf('/usr/home/DrScilab/sf_sat.sci','c')                   !
590 !                                                               !
591 !3- Define A,B,umax and call sf_sat function:                   !
592 !                                                               !
593 !  [Q,Y]=sf_sat(A,B,umax)                                       !
594 !                                                               !
595 !To check the result, use [LME,LMI,OBJ]=sf_sat_eval(list(Q,Y))  !
596
597 \end{verbatim}
598 and results in the creation of the file '/usr/home/curdir/sf{\_}sat.sci'
599 with the following content:
600 \begin{verbatim}
601   function [Q,Y]=sf_sat(A,B,umax)
602  // Generated by lmitool on Tue Feb 07 10:30:35 MET 1995
603    
604    Mbound = 1e3;
605    abstol = 1e-10;
606    nu = 10;
607    maxiters = 100;
608    reltol = 1e-10;
609    options=[Mbound,abstol,nu,maxiters,reltol];
610     
611  ///////////DEFINE INITIAL GUESS BELOW
612  Q_init=...
613  Y_init=...
614  /////////// 
615   
616  XLIST0=list(Q_init,Y_init)
617  XLIST=lmisolver(XLIST0,sf_sat_eval,options)
618  [Q,Y]=XLIST(:)
619   
620   
621   
622  /////////////////EVALUATION FUNCTION////////////////////////////
623   
624  function [LME,LMI,OBJ]=sf_sat_eval(XLIST)
625  [Q,Y]=XLIST(:)
626   
627  /////////////////DEFINE LME, LMI and OBJ BELOW
628  LME=...
629  LMI=...
630  OBJ=...
631 \end{verbatim}
632 It is easy to see how a small amount of editing can 
633 do the rest!
634
635
636 \subsection{Interactive mode}
637 {\tt lmitool} can be invoked with zero or one input argument as
638 follows:
639
640 \subsubsection{Syntax}
641 \begin{verbatim}
642 txt=lmitool()
643 txt=lmitool(file)
644 \end{verbatim}
645 where
646 \begin{itemize}
647 \item
648 {\tt file}: is a string giving the name of an existing ``.sci'' file
649 generated by {\tt lmitool}.
650 \end{itemize}
651 In this mode, {\tt lmitool} is fully interactive. Using a succession
652 of dialogue boxes, user can completely define his problem. This
653 mode is very easy to use and its operation completely self explanatory.
654 Invoking {\tt lmitool} with one argument allows the user to start off 
655 with an existing file. This mode is useful for modifying existing files 
656 or when the new problem is not too much different
657 from a problem already treated by {\tt lmitool}.
658
659 \subsubsection{Example}
660 Consider the following estimation problem
661 \[
662 y = H x + V w
663 \]
664 where $x$ is unknown to be estimated, $y$ is known, $w$ is a
665 unit-variance zero-mean Gaussian vector, and
666 \[
667 H \in \mbox{\bf Co}\left\{ H(1),...,H(N) \right\},\;\;\;
668 V \in \mbox{\bf Co}\left\{ V(1),...,V(N) \right\}
669 \]
670 where {\bf Co} denotes the convex hull and $H(i)$ and $V(i)$, $i=1,...,N,$
671 are given matrices.
672
673 The objective is to find $L$ such that the estimate
674 \[
675 \hat{x}=Ly
676 \]
677 is unbiased and the worst case estimation error variance
678 $\mbox{E}(\|x-\hat{x}\|^2)$ is minimized.
679
680 It can be shown that this problem can be formulated as a $\Sigma$
681 problem as follows: minimize $\gamma$ subject to
682 \begin{eqnarray*}
683 I-LH(i) &=& 0 ,\;\;\;i=1,...,N,\\
684 X(i)-X(i)^T&=& 0,\;\;\;i=1,...,N,
685 \end{eqnarray*}
686 and
687 \begin{eqnarray*}
688 \left( \begin{array} {cc} I & (L(i)V(i))^T\\
689                         L(i)V(i) & X(i) 
690          \end{array}  \right)  \geq 0,\;\;\;\;i=1,...,N, \\
691 \gamma-\mbox{Trace}(X(i)) \geq 0,\;\;\;\;i=1,...,N.
692 \end{eqnarray*}
693
694 To use {\tt lmitool} for this problem, we invoke it as follows:
695 \begin{verbatim}
696 --> lmitool()
697 \end{verbatim}
698 This results is an interactive session which is partly illustrated in
699 following figures.
700
701 \begin{figure}[hb]
702 \centerline{\psfig{figure=fig2.eps,height=6cm}}
703 \caption{This window must be edited to define problem name and the
704 name of variables used.}
705 \label{f1}
706 \end{figure}
707
708 \newpage
709
710 \begin{figure}[ht]
711 \centerline{\psfig{figure=fig3.eps,height=6cm}}
712 \caption{For the example at hand the result of the editing should
713 look something like this.}
714 \end{figure}
715
716 %\newpage
717
718 \begin{figure}[hb]
719 \centerline{\psfig{figure=fig4.eps,height=12cm}}
720 \caption{This is the skeleton of the solver function and the
721 evaluation function generated by {\lmitool} using the names
722 defined previously.}
723 \end{figure}
724
725
726 \begin{figure}[hbtp]
727 \centerline{\psfig{figure=fig8.eps,height=15cm}}
728 \caption{After editing, we obtain.}
729 \vskip.5cm
730 \centerline{\psfig{figure=fig6.eps,height=3cm}}
731 \caption{A file is proposed in which the solver and evaluation
732 functions are to be saved. You can modify it if you want.}
733 \end{figure}
734
735
736
737 \newpage
738
739 \appendix
740 \section{How {\tt lmisolver} works}
741 \label{s-lmisolver-works}
742 The function {\tt lmisolver} works essentially in four steps:
743 \begin{enumerate}
744 \item
745 {\em Initial set-up.}  The sizes and structure of the initial guess are
746 used to set up the problem, and in particular the size of the unknown
747 vector.
748 \item
749 {\em Elimination of equality constraints.}  Making repeated calls
750 to the evaluation function, {\tt lmisolver} generates 
751 a canonical representation of the form
752 \[
753  \begin{array}{ll} \mbox{minimize} & \tilde{c}^T z\\ 
754  \mbox{subject to} & \tilde{F}_0 + z_1\tilde{F}_1 + \cdots +
755 z_{\tilde{m}} \tilde{F}_{\tilde{m}} \geq 0, \;\; Az + b = 0,
756  \end{array}
757 \]
758 where $z$ contains the coefficients of all matrix variables. 
759 This step uses extensively  sparse matrices to speed up
760 the computation and reduce memory requirement.
761 \item
762 {\em Elimination of variables.} Then, {\tt lmisolver} 
763 eliminates the redundant variables.  The equality
764 constraints are eliminated by computing the null space $N$ of $A$ and
765 a solution $z_0$ (if any) of $Ax+b=0$.  At this stage, all solutions
766 of the equality constraints are parametrized by 
767 \[
768 z = Nx+z_0,
769 \]
770 where $x$ is a vector containing the independent variables.  The
771 computation of $N,z_0$ is done using sparse LU functions of Scilab.
772
773 Once the equality constraints are eliminated, the problem is
774 reformulated as
775 \[
776  \begin{array}{ll} \mbox{minimize} & c^T x\\
777  \mbox{subject to} & F_0 + x_1F_1 + \cdots + x_m F_m \geq 0,
778  \end{array}
779 \]
780 where $c$ is a vector, and $F_0,\ldots,F_m$ are symmetric matrices,
781 and $x$ contains the {\em independent\/} elements in the matrix
782 variables $X_1,\ldots,X_M$.  (If the $F_i$'s are dependent, a column
783 compression is performed.)
784 \item
785 {\em Optimization.}
786 Finally, {\tt lmisolver} makes a call to the function {\tt semidef}
787 (an interface to {\bf SP} \cite{sp}). This phase is itself divided into a
788 feasibility phase and a minimization phase (only if the linear
789 objective function is not empty).  The feasibility phase is avoided if
790 the initial guess is found to be feasible. 
791
792 The function {\tt semidef} is called with the optimization
793 parameters {\tt abstol}, {\tt nu}, {\tt maxiters}, {\tt reltol}.  The
794 parameter {\tt M} is set above the value
795 \begin{verbatim}
796 Mbnd*max(sum(abs([F0 ... Fm])))
797 \end{verbatim}
798 For details about the optimization phase, and the meaning of the above
799 optimization parameters see manual page for {\tt semidef}.
800 \end{enumerate}
801
802 \section{Other versions}
803 {\tt LMITOOL} is also available on Matlab. The Matlab version can be
804 obtained by anonymous ftp from {\tt ftp.ensta.fr} under
805 {\tt /pub/elghaoui/lmitool}.
806
807 \newpage
808
809 \begin{thebibliography}{99}
810 \bibitem{sp} Vandenberghe, L., and S. Boyd, ``Semidefinite
811 Programming,'' Internal Report, Stanford University, 1994 (submitted
812 to SIAM Review).
813
814 \bibitem{BEFB:94} Boyd, S., L. El Ghaoui, E. Feron, and V. Balakrishnan,
815 {\em Linear Matrix Inequalities in Systems and Control Theory}, SIAM
816 books, 1994.
817
818 \bibitem{khargo} Khargonekar, P. P., and M. A. Rotea, ``Mixed
819 $H_2/H_{\infty}$ Control: a Convex Optimization Approach,'' {\em IEEE
820 Trans Aut. Contr.}, 39 (1991), pp. 824-837.
821
822 \bibitem{ramine} Nikoukhah, R., Willsky, A. S., and B. C. Levy,
823 ``Kalman Filtering and Riccati Equations for Descriptor Systems,'' {\em IEEE
824 Trans Aut. Contr.}, 37 (1992), pp. 1325-1342.
825
826 \end{thebibliography}
827
828
829
830
831
832 \end{document}
833
834