ololo
ololo
Following the tragic death of Jos F. Sturm, the original author of SeDuMi, the Advances Optimization Lab at
McMaster University took over the development in late 2004. This document specifies our goals and plans with
the SeDuMi package. As always, we are open for comments and suggestions on how to make this package even
better. You can download a pdf version from the Downloads section.
The Advanced Optimization Lab at McMaster University took over the development of SeDuMi in the fall of 2004.
We are committed to maintaining the package, releasing new versions regularly and providing support for it.
The response we received from the optimization community was overwhelming: so far (June 9, 2005) the SeDuMi
portal registered more than 28000 visits, while we have more than 580 registered users. In the last couple of
weeks we received numerous questions about our future plans, this triggered the publication of this document.
The following major projects are either happening or will be started soon. We consider them of high
importance because they would result in an immediate improvement or they fill in some important gap.
The preprocessing abilities of SeDuMi are quite limited today. For SOCP/SDP problems the only technique used
is the separation of dense and sparse columns (which is not actually a preprocessing technique). We plan to
implement and possibly improve several recent techniques to exploit the special structure of some large-scale
problems.
So far (SeDuMi 1.1) we have implemented the following techniques:
- detect diagonal SDP blocks and convert them into nonnegative variables
- free variables are now handled in a quadratic cone instead of splitting
- detect split free variables and convert them into free variables
Currently, SeDuMi has a default assumption on the sparsity of its matrices, e.g., ADAT is always assumed
to be sparse and is stored accordingly. However, especially for SDP problems this matrix can be dense,
resulting in huge memory and computational overhead. This happens because SeDuMi is using Jos's version of
the rather old, yet effective Ng-Peyton solver (ORNL), implementing several additions to the basic code.
This code is designed for sparse, block-diagonal systems, but the same code is used for dense systems.
Meanwhile, most other SDP solvers use the ATLAS version of the BLAS package for dense matrix manipulations.
Incorporating this package and distinguishing between sparse and dense cases would result in immediate speed
improvement. If a preinstalled ATLAS package is not available then we can use the BLAS routines offered by
Matlab.
Nothing has been done in this direction yet.
SeDuMi has a lot of parameters that have a default value working well for the majority of cases. However, one
can easily tune these to solve a particular problem more efficiently. We plan to define some simple
heuristics that change the value of certain parameters according to the problem, either at the beginning of
the optimization, or at every iteration. The candidate parameters for these heuristics are the starting point
of the self-dual model, neighbourhood parameters, step-differentiation and the corrector method.
So far (SeDuMi 1.1) we have implemented the following technique:
- adaptive step-differentiation: some tests showed that using step-differentiation can be very effective.
It is generally more stable, especially close to convergence, but it is often inefficient at the beginning.
Thus we turn it on either after 20 iteration, or if we are close to a solution (feasratio is close to 1), or
if we have numerical problems (CG steps are needed).
We need efficient converters between the numerous SDP/SOCP formats and the .mat format in SeDuMi. There is a sparse-SDPA to SeDuMi converter in the SeDuMi distribution, but that needs some further work. There is no converter from SeDuMi format to others.
These are some small, easy to implement features.
- 64-bit implementation
With the arrival of 64-bit PC systems SeDuMi should make full use of the potentials of this new platform. We
need to make the C-code fully 64-bit compliant.
- Quadratic optimization
Allowing SeDuMi to solve quadratic problems by converting them into SOCOs.
- Problem statistics output
Output problem statistics (number of rows, columns, cones, etc.) if the user wants them.
So far (SeDuMi 1.1) we have completed the following small features.
- DIMACS errors
Output some error measures as specified at the 7th DIMACS Computational Challenge.
- Precision at every step
Show the current precision at every iteration (not only the duality gap of the self-dual model).
- Preprocessing information
Output the effect of preprocessing (how many free variables detected, cones eliminated, etc.)
As we don't have access to the TEX source of Jos's user guide we have started to write a new one.
Gradually, this will take over as THE user guide.
These are the topics that are important but we are not dealing with them right now either because they depend
on some other projects or they don't offer an immediate benefit.
Implementing some recent results in IPMs such as modified predictor-corrector methods, self-regular search
directions, the Ai-Zhang direction, modified neighbourhoods, etc. These are relatively easy to implement, but will require a lot of
testing and parameter tuning. Moreover, it is hard to tell how much we could gain here. This should be done
in an adaptive way.
Currently, SeDuMi is using the NT-scaling technique to symmetrize the Newton-system. The HKM-scaling used by
other SDP solvers (SDPT3, SDPA, CSDP) is an attractive candidate for implementation, though it requires major
changes to the code and the benefit is not immediate. A heuristic should be devised to decide which scaling
to use.
Another change in the PC market is the widespread accessibility of multiple-processor and dual core systems.
Although IPM methods are sequential, the work of one iteration is highly parallelizable. Assuming that we are
using a parallel version of ATLAS-BLAS for linear algebra, all we need to do is to implement a parallel
version of forming  . The difficulty is that implementing a hand-coded multithreaded version is a major
work. There is a new standard called OpenMP that is able to compile parallel code and requires only minor
modification of the original sequential code, but it's not available for the GNU compilers yet (although it
is already implemented for the PGI compiler family for Windows and Linux, xlc and xlf under AIX
and the Intel compiler), thus we can not use that in general. The GNU version of an OpenMP C compiler is not
even in alpha stage, it won't be usable in the near future.
Octave is a numerical algebra system released under the GNU/GPL license. It is similar to and mostly
compatible with Matlab. Some users on the SeDuMi forum have suggested that SeDuMi could be ported to Octave.
We are currently experimenting with this, if it works, this would make SeDuMi 100% free, although we plan to
keep Matlab as the main development platform.
All the rest, small enhancements, new features, future projects. We don't consider them to be of immediate
importance, but they would be useful.
- Accept problems in graph form
Many problems in graph theory lead to SDPs. It would be more efficient to solve these problems based on the
graph input instead of the standard SDP form. Some solvers are already doing this.
- AMPL/GAMS interface
An AMPL or GAMS interface would give SeDuMi a unique feature among SDP/SOCP solvers. The difficulty is that
currently neither of them supports semidefinite constraints.
- Stand-alone version
There are certain limitations in Matlab that have a serious impact on the capabilities of SeDuMi. Most
important is the memory issue, even the 64bit version of Matlab is using a 32bit integer to store the number
of nonzeros in a sparse matrix, thus limiting the maximum matrix size to 232-1 nonzeros. The other issue
is that as Matlab is not free, SeDuMi is not freely accessible. Recoding all the Matlab parts in C would make
SeDuMi a really free stand-alone solver. Of course, as most people value Matlab environment as the most
important feature in SeDuMi (see the recent poll on the SeDuMi portal) we have to keep SeDuMi callable from
Matlab.
|
