Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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

share|improve this answer
    
One particular difficulty with your phase I problem is that many problems have no strictly interior feasible solutions (i.e. the optimal $s$ in your phase I problem is $s^{*}=0$.) –  Brian Borchers Jun 28 '11 at 16:13

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

share|improve this answer
    
Thanks for commenting Brian. I am aware that illconditioning is a potential problem for barrier methods, but when I solved the original problems with some random data this was not an issue. However, as soon as I tried the feasibility problem with the same data, even the inital Hessian became terribly illconditioned ($\kappa>10^{17}$). This surprised me, as I thought that the feasibility problem was a problem of the same type as the original problems, just a different objective, and an extra variable. As you say, using e.g. SeDuMi to initalize the algorithm might be a good idea. –  Justus Jun 28 '11 at 20:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.