High computational effort due to Jacobian calculation and simplification operations in SdpSolInternal

[JOlucak]

It seems that the jacobian calculation and simplification in SdpSolInternal are responsible for the high computational effort in the solver building process. See first figure. Currently, only simple cost functions (level sets) are considered. I think if more sphisticated cost functions are used in the future this becomes even more a bottleneck since the hessian calculation becomes more difficult.

For small sized problems (such as VDP) this is not a bigger deal. However, for medium size (6 states) and higher order polynmials (e.g. 6) we run into high numerical effort. See figure 2.

I am aware that polynomials of degree 6 are already quiet large but if we want to solve larger systems in the future or to have less conservative results this should be improved. Is it possible to improve this computation in casadi? What else is possible?

[tcunis]

There are a few things we should do:

1. Check how CasADi transforms the problem from qpsol syntax to conic.
2. Test which impact the simplification actually has (possibly none).
3. Provide (partial) information about the Jacobian matrix from the SOS-to-SDP relaxation to sdpsol and/or call conic directly (but avoid code redundancy).

Also, representing the coefficient matrix using MX variables might have an impact.

[JOlucak]

Current status

• simplification is removed; for the case with only one constraint not fully tested with other example
• Simple test using casadi SX or mx to compute a random jacobian with different number of decision variables revealed that MX scales better
• First version that is capable to provide analytical parts of the Jacobian is in the repository; it does not work for several constraints and is hence not ready for useage yet

[JOlucak]

A first version to analytically calculate dg/dQg where g are the constraint functions and Qq the matrix decision variables. The implementation was/ is tested with the GTM example in different ways:

1. Calculate jacobian fully with casadi --> solve quasiconvex SOS problem to get reference values
2. Calculate jacobian partially with casadi and partially analytically --> solve quasi-convex problem and compare final results

We receive the same results. The computation of the analytical part can be neglect (compared to other more demanding parts) but can be implemented more efficiently (first version!).

The third test varied the polynomial and SOS decision variables (max degree). The "new" approach works but is only slightly more efficient for a few reasons:

1. The "heavy" computations, regarding the jacobian, come from dg/dx (x are the SOS decision variables) and and dg/dxl, the linear decision variables.
2. Altough not that much (as for now) we must concatenate (potentially) large matrices to get the overall jacobian.

I will continue working on that, altough I must admit I don't know how we can potentially speed up the calculation of dg/dx.

[JOlucak]

Additional remarks:

• it seem that dg/dx is the driver here i.e. takes the longest, dg/dxl is about 3-4x faster but it still takes rather long.

[JOlucak]

I found a weird behaviour I can't explain.

If we set up a problem, rather large, and compute the jacobian for different parts (instead of for all dec. var at once), the computation times differ a lot.

dg/dQgram_g ~ 6s dg/dQlin_x ~400s

Now the weird part is the size g = 72295 x 1 SX Qgram_g = 1123544x1 SX Qlin_x = 1x4350 SX

dgdQgram_g = 72295 x 1123544 dgdQlin_x = 72295 x 4350

I don't understand why the latter one takes so much longer. g is the same.

the expressions in Qgram_g and Qlin_x are just SX variables that are the coefficients/decision variables. So not really a difference in the expressions.

Espacially, the last screenshot shows an ecpression of g and the Qgram_g and Qlin_x. I don't see a reason why it is more difficult to compute for Qlin_X

See screenshots

[JOlucak]

Remark to previous comment.

• Maybe it has somethin to do that Qlin_x consists of differnt entries rather than only one i.e. in Qgram_g there are only "Q" terms.

[tcunis]

The variables of Qgram_g enter into the constraint in a very structured manner, i.e., the partial derivative is either zero or an integer. On the other hand, Qlin_x enters as arbitrary expression.