Scaling and numerical stability

1

Dear all,

I have a numerical issue when I use CVX (by SeDuMi and SDPT3) to solve an SDP problem of the form
$$\begin{array}{rl}\displaystyle\max_{{x_{nk},~y_{nk}}{n,k}}&\displaystyle\sum_n\sum_k y{nk}\{\rm s.t.~}&\displaystyle f(x_{nk})-y_{nk}{\bf I}N\succeq{\bf 0},\&\displaystyle y{nk}\geq 0,\end{array}$$
where f(x_{nk}):{\mathbb R}\mapsto\mathbb{S}^N_+ is a linear function of x_{nk} for all n and k.

If I scale the optimization variable y_{nk} by a proper scaling factor, say, \alpha=10, or 100, the linear SDP problem can be solved by CVX with cvx_status = Solved. But, usually, if I fixed \alpha=1 due to the difficulty of the choice of \alpha, the CVX will return the result with Inaccurate/Solved.

So, how can I improve the numerical stability of such kind of problems?

Thank you very much.

2

You’re actually doing exactly the right thing already! This kind of scaling is done by some solvers, particularly the professional ones, but not by SeDuMi and SDTP3.

3

Thank you very much.
The key issue in my work is that I employ the alternating optimization approach to successively update the variable \{x_{nk},y_{nk}\} and another set of variables. So, at each iteration, the stability issue above will arise, and an ideal case is that I can automatically select a good enough \alpha at each iteration to guarantee the accuracy.

However, I have no any good idea to choose a good \alpha. Oh, my \alpha!!

Thank you again.

4

Try one of the professional solvers, like MOSEK or Gurobi. I think they tend to be more aggressive about scaling.

5

Btw, this is some kind of dumb question but I shall put it fourth because I think I’m experiencing trouble because of this. Before I pass the problem data to CVX I do apply scaling to my objective function $norm(Ax)$ (which is a norm minimization so I scale its independent columns by a factor corresponding to the column norm), but I do not apply any scaling to the data in the semidefinite constraints which also depend on x. Then I ask the following: if I apply scaling to any piece of data, do I have to apply it throughout? I mean all coefficients the variable is dependent upon should receive that same scaling?

6

You want the unscaled scaled problem to be mathematically equivalent or recoverable from the solution of the scaled problem if exact arithmetic were used. So the combination of adjustments needed to various parts of the model depends on the problem.