Thread Subject: find solution a quadratic polynomial in n variables to make it has minimum value

I have a quadratic polynomial in n variables that mean it has the form
f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h

a,b,c,d,e,f,g are constant.
I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
could you helpe me please to solve that in Matlab?

"leo leonardo" <haboubg@hotmail.com> wrote in message <hnrbav$ts$1@fred.mathworks.com>...
> I have a quadratic polynomial in n variables that mean it has the form
> f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
>
> a,b,c,d,e,f,g are constant.
> I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> could you helpe me please to solve that in Matlab?
==============


But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.

leo leonardo wrote:
> I have a quadratic polynomial in n variables that mean it has the form
> f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
>
> a,b,c,d,e,f,g are constant.
> I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that
> mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> could you helpe me please to solve that in Matlab?

Can all possible pairs Xi*Xj appear, such as X1*X14 X5*X7 ?

Or only X[n]*X[n+1], such as X1*X2 X2*X3 X3*X4 ?

Or only X[2*n-1]*X[2*n] such as X1*X2 X3*X4 X5*X6 ?

Is the polynomial the sum of (a*X[2*n-1]+b*X[2*n])^2 terms (e.g., in your
expression, b would have to equal 2*sqrt(a)*sqrt(c)), except with a constant
term (your h) added at the end?

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hnrco0$ouv$1@fred.mathworks.com>...
> "leo leonardo" <haboubg@hotmail.com> wrote in message <hnrbav$ts$1@fred.mathworks.com>...
> > I have a quadratic polynomial in n variables that mean it has the form
> > f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
> >
> > a,b,c,d,e,f,g are constant.
> > I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> > could you helpe me please to solve that in Matlab?
> ==============
>
>
> But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.

thank you but i don't want solution with zero i want any another solution

Walter Roberson <roberson@hushmail.com> wrote in message <hnrd1g$cv4$1@canopus.cc.umanitoba.ca>...
> leo leonardo wrote:
> > I have a quadratic polynomial in n variables that mean it has the form
> > f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
> >
> > a,b,c,d,e,f,g are constant.
> > I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that
> > mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> > could you helpe me please to solve that in Matlab?
>
> Can all possible pairs Xi*Xj appear, such as X1*X14 X5*X7 ?
>
> Or only X[n]*X[n+1], such as X1*X2 X2*X3 X3*X4 ?
>
> Or only X[2*n-1]*X[2*n] such as X1*X2 X3*X4 X5*X6 ?
>
> Is the polynomial the sum of (a*X[2*n-1]+b*X[2*n])^2 terms (e.g., in your
> expression, b would have to equal 2*sqrt(a)*sqrt(c)), except with a constant
> term (your h) added at the end?

Thank you for your help.yes in my function can all possible pairs Xi*Xj appear

"leo leonardo" <haboubg@hotmail.com> wrote in message <hnreg7$q04$1@fred.mathworks.com>...
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hnrco0$ouv$1@fred.mathworks.com>...
> > "leo leonardo" <haboubg@hotmail.com> wrote in message <hnrbav$ts$1@fred.mathworks.com>...
> > > I have a quadratic polynomial in n variables that mean it has the form
> > > f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
> > >
> > > a,b,c,d,e,f,g are constant.
> > > I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> > > could you helpe me please to solve that in Matlab?
> > ==============
> >
> >
> > But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.
>
> thank you but i don't want solution with zero i want any another solution


If you write down the gradient of f(x) and set it equal to zero, you will get a set of linear equations which in matrix form will look like

A*x=0

If A is singular, x=0 is the only solution. If A is non-singular, the solutions are given by null(A).

However, if x=0 is an unacceptable solution, it's a little hard to see why any solution in the null space of A would be adequate to you. What if I give you a solution that is super-close to x=0, but not equal to it?

Matt J wrote:
> "leo leonardo" <haboubg@hotmail.com> wrote in message
> <hnrbav$ts$1@fred.mathworks.com>...
>> I have a quadratic polynomial in n variables that mean it has the form
>> f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
>>
>> a,b,c,d,e,f,g are constant.
>> I want to find at which X1 X2 ...X16 the f(x) has the miniumm value
>> that mean i want to find at which value of X1 X2 ...X16 we have
>> dF(x)/dx = 0
>> could you helpe me please to solve that in Matlab?
> ==============
>
>
> But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.

Though, Matt, that could have to be a saddle-point rather than a minimum.

Proof: allow X3 to the end to be 0. The expression would reduce to
a*X1^2+b*X1*X2+c*X2^2+h . Let X1 and X2 assume the values +/- 1 . If both are
negative or both are positive, then you would get a+b+c+h . If the two have
opposite signs, then you would get a-b+c+h . If b is non-zero, then one of
these two is an increase in value and the other is a decrease in value. As
this is the general case we are hypothesizing about, we know that a+c and b
exist such that one of a+c+b or a+c-b will be negative and the other positive;
  in such cases, we would have a saddle-point .


As this is a multivariate case, we have to form the partial derivatives with
respect to each variable. With respect to X1, the above original expression
would be d f(x)/d X1 = 2*a*X1 + b*X2 . To solve for inflection points we
equate this to 0 and note that X2 is considered a constant with respect to X1
(because it is an independent variable), so we would arrive at
X1 = -b*X2/(2*a)
To determine the type of the inflection, second derivative:
d2 f(x)/d X1 = 2*a
Using the usual rule, the inflection is a minimum if this expression is
positive, and a maximum if the expression is negative.

Extending this to the other variables, we see that in each case where the
coefficient of an Xi^2 is positive, we need to choose Xi = 0 to obtain a
minimum. This is likely to simplify the expression a fair bit, and by dropping
some of the cross-terms, may force some of the other variables to be 0 in
order for the first derivative with respect to that variable to be 0.

In some cases, you might find the second derivative to be 0 as well,
indicating a saddle-point. In such a case, the minima with respect to that
variable is going to be at one of the two extrema (no other choice for
something as simple as a quadradic.) The overall minimum for the expression is
thus likely to be a mix of 0's for some variables and extrema for several of
the remaining variables.

Walter Roberson <roberson@hushmail.com> wrote in message <hnrojl$vl$1@canopus.cc.umanitoba.ca>...

>
> Though, Matt, that could have to be a saddle-point rather than a minimum.
>
> Proof:

All that is true, Walter, but the OP spoke of the minimum as occuring where the gradient is zero, from which I assumed that this is an unconstrained problem and that he is sure that the quadratic is convex. I don't complicate my life unless the OP gives me a reason to... :)

Incidentally, if the quadratic has a saddle point, there is no finite miinimum if the problem is unconstrained. When you mentioned "extrema", I assume you were supposing box constraints. But we don't know what kind of constraints, if any, are in play here...

Walter Roberson wrote:
> Matt J wrote:
>> "leo leonardo" <haboubg@hotmail.com> wrote in message
>> <hnrbav$ts$1@fred.mathworks.com>...
>>> I have a quadratic polynomial in n variables that mean it has the form
>>> f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
>>>
>>>
>>> a,b,c,d,e,f,g are constant.
>>> I want to find at which X1 X2 ...X16 the f(x) has the miniumm value
>>> that mean i want to find at which value of X1 X2 ...X16 we have
>>> dF(x)/dx = 0
>>> could you helpe me please to solve that in Matlab?
>> ==============
>>
>>
>> But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.
>
> Though, Matt, that could have to be a saddle-point rather than a minimum.

Analyzing the more general case, you can only get a minimum if your
variables happen to meet certain constraints. The constraints can be
expressed in several ways, but perhaps the easiest way is to find the
constant terms of the Xi^2 in terms of the constants for the cross terms.

If we let C[{i,j}] be the constant term for the product involving Xi*Xj,
and thus C[{i}] are the constant terms for the Xi^2 for i from 1 to the
number of variables, then it can be shown without difficulty that

2*C[{i}] = -sum(C[{i,j},j<>i])
or C[{i}] = -1/2 * sum(C[{i,j},j<>i])

If these values are used, then you are guaranteed that the first
derivative with respect to each of the Xi will be 0. With these values,
it also turns out that the sums of the second derivatives will come out
as zero -- but individual second derivatives will not necessarily be 0.
The individual second derivatives will be 2*C[{i}] and are thus
-sum(C[{i,j},j<>i]) . Therefore if the sum itself is negative, then the
- in front of it will make it positive, thus indicating a minimum for
that partial derivative. For any sum which is positive then because the
- will make that negative,indicating a maximum, you must set the Xi for
that term to 0.

If you do not have the flexibility to set C[{i}] at will, then your
inflection coordinate for X[{i}] becomes -2*C[{i}]/sum(C[{i,j}],j<>i)
and the sign of C[{i}] determines whether the inflection is a maximum or
minimum. If it is a maximum, choose your X[{i}] to be the extrema
furthest from C[{i}].

Note: when I say "extrema" here, that could apply to a constrained
problem, or it could simply mean one of the infinities for an
unconstrained probem.

Walter Roberson <roberson@hushmail.com> wrote in message <hnsqh4$nqh$1@canopus.cc.umanitoba.ca>...

> Analyzing the more general case, you can only get a minimum if your
> variables happen to meet certain constraints. The constraints can be
> expressed in several ways, but perhaps the easiest way is to find the
> constant terms of the Xi^2 in terms of the constants for the cross terms.
==============

No, the well-known necessary and sufficient condition for a quadratic to have an unconstrained minimum is that the Hessian (matrix of 2nd partial derivatives) be non-negative definite. This does not lead to a very tractable relationship between the coefficients of Xi^2 and the cross terms. Sylvester's criterion is about the closest you can get to this.

For constrained quadratic minimization, conditions for the existence of a minimum are even less tractable.
 
> If we let C[{i,j}] be the constant term for the product involving Xi*Xj,
> and thus C[{i}] are the constant terms for the Xi^2 for i from 1 to the
> number of variables, then it can be shown without difficulty that
>
> 2*C[{i}] = -sum(C[{i,j},j<>i])
> or C[{i}] = -1/2 * sum(C[{i,j},j<>i])
=================

So no, unless I've misunderstood you, this will not give you an appropriate test. Take for example the simple unconstrained 2D minimization of X1^2+X2^2 where all the main terms C[{i}] are 1 and all the cross terms C[{i,j}]=0.

This clearly has a minimum at X1=X2=0, but does not satisfy your relation above.

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hnrjiq$niv$1@fred.mathworks.com>...
> "leo leonardo" <haboubg@hotmail.com> wrote in message <hnreg7$q04$1@fred.mathworks.com>...
> > "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hnrco0$ouv$1@fred.mathworks.com>...
> > > "leo leonardo" <haboubg@hotmail.com> wrote in message <hnrbav$ts$1@fred.mathworks.com>...
> > > > I have a quadratic polynomial in n variables that mean it has the form
> > > > f(x)=(a*X1^2)+(b*X1*x2)+(c*X2^2)+d+....+(e*X15^2)+(f*X15*X16)+(g*X16^2)+h
> > > >
> > > > a,b,c,d,e,f,g are constant.
> > > > I want to find at which X1 X2 ...X16 the f(x) has the miniumm value that mean i want to find at which value of X1 X2 ...X16 we have dF(x)/dx = 0
> > > > could you helpe me please to solve that in Matlab?
> > > ==============
> > >
> > >
> > > But it's clear from the formula that dF(x)/dx = 0 occurs when all Xi=0.

thank you for your help.I think your solution is right but i think i will have A*x=B
and not A*x=0 because in my equation i have vorgotten that i have some kX
k is constant.which mean at the end if the matrix A is non singular i will have solution.
thank you very much once again.
> >
> > thank you but i don't want solution with zero i want any another solution
>
>
> If you write down the gradient of f(x) and set it equal to zero, you will get a set of linear equations which in matrix form will look like
>
> A*x=0
>
> If A is singular, x=0 is the only solution. If A is non-singular, the solutions are given by null(A).
>
> However, if x=0 is an unacceptable solution, it's a little hard to see why any solution in the null space of A would be adequate to you. What if I give you a solution that is super-close to x=0, but not equal to it?