Problems finding feasible points with respect to linear matrix inequalty constraints

Question

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

Answer 1

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

Answer 2

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