JIPAM logo: Home Link
   
  Volume 5, Issue 1, Article 14
 
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}$.

         
       
  Download Screen PDF
  Download Print PDF
  Send this article to a friend
  Print this page
  

      search [advanced search] copyright 2003 terms and conditions login