find min/max of variable values that satisfy certain constraints

Hi all,

I have a set multivariate polynomial constraints, and i was trying to find the bounds for each variable with constraints satisfied. Is there a fastest way to do so? The bounds are allowed to be -inf or inf.

I understand fmincons could always be an option. However, since i am solving a huge number of such optimization problems, speed is my main concern.

  For example, i have q, t, g, d ,tb, vv, phi, rho, ft as my variables. and they have to satisfy 10 equations each look like "25*g*t+16*q+25=0", and they are all polynomials.
    Now i would love to see what the solutions of these equations look like, i.e. to find upper/lower bounds of the solution set(since condition for the roots might have free parameters) for q, t, g, d, vv, tb, phi, rho.
    one of the problems could be: 
    max/min q
    s.t. eq1, eq2, eq3, ..., eq10
   and i need to do this for all variables, i.e. 
    max/min t,g,d,tb...
    s.t. eq1, eq2, eq3, ..., eq10

This is considered 1 optimization problem (although it looks like 9, idk if there's a way to simplify this), and i have to run 10000 optimization problems so efficiency is extremely important here.

Thank you!

[Image Analyst]

Sounds kind of vague. Care to be specific by giving an example?

[Kylekk]

Absolutely, let me edit the question

Answer 1

[Walter Roberson]

25*g*t+16*q+25=0

If all values except g are known then create a vector of coefficients of g in descending order, in this case

[25*t, 16*q+25]

which should be a pure numeric vector.

Now use polyder() and roots() of the results. Take the results and polyval() those locations against the original coefficients.

What you have now is a list of critical values. You can proceed to filter them against the constraints, eliminating values that do not meet the constraints. Eventually you have a possibly empty list of g and corresponding polynomial values. You can proceed to try to figure out what max and min are, taking into account that some might be complex values.

The logic would be a bit different if you did not have the =0 part. The =0 restricts down to a number of values equal to the maximum coefficient degree.

[Kylekk]

Thank you again Walter! However, I don't think in the example above, t and q are known values. The constraints are multivariate polynomials, and i'm interested in the range of every variable, hence the optimization of q (just as an example). Is this method still working? Sorry for any confusion!

[Walter Roberson]

syms g t
eqn = 25*g*t+16*q+25 == 0
eqn2 = lhs(eqn)-rhs(eqn)
dg = diff(eqn2, g)
critg = solve(dg, g)

critg is the critical points. The max and min are either at these values or else at the constraints.

The polynomial constraints form simultaneous equations that can potentially be solved for. However beyond degree 4 you are not going to get exact solutions. For optimization purposes if you have fewer constraints than variables but what you do have implies degree 5 or more, then you are going to have difficulty characterizing the solutions. isosurface() can help for that purpose... Remembering that at that point you would be drawing surfaces of potential to be the active constraints for the purpose of determining where max and min are. It could get ugly.

[Kylekk]

That is very insightful! I don't think i fully understand why i need to find the critical values --what im trying to max/min here is g itself. critg should give me g's that max/min 25*g*t+16*q+25 (vaguely speaking)? Sorry i have to unaccept so that you will take another look at this question maybe...

Having degree 5 or more is definitely possible in my future work but not my primary concern here. I will try your method and hopefully its working for me.

In my case (even in the future, with more variables and equations), i have these variables rather sparse in the equations (a Grobner basis) . That's actually good and makes it easier to solve, right?

[Walter Roberson]

25*g*t+16*q+25 = 0

therefore 25*g*t=-(16*q+25). Therefore g = -16/25*q/t - 1/t or g = -(16/25*q + 1)/t which in this case is only one root; if you had multiple roots you would have to explore them separately.

What are the bounds for g? By inspection if 16/25*q + 1 is positive then the bound is -inf as t approaches 0, and if the expression is negative, the bound is +inf, and at 0 exactly it is undefined.

Your additional polynomial constraints could potentially be solved for q in terms of t and substitute in to the solution for g might possibly permit you to find the sign() of the expression and so determine the g bounds.

Is there a function call such that given a formula in symbolic variables that might include divisions, the function will tell you the range of values that the formula can sweep? No, there is not, with the exception of formulas that are the rational ratio of two polynomials in one variable, in which case Control System theory about poles and zeros can be used.

To implement such a function yourself you would need to use children() or perhaps findSymType for division or powers and recursively analyze bounds. The examination for powers would need to look at potentially negative powers (and so whether you can be dividing by 0), and would need to check for non-integral powers (in which case you need to check for negative values in the base, as negative to fraction generates complex.)

You might want to look at Maplesoft's Maple iscont() and evalr()