I have a programming problem that I want to optimize. To optimize it I have to calculate the minimum value that's possible for one variable given a set of equations (where some but not all variables are known at runtime). Is there any good automatized system that does that job for me and that gives me a formula given my constraints? 

New to LessWrong?

New Answer
New Comment

2 Answers sorted by

Timothy Johnson

Apr 25, 2021

50

What kind of constraints do you have?

There are many constraint solvers for different kinds of equations. I enjoyed using pySMT, which provides a Python wrapper for several different libraries: pysmt/pysmt: pySMT: A library for SMT formulae manipulation and solving (github.com).

chasmani

Apr 26, 2021

10

Maybe look at GAMS

5 comments, sorted by Click to highlight new comments since: Today at 10:40 AM

What equations are you using? Is there something special about them which makes you think your particular problem is tractable? A Bayesian optimization hyperparameter search like Facebook's Adaptive Experimentation Platform (Ax) might help if you're searching a continuous, differentiable space. Technically-speaking, an efficient general solution is probably impossible to construct within physical reality since it involves reversing trapdoor functions.

b²=m²+z², c²=n²+z², b²=o²+q², w²=o²+r², c²=s²+v², w²=v²+t² and y =b+c, z=m+n, x=q+r, l=s+t. I know that all values are positive. The space is continuous and differentiable. I know y,z,x and l at excecution time and want to know the minimal w that's possible for the system. 

I feel like I should have enough information to have be able to calculate a decent value value for the minimal w. 

I've used Optim.jl for similar problems with good results, here's an example: https://julianlsolvers.github.io/Optim.jl/stable/#user/minimization/

The example looks to me like it gives the library one equation that has to be minimized. I on the other hand have a bunch of equations. 

[-]gjm3y80

Of course what you asked for is information about computer systems for solving this kind of thing, but the particular system of equations you have here isn't so hard to make sense of (but, caution, I make a lot of mistakes, so if you want to make any use of what follows I strongly advise you to check it).

So, let's begin with the quantities z,m,n,b,c. z is known; m,n are constrained by having to add up to z, and z,m,n interact with the other variables only via b,c. Oh, and we also know y=b+c, so we've got two constraints on b,c which means we should expect there to be only finitely many possibilities for (b,c); let's see what they are.

This sort of thing is a bit painful by hand, but e.g. Mathematica can do it instantly. (Though it doesn't give what seems to me the simplest form, so I've made some hand-simplifications which of course might have introduced errors.) It turns out that b,c are 

which isn't too painful. OK, now we split up x as q+r and l as s+t, and then from b,q we calculate o and from c,s we calculate v, and then we have two expressions for w which need to be equal. So that gives us  which looks a bit unpleasant, but notice that we can write  where  can take any value in  and similarly for .

We have  and this has to equal  which by the remarks in the previous paragraph is  where  and and can therefore take any value between 0 and . So, first of all, the whole thing has solutions iff .

And now we get  by offsetting  by something between , and also by offsetting  by something between , and so the smallest we can make  is . (But remember that we can take b,c whichever way around we prefer; so we should put the + sign in b if x>l and in c if x<l.)