Post by @giuseppebilotta@fediscience.org

2026-07-05 10:02 UTC

OK I&#39;m going to need ask the Fediverse for some math help here, because I have a feeling I&#39;m forgetting something obvious and can&#39;t find the resources I&#39;d need to answer my own question. Let&#39;s say I have an underdetermined linear system. The methods generally employed to solve these find the least (l2) norm solution, which is generally acceptable. However, in my case, I need to find solutions that satisfy some constraint (simple inequality constraints: solution must be in a box, with known ranges [min max] for each variable). I think I have had a brain freeze because the only approach I can think of to solve this is to turn the problem into a constrained optimization problem. However, in my case (hundreds of thousands of variables) this is not computationally feasible: the time needed for the optimization approach is ridiculously higher than the standard linear system solution. OTOH, I have a vague feeling that it should be possible to approach this differently, possibly remaining in the domain of the linear system resolution. What am I missing? #askFedi #fediHelp #askMath #mathHelp #mathematics

Replies (4)

@benni@social.tchncs.de 2026-07-05 10:08

@giuseppebilotta@fediscience.org isn't this simple an system of linear inequalities then? I am sure there are solution algorithms which should work, but this is just guessing, too. Did you search for such algorithms?

Open ##4997752
@giorginolab@mstdn.science 2026-07-05 11:03

@giuseppebilotta@fediscience.org linear programming? I think there are solvers for very large problems

Open ##4997759
@CadeJohnson@toot.cat 2026-07-05 11:26

@giuseppebilotta@fediscience.org when I have math problems that have too many variables for me to count on my fingers, I turn to Monte-Carlo analysis.

Open ##4997761
@ActiveMouse@mathstodon.xyz 2026-07-05 14:15

@giuseppebilotta@fediscience.org this is linear programming. If you solve your initial linear problem (expressible in matrix form as Ax = b) as far as possible, you end up with a linear space of solutions with some dimension n (less than the number of variables you started with, but more than zero, because it's underdetermined). You want to consider only solutions x where you minimize some linear function of x, and also put linear conditions on x. This turns it into a classic linear programming problem. There are very effective software packages for solving linear programming problems, but you generally have to massage your problem into a standard form, which can take some doing if you're not familiar with this.

Open ##4997764