1
$\begingroup$

I have a series of inequalities:

$$y_{1min} \leq y_{1}(x) \leq y_{1max}$$ $$y_{2min} \leq y_{2}(x) \leq y_{2max}$$ $$..$$ $$y_{nmin} \leq y_{n}(x) \leq y_{nmax}$$

Note that $x\in\mathbb{R}$

The question is, is there a general method that allows me to find the range of $x$ that satisfies the above inequalities?

Things are easy if there is just one inequality, and $y_1(x)$ is at most a quadratic function. But I am looking for a general solution here.

Edit: My $y$ function can roughly be written as

$$y=\Biggl[\frac{(x^2+bx+c)^f}{(dx+e)^g}\Biggr]$$

where $c$ and $e$ are small comparatively.$(dx+e)^g$ must be positive.

In one of the $y_i(x)$, $f=5/3, g=2/3$, but in another, $f=1, g=1$. It is safe to assume that both $f,g\in\mathbb{Q}$, that is they are rational numbers.

$b,c,d,e\in\mathbb{R}$ , and they vary from one $y_i(x)$ to another.

Hope this helps.

Edit:Let's make this question a little general; instead of letting $y(x)$ depends on one variable, what if $y$ depending on multiple variables? That is, how to find the range for $(x_1,x_2,x_3,..., x_i)$, given that

$$y_{1min} \leq y_{1}(x_1,x_2,x_3,..., x_i) \leq y_{1max}$$ $$y_{2min} \leq y_{2}(x_1,x_2,x_3,..., x_i) \leq y_{2max}$$ $$..$$ $$y_{nmin} \leq y_{n}(x_1,x_2,x_3,..., x_i) \leq y_{nmax}$$

  • 0
    Does $x\in\mathbb{R}$? Are there any conditions on your functions $y_i(x)$?2010-09-21
  • 0
    @alext87, yes $x\in\mathbb{R}$2010-09-21
  • 0
    retag: if the $y_i(x)$ are not linear functions then this is not linear programming. I tagged as optimization as feasiblity problems can be thought of as constrained optimization.2010-09-21
  • 0
    @Ngu Soon Hui: not even a little bit, at least not with way more constraints on the y_i. They at least have to be computable and should probably be continuous as well. What are they actually? Polynomials?2010-09-21
  • 0
    @Qiaochu, they are computable, and they are usually continuous except maybe at some singularity points. But they are not polynomials.2010-09-21
  • 0
    @Qiaochu, on a second thought, I would like to clarify that the functions are well behaved, no singularity, continuous, even though they are not polynomials.2010-09-21
  • 0
    @Ngu Soon Hui: the question, I think, was already far too general. I cannot solve even the one-variable, one-inequality version for something horrible like the Weierstrass function. Can you please be much more specific?2010-09-21
  • 1
    @Ngu Soon Hui: at the generality in which you put the question I doubt there is anything that can be said. Given a closed subset $F\subseteq\mathbb R$ is is easy to give a set of inequalities (in fact just one) involving continuous functions which has solution set precisely $F$... To turn this into something which can reasonably be expected to have a general solution you will need to be more specific.2010-09-21
  • 1
    As mentioned already, solution strategies for such things are often tailored to the inherent structure of the problem. Not exploiting it can only be a profligate waste of computer time and effort. Please give more specifics about your function(s) of interest. Turning to the multivariate case, exploitation of structure becomes even more important, since you have much degrees of freedom.2010-09-21
  • 1
    @J.M., question updated.2010-09-21
  • 0
    With your last edit you turned an impossibly complicated problem with absolutely no hope for a non-tautological solution into a simple one :)2010-09-21
  • 0
    Ah, so it's a *rational* function! Why didn't you say so to begin with? You can do the analysis by looking at the numerators and denominators; rootfinding of the polynomials in the denominators may sometimes be necessary, but this is certainly more tractable than what you were asking at first.2010-09-21
  • 0
    @J.M., that's because there *are* functions in my problem that involves $sin{x}$, which, can somehow reduce to rational function within the range of $x$ that I'm interested with2010-09-21
  • 0
    Hmm, you should have mentioned that too; throwing an oscillatory function into the mix can present a different set of problems.2010-09-21
  • 1
    “We think in generalities, but we live in detail”.2010-09-21
  • 0
    @J.M, although I haven't done the calculation yet, but I am quite sure that the function with the dominator involving sine term can be reduced to polynomial term, as far as the practical $x$ is concerned. And if it doesn't, what kind of solution you would suggest?2010-09-21
  • 2
    How about you post the complete problem up!? Surely that would be easier rather than playing a cluedo game!2010-09-21
  • 1
    @Ngo Soon Hui: I agree with alext87. There's no point in being coy.2010-09-21
  • 0
    @alext87, as far as my function goes, I think the rational function I post is already rather explicit and comprehensive. All I withold back is the $a$, $b$, $c$, $d$, $e$,$f$,$g$ values, which I guess won't impact the solution method anyway. As for the sine term remark, I think we'll just assume that the dominator will also be reducible to quadratic term under the limit *I'm interested* in.2010-09-21
  • 0
    That's assuming your range of interest is within one period of the sine function; if the range covers more than that, then the troubles with oscillatories I was alluding to comes into play.2010-09-21
  • 0
    @Ngu Soon Hui: are f and g non-negative integers?2010-09-21
  • 0
    @Qiaochu, yes they are non-negative, but not integer. See updated question.2010-09-21
  • 0
    @J.M., it is safe to assume that.2010-09-21
  • 1
    @Ngu Soon Hui: are f and g _rational_? (I really do not understand why you aren't providing more information. If f and g are irrational you can't reasonably claim that the function you're studying is well-behaved.)2010-09-21
  • 2
    Please state the problem in all its gory details, so that people do not need to guess at the statement. Otherwise, this is really *not a real question*...2010-09-21
  • 0
    @Qiaochu, $f=5/3, g=2/3$. See the updated question.2010-09-22
  • 0
    @Mariano, I've supplied more details to the problem.2010-09-22
  • 0
    Dear Ngu, I think people would really love it if we didn't have to wring and squeeze you for details every time you ask a question. As I said in one of your previous questions, explicitly mention any reasonable (to you) constraints your problem has, since attacking a structured problem is much easier than playing blind man's bluff.2010-09-22

2 Answers 2

2

If $f$ and $g$ are rational the problem is very easy. Multiply out by the denominator, take the $d^{th}$ power of both sides where $d$ is the least common denominator of $f$ and $g$, and you've reduced to the polynomial case, which is easy (check the extrema and so forth). This is why it is important to provide details.

  • 0
    Yup, they are rational numbers.2010-09-22
1

For a start, suppose we can find the interval $I_i\subseteq\mathbb{R}$ such that $y_{imin}\leq y_i(x)\leq y_{imax}$. Then the interval $I$ which satisfies all the constraints is

$I=\bigcap_{i=1}^n I_i$

Thus we can concentrate on finding $I_i$ separately for each $1\leq i\leq n$. Here I'm sure we will need some conditions on $y_i(x)$. Do your functions have compact support? Are they continuous? Do they oscillate wildly in any region?

In the general case - finding a feasible point You mentioned that $y_i(x)$ are continuous. Lets suppose that in addition they are continuously differentiable. I'll do the problem with $1$ constraint for easy of notion but the general case is exactly the same though more difficult to write down.

Rewrite the constraints as

$y_1(x)\geq y_{1min}$

$-y_1(x)\geq -y_{1max}$

Now let $A(x) = \left(\nabla y_1(x),\nabla(-y_1(x))\right)^T$ (the jacobian matrix of the constraints).

Also let $b=\left(y_{1min},-y_{1max}\right)^T$.

Then we need to find a $x_0$ such that $Ax_0\geq b$. We do this by solving the following (phase-1) problem.

let $x_{guess}\in\mathbb{R}^n$. Let $r=\min(b-Ax_{guess},0)$ and solve the problem

$\min_{x\in\mathbb{R}^n,\mu\in\mathbb{R}}$ $\mu$ subject to $Ax + \mu r\geq b$ and $\mu\geq 0$

Now, you may not think that we have come very far but because $(x,\mu)=(x_{guess},1)$ is an initial feasible point for this minimisation problem it can be solved by standard software. If the optimal point gives an optimal value $>0$ then the orignal problem is not feasible. If the optimal value is $0$ then the orignal problem is feasible and the optimal point is a feasible point for the orignal problem.

  • 0
    I would like to clarify that the functions are well behaved, no singularity, continuous, even though they are not polynomials.2010-09-21
  • 0
    not sure how would you handle multiple $x_i$ variables case? See the updated question2010-09-21
  • 0
    not sure whether is there a matlab function that does this?2010-09-21
  • 0
    Look up at the optimization toolbox in Matlab.2010-09-21