JIPAM

The Boundary of Weighted Analytic Centers for Linear Matrix Inequalities  
 
  Authors: Shafiu Jibrin, James W. Swift,  
  Keywords: Linear matrix inequalities, Analytic center, Central path, Semidefinite programming.  
  Date Received: 28/10/03  
  Date Published: 03/02/04  
  Subject Codes:

90C22, 15A39, 49M15, 90C53

  
  Editors: Fuzhen Zhang,  
 
  Abstract:

We study the boundary of the region of weighted analytic centers for linear matrix inequality constraints. Let $ {}$ be the convex subset of $ {\mathbb{R}% ^{n}}$ defined by $ q$ simultaneous linear matrix inequalities (LMIs)$ {}$

$\displaystyle {A^{(j)}(x):=A_{0}^{(j)}+\sum_{i=1}^{n}x_{i}A_{i}^{(j)}\succ 0}, j=1,2,\dots ,q,$    
where $ A_{i}^{(j)}$ are symmetric matrices and $ x\in \mathbb{R}^{n}$. Given a strictly positive vector $ \omega =$ $ (\omega _{1},$ $ \omega _{2},$ $ \dots ,$ $ \omega _{q})$, the weighted analytic center $ x_{ac}(\omega )$ is the minimizer of the strictly convex function
$\displaystyle {\phi _{\omega }(x):=\sum_{j=1}^{q}\omega _{j}\log \det [A^{(j)}(x)]^{-1}}$    

over $ \mathcal{R}$. The region of weighted analytic centers, $ \mathcal{W}$, is a subset of $ \mathcal{R}$. We give several examples for which $ \mathcal{% W}$ has interesting topological properties. We show that every point on a central path in semidefinite programming is a weighted analytic center.

We introduce the concept of the frame of $ \mathcal{W}$, which contains the boundary points of $ \mathcal{W}$ which are not boundary points of $ \mathcal{R}$. The frame has the same dimension as the boundary of $ % \mathcal{W}$ and is therefore easier to compute than $ \mathcal{W}$ itself. Furthermore, we develop a Newton-based algorithm that uses a Monte Carlo technique to compute the frame points of $ \mathcal{W}$ as well as the boundary points of $ \mathcal{W}$ that are also boundary points of $ \mathcal{R}$.;


This article was printed from JIPAM
http://140.159.26.65/jipam

The URL for this article is:
http://140.159.26.65/jipam/article.php?sid=366