数理解析研究所講究録
1004 巻 1997 年 1-23

1Linear Algebra for Semidefinite Programming

Graduate School of Information Science and Engineering
Tokyo Institute of Technology, Masakazu Kojima
Graduate School of Information Science and Engineering
Tokyo Institute of Technology, Sadayoshi Kojima
Interdisciplinary Graduate School of Science and Engineering
Tokyo Institute of Technology, Shinji Hara

1.

Introduction.

There are numerous variations and extensions of primal-dual interior-point algorithms for linear
programs, convex quadratic programs, linear complementarity problems, convex programs andnonlinear complementarity problems ([8, 9, 10, 11, 13, 14, 17, 18, 19, 20, 24, 26,.. 29], etc.). A
common basic idea behind the algorithms in this class is “moving in a Newton direction for
approximating a point on the central trajectory at each iteration.” Among others, primal-dual
algorithms are known to solve large scale practical linear programs very
. In their recent paper [12], Kojima, Shindoh and Hara extended
efficiently
primal-dual interior-point algorithms to SDPs (semidefinite programs) and monotone SDLCPs(semidefinite linear complementarity problems) in real symmetric
See also [2]. This
paper is motivated by$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}-\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}_{0}\mathrm{r}-\mathrm{P}^{\mathrm{O}}\mathrm{i}\mathrm{n}\mathrm{t}$$([14, 15, 16],\mathrm{e}\mathrm{t}\mathrm{C}.)$mat..riceS.

(a) further extensions of interior-point algorithms to more general SDPs and SDLCPs in real
symmetric matrices, complex Hermitian matrices and quatemion Hermitian matrices, and(b) a unified treatment of those possible extensions.

There is another important class of interior-point algorithms which are founded on the theoryof self-concordance [21]. From the papers $[6, 22]$ , we know that algorithms in this class cover
SDPs not only in real symmetric matrices but also in complex Hermitian matrices and quaternion
Hermitian matrices. Hence the two issues (a) and (b) above have been settled there. The class ofprimal-dual
algorithms which we are concerned with is closely related to the classof interiOr-.point algorithms founded on the theory of self-concordance. For example, the central
trajectory which has been playing an
ole in the former class can be characterized as the
special case of self-concordant
set of minimizers of the primal-dual logarithmic barrier function
barrier functions (see [9, 17]), and primal-dual potential reduction algorithms ([8, 11, 18], etc.)
utilize the logarithmic potential function a special case of self-concordant potential functions.
Such close relationships support the issue (a) in the class of primal-dual interior-point algorithms.
A substantial difference, however, lies in their search directions. Roughly speaking, we employ asa search direction in the former class of interior-point algorithms “a Newton direction toward thecentral trajectory represented in terms of a system of equations,” while we apply Newton’s method
to the minimization of “the objective function of the problem to be solved (or the duality gap)a self-concordant barrier function” over the interior of the feasible region to get a search directionin the latter class of interior-point algorithms. When we deal with SDPs, this difference in search$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{r}-\dot{\mathrm{p}}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}$$\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}\dot{\mathrm{r}}\backslash$$=\mathrm{a}$

$=$

$+$

2
directions is critical; the minimization problem used in the latter class always yields a consistentsearch direction, but we need an essential modification in a usual Newton direction toward thecentral trajectory in the former class because it does not necessarily exist (see [2, 12]). Therefore
it seems difficult to rely on the theory of self-concordance to settle the issues (a) and (b) in theclass of primal-dual interior point algorithms.
Letdenote the set of$R$ of real numbers, the fieldofnumbers.
$\mathcal{A}4_{n}(K)$$n\cross n$

$G$

Let

of

$n_{1},$$n_{2},$$n\cross n\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{C}^{-}\mathrm{k}$matrices with elements in $K$ , where $K$ represents the fieldor the (noncommutative) field II of quaternion$\mathrm{C}\mathrm{o}\mathrm{m}_{\mathrm{P}^{1\mathrm{x}}}\mathrm{e}.\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{S}$be positive integers such that $n=n_{1}+n_{2}+\cdot$ ..
esdiagonal real$\ldots n_{\ell}$$+n_{\ell}$. Consider the set$\mathcal{T}$$\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\dot{\mathrm{c}}$$A=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(A_{11}, A_{22}, \ldots, A_{\ell}\ell)=(A_{11}OO$

wherematrices with the direct sum of$A_{ii}\in \mathcal{M}_{n}\dot{.}(R)(\dot{i}=1,2, \ldots,f)$$A_{22}OO$$A_{\ell\ell}OO))\in \mathcal{M}_{n}(R)$. We may identify the set$\mathcal{M}_{n_{i}}(R)(\dot{i}=1,2, \ldots,l)$$\mathcal{T}$of$n\cross n$,

block diagonal real;$\mathcal{M}_{n_{\mathrm{i}}}(R)\oplus \mathcal{M}n2(R)\oplus\cdots\oplus \mathcal{M}n_{l}(R)$if $l=n$ and $n_{i}=1$ $(\dot{i}=1,2, \ldots , n)$ then.
Euclidean space$\mathcal{T}$$\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}_{\mathit{3}}$.

turns out to be the n-dimensional$R^{n}$

Apparently the set$\mathcal{T}-$$K=R$ .

of block diagonal

forms a subring ofmatrices $A,$
to T.

(i)

$\mathcal{T}$$\mathrm{r}\mathrm{e}\mathrm{a}1\backslash$matrices satisfies the conditions below if we takewith the usual addition $A+B$ and multiplication $AB$ of; specifically the zero matrix $O$ and the identity matrix belong$\mathcal{M}_{n}(K)$$B\in \mathcal{M}_{n}(K)$$I$

is an $R$-module, $i.e.$ , a vector space over the field,
and $A,$

(ii)

$T$

$R;\alpha A+\beta B\in \mathcal{T}$for every$\alpha,$$\beta\in R$$B\in \mathcal{T}$(iii)$A^{*}\in \mathcal{T}$if$A\in \mathcal{T}$, where$A^{*}$

denotes the conjugate transpose of$A\in \mathcal{M}_{n}(K)$.

It is a subset
ofthese conditions that we will focus our attention in thispaper. We calla subalgebra ofover the field $Bt$ if it satisfies the conditions (i) and(ii), and simply a subalgebra if it is a subalgebra offor $K=R,$
or $H$ and for some
. We call-subalgebra if it satisfies the conditions (i), (ii) and (iii). For example, the set oflower triangular real matrices forms a subalgebra of
but it is not-subalgebra.
Obviously
is a -subalgebra. It should be noted that we always employ a real number
with which we perform the scalar multiple
in the condition (ii) evenofwhen $K=G$ or $K=H$ . To make this feature clear, we write,
instead ofand we call it $a*$-algebra (over the field $R$ ). Thus the dimension
and, respectively.
are 2 and$\mathcal{T}$$\mathcal{M}_{n}(K)\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}6^{\Gamma}\mathrm{i}\mathrm{n}\mathrm{g}$$\mathcal{M}_{n}(K)$$\mathcal{T}$$G$$\mathcal{M}_{n}(K)$$\mathcal{T}$

$n$

$*$

$a$

$n\cross n$$\mathrm{a}*$$\mathcal{M}_{n}(R)$$\mathcal{M}_{n}(K)$$*$$\alpha\in R$$\alpha A$$A\in \mathcal{M}_{n}(K)$$\mathcal{M}_{n}(K, R)$$\mathrm{o}\mathrm{f}.\mathcal{M}_{n}(e, R)$$n^{2}$$\mathcal{M}_{n}(K)$$\mathcal{M}_{n}(H, R)$$4n^{2}$, we use the notation
For every -subalgebraofto denote the set of all$T^{h}=\{A\in T:A^{*}=A\}$ . Obviously
Hermitian matrices informs a sub $R$-module ofbut it is not a subalgebra in general. Assume that $A\in \mathcal{M}_{n}(K, R)^{h}$ . The notation$A\succeq O$ (resp., $A\succ O$ ) means that $A$ is positive semi-definite, $i.e.,$ $x^{*}Ax\geq 0$
for every $x\in K^{n}$(resp., positive definite, $i.e.,$ $x^{*}Ax>0$ for every nonzero $x\in K^{n}$ ).
$*$$\mathcal{T}$$\mathcal{T};\dot{i}.e.,$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$$\mathcal{T}^{h}$$\mathcal{T}^{h}$3

Let $T$ be, and let-subalgebra ofare concerned with an SDP (semidefinite program) in$\mathrm{a}*$$(P)$minimizesubject to$A_{0}$$A_{i}$$\bullet$$\bullet$$\mathcal{T}$$X$$X=b_{i}(\dot{i}=1,2, \ldots, m)\}$$X\in T^{h}$$X\succeq O,$$(D)$

and $b_{i}\in R(\dot{i}=0,1,2,.\cdots , m)$ . We
and its dual

$A_{i}\in \mathcal{T}^{h}$$\mathcal{M}_{n}(K, R)$

maximizesubject to.

$\sum_{i=1i^{Z}i}^{m}b$$\sum_{\mathrm{Y}\succeq \mathit{0}}^{m_{1i}}i=,i+\mathrm{Y}=A_{0}A\chi \mathrm{Y}\in \mathcal{T}h.’\}$

Here $A$ $B$ stands for the inner product of matrices $A$ and $B$ in the $R$-module
whosedefinition will be given in the next section. Specifically, the inner product of matrices $A$ and $B$ in$\mathcal{M}_{n}(R)=\Lambda\tau n(R, R)$ turns out to be the standard one,
, the trace of $A^{T}B$ . The formulationof the primal-dual pair of SDPs above covers an equality standard form LP (linear program) and
its dual in the Euclidean spacewhen$\mathcal{M}_{n}(K, R)$$\bullet$$\dot{i}.e.$$R^{n}$$\mathcal{T}=\mathcal{M}_{1}(R)\oplus \mathcal{M}1(R)\oplus$$\cdot$..

$\oplus \mathcal{M}_{1}(R)$and a usual SDP and its dual in the entire matrix-algebra$\mathcal{T}=\mathcal{M}_{n}(R)([1,2,4,22,21,27],\mathrm{e}\mathrm{t}\mathrm{C}.)$.

We show a simple example of an SDP in$N(z)=N_{0}+ \sum_{j=1}^{m}Z_{j}N_{j}$where $N_{j}(j=0,1, \ldots, m)$ are given$\mathcal{M}_{n}(R)$$\mathrm{a}^{*}$,
of$n\cross n$real matrices when-subalgebra. Let

for every $z=(z_{1}, z_{2}, \ldots, z_{m})T\in R^{m}$ ,$k\cross l$complex matrices. Consider the problem

minimize $||N(z)||$subject to $||z||\leq 1$ .
Here$||\cdot|$[ denotes the 2-norm of vectors and matrices;$||u||$$=$$||N||$$=$$(_{j=} \sum_{1}^{p}uj\overline{u}_{j})^{1}/2$$\max\{||Nu|| :for every $u=(u_{1}, u_{2}, \ldots, u_{p})^{T}\in G^{p}$ ,||u||=1, u\in G^{\ell}\}$If we define$H(z, zm+1)=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(,$for every$)$$k\cross l$matrix $N$ .

for every $(z, Z_{m+1})^{T}\in R^{m+1}$ ,we can reformulate the problem above as
maximize$-z_{m+1}$

subject to$\mathrm{Y}=H(z, z_{m+}1)$$\mathrm{Y}\succeq O,$$\mathrm{Y}\in T^{h}$

,
.

Here
$\mathcal{T}=\mathcal{M}_{k+\ell}(G, R)\oplus \mathcal{M}m+1(R)$Thus we obtain a dual form SDP inof SDps.

$\mathrm{a}^{*}$-subalgebra$\mathcal{T}.$.

See. [1, 2, 4, 23], etc. for various applications

4
We are also concerned with a monotone SDLCP (semidefinite linear complementarity problem).
of. Let denote the dimension of the $R$-module
in -subalgebra of
$T$
(X,
)
such
that
The monotone SDLCP in is defined as the problem of finding an$\mathrm{a}^{*}$$\mathcal{T}^{h}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$\mathrm{Y}$(X,

where (X$0,$$\mathcal{M}_{n}(K, R)$$\mathrm{Y}$) $\in F\equiv F_{0}+(X_{0}, \mathrm{Y}_{0}),$ $X\succeq O,$, andsatisfying the monotonicity$\mathrm{Y}_{0}$)$\in \mathcal{T}^{h}\cross T^{h}$$\mathcal{M}_{n}(K, B\mathrm{i})$$q$$F_{0}\subset \mathcal{T}^{h}\cross \mathcal{T}^{h}$$dK$$\bullet$$d\mathrm{Y}\underline{>}0$

and $X$$\mathrm{Y}\succeq O$$\bullet$$\in T^{h}\cross \mathcal{T}^{h}$$\mathrm{Y}=0$,(1)

is a -dimensional sub $R$-module of

if

$q$

$(d\mathrm{X}, d\mathrm{Y})\in \mathcal{F}_{0}$$\mathcal{M}_{n}(K, R)\cross$.

(2)

simultaneously covers monotone LCPs
-subalgebra of
The monotone SDLCP in.
and(see, for example, [5, 8]), and monotone SDLCPs inin
was first introduced by Kojima, Shindoh and Hara [12].
The monotone SDLCP in$\mathrm{a}^{*}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$R^{n}$$\mathcal{M}_{n}(R),$$\mathcal{M}_{n}(H, R)$$\mathcal{M}_{n}(G, R)$$\mathcal{M}_{n}(R)$fun.damental algebraic structure of

In Section 2, we present a common

and$\mathcal{M}_{n}(Bf, R)$.

$\mathcal{M}_{n}(R),$$\mathcal{M}_{n}(\mathcal{O}, R)$

In Section 3, we state (without proof) the weak and the strong duality on the SDPs (P) and(Theorem 3.1), and derive a monotone SDLCP infrom(D) in-subalgebra ofthem.
$\mathrm{a}^{*}$$\mathcal{T}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$Section 4 is devoted to brief discussions on adaptation of interiOr-.p oint methods given for theby Kojima, Shindoh and Hara [12] to the monotone SDLCP inmonotone SDLCP in. The theoretical results, interior-point methods and their complexity
subalgebra $T$ ofbyanalysis presented in the paper Kojima-Shindoh-Hara [12] remain valid if we replaceand make appropriate minor modifications. Specifically, we state the existence of the central
trajectory in the SDLCP in (without proof), the existence of the Newton direction towards thecentral trajectory (with proof) and the Generic IP Method for the monotone SDLCP in . Theirinterior-point methods are based on the primal-dual interior point method [9, 17, 19, 26] for linear. Strictly speaking, however, their methods are not extensions
programs in the Euclidean spacecoversof the primal-dual interior point method simply because the monotone SDLCP in. Now, using *-subalgebras
neither the standard monotone LCP innor linear programs in, we can handle the monotone SDLCP and interior-point methods for solving it inofsimultaneously.
and$\mathrm{a}^{*}-$$\mathcal{M}_{n}(R)$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(R)$$\mathcal{T}$$\mathcal{T}$$\mathcal{T}$$R^{n}$$\mathcal{M}_{n}(R)$$R^{n}$$lR^{n}$$\mathcal{M}_{n}(K, R)$$R^{n},$$\mathcal{M}_{n}(R),$$\mathcal{M}_{n}(G, R)$$\mathcal{M}_{n}(R\tau, R)$.
Section 5 studies theoretical characterization of -subalgebras of”
In Section 5.1, we introduce “a faithful *-representationofwhere $d=1,2$$IH$
and 4 if $K=R,$
and , respectively. The mapping is a homomorphism from
intothat transforms each *-subalgebra of
into-subalgebraofhaving the same algebraic structure as , so that we may restrict ourselves tosubalgebras ofwhen we classify all *-subalgebras in Section 5.2. Furthermore the faithful-representationofmakes it possible to convert any SDP and any monotone$R)$ ) into some SDP and some monotone(or
SDLCP in a -subalgebra of(or), respectively. The homomorphism from
SDLCP in-subalgebra ofinto
was utilized in the paper [3] where duality of general linear programswith real, complex and quaternion matrix variables was discussed.
In Section 5.2, we present a classification of -subalgebras of. The main results areroughly summarized as follows:
There are exactly three types “irreducible” -subalgebras of$*$$\mathcal{M}_{n}(K, R)$$(\tilde{\rho}, IR^{dn})$$G$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$$\tilde{\rho}$$\mathcal{M}_{dn}(R)$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$\mathcal{M}_{dn}(R)$$\mathrm{a}^{*}$$\mathcal{T}’=\tilde{\rho}(\mathcal{T})$$*-$$\mathcal{T}$$\mathcal{M}_{n}(R)$$*$$(\tilde{\rho}, R^{dn})$$\mathcal{M}_{n}(K, R)$$*$$\mathcal{M}_{n}(G, R)$$\mathrm{a}*$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$\mathcal{M}_{2n}(R)$$\mathcal{M}_{n}(R\mathrm{f},$$\mathcal{M}_{4n}(R)$$\tilde{\rho}$$\mathcal{M}_{dn}(R)$$*$$0\dot{\mathrm{f}}$$\mathcal{M}_{n}(R)$$*$$\bullet$$\tilde{\rho}(\mathcal{M}_{n}(R))=\mathcal{M}_{n}(R),\tilde{\rho}$,( $\mathcal{M}_{n/2(R))}G$
and$\mathcal{M}_{n}(R)$$\tilde{\rho}(\mathcal{M}_{n/4(Bf,R})$),

is a faithful -representation of $\mathcal{M}_{n/d}(K, R)$ given in Section 5.1 and $d=$
$1,2,4$ when $K=R,$ $G,$ $H$ , respectively.

where$(\tilde{\rho}, R^{n})$

$*$

5

$\bullet$Any *-subalgebra ofis isomorphic to a direct sum of somebelongs to one of the three types of irreducible -subalgebras ofthat eachsome $m$ .

$\mathcal{T}_{i}(\dot{i}=1,2, \ldots, l)$$\mathcal{M}_{n}(B8)$$*$$\mathcal{T}_{i}$Fundamental Algebraic Structures of2.

$\mathcal{M}_{n}(K, R)$

such
for

$\mathcal{M}_{m}(R)$.

Let $K$ represent the field $lR$ of real numbers, the field of complex numbers or the (noncommutative) field, a linear space overof quaternion numbers. We will regard $lK$ an $lR$-module,$R$the field . To clarify this aspect, we write $K(R)$ . Apparently$G$$\dot{i}.e.$$R\mathrm{f}$if $K=R$ ,if $lK=G$ ,if $K=Bf$ .

1$\dim K(R)=\{$ 24(3)

We endow the $lR$-module $K(R)$ with an inner product$z^{1} \cdot z^{2}=\frac{z^{\overline{1}_{\chi^{2}+}}\overline{(zz)\overline{1}2}}{2}\in R$of$z^{1}$

and$z^{2}$

in $K(R).$ Here$\overline{z}--$$\overline{z}$$\overline{z}$$z^{1}\cdot z^{2}$$z^{1}\cdot z^{2}$$z^{1}\cdot z^{2}$

$=$

$=$

$=$

$=$

$=$

$\overline{z}$denotes the conjugate of $z\in K(R)$ . More specifically,

if $z\in R$ ,v-iw if $z=v+\dot{i}w\in G$ ,$v-\dot{i}w-jx-ky$ if $z=v+\dot{i}w+jx+ky\in Bf$ ,$z^{1}z^{2}\in R$$z^{2}\in R$,
if$z^{2}=v^{2}+\dot{i}w^{2}\in G$$v^{1}v^{2}+ww\in 12R$ if,$z$$z^{1},$$z^{1}=v^{1}+\dot{i}w^{\dot{1}},$$v^{1}v^{2}+w^{121}w+XX^{2}+y^{12}y\in R$

if $z^{1}=v^{1}+\dot{i}w^{1}+jx^{1}+ky^{1},$ $z^{2}=v^{2}+\dot{i}w^{2}+jx^{2}+ky^{2}\in Rf$ .

Here$\dot{i},$

$j$

and

$k$

satisfy$\dot{i}i=jj=kk=-1,\dot{i}=jk=-kj,$ $j=ki=-\dot{i}k,$$k=ij=-ji$ .

The definitions above naturally lead to the $R$-module $K(R)^{n}$ with the inner product$z^{1} \cdot z^{2}=\sum_{\ell=1}^{n}z\ell 1$

for every$z^{1}=(\chi_{1}^{1}, \ldots, z_{n}^{1})^{T},$.

$z^{2}=(z_{1}^{2}\ldots Z2)^{T}\in K(R)^{n}$$n$$\dim K(R)^{n}=\{$

$2n$

$4n$

. It follows from (3) that

if $K=R$ ,if $K=G$ ,if $K=Bf$ .

Note that $R(R)^{n}$ coincides with the -dimensional Euclidean space$z^{2}\in R^{n}$.
produCtof$n$$Z\cdot Z=(12)^{\tau_{Z^{2}}}z^{1}$(4)$z_{\ell}^{2}\in R$$R^{n}$

with the standard inner$z^{1},$

Each element $a\in K$ induces a linear transformation in $K(R)$ such that$z\in K(R)arrow az\in K(R)$ .

6Thus we may regard the set of such linear transformations in $K(R)$ as an $R$-module, which wewill denote by. We define the inner product of and in the $R$-moduleby$a^{1}$$\mathcal{M}_{1}(K, R)$$a^{1_{\bullet}}a^{2}=..

$a^{2}$$\mathcal{M}_{1}(K, R)$(5)\frac{(\dim K(R))(\overline{a^{1}}a+2(a\neg\overline{1}a^{2})}{2}$or$a^{1}\bullet a^{2}$$a^{2}$$a^{1}$$\bullet$$a^{1}$$a^{2}$$\bullet$if$a^{2}\in R$,$=$$a^{1}a^{2}\in R$$=$$2(v^{1}v^{2}+w^{1}w^{2})\in R$$=$$4(v^{1}w^{2}+w^{1}w^{2}+x^{1}x^{2}+y^{1}y^{2})\in R$$a^{1},$

if $a^{1}=v^{1}+\dot{i}w^{1},$ $a^{2}=v^{2}+iw^{2}\in G$ ,if $a^{1}=v^{1}+\dot{i}w^{1}+jx^{1}+ky^{1},$ $a^{2}=v^{2}+\dot{i}w^{2}+jx^{2}+ky^{2}\in Bf$ .
It should be noted that elements in $K$ have two distinct inner products “.” (see (4)) and “ ” (see$z^{2}\in K$(5) ; the former is used when we regard
as elements of $K(R)$ while the latter is used$a^{2}\in K$
when we regard
as elements of. But the difference in values of the former
and the latter inner products of two elements
in $K$ is a constant multiple;$\bullet$$z^{1},$$)$$a^{1},$$\mathcal{M}_{1}(K, R)$$e^{1},$$e^{1}$$\bullet$$e^{2}$$e^{2}=\dim K(R)e^{1}\cdot e^{2}$.

The use of these two distinct inner products will be necessary in Section 5.1 where we present afaithful -representationofwhich preserves the values of inner products inboth $R$-modules. See the conditions (f) and (g) in Section 5.1.
and$*$$(\tilde{\rho}, R^{dn})$$K^{n}$

Now we define$\mathcal{M}_{n}(K, R)$

forms$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$

as the set of all matrices with elements in. Thena linear transformation$\mathcal{M}_{1}(K, R)$$a*$-algebra, and each $A\in \mathcal{M}_{n}(K, R)$ induces$z\in K(R)^{n}arrow Az\in K(R)n$in the $R$-module $K(R)^{n}$ . The inner product of two matricesby$A^{1} \bullet A^{2}=\sum_{\ell=1p}^{n}\sum a^{1}\ell_{p^{\bullet}}a^{2}=1n\ell p$

and the norm $||A||$ of a matrix $A$ in$\mathcal{M}_{n}(K, R)$$A^{1}$

and$A^{2}$

in$\mathcal{M}_{n}(K, R)$

is given’

by$||A||=(A\bullet A)^{1/}2$

Here$a_{\ell p}$

denotes the$(l,p)\mathrm{t}\mathrm{h}$element of a matrix $A\in\lambda 4_{n}(K, R)$ .

If $A=[a\ell_{p}]$ is a matrix in$\mathcal{M}_{n}(K^{\mathrm{e}},R)$, its conjugate$A^{*}$

is defined as$A=(\overline{A})^{T}=$ .
For each subset;$\mathcal{T}$of$\mathcal{M}_{n}(K, R)$, we use the notation$\mathcal{T}^{h}$for the set of Hermitian matrices in$\mathcal{M}_{n}(K, R)$$\mathcal{T}^{h}=\{A\in \mathcal{T}:A^{*}=A\}$.

Let $A\in \mathcal{M}_{n}(K, R)^{h}$ . Then we can easily verify that$z\cdot Az=z^{*}Az$for every $z\in K(R)^{n}$ .

7Therefore a Hermitian matrix
only if$A\in \mathcal{A}4_{n}(K, R)^{h}$$z\cdot Az\geq 0$oris positive semi-definite or positive definite if andfor every $z\in K(R)^{n}$.or every nonzero$z\cdot A.z>0\mathrm{f}$respectively.

3.

$z\in K(R)^{n}$,

Duality in SDPs.

This section presents a duality theorem on the SDPs (P) and (D) in -subalgebra of.
$z)\in \mathcal{M}_{n}(K,$ $R)\cross R^{m}$ )We call an $X\in \mathcal{M}_{n}(K, R)$ (resp.,a feasible solution if it satisfies
the constraints of (P) (resp., the constraints of), and an interior feasible solution if in addition$X\succ O$ (resp.,). We have the following duality theorem between the primal-dual pair of
SDPs (P) and (D).
$\mathrm{a}^{*}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$(\mathrm{Y},$$\backslash$$(\mathrm{D})$$\mathrm{Y}\succ O$

be a -subalgebra of.
(Weak Duality) Let $X$ andbe feasible solutions of $(P)$ and $(D)$ , respectively. Then

Theorem 3.1. Let
$(a)$

$*$

$\mathcal{T}$$\mathcal{M}_{n}(K, R)$$(\mathrm{Y}, z)$.

$A_{0} \bullet \mathrm{x}-\sum_{1i=}b_{i}Zi=Xm\bullet \mathrm{Y}\geq 0$

If $X$$(b)$$\bullet$$\mathrm{Y}=0$

then $X$ and$(\mathrm{Y}, z)$

are optimal solutions of $(P)$ and $(D)$ , respectively.

(Strong Duality) Suppose that there exist interior feasible solutions of $(P)$ and $(D)$ . Then
there exist optimal solutions $X$ of $(P)$ andof $(D)$ such that$(\mathrm{Y}, z)$$A_{0^{\bullet}}$X.

$- \sum_{i=1}^{m}bi^{Z_{i}}=.x\bullet \mathrm{Y}=0$.

The assertion (a) (Weak Duality) can be verified easily. The assertion (b) (Strong Duality)
follows ffom a more general result (Theorem 4.1), given in the next section, on the monotone
SDLCP in-subalgebra of. These results (a) and (b) are well-known when $T$ is the$i.e.,$$T=\mathcal{M}_{n}(R)$real full matrix-algebra,. See, for example, [1, 4, 27].
$\mathrm{a}^{*}$$\mathcal{M}_{n}(K, R)$. Suppose that there exist interior feasible solutions(D) as assumed in (b) of Theorem 3.1. DefineLet$q=\dim \mathcal{T}^{h}$$\dot{F}_{0}$$\equiv$$F$$\equiv$$\{(d\mathrm{X}, d\mathrm{Y})\in \mathcal{T}^{h}\cross \mathcal{T}^{h}$$\mathcal{F}_{0}+(X_{0}, \mathrm{Y}_{0})$:$X_{0^{\mathrm{O}}}.\mathrm{f}(\mathrm{P})$and$d \mathrm{Y}=A_{i^{\bullet}}dx=0(\dot{i}=1,2,\ldots,m)-\sum i=\mathrm{f}m_{1}A_{i^{Z_{i}}}\mathrm{o}\mathrm{r}\mathrm{S}\mathrm{o}\mathrm{m}\mathrm{e}’ Z\in R^{m}\}$$(\mathrm{Y}_{0}, z\mathrm{o})$

of

,

..

.

Note that $F$ can be rewritten as$\dot{F}$$=$$\{(X, \mathrm{Y})\in \mathcal{T}^{h}\cross \mathcal{T}^{h}$

It is easily verified thatsuch that$F_{0}$:$\mathrm{Y}=A_{0}-\sum_{i=1i^{Z\mathrm{f}_{0}}}^{m}AA_{i^{\bullet}}x=bi(_{\dot{i}=1,2,\ldots,m_{\mathrm{o}\mathrm{m}}}\mathrm{s}i\mathrm{r}),$$\mathrm{e}z\in R^{m}\}$.

forms a -dimensional sub $lR$-module of the 2 -dimensional R-module
$q$

$q$

$\mathcal{T}^{h}\cross \mathcal{T}^{h}$$d\mathrm{X}$$\bullet$$d\mathrm{Y}=0$

for every$(\alpha, d\mathrm{Y})\in F_{0}$

.

(6)

8

is monotone (see (2)). Obviously $X$ andThis implies thatand (D) if and only if$(X, \mathrm{Y})\in F\equiv F_{0}+(X_{0}, \mathrm{Y}_{0}),$are feasible solutions of (P)$(\mathrm{Y}, z)$$F_{0}$

and$X\succeq O$.

$\mathrm{Y}\succeq O$

are optimal solutions of SDPs (P) and (D) if andHence we see by Theorem 3.1 that $X$ andonly if (X, Y) is a solution of the monotone SDLCP (1) in . Thus we have derived a monotone, which we will discuss in the next section, from the primal-dual pair of SDPs (P)SDLCP inand (D).
$(\mathrm{Y}, z)$$\mathcal{T}$$\mathcal{T}^{h}$Monotone SDLCPs and Interior-Point Methods.

4.

,
and
, and let and denote the dimensions of
be a -subalgebra ofLetfindingproblemofrespectively. Recall that the monotone SDLCP in has been defined as the
sub $R$-module of the 2qis asatisfying (1) and thatan (X, Y)satisfying the monotonicity (2).
dimensional $R$-module$*$$\mathcal{T}$$T^{h}$$\mathcal{T}$$\mathcal{M}_{n}(K, R)$

$p$

$q$

$\mathcal{T}$$\in \mathcal{T}^{h}\cross \mathcal{T}^{h}$$\mathcal{F}_{0}$$q- \mathrm{d}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}_{0}\mathrm{n}\mathrm{a}1\vee$$\mathcal{T}^{h}\cross \mathcal{T}^{h}$Let$\tau_{+}$$=$$\mathcal{F}_{++}$$=$,$\{(X, \mathrm{Y})\in F : X\succ O, \mathrm{Y}\succ O\}$ .
$\{(X, \mathrm{Y})\in F : X\succeq O, \mathrm{Y}\succeq O\}$a feasible solution of the monotone SDLCP (1), and (X, Y)
We call (X, Y)
interior feasible solution of the monotone SDLCP (1).
$\in \mathcal{F}_{+}$

an$\in\tau_{++}$The theorem below states the existence of the central trajectory under the assumption thatin
. The theorem was established by Kojima, Shindoh and Hara for the casetheorem,way
originalas thetheir paper [12]. The generalized theorem can be proved in a similar
Theorem 3.1 of [12], and the proof is omitted here.
$\mathcal{T}=\mathcal{M}_{n}(R)$$\mathcal{F}_{++}\neq\emptyset$

be a -subalgebra ofTheorem 4.1. Let$R$
is monotone and that
dimensional sub -module$*$$\mathcal{T}$$F_{0}$(i) For every $\mu>0$ , there exists a unique (X{ $(X(\mu),$ Y.

(iii) (X) converges to a solution$(\mu),$$\mathrm{Y}(\mu)$$(\mu.))$$(\mu),$$\tau_{++}\neq\emptyset$$\mathrm{Y}(\mu)$)$q=\dim \mathcal{T}^{h}$. Assume that the q-.

$\in \mathcal{F}_{++}$

such that $X(\mu)\mathrm{Y}(\mu)=\mu I$ .

: . $>0$ } $fo.7.mS$ a smooth trajectory. (We call(ii) The set
tmjectory.)$\Gamma=$and$\mathcal{M}_{n}(K, R)$$\mu$$(X^{*}, \mathrm{Y}^{*})$$\mathcal{T}^{skew}$

denote the class of skew symmetric matrices contained in$\mathcal{T}^{skew}$$=$$\{W\in \mathcal{T}:W^{*}=-W\}=\{X-X^{*} :are sub $R$-modules of
Obviously
andcomplement of the other in . That is,$\mathcal{T}^{skew}$$\mathcal{T}^{h}$$\mathcal{T}$the centralof the SDLCP (1) as $\mu>0$ tends to zero.

Theorem 4.1 ensures that the monotone SDLCP (1) has a solution whenevercan derive (b) (Strong Duali.ty) of Theorem 3.1 from Theorem 4.1.

Let$\Gamma$$\mathcal{T}$$\mathcal{F}_{++}\neq\emptyset$, and we;X\in T\}$ .

such that either of them is the orthogonal$\mathcal{T}$$\bullet$$\bullet$$V$$\bullet$$W=0$ if$V\in \mathcal{T}^{h}$and$W\in \mathcal{T}^{skew}$,

every $X\in T$ can be represented as the sum $V+W$ of a unique pair of$W\in \mathcal{T}^{skw}e$.

$V\in \mathcal{T}^{h}$

and

9

Let

be a $(p-q)$ -dimensional sub $R$-module of the $2(p-q)$ -dimensional $R$-module. We impose
on the condition below:$\tilde{F}_{0}$$\mathcal{T}^{skew}$$\mathcal{T}^{skew}\cross$$\tilde{F}_{0}$Condition 4.2.

$\tilde{\mathcal{F}}_{0}$is monotone,$d\tilde{X}$$\dot{i}.e.$,

for every$d\tilde{\mathrm{Y}}\geq 0$$\bullet$$(d\tilde{\mathrm{X}}, d\tilde{\mathrm{Y}})\in\tilde{F}_{0}$.

For example, we can take$\tilde{F}_{0}=\{(tW, (1-t)W):W\in T^{skew}\}$,where $t\in[0,1]$ is an arbitrary constant. Let$\mathcal{T}_{++}^{h}=\{X\in \mathcal{T}^{h} :X\succ O\}$

We now consider the Newton equation at (X, Y)(X’, )
on the central trajectory.

for approximating a point$\in \mathcal{T}_{++}^{h}\mathrm{x}\tau_{++}^{h}$$\mathrm{Y}’$$=(X+d\mathrm{X}, \mathrm{Y}+d\mathrm{Y})$$\Gamma$.

:$(X+\alpha, \mathrm{Y}+d\mathrm{Y})\in F,$$(d\tilde{\mathrm{X}}.’d\tilde{\mathrm{Y}})\in\tilde{\mathcal{F}}_{0}$$X(d\mathrm{Y}+d\tilde{\mathrm{Y}})+(d\mathrm{X}+d\tilde{\mathrm{X}})\mathrm{Y}=\beta\mu I-X$

and
Y.

(7)

$\}$

and $\beta\in[0,1]$ denotes a search direction parameter. We will see later that theHere $\mu=X$
andfor every (X, )Newton equation (7) has a unique solution$\bullet$$\mathrm{Y}/n$$(d\mathrm{X}, d\mathrm{Y}, d\tilde{\mathrm{x}}, d\tilde{\mathrm{Y}})$$\in \mathcal{T}_{++}^{h}\cross\tau_{++}^{h}$$\mathrm{Y}$every $\beta\in[0,1]$ .

Generic IP Method.
Step : Choose (X$0$

Step 1: Let (X,$\mathrm{Y}$

)

$0,$

$\mathrm{Y}^{0}$)$\in\tau_{++}^{h}\cross\tau_{++}^{h}$$=(X^{r}, \mathrm{Y}^{r})$. Let $r=0$ .

and $\mu=X$$\mathrm{Y}/n$$\bullet$.

Step 2: Choose a direction parameter $\beta\in[0,1]$ .
Step 3: Compute a solution$(d\mathrm{X}, d\mathrm{Y}, d\tilde{\mathrm{x}}, d\tilde{\mathrm{Y}})$

Step 4: Choose a step size parameter(X $r+1,$$\mathrm{Y}r+1$)$\alpha\geq 0$of the system (7) of equations.

such that$=(X, \mathrm{Y})+\alpha(d\mathrm{X}, d\mathrm{Y})\in \mathcal{T}_{++}^{h}\cross\tau_{++}^{h}$.

Step 5: Replace $r+1$ by , and go to Step 1.
$r$

The Newton equation (7) and the Generic IP Method above are essentially the same as theoriginal ones proposed by Kojima, Shindoh and Hara in their paper [12] except that we have
(or
by
by
-subalgebra of
replaced the real full matrix-algebra. As special cases of the Generic IP Method, Kojima, Shindoh and Hara [12] presented acentral trajectory following method, a potential reduction method and an
potential-reduction method. These three methods are based on the interior-point methods given, respectively. Once we establish
in the papers [10], [11] and [18] for the monotone LCP in
all the methods and theirtrajectory,
the existence of the Newton direction towards the central
convergence analysis remain valid for the monotone SDLCP in a -subalgebra ofwithout any substantial change. The details are omitted here.
$\mathcal{M}_{n}(R)$$\mathrm{a}^{*}$$\mathcal{M}_{n}(R)^{h}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$\mathcal{T}^{h})$$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}- \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}_{0}\mathrm{r}-\mathrm{P}^{\mathrm{o}}\mathrm{i}\mathrm{n}\mathrm{t}$$R^{n}$$*$$\mathcal{T}$$\mathcal{M}_{n}(K.R)$

In the remainder of the section, we give a proof of the existence of the Newton direction toof the system (7) of equations. We, a solution
wards the central trajectory,$\dot{i}.e.$$(d\mathrm{K}, d\mathrm{Y}, d\tilde{K}, d\tilde{\mathrm{Y}})$10
are concerned with a little more general system of equations than (7):$(d\tilde{\mathrm{X}}, d\tilde{\mathrm{Y}})\in\tilde{F}_{0}$$(X+d\mathrm{X}, \mathrm{Y}+d\mathrm{Y})\in \mathcal{F},$$X(d\mathrm{Y}+d\tilde{\mathrm{Y}})+(d\mathrm{X}+\tilde{\mathbb{R}})\mathrm{Y}=Q$

and

,

(7)

$\}$

where $Q$ is an arbitrary constant matrix in . If we take(7). The theorem below is an extension of Theorem 4.2 of [12].

$Q–\beta I-X\mathrm{Y}\in \mathcal{T},$$\mathcal{T}$Theorem 4.3. For every (X,.

$\mathrm{Y}$)$\in \mathcal{T}_{++}^{h}\cross \mathcal{T}_{++f}^{h}$(7)’ coincides withthe system (7) of equations has a unique solution$(dK, d\mathrm{Y}, d\tilde{\mathrm{x}}, d\tilde{\mathrm{Y}})$

Proof:

Let $\tilde{q}=p-q$ . Let$R$-module, andmodulewritten as$\mathcal{F}_{0},$$\tilde{F}_{0}$be a basis of the q-dimensionala basis of the -dimensional R. Then the first relation of the Newton equation (7) can be$\{(M^{i}, N^{i})\in \mathcal{T}^{h}\cross \mathcal{T}^{h}(\dot{i}=1,2, \ldots, q)\}$$\{(\tilde{M}^{j},\tilde{N}^{j})\in \mathcal{T}^{skew}\cross \mathcal{T}^{skew}(j=1,2, \ldots , \tilde{q})\}$$(X^{0}, \mathrm{Y}^{0})\in F$$\tilde{q}$..

ci $(M^{i}, N^{i})$ ,$(X+dK, \mathrm{Y}+d\mathrm{Y})=(X^{0}, \mathrm{Y}^{0})+\sum_{i=1}^{q}$

hence

,

$dK= \mathrm{x}^{0_{-}}\mathrm{x}+’\sum^{q}i=1c_{i}M^{i}$$d \mathrm{Y}=\mathrm{Y}^{0}-\mathrm{Y}+\sum i=1qc_{i}N^{i}$,where ci $(\dot{i}=1,2, \ldots, q)$ are real variables. With new variables
rewrite the second relation of (7) as$( \tilde{\alpha}, d\tilde{\mathrm{Y}})=\sum_{j=1}^{\overline{q}}\tilde{c}_{j}.(\tilde{M}j,\tilde{N}^{j})$$\tilde{c}_{j}(j=1,2, \ldots,\tilde{q})$, we also.

Now the last equation in (7) is reduced to.

$\sum_{i=1}^{q}C_{i}(XN^{i}+M^{i}\mathrm{Y})+\sum_{j=1}^{\tilde{q}}\tilde{c}_{j}(X\tilde{N}^{j}+\tilde{M}^{j}\mathrm{Y})=Q-X(\mathrm{Y}^{0}-\mathrm{Y})-(X^{0}-x)\mathrm{Y}$Thus we have only to show that the system of linear equations above in $p=q+\tilde{q}$ variables
has a unique solution. We note that all theci $(i=1,2, \ldots, q)$ andcoefficient matrices$\tilde{c}_{j}(j=1,2, \ldots,\tilde{q})$$(XN^{i}+M^{i}\mathrm{Y})(i=1,2, \ldots, q)$$\mathrm{p}$and$(X\tilde{N}^{j}+\tilde{M}^{j}\mathrm{Y})$(8)$(j=1,2, \ldots,\tilde{q})$appearing on the lefli hand side of the system of equations above are in the -dimensional sub, and that the constant matrix-module of
$p$

$R$

$\mathcal{T}$$\mathcal{M}_{n}(K, R)$$Q-X(\mathrm{Y}^{0}-\mathrm{Y})-(X^{0}-x)\mathrm{Y}$on the right hand side also belongs to . Therefore it suffices to show that the set of matrices. Assuming thatgiven in (8) forms a basis of the -dimensional sub $R$-module of$\mathcal{T}$

$p$

$p$

$\mathcal{T}$$\mathcal{M}_{n}(K, R)$,$\sum_{i=1}^{q}ci(XN^{i}’+M^{i}.\mathrm{Y})+\sum_{jarrow-1}^{\tilde{q}}\tilde{C}_{j}’.\cdot(.\mathrm{x}\tilde{N}^{j}+\tilde{M}^{j}\mathrm{Y})=O$

(9)

11

we will show that all the$M’= \sum^{q}C_{i}Mi=1\prime i,$

Then
that

and

$c_{i}’(\dot{i}=1,2, \ldots, q)$’$d \mathrm{Y}’=\sum_{=i1}qc_{i}’Ni,$and$(M’, d\mathrm{Y}’)\in \mathcal{F}_{0}\subset \mathcal{T}^{h}\cross T^{h}$$d_{j}^{\sim}(j=1,2, \ldots,\tilde{q})$$d \tilde{X}’=\sum_{j=1}\tilde{c}_{j}\tilde{M}^{j}\tilde{q}$

and
and

$X\in \mathcal{T}\subset \mathcal{M}_{n}(K, R)$$\sqrt{X}\in \mathcal{M}_{n}(K, R)$$O$$d \tilde{\mathrm{Y}}’=\sum_{j=1}^{\tilde{q}}\tilde{c}_{j}\tilde{N}^{j}’$$(d\tilde{\mathrm{X}}’, d\tilde{\mathrm{Y}})’\in\tilde{F}_{0}\subset \mathcal{T}^{skew}\cross \mathcal{T}^{skew}$$O=X(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)+(d\mathrm{X}’+d\tilde{K}’)\mathrm{Y}$

Since
gular
follows from (10) thatandvanish. Let$\mathrm{Y}\in T\subset \mathcal{M}_{n}(K, R)$. We also see from (9)

.

(10)

are positive definite, there exist nonsin-

such that $X=\sqrt{X}\sqrt{X}$ and$\sqrt{\mathrm{Y}}\in \mathcal{M}_{n}(K, R)$.

$\mathrm{Y}=\sqrt{\mathrm{Y}}\sqrt{\mathrm{Y}}$

. It

.

$\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}+\sqrt{X}^{-1}(d\mathrm{X}’+d\tilde{\mathrm{X}}’)\sqrt{\mathrm{Y}}$$=$From the above equality, we obtain that
$0$

$=$

$(\sqrt{X}(d\mathrm{Y}^{;}+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}+\sqrt{X}^{-1}(d\mathrm{X}’+d\tilde{\mathrm{K}}’)\sqrt{\mathrm{Y}})$$\bullet$$(\sqrt{X}(d\mathrm{Y}’+d\tilde{Y}^{r})\sqrt{\mathrm{Y}}^{-1}+\sqrt{X}^{-1}(d\kappa’+d\tilde{K}^{r})\sqrt{\mathrm{Y}})$$||\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}||^{2}+||\sqrt{X}^{-1}(M’+d\tilde{K}’)\sqrt{\mathrm{Y}}||^{2}$$=$$+\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}-1\bullet$ $\sqrt{X}^{-1}(d\mathrm{X}’+\tilde{\alpha}’)\sqrt{\mathrm{Y}}$$+\sqrt{X}^{-1}(d\mathrm{x}^{;}+\tilde{\alpha}’)\sqrt{\mathrm{Y}}$$\bullet$$\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}$$||\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}||^{2}+||\sqrt{X}^{-1}(\alpha’+d\tilde{K}’)\sqrt{\mathrm{Y}}||^{2}$$=$$+(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)$$(d\mathrm{X}’+\tilde{\alpha}’)+(d\mathrm{X}’+d\tilde{\mathrm{X}}’)$$\bullet$$\bullet$$(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)$$||\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}||^{2}+||\sqrt{X}^{-1’}(d\kappa’+d\tilde{K}’)\sqrt{\mathrm{Y}}||^{2}$

$=$

+2
,

$d\mathrm{Y}’$(since$\bullet$$dX’+2d\tilde{\mathrm{X}}’$$d\mathrm{Y}’$$d\tilde{\mathrm{Y}}’$$\bullet$$d\tilde{X}’=d\tilde{\mathrm{Y}}’$$\bullet$$\bullet$$dX’=0$ )$||\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}||^{2}+||\sqrt{X}^{-1}(dK’+d\tilde{\mathrm{X}}’)\sqrt{\mathrm{Y}}||^{2}$$\geq$.

(since$d\mathrm{Y}’$$\bullet$$dX’\geq 0$

and$d\tilde{X}’$$d\tilde{\mathrm{Y}}’\geq 0$$\bullet$

)

.

..

Hence we see that$||\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}^{r})\sqrt{\mathrm{Y}}^{-1}||=0$and$||\sqrt{X}^{-1}(d\kappa’+d\tilde{\mathrm{X}}’)\sqrt{\mathrm{Y}}||=0$.

This implies that$\sqrt{X}(d\mathrm{Y}’+d\tilde{\mathrm{Y}}’)\sqrt{\mathrm{Y}}^{-1}=O$

By the nonsingularity of$\sqrt{X}$and$\sqrt{\mathrm{Y}}$

Since
Hence the equalities above imply th-at$d\tilde{K}’\in \mathcal{T}^{skew},$$d\mathrm{Y}’\in T^{h}$$(O, O)=(dK’, d \mathrm{Y}’)=\sum_{i=1}^{q}c_{i}’$($\sqrt{X}^{-1}(d\mathrm{x}^{;}+d\tilde{\mathrm{X}}’)\sqrt{\mathrm{Y}}=\mathit{0}$.

, we obtain$d\mathrm{Y}’+d\tilde{\mathrm{Y}}’=O$$dK’\in \mathcal{T}^{h},$and$M^{i},$

andand $dX’+d\tilde{\mathrm{X}}’=O$ .
$d\tilde{\mathrm{Y}}’\in T^{skew}$N) and, we see that.

$dX’\bullet d\tilde{\mathrm{x}}’=d\mathrm{Y}’\bullet d\tilde{\mathrm{Y}}’=0$$(O, O)=(d \tilde{K}’, d\tilde{\mathrm{Y}})’=\sum_{j=1}^{\tilde{q}}\tilde{C}_{j}’(\tilde{M}^{j},\tilde{N}^{j})$

.

12

and
and the -dimensionalof$1,2,$
are bases of the -dimensional sub $R$-module$c_{i}’=0(\dot{i}=1,2, \ldots, q)$ and $\tilde{c}_{j}’=0(j=$
$R$
Hence
respectively.
,of
sub -module$1,2,$. This means that the set of matrices given in (8) is linearly independent, and. This completes the proof offorms a basis of the -dimensional sub $R$-module ofTheorem 4.3.

Recall that$\{(\tilde{M}^{j},\tilde{N}^{j})\in \mathcal{T}^{skew}\cross \mathcal{T}^{skew}(j=$$\{(M^{i}, N^{i})\in \mathcal{T}^{h}\cross \mathcal{T}^{h}(\dot{i}=1,2, \ldots , q)\}$$\ldots,\tilde{q})\}$$\mathcal{T}^{h}\cross T^{h}$$F_{0}$$q$$\tilde{q}$$\mathcal{T}^{skew}\cross \mathcal{T}^{skew}$$\tilde{\mathcal{F}}_{0}$$p$$\ldots,\tilde{q})$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$p$$\mathrm{r}$5.

Characterization of -Subalgebras of

5.1.

A -Representation of

$*$

$*$

$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$.

.

-homomorphism” that transforms
In the latter part of this section, we construct “a. The *-homomorphism then makes it possible
into
the algebraic structure of
into an SDP and a monotone
for us to convert any SDP and any monotone SDLCP in$\mathcal{M}_{dn}(K,R)$.
several definitions. SupposeneedWe$d=\dim
K(R)$, respectively. HereSDLCP in$T’$
is a homomorphism if it satisfies:
are subalgebras. A mapping :that $T$ and$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}\mathrm{O}- \mathrm{o}\mathrm{n}\mathrm{e}*$$\mathcal{M}_{n}(K, R)$$\tilde{\rho}$$\mathcal{M}_{dn}(R)$$\tilde{\rho}$$\mathcal{M}_{n}(K, R)$$\mathcal{T}arrow \mathcal{T}’$$\rho$(a) $\rho(A+B)=\rho(A)+\rho(B)$ and $\rho(AB)=\rho(A)\rho(B)$ for every $A,$ $B\in T$ .
(b)$\rho$

is linear on $T;\rho(\alpha A+\beta B)=\alpha\rho(A)+\beta\rho(B)$ for every

is
If in addition
are *-subalgebras,and(c)For example, if

for every$S\in \mathcal{M}_{n}(R)$is$\mathrm{a}^{*}$-homomorphism(or *-isomorphism)$\rho$

onto$\mathcal{M}_{n}(R)$onto$\mathcal{T}’,$to$\mathcal{T}$and$\mathcal{T}’$(d)$\rho(I)=I\in \mathcal{M}_{n}(R)$

(12)

$*$

$\mathcal{M}_{m}(K, R)$. If a homomorphism (or a$*-$$\mathcal{M}_{n}(R)$,is a representation (or $a*$-representation) of . In this case $\rho(T)$ forms a subalgebra (or-representation)of $T$ is faithful if. A representation (or-subalgebra) of$\mathcal{T}$$(\rho, R^{n})$$\mathrm{a}^{*}$(11)

there exists an isomorphism
are isomorphic (or -isomorphic).

$*$$\rho$an orthogonal matrix then$\mathrm{A}\overline{4}_{2n}^{\vee}(:\dot{R}).\dot{\mathrm{I}}f$$\mathcal{T}$$\mathcal{T}$$\mathcal{T}$, andbe a subalgebra (or a -subalgebra) of
satisfies
homomorphism) from
into
Let

$P\in \mathcal{M}_{n}(R)$: $A\in \mathcal{M}_{n}(R)arrow SAS^{-1}\in \mathcal{M}_{n}(R)$$\mathrm{h}\mathrm{o}\mathrm{m}\mathcal{M}_{n}(R)\mathrm{i}\dot{\mathrm{n}}$from$\mathcal{T}’$: $A\in \mathcal{M}_{n}(R)arrow\in \mathcal{M}_{2n}(R)$$\mathcal{T}$.

$\rho$

is a nonsingular matrix and$\mathcal{M}_{n}(R)$$\rho^{2}$$B\in \mathcal{T}$$A\in \mathcal{T}$$\rho^{1}$is an isomorphism fromand $A,$

onto . Whenand onto, is an isomorphism$a*$-isomorphism) if it satisfies
is $a*$-homomorphism (or$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{0^{-}\mathrm{o}\mathrm{n}\mathrm{e}}$$\rho:Tarrow \mathcal{T}’$$\rho(A^{*})=\rho(A)^{*}$$\beta\in R$$\mathrm{h}\mathrm{o}\mathrm{m}\mathcal{T}$$\rho:\mathcal{T}arrow \mathcal{T}’$$\mathcal{T}’$$\alpha,$(e)$\mathcal{M}_{n}(R)$$\rho$

is$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{\mathrm{o}^{-}\mathrm{o}\mathrm{n}\mathrm{e}}$on$\mathcal{T}$$(\rho, R^{n})$$\mathrm{a}^{*}$.

but it is notin the example (11) is a faithful representation ofof*-representation
faithful(12)aexampleisinthein general.
$\mathcal{M}_{n}(R)$$(\rho^{1}, R^{n})$$\mathcal{M}_{n}(R)$$(\rho^{2}, R^{2n})$

We will construct below a faithful *-representation
the following additional conditions.

$\mathrm{a}^{*}$$(\rho, R^{dn})$-representation.

of $T=\mathcal{M}_{n}(K, R)$ that satisfies

13

(f)

iinear mapping) from the
There is an isomorphism ( $i.e.$ , a$R$-module
such that
onto the $dn$-dimensional Euclidean space$\phi(Az)$$\phi(z^{1.2})\phi(z)$$\rho(A)$$\bullet$.

$R^{dn}$$K^{n}$(g)$dn- \mathrm{d}\mathrm{i}\mathrm{m}$$\phi$$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{\mathrm{o}^{-}\mathrm{o}\mathrm{n}\mathrm{e}}$$\rho(B)=A$$\bullet$$B$for. every$\rho(A)\phi(z)$$=$$z^{1}\cdot z^{2}$$=$for every $A,$for every$B\in \mathcal{T}$$z^{\mathrm{i}},$$A\in \mathcal{T}$ensional

and $z\in K^{n}$ ,$z^{2}\in lK^{n}$.

.

preserves the algeHere $d=\dim K(R)$ . Such a faithful *-representation $(\rho, R^{dn})$ ofbraic structure which is necessary to study SDPs and monotone SDLCPs. It is easily seen that if
is anorthogonal matrix and$\mathcal{M}_{n}(K, R)$$n\cross n$$P\in \mathcal{A}4_{n}(R)$$\rho:A\in \mathcal{M}_{n}(R)arrow P^{T}\dot{A}P\in \mathcal{M}_{n}(R)$is a faithful$\phi(z)=P^{\tau_{Z}}(z\in R^{n})$ .

then$(\rho, R^{n})$.ation of$*- \mathrm{r}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{t}$that satisfies the conditions (f) and (g) with$\mathcal{M}_{n}(R)$

Theorem 5.1. Let $T$ be a -subalgebra of $\mathcal{M}_{m}(K, R)$ andbe a faithful -representation$(f)$ and $(g)$ . Then the following $(h),$satisfying
theand $(j)$ hold.
conditionsof.
is a -subalgebra ofwith$R))$ is a -subalgebra)(Specificallyof$*$$\mathcal{T}$$(\dot{i})$$(h)\rho(\mathcal{T})$$*$$\mathcal{M}_{dn}(R)$$\rho(\tau^{h})=\rho(\tau)^{h}$$\dim\rho(\mathcal{T})=\dim \mathcal{T}$$*$$\rho(\mathcal{M}_{n}(K,$

(i)

$*$

$(\rho, R^{n})$$\mathcal{M}_{dn}(R).$.

is positive semi-definite (or positive definite) if and only if
semi-definite (or positive definite).

$(j)\rho(A)\in\rho(\mathcal{T})^{h}$$A\in \mathcal{T}^{h}$is positive

By the assumption, all the conditions (a) through (g) are satisfied. We can easily
derive the assertion (h) and (i) from these conditions, so that we will only prove the assertion(j). Let. By the condition (f),Proof:$A\in \mathcal{T}^{h}$$\phi(z)\cdot\rho(A)\phi(z)=\phi(z)\cdot\phi(Az)=Z\cdot Az$, we know that
holds for every $z\in K(R)^{n}$ . Since is an isomorphism from $K(R)^{n}$ onto$\phi(K(R)^{n})=R^{dn}$ and $\phi(z)=0$ if and only if $z=0$ . Hence $u\cdot\rho(A)u$ is nonnegative for every$u\in R^{dn}$ (or positivefor every nonzero $u\in R^{dn}$ ) if and only if $z\cdot Az$ is nonnegative for every$z\in K(R)^{n}$ (or positive for every nonzero $z\in K(R)^{n}$ ). This implies the assertion (j).
1$R^{dn}$$\phi$

Using the properties (a) through (j) presented so far, we can convert the primal-dual pair of, which we have stated in Section 1, into a-subalgebra of
SDPs (P) and (D) in:
primal-dual pair of SDPs inof-subalgebra$\mathrm{a}*$$\mathcal{T}$$\mathrm{a}^{*}$$(P)’$$\mathcal{M}_{n}(K, R)$$\mathcal{T}’=\rho(\mathcal{T})$minimizesubject to$\rho(A_{0})$$\rho(A_{i})$$\bullet$$\bullet$$X’$$X’=b_{i}(\dot{i}=1,2, \ldots , m)\}$$X’\succeq O,$$(D)’$

maximizesubject to$X\in \mathcal{T}$$\mathrm{x}’\in\rho(\mathcal{T})^{h}$$\sum_{i=1}^{m}\rho(A_{i})_{Z_{i}}+\mathrm{Y}’=\rho(A_{0}),$$\mathrm{Y}’\in\rho(\mathcal{T})^{h}$$(\mathrm{Y}, z)\in \mathcal{T}\cross R^{m}$

$\}$

.

are optimal solutions of (P) and (D) if andare optimal solutions of (P) and$(\mathrm{Y}, z)=(\rho(\mathrm{Y}), z)\in\rho(\mathcal{T})\cross R^{m}$

(D).

.

$\sum_{i=1i}^{m}bz_{i}$$\mathrm{Y}’\succeq O,$andIt is easily verified that
only if $X’=\rho(X)\in\rho(\mathcal{T})$ and$\mathcal{M}_{dn}(R)$14
We now consider the monotone SDLCP (1) in a -subalgebra $T$ . Recall thatappearing in the SDLCP (1) is a -dimensional sub $R$-module ofthe monotonicity (2). Define$*$$\mathcal{T}^{h}$$F_{0}\subset T^{h}\cross$$\mathcal{M}_{n}(K, R)\cross \mathcal{M}_{n}(K, R)$$q$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\Phi \mathrm{i}\mathrm{n}\mathrm{g}$$\mathcal{F}_{0}’${$=$$(\rho(\mathrm{x}),\rho(\mathrm{Y}))$

: (X,

.

}

$\mathrm{Y})\in F_{0}$$\subset\rho(\mathcal{T}^{h})\cross\rho(T^{h})=\rho(\mathcal{T})^{h}\cross\rho(T)^{h}$Then
forms a -dimensional sub $R$-module of the 2 -dimensional $R$-module
We also know that$\mathcal{F}_{0}’$

$q$

$q$

$\rho(\dot{X})$This ensures that$\bullet$$\rho(\mathrm{Y})=X$$\bullet$$\mathrm{Y}$for every (X,inherits the monotonicity from
: Find ansuch that$F_{0}’$$\rho(T)\subset \mathcal{M}_{dn}(K, R)$$F_{0}$$\mathrm{Y}$)$\in \mathcal{T}^{h}\cross \mathcal{T}^{h}$$\rho(.\mathcal{T})^{h}\cross\rho(\mathcal{T})^{h}$.

. Thus we have the monotone SDLCP in$(X’, \mathrm{Y}’)$$(X’, \mathrm{Y}’)\in F’\equiv \mathcal{F}_{0}^{J}+(\rho(X_{0}),\rho(\mathrm{Y}_{0})),$$X’\succeq O,$$\mathrm{Y}’\succeq O$

and $X’$$\bullet$$\mathrm{Y}’=0$;

The monotone SDLCP (13) is equivalent to the monotone SDLCP (1) in the sense that (X,is a solution of the SDLCP (1) if and only if (X’, )is a solution of the SDLCP (13).
$\mathcal{T}^{h}\cross \mathcal{T}^{h}$

Now we construct a faithful *-representation
conditions (f) and (g) Define$(\rho, R^{dn})=(\tilde{\rho}, .R^{dn})$

if

$h$

$=$

$\{$

$=$

$(\tilde{\rho}(a_{n}1)\tilde{\rho}(a21)\tilde{\rho}(a_{11})$$\tilde{\rho}(a_{n}2)\tilde{\rho}(a\tilde{\rho}(a_{12})22)$$-\tilde{\rho}(A)$.. .

$h\in \mathcal{M}_{1}(R)$(13)$\mathrm{Y}$

)

$\in$

$=(\rho(X), \rho(\mathrm{Y}))\in\rho(T)^{h}\cross\rho(\mathcal{T})^{h}$$\mathrm{Y}’.$$\tilde{\rho}(h)$of$\mathcal{M}_{n}$(K.’ $R$)$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathfrak{h}\mathrm{i}\mathrm{n}\mathrm{g}$the,$\tilde{\rho}(a_{nn})\tilde{\rho}(a_{2n})\tilde{\rho}(a_{1n}))\backslash )\in \mathcal{M}_{dn}(R)$if $A\in \mathcal{M}_{n}(K, R)$ .

(14)

Theorem 5.2. $(\rho, R^{dn})=(\tilde{\rho}, R^{dn})$ is a faithful -representation ofsatisfying theconditions $(f)$ and $(g)$ .
Proof: It is easily seen that satisfies the conditions (a), (b), (c), (d), (e) and (g). We canalso verify that the condition (f) holds with the isomorphismfrom $K(R)^{n}$ onto
given below:$*$$\mathcal{M}_{n}(K, R)$$\tilde{\rho}$$\phi=\tilde{\phi}$$\tilde{\phi}(z)$

.

$=$

$z$

if $z\in R$ ,$\in lR^{d}=R^{2}$

if $z=v+\dot{i}w\in G(R)$ ,$\in R^{d}=R^{4}$

if $z=v+\dot{i}w+jx+ky\in H(R)$ ,$\{$$R^{dn}$15$\tilde{\phi}(z)$$=$$\in lR^{dn}$ if $z=(\chi_{1}, z2, \ldots, Z_{n})\tau_{\in K}(R)n,$ .

Remark. The observation below relates the faithful -representationoftothe recent paper [6] by G\"uler. Let
denote the convex cone consisting of positive
semi-definite Hermitian matrices in. Then we know by Theorems 5.1 and 5.2 that$*$$(\tilde{\rho}, R^{dn})$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)_{+}^{h}$$\mathcal{M}_{n}(K, R)$.
$\tilde{\rho}(\mathcal{M}n(K, R)_{+}h)=$ $\mathcal{M}dn(R)_{+}h\cap\tilde{\rho}(\mathcal{M}n(K, R))$.

The convex coneenjoys some nice properties, the irreducibility, the regularity,
the homogeneity and the self-duality in the $R$-module. By Theorems 4.1 and 4.3of [6], we can represent the self-concordant universal barrier function (Nesterov-Nemirovskii [21])for the conein terms of the logarithm of a characteristic function of the cone
. See [6] for more details.
$\tilde{\rho}(\mathcal{M}_{n}(K, R)_{+}^{h})$$\tilde{\rho}(\mathcal{M}_{n}(K, R))$$\tilde{\rho}(\mathcal{M}_{n}(K, R)_{+}^{h})$$\tilde{\rho}(\mathcal{M}_{n}(K, R)_{+}^{h})$The next theorem shows that$\mathrm{a}^{*}$-subalgebra of$\mathcal{M}_{n}(R)$is closed under the inversion.

Theorem 5.3.
Let $(\rho, R^{dn})$ be a faithful -rep sentation of
$(f)$
$(g)$
. Then the following $(k)$ and $(f)$ hold.
tions
and
$*$

$7\mathrm{e}$

$(k)$

$(l)$

is nonsingular if and only
is nonsingular.

$A\in \mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(K, R)$Let$\mathcal{T}$Proof:

be a -subalgebm of$*$$\mathcal{M}_{n}(K, R)$$\dot{i}f\rho(A)$$\mathcal{M}_{n}(K, R)$satisfying the condi-

is, and $\rho(A^{-1})=\rho(A)^{-1}$ if $A\in$. If $A\in \mathcal{M}_{n}(K, R)$ is nonsingular then$A^{-1}\in \mathcal{T}$.

Recall that $A\in A4_{n}(K, R)$ is nonsingular and $B\in \mathcal{M}_{n}(K, R)$ is its inverse if$BA=AB=I$ .
From the conditions (a) with
if and only if$\mathcal{T}=\mathcal{M}_{n}(K, R),$$(\mathrm{d})$and (e), we see that the equalities above hold.

$\tilde{\rho}(B)\tilde{\rho}(A)=\tilde{\rho}(A)\tilde{\rho}(B)=\tilde{\rho}(I)=I$

Thus the assertion (k) follows. To prove the assertion $(f)$ , we only need to deal with the casewhere is -subalgebra ofin view of Theorem 5.1 and the assertion (k). Suppose that
. Take a sufficiently small positive number
is nonsingular. Then we know thatsuch that all the eigenvalues of the positive definite matrix
are less than 1. Then the
inverseof the matrix
can be written as$\mathcal{T}$$\mathrm{a}^{*}$$\mathcal{M}_{n}(R)$$A^{T}\in \mathcal{T}$$A\in \mathcal{T}$$\epsilon A^{T}A$$\epsilon$$\epsilon A^{T}A$$(\epsilon A^{T-1}A)$$(\epsilon A^{\tau_{A)}-}1$$=$$(I-(I-\epsilon A^{T}A))-1$$=$$I+(I-\epsilon A^{T}A)+(I-\epsilon A^{\tau}A)^{2}+\cdots$.

By the conditionsand (iii) imposed on the *-subalgebra , each term on the right handside belongs to . Since $T$ is topologically closed, the infinite sum of matrices on right hand side
belongs to ; hence so does the matrix
on the left hand side. Therefore we obtainby the conditions (i) and (ii) that$\mathcal{T}$$(\mathrm{i})_{\mathit{3}}(\mathrm{i}\mathrm{i})$$\mathcal{T}$$(\epsilon A^{T-1}A)$$\mathcal{T}$$A^{-1}$$=$$\epsilon(\epsilon A^{T}A)^{-1}A^{\tau}\in \mathcal{T}$.

16Classification of -Subalgebras of

5.2.

$*$

.

$\mathcal{M}_{n}(R)$”In Section 5.1, we have utilized some notions such as “homomorphism ” and “isomorphism from.
ofthe representation theory of algebras to describe a faithful *-representation
We need to rely more upon the theory in order to derive a complete set of characterizations ofin Theorem 5.4. Our discussions here are based on the literature [7]-subalgebras of
written in Japanese. We also refer to Chapter III of the book [28] written in English although
the readers may have some difficulty relating the results presented there to ours. We have been
searching for more appropriate sources, but all other literatures we have found so far do not fit
well in our discussions. We should also mention that Chapter IV of the book [25] studies algebras
with an involution and $*- algebr.aS$ which includes our *-subalgebra as a special case but the main
subject of the book is not relevant to our discussions.
$(\tilde{\rho}, R^{dn})$$*$$\mathcal{M}_{n}(K, R)$$\mathcal{M}_{n}(R)$Let$\mathcal{T}$be$\mathrm{a}^{*}$-subalgebra of$\mathcal{M}_{n}(K, R)$. An ideal ofif$AB\in \mathcal{I}$$A\in \mathcal{T}$$\mathcal{T}$andObviously, $\{O\}$ and are ideals of . If $T$ contains no
A sub $R$-module of $K(R)^{n}$ is $T$ -invariant if

is a sub $R$-module$B\in \mathcal{I}$of$\mathcal{T}$satisfying.

$\mathcal{T}$$\mathcal{T}$$\mathcal{I}$$\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{l}_{0,\backslash }\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}$than $\{O\}$ and $T,$ $T$ is simple.

$V$$AV\subset V$for every$A\in \mathcal{T}$.

and the entire $R$-module $K(R)^{n}$ are always
Note that the -dimensional sub $lR$-module
is reducible if there is a -invariant sub $R$-module of-subalgebra ofinvariant.
$K(R)^{n}$ other thanand $K(R)^{n}$ , and irreducible otherwise. For example, consider$0$$\mathcal{T}-$$\{0\}$$\mathrm{A}*$$\mathcal{M}_{n}(K, R)$$\mathcal{T}$$\mathcal{T}$$\{0\}$$\mathcal{T}_{1}$$=$$\mathcal{T}_{2}$$=${diag $(A, P^{T}AP)$ :$\mathcal{M}_{n}(R)\oplus\tau_{1}$$A\in \mathcal{M}_{n}(R)\}$,

orthogonal matrix. Then
is an
where
is neither simple nor irreducible.
$P\in \mathcal{M}_{n}(R)$,$n\cross n$$\mathcal{T}_{1}$is simple but not irreducible, and$\mathcal{T}_{2}$Theorem 5.4.
$(A)$

Let
be a -subalgebra ofsimple -subalgebras$*$$\mathcal{T}$$*$$P^{T}TP$$=$If a -subalgebra$*$$\mathcal{T}$

of

{diag

$\mathcal{M}_{n}(R)$irreducible -subalgebra
$*$

If a

-subalgebra
that

$*$

$\mathcal{M}_{n}(R)$such.

$\mathcal{T}$

of

...

$\mathcal{T}’$of$(A_{1},$ $A_{2},$and$\oplus \mathcal{T}_{\ell}$$\ldots,$$A\ell)$: $A_{j}\in \mathcal{T}_{j}(j=1,2,$$\ldots,l)$is simple, there is an orthogonal matrix
such that$\mathcal{M}_{n}(R)${diag $(B,$ $B,$

and an$\ldots,$$B)$:$B\in \mathcal{T}’$}.

is irreducible then there exists an orthogonal matrix $P\in$$-$$P^{T}\mathcal{T}P=\tilde{\rho}(\mathcal{M})$$\mathcal{M}=\mathcal{M}_{n}(R),$$(\tilde{\rho}, R^{n})$}.

$P\in \mathcal{M}_{n}(R)$

.

Here

and

$P\in \mathcal{M}_{n}(R)$$\mathcal{M}_{n’}(R)$$P^{T}\mathcal{T}P=$$(C)$. Then there is an orthogonal matrix
such that$\mathcal{T}_{1}\oplus \mathcal{T}_{2^{\oplus}}$

$=$

$(B)$

$\mathcal{M}_{n}(R)$$\mathcal{T}_{j}of.\mathcal{M}_{n_{\mathrm{j}}}(R)(j=1,2, \ldots, \ell)$$\mathcal{M}_{n/2}(g, R)$

denotes the faithful -representation of$*$or$\mathcal{M}$$\mathcal{M}_{n/4}(aeT, R)$,

given in Section 3.

17

To prove the theorem, we need a series of lemmas.
Lemma 5.5. If a subalgebra has a faithful representation
then is simple.
Proof: See Theorem 1.16 of [7]. 1$\mathcal{T}$such that$(\rho, R^{n})$$\rho(\mathcal{T})$is irreducible,$\mathcal{T}$be a faithful representation of such thatbe a subalgebra, and let
Lemma 5.6. Let
is irreducible. Thenis irreducible. Let $(\rho’, R^{n})$ be a representations of $T$ such that$\rho’(A)=s^{-}1\rho(A)S$.
$n=n’$ and there exists a nonsingular matrix
such thatfor everyof [28]. 1
Proof: See Corollary of Theorem 1.15 of [7], and Theorem$(\rho, R^{n})$$\mathcal{T}$$\mathcal{T}$$\rho’(\mathcal{T})$$\rho(\mathcal{T})$$S$$A\in \mathcal{T}$$(3.3.\mathrm{E})$

Lemma 5.7. If a subalgebra$\mathcal{T}$of$(\rho’, IRn)$ofis irreducible then there is a faithful representation$\mathcal{M}_{n}(R)$$\mathcal{M}=\mathcal{M}_{n}(R),$$\mathcal{M}_{n/2}(^{g}., R)$or$\mathcal{M}_{n/4}(RT, R)$such that $\rho’(\mathcal{M})=T$ .
Proof. The lemma follows directly from Wedderbums’s Theorem. See Theorem 1.17 of [7], andChapter III, Section 4 of [28]. 1$\cdot$be a faithful *-representation of such that
Lemma 5.8. Let be a -subalgebra, and let
is irreducible. Thenbe a -representation of such thatis irreducible. Let.
$n=n’$ and $ere$ exists an orthogonal matrix $P$ such that $\rho’(A)=P^{T}\rho(A)P$ for every
t.hsuch that
Proof: By Lemma 5.6, $n=n’$ and there is a nonsingular matrix$*$$\mathcal{T}$$(\rho, R^{n})$$*$$(\rho’, R^{n’})$$\rho(\mathcal{T})$$\mathcal{T}$$\rho’(\mathcal{T})$$\mathcal{T}$$A\in \mathcal{T}$$S\in \mathcal{M}_{n}(R)$$\rho’(A)=S^{-1}\rho(A)S$

By the assumption$(\rho, R^{n})$and$(\rho’, lR^{n’})$$A\in \mathcal{T}$$A\in \mathcal{T}$.

are *-representations of , so that the relation$S^{-1}\rho(A)s$holds for every

for every$\mathcal{T}$$=$$(\rho’(A)^{*})^{*}$$=$$(\rho’(A*))*$$=$$(S^{-1*}\rho(A)s)^{*}$$=$$S^{*}\rho(A)(s*)-1$; hence$(SS^{*})B(Ss*)^{-1}=B$

for every$B\in\rho(\mathcal{T})$.

by assumption, and all theis an irreducible subalgebra of
In the relation above,$SS^{*}$$R$is symmetric. By applying Schur’s lemma (seeare in since
eigenvalues of the matrix[28]
their proofs), we know that all the eigenvalues
and
of
[7],
Lemma
and
Theorem 1.8 of$SS^{T}=\alpha I$. Hence, letting $P=S/\sqrt{\alpha}$, we obtain thatandare the same$\mathcal{M}_{n}(R)$$\rho(\mathcal{T})$$SS^{*}$$(3.1.\mathrm{C})$$\alpha(\neq 0)$,$P^{T}P$$=$$I$$\rho^{f}(A)$$=$$S^{-1}\rho(A)S=P^{T}\rho(A)P$for every $A\in T$ .

18-subalgebra of$(Q_{1}, Q_{2}, \ldots, Q_{m})\in \mathcal{M}_{n}(R)$ , whereis an, such that

Lemma 5.9. Let $T$ be a$*$$\mathcal{M}_{n}(R)$$Q_{i}$$n\cross n_{i}$. Then there is an orthogonal matrix $P=$

matrix $(\dot{i}=1,2, \ldots, m)$ and $n_{1}+n_{2}+\cdots+n_{m}=$$n$$P^{T}\mathcal{T}P$$=$$\equiv$$\mathcal{T}_{i}’$$\{d_{\dot{i}}ag(Q_{1}^{\tau_{AQ}\tau_{AQ_{2}}\tau}1, Q2’\cdots, QmAQ_{m}):A\in \mathcal{T}\}$is an irreducible -subalgebm of$*$$\{Q_{i}^{T}AQi:A\in \mathcal{T}\}$$(_{\dot{i}}=1,2, \ldots,m)$,$\mathcal{M}_{n}(:R)$.

(i) If is irreducible, the lemma obviously holds with $m=1$ and $P=Q_{1}=I$ . If
with $1\leq k_{1}<n$ . Let
is reducible, there is -dimensional -invariant sub $R$-module $V$ of

Proof:$\mathcal{T}$$\mathcal{T}$$k_{2}=n-k_{1}$$Q_{i}$

is an$R^{n}$$\mathcal{T}$$k_{1}$. We will show that there is an orthogonal matrix $P=(Q_{1}, Q_{2})\in \mathcal{M}_{n}(R)$ , where$n\cross k_{i}$matrix $(\dot{i}=1,2)$ , such that,(15)-subalgebra of $\mathcal{M}_{k}.(R)(\dot{i}=1,2)$ .

(16)$P^{T}\mathcal{T}P=\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(Q_{1}^{\tau_{AQ1}T}, Q_{2}AQ_{2}):A\in T\}$$\mathcal{T}_{i}’\equiv\{Q^{\tau_{A}}iQi:A\in T\}$is$\mathrm{a}^{*}$,
be an orthonormal basis of the -dimensional -invariant sub $R$-moduleLetof , and Let $p_{k_{1}+1},p_{k}1+2’\ldots,pn$ be an orthonormal basis of the orthogonal complementof . Define$p_{1},p_{2},$$\mathcal{T}$$k_{1}$$\ldots$$V$$p_{k_{1}}$$V^{\perp}$$R^{n}$$V$$Q_{2}\equiv(p_{k_{1}+1},pk_{1}+2’\ldots,pn),$$Q_{1}\equiv(p_{1},p_{2}, \ldots,p_{k_{1}}),$, we see that-subalgebra ofSince isthat
-invariance of the sub $R$-module of$\mathcal{T}$$\mathcal{M}_{n}(R)$$\mathrm{a}^{*}$$V$$\mathcal{T}$$A^{T}\in \mathcal{T}$$P\overline{=}(Q_{1}, Q_{2})\in \mathcal{M}_{n}(R)$for every$A\in \mathcal{T}$.

. It follows$\mathrm{h}\mathrm{o}\mathrm{m}$the$R^{n}$$Ap_{j}$$\in$$V(j=1,2, \ldots, k_{1})$for every$A\in \mathcal{T}$,$A^{T}p_{j}$$\in$$V(j=1,2, \ldots, k_{1})$for every$A\in \mathcal{T}$

.

.

Hence
$(p_{i})^{T}Ap_{j}$$=$$0(j=1,2, \ldots, k_{1}, i=k_{1}+1, k_{2}+1, \ldots, n)$$(p_{i})^{T}A^{\tau}\mathrm{p}_{j}$$=$$0(j=1,2, \ldots, k_{1}, i=k_{1}+1, k_{2}+1, \ldots, n)$This implies$Q_{i}^{T}AQ_{j}=O(i\neq j)$

Thus we obtain (15). The
subalgebra.

$\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i},\mathrm{o}\mathrm{n}(16)$follows

for every$A\in \mathcal{T}$.

$\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}1.\mathrm{y}.\mathrm{f}_{\mathrm{f}\mathrm{o}\mathrm{m}}(15)$for every
for every$A\in \mathcal{T}$,$A\in \mathcal{T}$.
(17)

and the definition of a

$*-$

or
is reducible, we can repeatedly apply the(ii) As long as the resultant subalgebra(i)
obtainthe desired result. 1
of
them
to
above to either or bothargument$T_{2}’$$\mathcal{T}_{1}’$Lemma 5.10. Let
such that bothorthogonal matrix
Proof: (i) Let
such that$(\rho, R^{n})$$\rho(\mathcal{M})$andbe faithfut representations of a simple subalgebra
are irreducible -subalgebras. Then $n=n’$ and there exists an.
such that. By Lemma 5.6, we can take a nonsingular matrix

and$\rho’(\mathcal{M})$$P\in \mathcal{M}_{n}(R)$$\mathcal{T}=\rho’(\mathcal{M})$$(\rho’, R^{n’})$$\mathcal{M}$$*$$\rho’(\mathcal{M})=P^{T}\rho(\mathcal{M})P$$S\in \mathcal{M}_{n}(R)$$\mathcal{T}=S^{-1}\rho(\mathcal{M})s$

.

(18)

19

Since $S^{T}S$ is a positive definite matrix, we can take an orthogonal matrix
and a$(\dot{i}=1,2, \ldots , n)$ such that $P_{1}^{T}S^{\tau}sP_{1}=D^{2}$diagonal matrix $D$ with positive diagonal entries.
Here each diagonal entryofcorresponds to a positive eigenvalue of $S^{T}S$ . It follows that
$P_{1}\in \mathcal{M}_{n}(R)$$D_{ii}$$D_{ii}^{2}$$D^{2}$$I=D^{-1}P\tau S1SP1\tau D-1=(SP_{1}D-1)\tau_{S}P1D-1$ .

Letting $P_{2}=SP_{1}D^{-1}\in \mathcal{M}_{n}(R)$ , we obtain $S=P_{2}DP_{1}^{T}$ , and $P_{2}^{T}P_{2}=I(i.e., P_{2}\in \mathcal{M}_{n}(R)$is an orthogonal matrix). Hence it follows from the equality (18) that($\mathcal{T}=P_{1}D-1P2T\mathcal{M})P2DP_{1}\tau\rho$

Since both$\mathcal{T}$and$\rho(\mathcal{M})$are *-subalgebras of.

$\mathrm{A}4_{n}(R)$

.

(19)

, we then have$P_{1}D^{-1T\tau}P\rho 2(\mathcal{M})P2DP1=T=\mathcal{T}^{T}=P_{1}DP_{2\rho}^{T-}(\mathcal{A}4)P2D1PT1$.

Thus we obtain that(20)

$P_{2}^{\tau}\rho(\mathcal{M})P_{2}=D2P_{2}^{T2}\rho(\mathcal{M})P_{2}D^{-}$

be a sub $R$-module ofand $E$ be an $m\cross m$ nonsingular symmetric matrix.
$E^{2}V=V$ . We will show that
Assume that is -invariant,$EV=$
is $E$-invariant,$k=\dimV$
V. Let. Under the assumption we can take a set of eigenvectors,of the symmetric matrix
which forms a basis of . Since
are eigenvectorsof the matrix $E$ too and the eigenvalues
of $E$ associated with them are real andnonzero, we obtain that(ii) Let$R^{m}$$d\mathrm{Y}$$V$$E^{2}$$V$$\dot{i}.e.,$$\dot{i}.e.,$$k$$E^{2}$$V$$\lambda_{1},$$\lambda_{2},$$w_{1},$ $w_{2},$$w_{1},$ $w_{2},$$\ldots,$$\ldots$$w_{k}$$w_{k}$$\lambda_{k}$$\ldots,$$EV=E \{_{j=1}\sum^{k}\alpha_{jj}w$: $\alpha_{j}\in R\}=\{\sum_{j=1}^{k}\alpha j\lambda jwj:\alpha_{j}\in R\}=V$.

(iii) Consider the linear transformation$\phi$

in$\mathcal{M}_{n}(R)$such that$\phi(A)=DAD^{-1}$or component-wisely$\phi(A)_{ij}=D_{ii}D_{jj}^{-}1A_{ij}(\dot{i},j=1,2, \ldots, n)$for$\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}\gamma A\in \mathcal{M}_{n}(R)$. Then the equality (20)$\mathrm{c}\mathrm{a}\mathrm{n},\mathrm{b}\mathrm{e}$rewritten as$P_{2}^{T\tau}\rho(\mathcal{M})P_{2}=\phi(\phi(P\rho(2\mathcal{M})P2))$

.

(21)

If we identify
with the -dimensional Euclidean space, then the linear transformation incorresponds to a linear transformation associated with the
diagonal$(\dot{i},j=1,2, \ldots , n)$ , and the identity (21) implies thatmatrix $E$ with positive entries
the sub $IR$-module ofcorresponding to the sub $R$-moduleofinvariant. Hence we see by the result shown in (ii) above that$R^{n^{2}}$$n^{2}$$\mathcal{M}_{n}(R)$$\phi$$n^{2}\cross n^{2}$$\mathcal{M}_{n}(R)$$D_{ii}D_{jj}^{-1}$$R^{n^{2}}$$P_{2}^{T}\rho(\mathcal{M})P2$$\backslash \cdot$$\mathcal{M}_{n}(R)\mathrm{i}\mathrm{s}..E^{2}-$$P_{2}^{T}\rho(\mathcal{M})P_{2}=\phi(P_{2}\tau\rho(\mathcal{M})P_{2})$or$P_{2}^{T}\rho(\mathcal{M})P_{2}=DP_{2\rho(\mathcal{M})PD^{-}}^{T1}2$.

Finally, substituting the equality above into (19) and letting $P=P_{2}P_{1}^{T}$ , we obtain that$\mathcal{T}=P_{1}D^{-1}P^{T\tau}2\rho(\mathcal{M})P2DP_{1}=P_{1}P_{2}^{\tau_{\rho(}}\mathcal{M})P_{2}P_{1}T=P^{T}\rho(\mathcal{A}4)P$.

20

Now we are ready to prove Theorem 5.4. Let
as in Lemma 5.9. Let
orthogonal matrix$\mathcal{T}$be a -subalgebra of$*$$\mathcal{M}_{n},(R)$. Take an$P\in \mathcal{M}_{n}(R)$$\mathcal{T}_{1}$$=$$\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(Q_{1}TAQ_{1}, Q_{2}\tau AQ2, \ldots, Q_{p}\tau AQ)$$\mathcal{T}_{j}’$$=$$\{Q_{j}TAQj:A\in \mathcal{T}\}(j=1,2, \ldots, m)$$\mathcal{I}_{j}’$$=$$\{Q_{1}^{\tau_{A}}Q1$:$A\in \mathcal{T}\}$,,: $Q^{T}jAQj=\mathit{0},$ $A\in T\}(j=1,2, \ldots, m)$ .

is irreducible, so that it is simple by Lemma 5.5. Also we can easily verify that each
Then each
forms an ideal of . Hence$\mathcal{T}_{j}’$$\mathcal{T}_{1}’$$\mathcal{I}_{j}’$or$\mathcal{I}_{j}’=\{O\}$$\mathcal{T}_{1}’(j=1,2, \ldots, m)$.

We may assume without loss of generality thatFor$\mathrm{e}.\mathrm{v}$$\mathcal{I}_{j}’$$=$$\{O\}(j=1,2, \ldots,p)$ ,$\mathcal{I}_{j}’$$=$$\mathcal{T}_{1}’(j=p,p+1, \ldots, m)$

(22)

.

ery $j=1,2\ldots,p$ , the mapping$\rho_{j}$: diag$(Q_{1}^{T\tau}AQ_{1}, Q2QA2, \ldots , Q_{p}^{\tau_{A}}Q_{p})\in \mathcal{T}_{1}arrow Q_{j}^{T}AQ_{j}\in \mathcal{T}_{j}’$is asuch that $\rho_{j}(I)=I$ . This implies that
onto
forms a homomorphism from:is faithful.
is irreducible. In particular,such that
representation ofis simple by Lemma 5.5. Applying Lemma 5.8, we then see that $n_{j}=n_{1}(j=1,2, \ldots,p)$
Hence
and
$Q_{j}^{T}AQ_{j}=R_{j}^{T}Q^{\tau}1AQ_{1j}R$ for every $A\in T$ .
$T_{1}$$T_{1}$$(\rho_{j}, R^{n_{j}})$$\mathcal{T}_{j}’$$\mathcal{T}_{1}arrow \mathcal{T}_{1}’$$\mathcal{T}_{j}’=\rho_{j}(T_{1})$$\rho_{1}$$T_{1}$

for some$n_{1}\cross n_{1}$orthogonal matrix $R_{j}(j=1,2, \ldots,p)$ . Therefore we obtain that$\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(Q1Q\tau_{A}1’ Q^{\tau T}2AQ2’\cdots, QpAQ_{p})$$=$$\mathcal{T}_{1}$

{diag
{diag

$=$

$=$

:

$A\in \mathcal{T}\}$$(Q_{1}^{T}AQ1’ R_{2}^{T\tau\tau}Q1AQ_{12}R, \cdots, RQ_{1}pQ\tau_{A}R1p):A\in T\}$$(B, R_{2p}^{\tau_{B}}R_{2}, \cdots, R_{p}TBR)$:$B\in \mathcal{T}_{1}’\}$

hence the assertions (A) and (B)If $p=m$ thenthere is a matrix $A_{j}\in T$ such that
$T=\mathcal{T}_{1;}$$Q_{1}^{\tau_{A_{j}}}Q_{1}=I\in \mathcal{T}_{1}’\subset \mathcal{M}_{n_{1}}(R)$and$.\mathrm{f}‘ 0$llow. Suppose that $p<m$ . By (22),$Q_{j}^{T}A_{j}Q_{j}=O\in T_{j}’\subset \mathcal{M}_{n_{j}}(R)$$(j=p+1,p+2, \ldots,m)$ . Define$\hat{A}$$=$$\prod_{j=p+1}^{m}A_{j}\in T\subset \mathcal{M}_{n}(R)$and$\cdot\cdot\tilde{A}=I-\hat{A}\in \mathcal{T}\subset \mathcal{M}_{n}(R)$Then$P^{T}\hat{A}P$$P^{T}\tilde{A}P$

$=$

$=$

$O$ )
,
diag (I, . . . , $I,$ $O,$$(O, \ldots, O, I, \ldots, I)\in P^{T}\mathcal{T}P$ .
diag$\in P^{T}\mathcal{T}P$$\ldots,$

.

21

Hence
$P^{T}\hat{A}\mathcal{T}P$$P^{T}\tilde{A}\mathcal{T}P$$=$$\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(Q_{1}^{\tau}AQ1, \ldots, QpQTAp’ oo, \ldots,)$$=$$\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}$It is easily seen that:

$A\in \mathcal{T}\}\subset P^{T}\mathcal{T}P$:$(O, \ldots , O, Q_{p+1}^{\tau T}AQ_{p1}+’\ldots, Q_{mm}AQ)$$P^{T}\hat{A}\mathcal{T}P$

is an ideal of$P^{T}\mathcal{T}P$; hence$\mathcal{T}$,$A\in \mathcal{T}\}\subset P^{T}\mathcal{T}P$.

can not be simple. If we define$\tilde{\mathcal{T}}=\{\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(Q_{p+1}^{TT}AQp+1’\ldots, Q_{mm}AQ)$:$A\in \mathcal{T}\}$

then$P^{T}\mathcal{T}P\supset P^{T}\hat{A}\mathcal{T}P+P^{T}\tilde{A}TP=\mathcal{T}_{1}\oplus\tilde{\mathcal{T}}$,.

By the construction, we obviously see that
$P^{T}\mathcal{T}P\subset \mathcal{T}_{1}\oplus\tilde{\mathcal{T}}$.

$P^{T}\mathcal{T}P=\mathcal{T}1^{\oplus\tilde{\mathcal{T}}}$.

Therefore we have shown that

Applying the(A).

.ame argument as a.bove$\mathrm{s}$repeatedly to the, we obtain the assertion$*- \mathrm{s}\mathrm{u}\mathrm{b}.\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}\tilde{\tau}$. By
is an irreducible -subalgebra of
Now prove the assertion (C). Suppose that
. Letofsuch thatbeLemma 5.7, there is a faithful representation
are *-subalgebras,
given in Section 3. Since both andthe faithful *-representation of
we obtain the desired result by Lemma 5.10. This completes the proof of Theorem 5.4.
$*$$\mathcal{T}$$(\rho’, R^{n})$$\mathcal{T}$$\mathcal{M}$$\mathcal{M}_{n}(R)$$\rho’(\mathcal{M})=\mathcal{T}$$\mathcal{M}$$(\tilde{\rho}, R^{n})$$\tilde{\rho}(\mathcal{M})$

References[1] W. F. Alizadeh, “Interior point methods in semidefinite programming with applications to
combinatorial optimization,” SIAM Joumal on Optimization 5 (1995) 13-51.
[2] W. F. Alizadeh, J-P. A. Haeberly and M. J. Overton, “Primal-dual interior-point methods”
for semidefinite
Technical paper, Computer Science Department, Rutgers
University, August, 1994.
$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{t}^{\mathrm{a}\mathrm{m}}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g},$[3] B. D. Craven and B. Mond, “Linear programming with matrix variables,” Lin ear Algebra
and Its Applications 38 (1981) 73-80.

[4] S. Boyd, L. E. Ghaoui, E. Feron and V. Balakrishnan, Linear
and Control Theory, (SIAM, Philadelphia, 1994). .
[5] R. W.Cottle, J. S. Pang, R.
Press, New York, 1992).

$Matr\dot{i}x$

Inequalities in System

E.. Stone, The Linear Complementarity Problem, (Academic[6] O. G\"uler, “Barrier functions in interior point methods,” Dept. of Mathematics and Statistics,
University of Maryland Baltimore County, Baltimore, Maryland 21228, USA, 1994.
[7] N. Iwahori, Taishougun to ippan senkeigun no hyougenron (The Representation Theory ofSymmetric Group and General Linear Group) in Japanese, Iwanami, Kiso sugaku, Senkei
daisu vi (iwanami shoten, 1978).

22[8] M. Kojima, N. Megiddo, T. Noma, A. Yoshise, A Unified Approach to Interior Point Al538,
lems,
Notes in Computer
gorithms for Linear $Complementar\dot{i}ty$(Springer-Verlag, New York, 1991).

Pro.b

Scie.nce$\mathrm{L}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{u}\prime \mathrm{r}\mathrm{e}\backslash$for linear
point
-dual
[9] M. Kojima, S. Mizuno and A. Yoshise, “A$Inter\dot{i}or$-Point
Programming,ed.,inMathematical
Progress
In
N.
Megiddo,programming,”
and Related Methods (Springer-Verlag, New York, 1989) 29-47.
$\mathrm{p}\mathrm{r}\mathrm{i}\acute{\mathrm{m}}\mathrm{a}\mathrm{l}$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}1_{1^{-}}\mathrm{m}$$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}_{\mathrm{o}\mathrm{r}}$[10] M. Kojima, S. Mizuno and A. Yoshise, “A polynomial-time algorithm for a class of linear
complementary problems,” Mathematical Programming 44 (1989) 1-26.
[11] M. Kojima, S. Mizuno and A. Yoshise, “An $O(\sqrt{n}L)$ iteration potential reduction algorithm
for linear complementarity problems,” Mathematical Programming 50 (1991) 331-342.
[12] M. Kojima, S. Shindoh and S. Hara, “Interior-point methods for the monotone semidefinite
linear complementarity problems in symmetric matrices,” Research Reports B-282, Dept. ofInformation Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, April
1994, Revised Apri11995, to appear in SIAM Journal on Optimization.
[13] K. O. Kortanek and J. Zhu, “A polynomial algorithm for convex programming problems
scaled Lipschitz condition,” Working Paper Series 90-17, Dept. of Management
satis
Sciences, College of Business Administration, The University of Iowa, Iowa City, Iowa 52242,$q_{\mathrm{i}}\mathrm{n}\mathrm{g}$1990.
[14] I. J. Lustig, “Feasibility issues in primal-dual interior-point method
Mathematical Programming 49 (1990/1991) 145-162.

for- linear programming,”[15] I. J. Lustig, R. E. Marsten and D. F. Shanno, “Computational experience with a primaldual interior-point method for linear programming,” Linear Algebm and Its Applications 152(1991) 191-222.
[16] R. Marsten, R. Subramanian, M. Saltzman, I. Lustig and D. Shanno, “Interior point methods”
for linear progranmin. Just call Ne.w.t0n, Lagrange, and Fiacco andInterface
20 (1990) 105-116.
..

g..

$\mathrm{M}\mathrm{c}\mathrm{C}_{0}\mathrm{r}\mathrm{m}\mathrm{i}_{\mathrm{C}\mathrm{k}!}$[17] N. Megiddo, “Pathways to the optimal set in linear programming,” In N. Megiddo, ed.,
Methods (Springer-Verlag,
Progress in Mathematical Programming,
New York, 1989) 131-158.

Inter.ior-Point and.R.elated[18] S. Mizuno, M. Kojima and M. J. Todd, “
reduction algorithms for linear programming,”$\bullet$point primal-dual potentialOptimization 1 (1995)$\mathrm{I}\mathrm{n}\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}- \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}_{\mathrm{o}\mathrm{r}}$SIAM$J_{oum,\mathrm{t}}alo.n$

52-67.
[19] R. D. C. Monteiro and I. Adler, “Interior path following primal-dual algorithms. Part I:
Linear programming,” Mathematical Programming 44 (1989) 27-41.
[20] R. D. C. Monteiro and I. Adler, “Interior path following primal-dual algorithns. Part II:
Convex quadratic programming,” Mathematical Programming 44 (1989) 43-66.

[21] Y. E. Nesterov and A. S.Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications (SIAM, Philadelphia, 1993).
[22]

and’

“
in
erior-point
and
M. J.
. Nesterov
programming,” Catholic University of Louvain, Louvain-la-Neuve, Belgium, 1994.
$\mathrm{Y}^{\backslash }.\mathrm{E}’$$\mathrm{S}\mathrm{e}\mathrm{l}\mathrm{f}- \mathrm{S}\mathrm{C}\dot{\mathrm{a}}\mathrm{i}_{\mathrm{e}}\mathrm{d}\mathrm{c}\mathrm{o}\mathrm{n}\dot{\mathrm{e}}\mathrm{s}$$\mathrm{T}\mathrm{o}\mathrm{d}\dot{\mathrm{d}},$$\mathrm{i}\mathrm{n}\dot{\mathrm{t}}$$\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{d}_{\mathrm{S}}t$$\dot{\mathrm{n}}\mathrm{o}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}$23[23] A. Packard, K. Zhou, P. Pandey and G. Becker, “A collection of robust control problems
leading to LMI’s,” Proceedings of the 30th Conference on Decision and Control, Brighton,
England, December 1991, pp.1245-1250.
[24] F. A. Potra and Y. Ye, “Interior point methods for nonlinear complementarity problems,”
Technical report, Dept. of Mathematics, The University of Iowa, Iowa City, Iowa 52242, 1991.
[25] C. E. Rickart, General Theory of Banach Algebras, (Van Nostrand Co., 1960).
[26] K. Tanabe,
K. Yajima,“Centered Newton method for mathematical programming,” In M. Iri and, System Modeling and ’ptimization (Springer-Verlag, New York, 1988).

$\mathrm{e}\mathrm{d}\mathrm{s}.$$O$[27] L. Vandenberghe and S. Boyd, “A primal-dual potential reduction method for problems
involving matrix inequalities,” Mathematical Programming, Series $B69$ (1995) 205-236.
[28] H. Weyl, The Classical Groups, Princeton University Press, Princeton, New Jersey, 1946.
[29] Y. Zhang, “On the convergence of an infeasible interior-point algorithm for linear programming and other problems,” SIAM Journal on $O.p$ timization 4 (1994) 208-227.