1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$.) $\endgroup$ Jun 28, 2011 at 16:13
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Justus
    Jun 28, 2011 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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