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 Accepted: 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 $ xin 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://jipam.vu.edu.au

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