minimization constraints

[sagastra]

Is your feature request related to a problem? Please describe.

Hi, is there a way of doing constraints that are not equality constraints Bx=0, but minimizing a function like Bx.

Describe the solution you'd like

basically in the optimizer step that is using a sparsity to minimize the coefficients would be multiplied by a weighted matrix B

Describe alternatives you've considered

I looked at the features and there was an example using equality constraints, but I was wondering if it could also have minimizing or maximizing functions

Thank you!

[akaptano]

If I'm understanding correctly, this should be straightforward. You are already minimizing ||Ax - b||^2 in the SINDy optimization problem (here A is the "candidate library", and so forth). So you can simple expand the definitions of all your variables to be: A' = [A, B], b' = [b, 0], and x' = [x, x], and now you are minimizing both ||Ax-b||^2 and ||Bx||^2 at the same time. Other than using these expanded definitions, you shouldn't need to change anything else.

If you are interested in the more complicated case where you minimize some generic (nonlinear) function f(x), you would need to add this as a new term in the optimization problem and derive an algorithm for solving this new problem. If that is the case, let me know what you're thinking and I can try to help.

[sagastra]

Hey akaptano, Thanks so much for your response. I am trying to minimize ||Ax-b||^2, and I also have a constrain to minimize ||AB|| (where AB are both matrices and AB is a element multiplication not matrix multiplication). Basically I have a biological optimization problem, where A is a wiring diagram for some neurons, and B are the lengths between them. In my own optimization I basically solve for ||Ax-b||^2 and then put a sparsity penalty on ||AB|| and this gives me a good estimate. If you can think of an easy way to do this please let me know.

[akaptano]

To clarify, are you minimizing ||AB|| over B? The normal SINDy minimization is over x, so if you have a minimization over B as well, you can simple solve min_x min_B ||Ax-b||^2 + coeff ||AB||^2 = min_x ||Ax-b||^2 + coeff min_B ||AB||^2 since this problem separates and both are easy problems. If the optimization is actually over A (i.e. choosing a candidate library that represents a minimal-size diagram of neurons), this is still solvable as min_x min_A ||Ax-b||^2 + coeff * ||AB||. You will need to add code to pysindy to implement the extra minimization you are doing over A (or B) but this is straightforward.

To clarify, the reason we cannot implement the minimum of ||AB|| as a type of constraint in the optimization, is that SINDy uses affine constraints of the form Cx = d, i.e. constraints on x, not constraints on A.

Let me know if you need some pointers on solving any of these variants, and different variants might produce different results. Moreover, if you are solving this in the above ways, you need to decide what tradeoff you want between "fitting the data" (the ||Ax-b|| term) and "producing a minimal size diagram" (the ||AB|| term), which is determined by the value of 'coeff'.

Best, Alan Kaptanoglu

[sagastra]

Hi Alan, Thanks so much for the thorough explanation. Indeed I am solving for A, in order to minimize ||Ax-b||^2 but additionally I am trying to minimize the product ||AB|| (The matrix B is known, x is a bunch of data, and A is what I am trying to solve for). Yes, I need a tradeoff coefficient for fitting the data and minimizing wiring length. I am down to hack your code, just making sure that what I am trying to do is possible and makes sense. I also want to add some non-negative constraints and some symmetry constraints on A (but I think that should be doable from the tutorial that you posted), and perhaps change the norm of ||AB|| into L1, L2, and Hoyer sparsity (Basically, in general want to minimize ||Ax-b||^2 + f(A), where f is a function that I can define). Really appreciate your help, big fan of all of your work in system ID.

[akaptano]

Thanks, hope it comes in handy!

There are different ways you can go with this optimization. I am doing something similar right now so I've been thinking about this a lot. In general what you are solving is ||Ax-b||^2 + f(A) subject to some constraints (let's assume affine) CA = D. Let's take f(A) potentially nonconvex. But this is precisely the SINDy optimization, except the minimization is over A instead of x!

So, assuming you also want a sparse x, so there is some regularizer R(x), you can solve this as min_x min_A (||Ax-b||^2 + f(A) + R(x)) = min_x (R(x) + min_A(||Ax-b||^2 + f(A)) subject to CA = D. The inner optimization over A is solved by the constrained SR3 algorithm (see Champion et al 2019, unified framework ...) but the roles of A and x have swapped. It actually might make most sense to solve the minimization over x first, and then plug this value into the minimization over A. How the two minimizations interact is pretty subtle if the problem is nonconvex.

Before embarking on this, it might be easier to solve min_A f(A), subjected to CA = D and then plug this into min_X ||Ax-b||^2 + R(x). In other words, find the minimal size diagram subject to the constraints irrespective of the data, and then solve the SINDy problem with this candidate library. The only risk you run is that the A matrix (the candidate library) will be ill-suited for your data. But since we would expect this constrained, minimal size diagram to be somewhat sparse, you could potentially make it reasonably large in dimension, making it reasonably likely it can fit whatever data you throw at it.

Anyways, let me know if you have any more specific questions.

Best, Alan