From: [Permission pending]
Newsgroups: sci.math
Subject: monotonicity of polynomial quotients
Date: 11 Jan 1995 14:09:59 GMT

A question about the monotonicity of ratios of polynomials:
 
Given two polynomials, P(x1, ..., xn) and Q(x1, ..., xn) with
P and Q linear in any one of x1, ..., xn (i.e., no terms contain
values of x1, ..., xn such as x1**m where m >= 2.) The highest order
terms are of the form xi * xj, xi * xj * xk, or in general xi * xj * ... * xk.
What, if anything, can be said in general about the monotonicity
of the quotient P/Q  if xmini <= xi <= xmaxi, xmini > 0, and xmaxi is
bounded (say < 100).
  
Thanks,
[sig deleted - djr]
==============================================================================

Date: Tue, 17 Jan 95 10:14:50 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: monotonicity of polynomial quotients
Newsgroups: sci.math

In article <[identifier deleted - djr]> you write:
>A question about the monotonicity of ratios of polynomials:
> 
>Given two polynomials, P(x1, ..., xn) and Q(x1, ..., xn) with
>P and Q linear in any one of x1, ..., xn (i.e., no terms contain
>values of x1, ..., xn such as x1**m where m >= 2.) The highest order
>terms are of the form xi * xj, xi * xj * xk, or in general xi * xj * ... * xk.
>What, if anything, can be said in general about the monotonicity
>of the quotient P/Q  if xmini <= xi <= xmaxi, xmini > 0, and xmaxi is
>bounded (say < 100).

I hate to see a posted query go unanswered, but I can't think of anything
really helpful. I think part of the problem is in understanding what an
answer would look like. Suppose  n=1; what kind of statement would you
like to have about  (a+bx)/(c+dx) ? You can decide whether it's monotonic
over [0,100] with a condition on the coefficients (need -c/d not to be in 
the interval). If this is your goal, then, sure, you can write down a
condition for monotonicity in the multivariate case as well. I interpret
"monotonic" to mean that any increase in any variable at any point causes
the same change (positive or negative) in the value of the function; this
is implied by the positivity of all partial derivatives at each point (although
strictly speaking the latter condition is not necessary for a general
function). So you could write down this derivative and say, "the ratio
P/Q is monotonic as long as the following have no roots in the domain."
For example, if P=a+bx+cy+dxy and Q=a'+... then you need
(b'a-a'b)+y(d'c-c'd) and (c'a-a'c)+x(d'b-b'd) to stay positive on your
region (and  Q  not to be zero). Then the monotonicity would follow from
certain  x's  and  y's  not being in your region.
[In the general multivariate setting, write  P=P1 + xi P2, Q=Q1+xi Q2 and
you'll see partial(P/Q) / partial(xi) is (Q2 P1 - Q1 P2) / Q^2; monotonicity
requires that  Q  not be zero in the domain as well as each  Q2 P1 - Q1 P2
(an expression which will change for each  xi).  Thus you will mark off
n quadratic hypersurfaces in n-space; as long as none of these intersect
your domain, the ratio P/Q is monotone; otherwise it isn't.]

A couple of observations:
1) Monotonicity is shared by functions which are sufficiently "close"
to one another; using Taylor series, you can approximate much more
general functions to yours. Hence you can't expect to be able to say
much more about monotonicity in the case you posted than in the
general case. On the other hand,  ...
2) You must know more about the functions than you're letting on. For
example, the statement "xi<100" is only of use if we know something
about the size of the coefficients; otherwise any problem in your
class can be scaled to one with xi<100 (or whatever), so that extra
information wouldn't be helpful. So you must know something about
the coefficients you're not saying. In particular, I'm guessing that
they'r all positive (or possibly zero) -- am I right?

good luck.
dave

==============================================================================

Date: Wed, 18 Jan 95 08:53:41 EST
From: [Permission pending]
To: @ti.com:, rusin@math.niu.edu
Subject: re monotonicity

Dave,
Thanks for your reply; it is the most informative I have received.
Several example functions are:
{(1 + b1 + b1/b2 + b1/b3 + b1/(b2*b3))^(-1)}
{(b1 + b1*b2 - b3)/(b1 + b2 + b1*b2 - b3)}
{(-1 + b1*b3 + b1*b2*b3)/(b1*(1 + b3 + b2*b3))}
{(b1*b2 + b3 + b1*b3 + b1*b2*b3)/((1 + b1 + b1*b2)*(1 + b3))}

2) You must know more about the functions than you're letting on. For
example, the statement "xi<100" is only of use if we know something
about the size of the coefficients; otherwise any problem in your
class can be scaled to one with xi<100 (or whatever), so that extra
information wouldn't be helpful. So you must know something about
the coefficients you're not saying. In particular, I'm guessing that
they'r all positive (or possibly zero) -- am I right?
 
>>The coefficients are not all positive but are either 1, -1 or zero.
Any thoughts about the usefulness of this fact?

Thanks,
[Permission pending]
==============================================================================

Date: Wed, 18 Jan 95 10:23:20 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re:  re monotonicity

You wrote:
>Several example functions are:
>{(1 + b1 + b1/b2 + b1/b3 + b1/(b2*b3))^(-1)}
>{(b1 + b1*b2 - b3)/(b1 + b2 + b1*b2 - b3)}
>{(-1 + b1*b3 + b1*b2*b3)/(b1*(1 + b3 + b2*b3))}
>{(b1*b2 + b3 + b1*b3 + b1*b2*b3)/((1 + b1 + b1*b2)*(1 + b3))}

Perhaps I misread your original quote: I see now that the numerator and
denominator can be of greater total degree than  2. This does not
affect anything that I know how to do, though.

I notice that several of your functions are built up from simpler parts.
You should observe that  (f)^(-1) is (locally) monotonic iff  f  is,
using the formula for derivatives of an inverse. ["Locally" meaning that
it's monotonic in any neighborhood it's defined (and differentiable);
the example f(x) = x-1 on [0,2] shows that monotonicity of the inverse
need not be true on intervals including zeros of  f]. Thus in your
first example you may delete the "^(-1)".

Also observe from the product rule that if  f1  and  f2  are positive and
either both increasing or both decreasing then  f1.f2  is, too. This may
apply to the last two examples, although it starts to call attention to
the fact that we need to be more precise in our discussion: calling  f
monotone will be insufficient; we will try to observe whether  f  is
monotone increasing or monotone decreasing.

I will repeat my earlier understanding: that f is (locally) monotone increasing 
on a set iff all partial derivatives are positive everywhere on the set. Since
every one of your functions may be written f=(A+Bxi)/(C+D xi) (for every  i ),
the partials are just   (DA-BC)/(C + Dxi)^2, which has the same sign as
DA-BC.  So we check to see if all such cross-multiples are positive.
(We will similarly discover if  f  is monotone decreasing).

Let's take your second sample function. Viewing it as a function of  b1,
I see A=-b3, B=1+b2, C=b2-b3, D=1+b2, so AD-BC is -(b2+b2^2).  If we view the 
original function as a function of  b2, I see A=b1-b3, B=b1, C=b1-b3, D=1+b1 and
AD-BC=b1-b3, and if we view it as a function of b3, similar computations
lead to  AD-BC = b2. Thus the region on which  f  is monotone increasing is
where  -(b2+b2^2)>0, b1-b3>0, and b2>0; the region on which  f  is monotone
decreasing is the region where the three inequalities are reversed.
Actually the first set is empty (the conditions are contradictory) and the
second is simply the set where  b2<-1 and b1<b3. In either case, the region
on which  f  is monotone does NOT include any set of the form
[0,N]x[0,N]x[0,N]. 
 
>The coefficients are not all positive but are either 1, -1 or zero.
>Any thoughts about the usefulness of this fact?

No, but in my previous letter I noted the conditions I heard you giving
did not make the problem any different from the general case; I can't
make that comment now. The functions you're looking at are "special".
I just don't know how to use that "specialness".

It seems quite straightforward to establish the monotonicity of any
individual function in your set of of functions; dealing with the
functions generally (covering broad sweeps at a time) does not seem
so easy. I guess you'd like to say: every such function corresponds
to four collections of subsets of {1,...,n} -- given collections
C1 C2 C3 and C4 we let  f = (P1-P2)/(P3-P4)  where  P_i  is the sum of the 
products of variables corresponding to sets in  C_i. Then you want a
way to look at 4-tuples of collections of subsets and to vote
yea or nay as to whether the corresponding  f  is monotone. This
sounds like a rather ungodly combinatorial problem; the size of your
family of functions grows really fast with the number of variables,
although your {+,-,0} condition at least keeps it finite.
(There are [(n+2)(n+1)/2]^2 functions of your type with  n  variables;
fewer if you consider e.g.  b1/(-b1)  and  (b2-b3)/(b3-b2) to be the same).

[The problem is reminiscent of the classification of topologies that
can be put on a finite set, which is not known to have a workable solution.
(Recall that a topology on a set is a collection of subsets of that
set -- called the "open" subsets -- subject to a few axioms.) It
would be a real kicker to reduce your problem to a variant of that, 
but I don't see any way to do so.]

As always I'd be happy to clarify any of these points if they seem useful.

dave

==============================================================================

Date: Fri, 20 Jan 95 09:18:24 EST
From: [Permission pending]
To: rusin@math.niu.edu
Subject: re your notes on polynomials

Dave,
Your last note was very helpful. I haven't had time to formulate
a good reply. I do appreciate your help.
Thanks,
[Permission pending]

==============================================================================

Date: Mon, 23 Jan 95 12:22:15 EST
From: [Permission pending]
To: rusin@math.niu.edu
Subject: re solution of nonlinear polynomial systems

Dave,
The latest J. Mechanical Design (ASME) has several articles which discuss
the solution of nonlinear polynomial systems.
One of these is homotopy (or continuation) which evidently is described
in a  book by Morgan (Solving Polynomial Systems Using Continuation for
Scientific and Engineering Problems, 1987, Prentice Hall). Do you know anything
about this method?
Thanks,
[Permission pending]

==============================================================================

Date: Wed, 25 Jan 95 11:24:47 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re:  re solution of nonlinear polynomial systems

Sorry, I'm not familiar with this method, but I have a suspicion of what's
up. Given, for example, the equation x^2+y^2=1, you can solve for  y  as
a function of  x  as  y=sqrt(1-x^2). Thus you confidently assert that
when  x=3/5, y=4/5. But as you increase  x  to x=1, you find that y decreases
to zero. As you decrease  x  again, you may find it natural  or unavoidable 
to have  y taking small _negative_ values. As you decrease  x  all the way
to  x=3/5 again, you have found  y=-4/5. Thus, the method of contiuous
extension of your solution has led you to a different solution for y
even with the same value for  x.  A consideration of the set of all solutions
leads you to topological issues like the homotopy groups of your solution set.
Mostly I'd say this is a way of desribing how bad the problem will be, not
really a way of solving it. But, like I say, I'm not familiar with how
homotopy is used in this case.

dave
==============================================================================