Symbolic expression bounds

19 views (last 30 days)
Joan Puig
Joan Puig on 1 Jun 2011
I have a symbolic expression (the real expression can be anything the Symbolic Toolbox supports) but for example we can use the following:
expr = sym('a + b')
Also, I know that a and b are integers and that their "legal" values go from 1 to 7.
I would like to figure out what are the bounds of expr. In this case, the min value would be 2 and the max value would be 14.
Is there any way to do this type of analysis?
Thanks Joan
  3 Comments
Walter Roberson
Walter Roberson on 1 Jun 2011
Would it not also be necessary to prove that the output was integral?
Joan Puig
Joan Puig on 2 Jun 2011
The user is only allowed to use certain variables.
With the symvar function I can extract them and make sure that they are all known.
Each one of this variables has a set of properties (value bounds, matrix size, and if they are integers or reals) which I know and I can use to help the solver.

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 1 Jun 2011
Unfortunately there is no theoretical way to do that for arbitrary expressions.
For the special case of linear operations, you can use the linear minimizer or maximizer: see http://www.mathworks.com/help/toolbox/mupad/linopt/index.html
More generally for expressions in one variable, you would differentiate the expression, find the zeros of that, differentiate the expression again, evaluate at the zeros to determine whether you are looking at a min, max, or saddle point. Solving for the zeros might be difficult or impossible though...
For expressions in multiple variables, the question of the range becomes equivalent to the question of finding the global extrema. It is known that there is no general algorithm for that, but there are some classes of expressions that it can be solved for.
  4 Comments
Walter Roberson
Walter Roberson on 2 Jun 2011
I am not sure of the best way to express negation in MuPad's solve()
Perhaps something like,
EXPRESSION minus LowValue..HighValue <> {}
Joan Puig
Joan Puig on 6 Jun 2011
While there doesn't seem to be any out of the box solutions, I am going to accept this answer as it provides some good ideas and allowed me to implement apartial solution to the problem

Sign in to comment.

More Answers (2)

Andrew Newell
Andrew Newell on 1 Jun 2011
It makes little sense to use the Symbolic Toolbox for such an operation because comparisons like max and min are not allowed on symbolic objects and it is trivial to do in MATLAB:
a = 1:7;
b = 1:7;
min(a+b), max(a+b)
  5 Comments
Walter Roberson
Walter Roberson on 2 Jun 2011
If the user is allowed to type in "any symbolic expression they want" then they could, for example, put 1/(a^d + b^d - c^d) as one of the sub-terms. This is a rational number for all a, b, c, d positive integers, d>=3, if and only if Fermat's Last Theorem holds, and otherwise could become 1/0 . Is your formal verification system prepared to prove Fermat's Last Theorem?
Likewise a similar technique could be used to express the Riemann Zeta function and make assertions about its values.
You have to restrict operations and functions called by quite a bit in order to hope to be able to reliably do formal verification.
Joan Puig
Joan Puig on 2 Jun 2011
I agree, the general problem is not solvable. In practive though, I don't need to be able to verify all inputs.
It would be acceptable to tell the user that we could not verify the input therefore they need to change it if they want to continue.

Sign in to comment.


Andrew Newell
Andrew Newell on 2 Jun 2011
If you have a pre-determined set of variables and a finite number of possible values for them, you might be able to use an approach like this:
  1. Create a function out of the expression using matlabfunction.
  2. Feed all possible values of the variables into your function and find the min and max.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!