Problems finding feasible points with respect to linear matrix inequalty constraints Hi!
I'm a trying to learn the basics of semidefinite programming
and how to solve problems with linear matrix inequalities.
Inspired by the book "Convex Optimization" by Boyd and Vandenberghe (can be downloaded for free
here) I decided to try and implement a simple barrier method in Matlab. My program 
looks very much like this one, and have worked well for some simple test problems
(e.g. compared with results from SDPT3), of the form
$\min_{x} \qquad c^{T}x$ 
subject to $\sum_{i=1}^{m}F_{i}x_{i} - G \succeq 0$, 
where $x,c\in\mathbb{R}^{m}$, $F_{i},G$ symmetric and 
$\in\mathbb{R}^{p\times p}$. 
In order make my program easier to use I have also 
tried to implement a code that should find a strictly feasible 
starting point point, based on solving the problem (referred to here as the feasibility problem)
$\min_{s,x} \qquad s$ 
subject to $\sum_{i=1}^{m}F_{i}x_{i} - G + sI \succeq 0$, 
where $s\in\mathbb{R}$, and $I$ is an identity matrix. A strictly feasible point to this problem
can be found by taking $x$ arbitrary and then $s$ greater than the smallest 
eigenvalue of $\sum_{i=1}^{m}F_{i}x_{i} - G$. Now, if we find $s<0$, 
then the corresponding $x$ is strictly feasible and we can proceed to solve the original 
problem. This should be pretty straightforward I thought; however, it turns out that the
Hessian of the feasibility problem (see below) becomes extremely illconditioned, sometimes even having small negative eigenvalues, and the resulting Newton search directions are useless. This seems to be the case regardless of the problem data, so my question is thus:

Is my approach to find feasible points fundamentally flawed, i.e. not just simple programming errors etc, in some way?

Kind regards 
Justus

The Hessian for the feasibility problem is given by
$H_{ij} = trace(SF_{i}SF_{j})$, 
where
$S = (\sum_{i=1}^{m+1}F_{i}x_{i} - G)^{-1}$,
 in which $F_{m+1} = I$, and $x_{m+1} = s$. (As may be noted, I consider the feasibility problem to be an instance of the original problem but with one additional variable.)
 A: There are a number of widely used primal--dual interior point codes for SDP, including SeDuMi, SDPA, SDPT3, and CSDP.  Of these, SeDuMi approaches this problem by using the self dual embedding, while the others are "infeasible interior point methods" that start with primal/dual solutions that are positive definite but do not necessarily satisfy the linear equality constraints.  You'd do well to consider these approaches to initilizing your algorithm instead of using your phase I problem.    
You should be aware that the ill conditioning you're seeing is characteristic of barrier methods- getting accurate solutions can be quite challenging and the codes typically take extensive steps to deal with the ill-conditioning (scaling, iterative refinement, etc.)  
A: Sorry, couldn't find a way to edit my own question. Anyway, just to be clear about one thing, I take the initial value of $s$ to be positive and larger in magnitude than the magnitude of the smallest eigenvalue of $\sum_{i=1}^{m}F_{i}x_{i} - G$ (assuming that this eigenvalue is negative of course), so the inital $(x,s)$ is of course feasible.
Justus
