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.)