数理解析研究所講究録
1004 巻 1997 年 24-39

24

LMI based control design:
Solutions to nonconvex problems
Tetsuya Iwasaki1 and Shinji Hara2

1

Introduction

In this article, a list of open computational problems arising in the field of control systems
engineering is presented. The problems are all considered to be very important in the analof control systems. They are, however, also known to be extremely difficult,and only partial solutions are available till date. Some of the existing approaches to these
problems are explained to motivate further development of “better” algorithms.
denote its transpose andWe use the following notation. For a matrix $A,$ $A’$ andis symmetric positive
its complex conjugate transpose, respectively. $A>0$ means thatwith areal symmetric matrices is denoted by . A subset ofdefinite. The set of.
andare the spectral radius and theblock diagonal structure is denoted byspectral norm (.the maximum singular value) of , respectively.

$\mathrm{y}\mathrm{s}\mathrm{i}\mathrm{s}/\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}$$A^{*}$$A$$n\cross n$$S_{n}$$S_{n}$$DS_{n}$$||A||$$\rho(A)$$A$

2Open problems in control engineering

In this section, we provide a list of some computational problems in the analysis and thesynthesis of control systems. All the problems are characterized by feasibility problems offinding a matrix satisfying certain matrix inequalities. Many control problems can be reduced
to one of these problems, and hence a complete solution to any of these problems can havea tremendous impact on the control theory. The significance of the problems can be found,for example, in [3, 9, 19].
analysis of linear timeThe first problem arises in the robust
invariant uncertain systems [10, 13, 14].
$\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}/\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}_{0}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{n}\mathrm{C}\mathrm{e}$Problem 1 Let

and$M\in \mathrm{R}^{n\cross m}$($\nabla$(I$\nabla\subseteq\oplus^{m\cross n}$

be given. Find$I)\ominus\geq 0$ ,

$M$

)

$<0$

$\in \mathrm{R}^{\mathrm{t}}n+m$$\forall\nabla\in\nabla$.

) $\cross 1n+m$ )such that(1)(2)

is given by the intersection ofThis problem is a convex problem; The set of feasiblesets,
the LMIs for a fixed
.
is
by
each
of
which
definedmany)
convex(uncountably$\ominus \mathrm{s}$$\nabla\in\nabla$

25

However, it is difficult to solve this problem since the infinitely many constraints are not easily
dealt with. In the context of control system analysis, the set
has a particular structure,
as illustrated by the following example.
$\nabla$Example 1 An important special case of Problem 1 is characterized by $[4, 17]$$\nabla:=\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\nabla_{1}\cdots\nabla_{m}) :\nabla_{i}\in\oplus^{n:\cross n}:, ||\nabla_{i}||\underline{<}1\}$.

If the number of the blocks inis three or less $(m\leq 3)$ , then a complete solution to
Problem 1 is known [14]; In this case, it can be shown that if there exists
and (2) then there exists another feasible of the following structure:$\nabla$$\ominus \mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}6r\mathrm{i}\mathrm{n}\mathrm{g}(1)$$\ominus$(3)$\ominus=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(-\theta_{1}I, \ldots-n1’\theta_{mn_{m}}I, \theta_{1}I_{n_{1}}, \ldots, \theta_{m}I_{n_{m}})$for some real scalars. Note that for a of this structure, condition (1) is automaticallysatisfied. Thus, Problem 1 reduces to the search for parameterssatisfying the LMI in(2), which can be solved efficiently. Unfortunately, this trick does not work for the case where$m>3$ ; a matrix $M$ can be constructed such that there is a feasible (unstructured)but nothe structure in (3) exists. Nevertheless, the use of the structured results ina sufficient condition for solvability of Problem 1, which is often. of.
Another instance of specificis given by$\theta_{i}>0$$\ominus$$\theta_{i}>0$$\ominus$$\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}\ominus \mathrm{o}\mathrm{f}$$\Theta$$\mathrm{P}^{\mathrm{r}\mathrm{a}\mathrm{C}\mathrm{t}\mathrm{i}_{\mathrm{C}}}\mathrm{a}1.\mathrm{i}.\mathrm{m}..\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}$$\nabla$$\nabla:=\{\sum_{=i1}^{m}\lambda i\nabla i:\lambda_{i}\geq 0,\sum_{i=1}^{m}\lambda_{i}=1\}$

where$\nabla_{i}$are given real matrices. Clearly,($\nabla_{i}$$I)\ominus\geq 0$ ,$\forall\dot{i}=1,$$\ldots,$

$m$

(4)

is necessary for (1). On the other hand, if$\ominus_{11}\leq 0$,$\ominus:=$(5)

then the vertex condition (4) becomes also sufficient for (1). This fact can readily be seen
once we notice that the inequality in (1) is equivalent to$\geq 0$by the Schur complement formula, and thus the set of
this inequality for a given
is convex. Hence, by searching for(4) and (5), a feasible $$ to Problem 1
may be found. Note, however, that this is only a sufficient condition due to (5) and thisapproach may fail even if Problem 1 admits a solution. See [1, 10, 13] for more details.
$\nabla \mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}6^{\Gamma \mathrm{i}}\mathrm{n}\mathrm{g}$$\ominus$$\ominus \mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}\mathrm{p}\mathrm{i}\mathrm{n}\mathrm{g}(2),$$\blacksquare$

The following four problems arise in the synthesis of control systems. The first one
probably covers the largest class of control problems among the four. The internal structureof each control problem has been lost by posing the problem in the general setting, and hence
the first problem is perhaps the most difficult.

26
Problem 2 Let real symmetric matrices
be given, where $i=1,$
and
,
and
$j=1,$
andare given positive integers. Find
andthat$\Omega_{0},$$\ldots$$n_{x}$$n_{y}$$F_{i},$$H_{ij}$$G_{\overline{J}}$$x\in \mathrm{I}\mathrm{R}^{n_{x}}$$n_{y}$$\ldots$$y\in \mathrm{I}\mathrm{R}^{n_{y}}$

, ;
such
$n_{x}$$\Omega(x, y):=\Omega_{0}+\sum_{i=1}^{n_{x}}xiFi+\sum_{=j1}^{n_{y}}y_{jj}G+\sum_{1i=j}^{n_{x}}\sum_{=1}^{n_{y}}xiyjH_{i}j>0$

Note that is a bilinear function of variables and . We call $\Omega(x, y)>0$ a bilinear matrix
inequality (BMI). The feasible set is, in general, not convex. In particular, the smallest
is not necessarily a concave function of and . A particular example
eigenvalue ofof Problem 2 is given below. See $[9, 18]$ for more instances of control problems that can be
reduced to Problem 2.
$\Omega$$x$$y$$\Omega(x, y)$

$x$

$y$

E.xample 2 Consider a linear time-invariant discrete-time system$x_{k+1}=AXk+Bu_{k}$ ,(6)$y_{k}--Cx_{k}$whereare, respectively, the state, the control input, andand$B$
the measured output; $A,$ and are real matrices of appropriate dimensions; is the timeindex. A fundamental problem in control design is the static output feedback stabilization
problem: Find a feedback gain (constant matrix) $K$ such that the control law$x_{k}\in \mathrm{I}\mathrm{R}^{n},$$u_{k}\in \mathrm{I}\mathrm{R}^{m}$$y_{k}\in \mathrm{I}\mathrm{R}^{p}$

$C$

$k$

(7)

$u_{k}=Ky_{k}$stabilizes the system. That is, find $K$ such that the state of the closed loop system3$x_{k+1}=(A+BKC)xk$

approaches zero as the time goes to infinity for any given initial statethat, V$\lim_{karrow\infty}x_{k}=0$$x_{0}$. It is well known$x_{0}$

holds if and only if$\rho(A+BKC)<1$

holds. Note that$\rho(A+BKC)<1$$\Leftrightarrow$$\exists D>0:||D^{-1}(A+BKC)D||<1$$\Leftrightarrow$$\exists P>0:P>(A+BKC)P(A+BKC)’$ .

Hence, using the Schur complement formula, thematrices $P\in S_{n}$ and $K$ such thatproblem is equival.ent to finding$>0$$\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{i},1\mathrm{i}\mathrm{z}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$

.

.

(8)

Clearly, this is a BMI in variables $P$ and $K$ , and hence is a special case of Problem 2.
3The difference equation for the closed loop system can be.. obtained by simply substituting (7) to (6).

$\blacksquare$

27

The next problem is characterized by LMI constraints plus a rank constraint. This problem also covers a large class of control problems $[9, 19]$ .

Problem 3 Let and be positive integers. Let an affine $fu$ nction
given. Find matrices $X\in DS_{n}$ and $Y\in DS_{n}$ such that
$n$

$r$

$\Phi(X, \mathrm{Y})>0$$\geq 0$ ,,rank $\leq:$\Phi$$S_{n}\cross S_{n}arrow S_{\ell}$

be

r$ .

The first two constraints in Problem 3 are LMIs in terms of the variables $X$ and $Y$ , whilethe
one is not convex in general. Thus, the rank constraint complicates the problem. Note$r\geq2n$ , then the rank condition isthat if
automatically satisfied and Problem 3 becomes an
LMI problem which can readily be solved. The following example reveals when this happens
and gives a physical intuition to the rank condition.
$1\mathrm{a}s\mathrm{t}$Example 3 As in Example 2, we consider the stabilization problem for the system given in(6). This time, the controller to be designed is a dynamical system of the form

$=$

where
is the controller state. The number is called the order of the controller. It
can be shown $[5, 11]$ that there exists a dynamic stabilizing controller of order if and only
if there exist matrices $X\in S_{n}$ andsuch that$\hat{x}_{k}\in 1\mathrm{R}^{\hat{n}}$$\hat{n}$$\hat{n}$$\mathrm{Y}\in S_{n}$$B(X-AXA’)B^{j}>0$$C(Y-A’\mathrm{Y}A)c’>0$$\geq 0$ ,’rank $\leq n+\hat{n}$where and are given matrices defined by the system matrices $B$ and in (6), respectively.
Clearly, the problem of finding such matrices $X$ and is a special case of Problem 3. Notethat $r:=n+\hat{n}$ is greater than or equal to $2n$ when
, i.e., the controller order isgreater than or equal to the order of the system to be stabilized. Hence, if we allow for
the controller order to be ffee in the design, then the stabilization problem becomes an LMI
problem. In certain control applications, however, it is desired or required that the controller
order be small, in order to allow
implementations. This fact shows the significanceof Problem 3.
$B$

$C$

$C$

$\mathrm{Y}$$\hat{n}\geq n$$\mathrm{p}\mathrm{r}\mathrm{a}\mathrm{c}\sim \mathrm{t}\mathrm{i}_{\mathrm{C}}\mathrm{a}1$$\blacksquare$

It can be shown that if $r=n$ then the last two conditions in Problem 3 are equivalent to. The following problem is concerned with this case.

$X=Y^{arrow 1}>0$

Problem 4 Let and be a positive integer. Let an affine function
given. Find matrices $X\in DS_{n}$ and $Y\in DS_{n}$ such that$n$$\ell$$\Phi(X, \mathrm{Y})>0$,$Y>0$ ,

$X>0$ ,

$X\mathrm{Y}=I$$\Phi$:$S_{n}\cross S_{n}arrow S_{\ell}$be.

As noted above, this is a special case of Problem 3 with $r=n$ . In fact, any control
problem known to be reducible to Problem 3 can also be cast as a special case of Problem 4[9] with a different definition for the function
and an increased size of matrices $X$ and
Y. In this sense, Problems 3 and 4 are equivalent. However, algorithms that address these
problems can be quite different due to the difference in the nature of the constraints.
$\Phi$

28

Example 4 Let us consider the static output feedback stabilization problem defined in Example 2. As shown there, the problem has a solution if and only if there exist matrices$P=P’$ and $K$ such that the BMI in (8) holds. It can be shown further [15] that the BMI
admits a solution pair $(P,K)$ if and only if there exist $X\in S_{n}$ and $Y\in S_{n}$ such that

$B(X-AXA’)B’>0$$C(Y-A’YA)C’>0$ ’$X>0$ ,

$Y>0$ ,

$XY=I$

holds, where and are given matrices defined by the system matrices in (6). Note thatthe parameter $K$ has been eliminated. This problem is a special case of Problem 4. The
condition given above is precisely the necessary and sufficient condition for the existence of$K$ satisfying (8) for a fixed $P$ , where $X$ and $Y$ correspond to $P$ and, respectively.
$B$

$C$

$P^{-1}$$\blacksquare$

The last problem presented below is characterized by LMI constraints plus a spectralthatradius condition, and is very similar to Problem 4. However, there is abecomes significant when developing computational algorithms for these problems; namely,in the following problem, the feasible set can have a nonempty interior, while in Problem 4,
there is no interior point in the feasible set due to the constraint $X\mathrm{Y}=I$ .
$\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}\dot{\mathrm{e}}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}$Problem 5 Let and be a positive integer. Let an affine function
given. Find matrices $L\in DS_{n}$ and $R\in DS_{n}$ such that$\ell$$n$$\Psi(L, R)>0$ ,$L>0$ ,

$R>0$ ,$\rho(LR)\leq \mathrm{I}$$\Psi$:$S_{n}\cross S_{n}arrow S_{\ell}$be.

The troublesome factor of this problem is the last constraint given by the spectral radiusinequality. This constraint is not convex, while all the other constraints are LMIs (and hence
convex). In the context of control synthesis, Problems 4 and 5 are (different but) equivalent
problem. This point is clarified in the following example.
formulations of the same
Related results can be found in [16].
$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\dot{\mathrm{r}}\mathrm{o}\mathrm{l}$Example 5 Recall from Example 2 that the static output feedback stabilization problem is
equivalent to finding matrices $P\in S_{n}$ and $K$ such that

$P>(A+BKC)P(A+BKC)’$ .

$P>0$ ,

It can readily be shown that, given $K$ , there exists $P\in S_{n}$ satisfying this condition if andonly if there exist $R\in S_{n}$ and $L\in S_{n}$ such that
$R^{-1}\geq L>0$

$L>(A+BKC)R^{-1}(A+BKC)’$ .

,correspond to the left and the right “scaling matrices” as in$||L^{-1/2}(A+BKC)R^{-1}/2||<1$ . Eliminating the parmeter $K$ from the second condition as
explained in Example 4, we have

Note that matrices

$L$

and

$R$

$B(L-AR^{-}1A’)B’>0$ ,$C(R-A\prime L^{-1}A)C’>0$

where and are computed from and , respectively. Noting that, for $L>0$ and $R>0$ ,condition $R^{-1}\geq L$ is equivalent to $\rho(LR)\leq 1$ , and using the Schur complement formula, theproblem reduces to: Find $L\in S_{n}$ and $R\in S_{n}$ such that
$B$

$C$

$B$

$C$

$>0$ $>0$,

This is a special case of Problem 5.

,$\rho(LR)\leq 1$.
$\blacksquare$29

3Computational Methods

In this section, we present several computational methods that address the problems listed in
the previous section. As noted before, none of these problems have been solved completely.
Our objective here is to give a tutorial overview of currently available computational techniques; The three methods given below often find solutions to Problems 3 and 4 without aguarantee for global convergence to the solution set.

3.1

Coordinate Descent Methods

This section presents an approach to Problem 4. The results given below are essentially from[12]. One way to address Problem 4 is to consider the following optimization problem:(9)$\lambda_{\mathrm{o}\mathrm{p}\mathrm{t}}:=\min_{C1X,\mathrm{Y})\in}\lambda_{\max}(x\mathrm{Y})$$C:=\{(X, Y)\in DS_{n}\cross DS_{n} :\Phi(X, \mathrm{Y})>0, \geq 0\}$In order to motivate this formulation, note that, for $X>0$ and$\geq 0$$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$.X$\mathrm{Y}>0$,$\geq Y^{-1}$$Y^{1/2}XY^{1}/2\geq I$$\lambda_{i}(Y^{1//}2xY^{1}2)\geq 1$$\lambda_{i}(XY)\geq 1$.

Hence, the set is nonempty whenever Problem 4 has a solution. Moreover, Problem 4 admits
a solution iff
and the optimal value is attained at a point in . Unfortunately, theminimization problem is not convex since the objective function $\lambda_{\max}(XY)$ is not, although
the feasible set is convex.
An approach to this nonconvex problem is to utilize the fact that, for each fixed $Y>0$ ,the function $\phi(X):=\lambda_{\max}(XY)$ is convex. Thus, we can$(XY)$.
over one variable while fixing the other by convex programming:
$C$

$C$

$\lambda_{\mathrm{o}\mathrm{p}\mathrm{t}}=1$$C$$\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{y}$$.\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\lambda_{\max},$

Coordinate Descent Algorithm
initialization: $k=1$ ,$X_{k}:=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}${$(X_{0}, Y_{1})\in C$$\lambda_{\max}(XY_{k})$: (X,$Y_{\mathrm{k}})\in C$}$\mathrm{Y}_{k+1}:=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}\{\lambda_{\max}(xkY):(X_{k}, Y)\in C\}$Of course, this .lgorithm may not give a globally optimal solution to the above minimization
problem.
It is easily shown that the optimal value of each minimization problem is not attained,i.e.
andlie on the boundary of the open feasible domain . Hence, the set must
be replaced by a closed set inner approximation using a small scalar
to guarantee$(X_{k},Y_{k})\in C$ for all. The initialization $(X_{0}, Y1)\in C$ guarantees that the feasible set of each$\mathrm{a}$$X_{k}$$C$$\mathrm{Y}_{k+1}$$C$$\epsilon>0$

$k$

30

minimization problem is nonempty at every iteration. Moreover, it can readily be shown thatthe value of the objective function is monotonically nonincreasing at every step:$\lambda_{\max}(X_{k}Y_{k})\geq\lambda(\max k+1Y_{k+1}x)$.

is bounded below by one, the sequence is guaranteed to converge.
Sinceslow convergence andThis simple algorithm works well for some cases but is suffereda huge gap between the obtained solution andfor other cases. The following algorithm isa version of coordinate descent algorithms modified by replacing the minimization problemsby the computation of the analytic center. Our numerical experience suggests that thisthealgorithm tend to give a better solution with smaller amount of computations
stmdard coordinate descent algorithm given above.
$\lambda_{\max}(X_{k}Y_{k})$$\mathrm{h}\mathrm{o}\mathrm{m}$$\lambda_{\mathrm{o}\mathrm{p}\mathrm{t}}$th.anSuccessive Centering Algorithm (SCA)

1. Choose $\theta\in(0,1)$
2. Initialize $k=1$ , and, with$(\hat{X},\hat{\mathrm{Y}})\in C$,$Y_{1}:=\hat{Y}$,3. Compute the analytic center$X_{k}$$\beta_{1}>\lambda(\max\hat{X}\hat{Y})$and update$\alpha_{k}$$X_{k}:=\mathrm{a}\mathrm{c}\{I<\mathrm{Y}_{k}^{1/2}x\mathrm{Y}^{1/2}k<\beta_{k}I, (X,Y_{k})\in C\}$$\alpha_{k}:=(1-\theta)\lambda_{\max}(X_{k}\mathrm{Y}k)+\theta\beta k$

4. Compute the analytic center$Y_{k}$

and update$\beta_{k}$$\mathrm{Y}_{k+1}:=\mathrm{a}\mathrm{c}\{I<x_{k}^{1/_{YX^{1}}/2}2k<\alpha_{k}I, (X_{k}, Y)\in C\}$$\beta_{k}:=(1-\theta)\lambda(\max xkYk+1)+\theta\alpha_{k}$, stop.
5. If $(X_{k},x^{-1}k)\in C$ or
Otherwise let $k\vdash k+1$ and go to Step 3.
$(Y_{k+1}^{-1}, Y_{k+1})\in C$

Note that ac denotes the analytic center and is defined by (e.g. [2])$\mathrm{a}\mathrm{c}\{(\mathrm{J}(X)>0\}:=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}\{\log\det l\mathrm{J}(X)-1 :\mathrm{U}(X)>0\}$where $\mathrm{U}(X)>0$ is an LMI.
In this algorithm, an initialization parametercan be found by solving an LMI
problem, or it can be determined that is empty, in which case, Problem 4 has no solution.
If is nonempty, then the SCA is well-defined, i.e. each set defined by the argument of. at Steps 3 and 4 is nonempty and bounded, and hence the analytic centers exist at any
iteration $k\geq 1$ . Moreover, upper boundson
are strictly decreasing
and bounded
one:$(\hat{X},\hat{Y})\in C$

$C$

$C$

$\mathrm{a}\mathrm{c}$$\alpha_{k}$a.nd$\beta_{k}$$\lambda_{\max}(X_{k}\check{Y}_{k})$$\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{W}..\mathrm{b}\mathrm{y}$$\beta_{k}>\alpha_{k}>\beta_{k}+1>\mathrm{I}$and hence the convergence is guaranteed.

,$\forall k\geq 1$

31

Example 6 Consider$\min_{(x,y)\in c}xy$$C:=\{(X, y) :y\geq 5(1-x)+1, y\geq 0.5(1-x)+1\}$

It can be checked that the global minimum value is one and is attained at $x=y=1$ .
Applying the SCA, the following results are obtained.
Initial conditions: $y_{0}=2,$$\beta_{0}=5,$$\theta=0.2$

Final values: $(x, y)=(1.0230, 0.9886)$ , $xy=1.0112$
The
in Fig. 1.

$\mathrm{s}\mathrm{e}\dot{\mathrm{q}}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{C}\mathrm{e}\mathrm{S}xk$nd$y_{k}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e}\dot{\mathrm{d}}$by the algorithm are’$\mathrm{P}^{1_{\mathrm{o}\mathrm{t}\mathrm{t}}\mathrm{e}\mathrm{d}}$on$\mathrm{t}\dot{\mathrm{h}}\mathrm{e}$x-y plane as shown

Figure 1. Behavior of the SCA on the x-y plane

In Fig. 1, the two straight lines intersecting at $(x, y)=(1,1)$ are the boundary ofwhich is the region above the lines. The curves are the hyperbolas
and $xy=\beta_{k}$ for$k=1,2,$For a given , the analytic centeris determined to be the -coordinate of the
middle point of the segment defined by the intersection of the horizontal line $y=y_{k}$ , the set, and the region between $xy=1$ and $xy=\beta_{k}$ .
Note that if we appl.y the coordinate descent algorithm, then the algorithm ops in one
step, resulting in the final values $(x, y)=(0.8,2)$ , with $xy=1.6$ .
$C$$xy=\alpha_{k}$$\ldots$$y_{k}$$x$$x_{k}$$C$s.t$\blacksquare$

A novel aspect of the SCA is that we do not require $\lambda_{\max}(X_{k}Y_{k})=1$ to have a solution
to Problem 4. Intuitively, the algorithm tries to make(or equivalently,
andand ) closer to each other while maintaining
to be located “deep inside” the set. Thus,andare forced to move into . This point is illustrated by thefollowing examples.
$X_{k}$$(X_{k},Y_{k})$$Y_{k}$$C$$(X_{k}, X_{k}^{-1})$$(Y_{k}^{-1}, Y_{k})$$C$$\mathrm{Y}_{k}^{-1}$$X_{k}^{-1}$32

Example 7 Consider Problem 4 with$\Phi(X, Y)$

$:=$

$A$

$:=$ ,,$\Phi_{x}(X).\cdot.=-\beta(Ax+XA)\Phi_{y}(Y)\cdot=-C(YA+A’ Y’)c^{B’}$’$B:=(1$0) , $C:=(0\cdot 1)$ .

The choice ofcorresponds to the problem of static output feedback stabilization
andfor continuous-time systems as opposed to the discrete-time setup given in Examples 2 and4. The choice of $(A, B, C)$ above corresponds to the fact that the underlying system is the
double integrator. It is known that there is no static output feedback stabilizing gain
for this system, and thus Problem 4 is infeasible.
$\Phi_{x}$$\Phi_{y}$$\ddot{y}=u$$1l$ el$\overline{\mathrm{d}}$IIOII$\perp T$

uIIlDGr$\kappa$

Figure 2. Behavior of the SCA (static output feedback)
The SCA is applied to this problem. The parameter is chosen to be $\theta=0.2$ . See [12]for details of the choice of an initial feasible point.
Fig. 2 shows the behavior of the SCA applied to this problem, whereandareupper bounds on. To visualize the convergence behavior,is plotted insteadof ; in this way, the distance between the two curves corresponding toandcanbe considered as a measure for the “distance” between
and. Similarly, the curvesindicate the “distance” between
and , andand , respectively. For instance,
if and only.
Interestingly, the sequence
approaches (or equivalently,) even though
Problem 4 is infeasible. What’s happening here is thatapproaches , but neverto) , that is,reaches (for all . After 33 iterations, we have$\theta$$\alpha_{k}$$\lambda_{\max}(x_{k}Y_{k})$$\beta_{k}^{-1}$$\beta_{k}$$\beta_{k}^{-1}$$\alpha_{k}$$X_{k}$$Y_{k}^{-1}$$(Y_{k}^{-1}, Yk)$$-\Phi_{x}(Y_{k}^{-1})\mathrm{a}\mathrm{n}\mathrm{d}-\Phi_{y}(X_{k}^{-1})$$C$$(Y_{k}^{-1}, Y_{k})\in C$$\alpha_{k}arrow 1$$(Y_{k}^{-1}, Y_{k})$

$X=$
$C$

$\Phi_{x}(Y_{k}^{-1})\leq 0$,$(X_{k}, X_{k}^{-1})$$C$$\mathrm{i}\mathrm{f}-\Phi_{x}(Y-1)k<0$$I$$X_{k}Y_{k}$$\mathrm{b}\mathrm{e}\mathrm{I}\mathrm{o}\mathrm{n}\mathrm{g}_{\mathrm{S}}$$\beta_{k}$

$C$

$k$

$\Phi_{x}(X)=9.00\cross 10^{-5}$,$\Phi_{y}(x^{-}1)=-1.23\cross 10^{-5}$

,

33

$Y=$

,

$\Phi_{x}(Y^{-1})=-7.54\cross 10-5$$\lambda(XY)=1.00008$ ,,$\Phi_{y}(Y)=1.03\mathrm{X}10^{-}5$

1.00002.

Thus,
holds but neither (X,) nor $(Y^{-1}, Y)$ belongs toexample shows that
does not imply that Problem 4 is feasible.
$X\cong Y^{-1}$$X^{-1}$$C$. Note that, this$\alpha_{k}arrow 1$$\blacksquare$

Example 8 Consider the same problem as the one treated in Example 7 with different
problem data:
$A$

$:=,$

$B:=(.$ 1

$00$

),

$C$

$:=(0$

1$0)$.

This problem corresponds to the stabilization of the double integrator system mentioned in
Example 7 with a dynamic controller of order one (as opposed to the static output feedback
controller in Example 7). In this case, it isthat a stabilizing controller exists, i.e.,
Problem 4 is feasible.
Again, the SCA is applied to the problem. The parameter is set to $\theta=0.2$ as before.
Fig. 3 shows the behavior of the algorithm. To design a stabilizing controller, four iterations
suffice since $(X_{k}, X_{k}^{-1})\in C$ and $(Y_{k}^{-1}, Y_{k})\in C$ at $k=4$ . When the algorithm continues torun,
andmove “deep inside’.’. the set . This is a typical. theSCA. After 17 iterations, we have.nown$\mathrm{k}$$\theta$$(X_{k}, X_{k}^{-1})$$(Y_{k}^{-1}, Y_{k})$$C$$\mathrm{b}.\mathrm{e}\mathrm{h}\mathrm{a}\mathrm{v}\mathrm{i}_{\mathrm{o}\mathrm{r}}\mathrm{o}.\mathrm{f}$$Y^{-1}\cong X=$,$\lambda(XY)=\{$

1.000048
1.000048
1.000048

Thus we obtained a globaly optimal solution to problem. (9) within the optimality.
$|\lambda(XY)-\lambda_{\mathrm{o}_{\mathrm{P}^{\mathrm{t}}}}|\leq 5\cross 10^{-5}$

Figure 3. Behavior of the SCA (1 $st$ order dynamic output feedback)tole.rance$\blacksquare$,

34

Linearization methods

3.2

The computational method presented in this section addresses Problem 3 and is due to [6].
Here, we will try to minimize the bound on the rank subject to the constraints in Problem 3.
The idea is based on the following observation: The rank condition in Problem 3 is satisfied
by pushing $X$ and to the “boundary” of the second inequality in Problem 3. A natural
way to do this is to consider the following minimization problem:$r$$\mathrm{Y}$$\emptyset \mathrm{o}\mathrm{p}\mathrm{t}:=\min_{C\langle x,Y)\in}\emptyset(x, \mathrm{Y})$$C:=\{(X, \mathrm{Y}) :where$\phi:Carrow 1\mathrm{R}$is a function(a) $\phi(X, Y, )\geq\phi_{m*n},$$\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}6^{\mathrm{i}\mathrm{n}}r\mathrm{g}$\Phi(X, Y)>0, \underline{>}0\}$

the properties:$\forall(X,Y)\in C$(b) $\phi(X,Y)=\phi_{\min}\Leftrightarrow XY=I$(c)$\phi$(d)$\phi$

is differentiable on$C$is quasi-concave on$C$’
The function is called the “attracting
due to properties (a) and (b). Recall from
Section 3.1 that the second inequality in Problem 3 holds if and only if all the eigenvalues of$XY$ is greater than or equal to one. If $X$ and $Y$ are “right” on the, thenfor all , in which case we have $XY=I$ . A choice for is given by$\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\grave{\mathrm{i}}_{\mathrm{o}\mathrm{n}’}$$\phi$$\lambda_{i}(\dot{X}\mathrm{Y})=1$$\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\dot{\mathrm{a}}\mathrm{r}\mathrm{y}$$\dot{i}$$\phi$$\phi(X, \mathrm{Y})=2\mathrm{t}\mathrm{r}(XY)^{\mathrm{i}/2}$.

This function satisfies all the properties listed above. Then, the following algorithm can beapplied to find a local solution to the above minimization problem.

Linearization Algorithm (LA)
1. Initialize $k=0$ and $(X_{0}, Y_{0})\in C$ .

2. Let$V_{k}:= \frac{\partial\phi}{\partial X}(X_{k},Y_{k})$,$W_{k}:= \frac{\partial\phi}{\partial Y}(X_{k}, Y_{k})$3. Solve the LMI problem:$(xk+1,\mathrm{Y}k+1):=(\mathrm{x}^{\mathrm{r}_{\mathrm{F}\in^{\mathrm{n}_{C}}}}\mathrm{a},\varphi \mathrm{i}\mathrm{t}\mathrm{r}(V_{k}x+W_{k}Y)$

Note that property (c) is necessary to compute the gradientsandat step 2. In
some cases, explicit formulas for the gradients exist. For instance, the gradients of $\phi(X, Y)=$are given by$V_{k}$$W_{k}$$2\mathrm{t}\mathrm{r}(X\mathrm{Y})^{1/2}$$V=H^{-1}(HYH)1/2H-1$$W=V^{-1}$$H:=X^{1/2}$.

It can be shown that if satisfies properties (a), (b) and (d), then the sequenceis bounded below and decreasing. Thus, the LA converges. The idea for the proof is that a
concave function is bounded above by its linear approximation.
$\phi$$\phi(X_{k}, Y_{k})$35

Example 9 Consider Problem 3 with$\Phi(X, Y)$

$A$

$:=$

,

$\Phi_{x}(x_{Y}\Phi_{y}().\cdot=):=-B(Ax+XA’+\mathrm{o}-c(YA+A’ Y+0.\cdot 44X)B’Y)c$’$:=,$ $:=,$ $:=$
$B$

$C$

problem corresponds to the design of a controller that yields the closed loop poles in
the region $\{\lambda\in\oplus:Re(\lambda)<-0.2\}$ whereis the real part of the complex number.
This pole constraint imposes a requirement on the rate of convergence of the initial state
response. The problem data $(A, B, C)$ has a physical significance; the underlying system tobe controlled is a mechanical system consisting of two masses connected by a spring, placedon a frictionless horizontal surface [20]. It is known that the system is stabilizable via 2ndorder controller but no 1 $st$ order controller stabilizes the system. Therefore, we see that
Problem 3 has no solution if $r\leq 5(=4+1)$ .
Applying the LA to this problem with a particular choice of given above, we obtained
a solution. The behavior of the LA is plotted in Fig. 4.
$\tilde{\mathrm{T}}\mathrm{h}\mathrm{i}\mathrm{s}$$Re(\cdot)$$\phi$

Figure 4. Behavior of the LA
After 5 iterations, the algorithm converged and we obtained the following result:

$X=$

36

$Y=$
$\lambda(XY)=1.0000$, 1.0000, 8.9284, 21.7285

Note that the rank in Problem 3 is reduced from the full rank by 2 (the number of theeigenvalues of $XY$ that are equal to one). Thus we have found a solution to Problem 3 with
$r=6$ . Since there is no solution for $r\leq 5$ , we conclude that the global minimum rank isattained.

$\blacksquare$

Projection Method

3.3

Problem 3 again. The projection method presented here is from [7] and its
Weextensions.
such thatIn this method, Problem 3 is formulated as follows: Find$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}’.\mathrm{d}\mathrm{e}\mathrm{r}$$Z_{\mathrm{f}\mathrm{e}\mathrm{a}\S}$$Z_{\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}}\in C\cap \mathcal{R}$

where$C:=\{Z= :\Phi(X,\mathrm{Y})\geq 0, Z\geq 0, X\in DS_{n}, Y\in DS_{n}\}$$\prime \mathcal{R}:=\{Z:\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(Z)\leq r\}$Here, is a closed convex set and 72 is closed but not convex. The closedness of these sets is
crucial for the projection method. Note that in Problem 3, the inequality for $\Phi(X, Y)$ is strict,while it is weakened to be $\Phi(X, Y)\geq 0$ in the above formulation. If this is not acceptable,
to define a closed inner-approximation for theone may use a fixed small parameterfeasible domain of Problem 3.
to a point in the intersection of the two sets
The following algorithm locally
and .
$C$

$\epsilon>0$$C$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}\mathrm{e}\mathrm{r}.\mathrm{g}\mathrm{e}\mathrm{s}$$\prime \mathcal{R}$

Alternating Projection Algorithm (APA)
1. Initialize $k=0$ and$Z_{0}$.

2. $\hat{Z}_{k1}+:=PCzk$3.

$Z_{k+1}:=P_{\mathcal{R}},\hat{z}_{k+1}$

where$P_{S}$

is the projection onto the set $S$ ( $=C$ or $R$ ):$P_{S}z_{0}:=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}\{||Z-Z\mathrm{o}||F:Z\in S\}$

(10)

with
being the Frobenius norm.
by alternatingly projecting the current point inThis algorithm generates a sequence
one set onto the other set (see Fig. 5 for the conceptual sketch). Note that the algorithm
does not require any property for the initial point; it can be chosen arbitrarily.
$||\cdot||_{F}$$Z_{k}$

37$\mu_{1}^{\iota}\mathrm{g}\mathrm{u}\mathrm{r}\mathrm{e}5$. Alternating projection algorithm

If the set $S$ is convex, then the projectionis unique, i.e. the minimization problem
in (10) has a unique minimizer. In fact, if both and $R$ were convex, then the APA isguaranteed to find awhenever $C\cap R$ is nonempty, regardless of the initial point . If
is empty, then the algorithm generates, insteady state, a sequence that alternates
between the two points giving the minimum distance of and 72. Thus, under the convexity
assumption, the APA is globally convergent. However, the set $R$ is not convex and the APA
is only locally convergent when applied to Problem 3.
The projection
can be computed by solving an LMI problem. A projection
can be obtained by replacing the $2n-r$ small singular values ofby zeros [8]. This procedure gives a minimizer to problem (10) with $S$ andreplaced by and, respectively.
Note that such minimizers may not be unique.
$P_{S}Z_{0}$$C$$Z_{\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}}$$Z_{0}$$C\cap \mathcal{R}$$\mathrm{t}\mathrm{h}\mathrm{e}\sim$$C$$P_{C}Z_{k}$$P_{\mathcal{R}},\hat{Z}_{k+1}$$\hat{Z}_{k+1}$$Z_{0}$$\prime \mathcal{R}$$\hat{Z}_{k+1}$

Example 10 We consider the problem treated in Example 9. Fig. 6 shows the behavior of
the APA, whereandare the smallest two eigenvalues of $XY$ . The curves
are plotted using the data
. Note that the smallest eigenvalue
is always one.
This is because the projection
always lies on the boundary of when(in particular the “boundary” of $Z\geq 0$ ). For this particular problem, the APA took moreiterations than the LA. It is possible to (heuristically) improve the rate of convergence bytaking the directional information into account [19].
$\lambda_{1}(XY)$$\lambda_{2}(XY)$$\hat{Z}_{k}\in C$$P_{C}Z_{k}$$C$$\lambda_{1}(XY)$$C$$Z_{k}\not\in$38

Figure 6. Behavior of the APA
After 130 iterations, the APA converged to

.

$X=$
$Y=$
..
$\lambda(XY)=0.9990$, 1.0024, 13.7234, 25.6750.

Thus, we have found a feasible solution to Problem 3 with $r=6$ which is the minimum.
. .
attainable rank.
$\cdot$$\cdot$$=$$\blacksquare$

References[1] T. Asai, S. Hara, and T. Iwasaki. LFT scaling: A unified approach to robust control.
The 18th SICE Symposium on Dynamical System Theory, 1995.
[2] S. Boyd and L. El Ghaoui. Method of centers for minimizing generalized eigenvalues.
Linear Algebra and Applications, 188,189:63-111, 1993.

[3] S. P. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in
System and Control Theory. SIAM Studies in Applied Mathematics, 1994.

39[4] J. C. Doyle. Analysis of feedback systems with structured uncertainties. IEE Proc., 129,
Part $\mathrm{D}(6):242-250$ , November 1982.
[5] P. Gahinet and P. Apkarian. A linear matrix inequality approach to
J. Robust Nonlin. Contr., 4:421-448, 1994.

$H_{\infty}$

control. Int.

[6] L. El Ghaoui, F. Oustry, and M. AitRami. An LMI-based linearization algorithm forstatic output-feedback and Teiated problems. IEEE Trans. Auto. Contr., 1997. (Toappear).
[7] K. M. Grigoriadis and R. E. Skelton. Alternating.
ance control design. Proc. Allerton Conf., 1992.

-$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{X}$projection methods for covari-[8] K. M. Grigoriadis and R. E. Skelton. Low order control design for LMI problems using
alternating projection methods. Proc. Allerton Conf., October 1993.
[9] T. Iwasaki. A unified matrix inequality approach to linear control design. Ph.D Disser, Purdue University, West Lafayette, IN, December 1993.
$tai\dot{i}on$[10] T. Iwasaki and S. Hara. Well-posedness of feedback systems: a fundamental conceptbehind robust stability tests. Proc. SICE Sympo. Contr. Theory, Chiba, Japan, 1996.
[11] T. Iwasaki and R. E. Skelton. Parametrization of all stabilizing controllers via quadratic
Lyapunov functions. J. Optimiz. Theory Appl., 85:291-307, 1995.
[12] T. Iwasaki and R. E. Skelton. The-centering algorithm for the dual LMI problem:a new approach to fixed order control design. Int. J. Contr., $62(6):1257^{-}1272$ , 1995.
$\mathrm{X}\mathrm{Y}$[13] A. Megretski and A. Rantzer. System analysis via integral
Trans. Auto. Contr., 1995. (To appear).

$\mathrm{q}.\mathrm{u}$adratic

co.nstraints. IEEE

[14] A. Packard and J. Doyle. The complex structured singular value. Automatica, $29(1):71-$
109, 1993.
kard, K. Zhou, P. Pandey, J. Leonhardson, and G. Balas. Optimal, constant[15] A.
similarity scaling for full-information and state-feedback control problem, s. rSys. Contr.
Lett., 19:271-280, 1992.
$\mathrm{P}\mathrm{a}\dot{\mathrm{c}}$$\mathrm{I}/\mathrm{O}$[16] M. A. Rotea and T. Iwasaki. An alternative to the D-K iteration? Proc. American
Contr. Conf., pages 53-57, 1994.

[17] M. G. Safonov. Stability margins of diagonally perturbed multivariable feedback systems.
, November 1982.
IEE Proc., 129, Part$\mathrm{D}(6):251^{-256}$..

[18] M. G. Safonov, K. C. Goh, and J. H. Ly. Controller synthesis via bilinear matrix
inequalities. Proc. American Contr. Conf., pages 45-49, 1994.

[19] R. E. Skelton, T. Iwasaki, and K. M. Grigoriadis. A Unified Algebraic Approach toLinear Control Design. Taylor and Francis, 1997. (To appear).
[20] B. Wie and D. S. Bernstein. A benchmark problem for robust control design. Proc.
American Contr. Conf., pages 961-962, May 1990.