Feature Request: Allow supplying initial guess
Opened this issue · 11 comments
This would be extremely helpful for reducing runtime when running many similar problems in sequence. As far as I can tell, this is supported by many other solvers (and is available through YALMIP) but not currently available for ECOS.
Since ecos implements an interior-point method, it is far from obvious that warm starting is useful. There are methods that claim to save about 50% of the iterations, but this is not accomplished by simply supplying an initial guess. Do you have a particular application in mind where this might be useful / is critical to achieve fast computation times?
Actually, the benefits of supplying an initial guess depend heavily on the specific algorithm used, the quality of the guess, and the structure of the model. In the case of an interior-point method like ECOS employs, it is in no way certain that it would be "extremely helpful". The folks at MOSEK, for instance, have put a lot of effort into doing warm start for interior-point methods but the benefits are somewhat limited. It's certainly not a slam-dunk.
In fact, with interior-point methods, supplying the solution to a related problem as an initial guess can be counterproductive, because the guess may be very close to the boundary of the feasible region and/or far from the central path.
Here is a paper on some of the academic work by MOSEK's founder and colleagues. They claim to get speedups of 30-75% in some cases, so that's good. But still this is cutting-edge stuff. For the simplex method, first-order methods, etc., the situation is different.
MOSEK was the primary comparison, perhaps I was mistaken about the usefulness of warm starts over all solvers.
We're currently solving the same problem repeatedly with slightly different data each time. Most values in the solution vector remain very similar between runs. I supposed that the guess would be closer to the central path, but perhaps not?
I don't think it would be that hard to implement MOSEK's approach in ECOS. But make no mistake, simply starting from the previous solution would not be good.
The central path is defined in the primal-dual space, so you also need to
know the multipliers and the slack variables to construct a useful
warm-start. This is rather tricky… Have you tried first-order methods?
2014-10-30 18:33 GMT+01:00 iamed2 notifications@github.com:
MOSEK was the primary comparison, perhaps I was mistaken about the
usefulness of warm starts over all solvers.We're currently solving the same problem repeatedly with slightly
different data each time. Most values in the solution vector remain very
similar between runs. I supposed that the guess would be closer to the
central path, but perhaps not?—
Reply to this email directly or view it on GitHub
#87 (comment).
Actually, it looks like hot start is not yet enabled for nonlinear problems in MOSEK. It is only available for linear programs using the simplex method, not the interior-point method.
So... time to implement a simplex method when warm-starting is requested and the problem is an LP? :-p I jest, but only so much.
@adomahidi From what I can tell most first-order methods around don't support the sort of constraints we want.
This paper suggests an intelligent warm start can be useful in reducing number of iterations (though in their implementation this did not reduce time spent in total): http://www.ime.unicamp.br/~aurelio/artigos/cor.pdf
While my initial assumption that previous solution would be useful was shown to be wrong, I still think this would be a useful feature to support, if just to allow experimentation such as that in that paper.
It’s not just that it “did not reduce the time spent in total.” It was slower in all but one case, sometimes many times over.
Given that result and the complexity of it, it’s a non-starter IMO. The MOSEK approach seems more reasonable.
On Nov 17, 2014, at 10:15 AM, iamed2 <notifications@github.commailto:notifications@github.com> wrote:
@adomahidihttps://github.com/adomahidi From what I can tell most first-order methods around don't support the sort of constraints we want.
This paper suggests an intelligent warm start can be useful in reducing number of iterations (though in their implementation this did not reduce time spent in total): http://www.ime.unicamp.br/~aurelio/artigos/cor.pdfhttp://www.ime.unicamp.br/%7Eaurelio/artigos/cor.pdf
While my initial assumption that previous solution would be useful was shown to be wrong, I still think this would be a useful feature to support, if just to allow experimentation such as that in that paper.
—
Reply to this email directly or view it on GitHubhttps://github.com//issues/87#issuecomment-63328888.