Seidel Warm start

[xbaosong]

Hi, there.
While I was reading the seidel.cpp file, I saw the following comment:

// warmstarting feature: one in two solvers, upper and lower,
// is be selected depending on the sign of g[1]

What does it mean by warmstarting feature? I didn't see how it's working or perhaps it is a todo?

Also, I checked the Seidel's linear algorithm(https://www.cs.cmu.edu/~avrim/451/lectures/lect1021-lpII.pdf), and did't see any warm-start trick, can someone explain the idea?

[xbaosong]

also it seems to me that member variable m_A_ordered, m_index_map, m_active_c_up and m_active_c_down are obsolete. I commented out related code, and it worked just fine, with execution time shortened a little bit (~20 us).

[hungpham2511]

What does it mean by warmstarting feature? I didn't see how it's working or perhaps it is a todo?

I can't immediately recall now as it has been a few years since we worked on this implementation.

If I recall correctly thought, it's about selecting the constraints to add to the Seidel solver. In the optimal case, we select the optimal constraint right away.

Regarding time-complexity though, since the random variant of Seidel LP algorithm is linear w.r.t the number of constraints anyway, so this does not give a theoretical benefit. However practically I think it should help quite a bit.

[xbaosong]

For constraints like joint speed or acceleration, one has a lower and an upper bound, which, in the project version, can be written as $$au + bx \in [c_{min}, c_{max}]$$
The insight is that we can tell which constraint (w.r.t to $c_{min}, c_{max}$) will never be the optimal constraint since the two constraints are parallel. In this way, half of the constraints can be pre-eliminated.

Is this what you meant by selecting the constraints?

[hungpham2511]

What I meant is if constraint i and j are the active constraints in the previous step, then we can start with those two constraints first in the current step.

If the same constraints are the solution, then the algorithm simply checks all other constraints in linear time. This is what I mean by warm-starting. This is the same idea as the qpOASES algorithm.

In fact both experimentally and theoretically, it can be rather easy to demonstrate that the number of times the set of active constraints change is significantly smaller than the number of discretization step.

[xbaosong]

Okay, I got it. Thanks, man.