find min/max of variable values that satisfy certain constraints

Question

Kylekk 2022-5-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1730430-find-min-max-of-variable-values-that-satisfy-certain-constraints

编辑： Walter Roberson 2022-6-3

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!

2 个评论
显示无隐藏无

Image Analyst 2022-5-31

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

Kylekk 2022-5-31

Absolutely, let me edit the question

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2022-5-31

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1730430-find-min-max-of-variable-values-that-satisfy-certain-constraints#answer_974670

在 MATLAB Online 中打开

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.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Kylekk 2022-6-3

编辑：Kylekk 2022-6-3

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 2022-6-3

编辑：Walter Roberson 2022-6-3

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()

请先登录，再进行评论。