# Maximising the minimum of a linear combination of polynomials

I have list of finArray of 6 rational polynomials, of degrees of about 4 to 6, in around 200 variables allVars, along with a list of equality-based constraints, pConstraints.

As I've been unable to generate a set of constraint-obeying variables that makes the convex cover of the polynomial values include $$0\in \mathbb{R^6}$$, I strongly suspect there exists a $$6$$-tuple qVals = {q1, q2, q3, q4, q5, q6} of rational values, unique up to multiplication by a positive constant, such that finArray.qVals is always semi-positive for any possible values of allVars obeying pConstraints.

The question is, assuming such a $$6$$-tuple exists, what would the best algorithm be to converge to it? I've tried naively doing Minimize[{finArray.qVals , pConstraints}, allVars] in the hopes of getting a complete description of the solution space, but I lack both sufficient memory and time for this endeavour to be successful.

I've also tried to find values that "extremise" the values of the normalization of the finArray vector, in order to have a guess at what {q1, q2, q3, q4, q5, q6} could look like. However, don't know how to do this systematically enough to guess {q1, q2, q3, q4, q5, q6}.

What I'm looking for is either a numeric algorithm that will converge to a valid qVals, or some way to deduce them analytically in reasonable time and memory.

As a toy example consider:

finArray = {x^3 , x^2 + x^3}
pConstraints= {}
allVars = {x}
qVals = {q1, q2}


Running
answer1 = Minimize[{finArray.qVals , pConstraints}, allVars][[1]]

you will get So the mimimum will be $$-\infty$$ if any of the conditions of the first row are satisfied, or $$0$$ if otherwise. By negating the conditions of the first row, we get the exact conditions under which the minimum is $$0$$.

Running FullSimplify[Not [answer1[[1, 1, 2]]]] gives:

which gives the answer we're looking for:

For the minimum of finArray.qVlrs not to go to $$-\infty$$, our vector qVals must be exactly of the form q1*{1,-1}, with q1 <= 0 .

The problem is scale and computation time. I can't apply here the same method when qVals = {q1, q2, q3, q4, q5, q6} and the polynomials in finArray have 200 variables. Although, by knowing the qVals vector is proportional to a vector of rational numbers, an attempt might be made to guess it if a sufficiently accurate approximation is computed.

We are looking for the real number qs such that the values taken by a linear combination of our polynomials with those qs, under the given equality constraints pConstraints, have a (semi)positive lower bound. It is likely that for all other qs besides those, the lower bound will be $$-\infty$$ anyway.

If we find a set of values for our "polynomial vector" finArray such that interior of the convex cover of that set includes $$0$$, then obviously no compatible qVals vector exists. It would be impossible for finArray.qVals>=0 for all those valuations of finArray simultaneously, if the convex cover of the valuation set were to include $$0$$. My failiure to find such a set is what leads me to believe a non-zero qVals vector exists.

• It would be nice to have a toy example. – yarchik Apr 21 at 14:52
• I've added a toy example. Hopefully this will clarify what I'm trying to achieve. – user3257842 Apr 21 at 15:39
• I still find it very very difficult to understand your question. For instance, what does it mean "interior of the convex cover of that set includes 0"? In your 2D example you refer to 0 as a number, but in all other places 0 is a vector in the interior of a 6D convex hull. Why can't you simply say "Find constraints on $q_1, q_2,\ldots$" such that a sum of polynomials $p_i(x)$ weighted with $q_1, q_2,\ldots$ is never negative. By removing all this highbrow math terminology, your post will be more accessible to simple-minded users like me. – yarchik Apr 22 at 7:46
• Another point is some of your requested conditions, like the method should work for 200 variables polynomial generating rational (!) constraints. Quite unrealistic I would say. Also, your minimal example is too minimal as it does not show at least 2 variables (which would be nontrivial) and it does not illustrate the rational constraints. – yarchik Apr 22 at 7:55