Inner Fire
08-02-07, 11:09 PM
Hi guys. This is actually a frustrating research problem I've been stuck on for a while, and while I'm not supposed to say what context this applies to, I'm hoping some of you optimization or math gurus can help me out. The mathematical problem is as follows:
Suppose you have a polynomial function in 2n variables, say x1, x2, ..., xn, y1, y2, ... ,yn. The polynomial has degree k < n and can have several terms with both positive and negative coefficients, but each variable must be in at least one term. Each monomial term in the polynomial has degree at least 2, but is at most degree 1 in any variable (i.e. no squared, cubed, etc). Moreover, if a monomial has xi in it, it can NOT have yi in it, and vice versa. So for example:
Valid:
2*x1*x2 + y2*y3*x5
-x1*x3 + 3*x1*y2
Not Valid:
2*x1^2 (squared term not allowed)
x1+ x2*x3*x4 (degree 1 monomial)
x1*y1 - x2*y3 (x1 and y1 are in the same term)
Suppose I have a convex set described by the following properties: all variables lie between 0 and 1. Variables with different indices (e.g. x1 and y2) have no joint constraints. However, variables with same indices (i.e. x1 and y1) have a joint feasible region that can be described by a convex subset of the unit square. (For now, assume it is simply any convex subset. No further specification is allowed.) A simple way to formulate the constraints is as follows:
(x1,y1) is in S1, (x2,y2) is in S2, ...(xn,yn) is in Sn, where S1...Sn are convex subsets of the unit square. In addition, you have simple linear constraints 0<=xi <=1 and 0<=yi <=1 for all i.
The question: is there a UNIQUE local maximum for the polynomial in this set (i.e. the global maximum)?
You might be tempted to say "no" because the polynomial is not a convex function (In fact, a polynomial of this form with degree >= 2 never has a positive semidefinite Hessian.) However, let me provide a few hints (i.e. approaches or insights that I've thought about).
Hint #1: There are, at worst, saddle points in the polynomial function (in fact, only at the origin!), but no local maxima. Hence, you will expect to find the maxima at a boundary point of the entire set, i.e. it will be on the boundary of ALL sets S1, S2, ..., Sn.
Hint #2: Notice that if you fix all but one variable, the polynomial is a linear function of that variable. Hence if S1, S2, ... ,Sn were all unit squares (i.e. they impose no tighter constraints), you can always find the maximum value by "sliding along the edges," i.e. changing one variable at a time to increase the utility in a linear fashion. You will also find the maximum utility to lie on one of the vertices of the 2n-dimensional unit cube.
Hint #3: (The way I'm currently attacking it) Notice that while "sliding along the edges" can not be done in general, "sliding through the sets" (S1,...,Sn) using two variables at a time (xi, yi) can be done. This is because when fixing other variables, the polynomial becomes a linear function of (xi, yi) (Remember that xi and yi are never in the same monomial; hence linearity holds.) The consequence is that you have gradient lines a*xi+b*yi = C, and you can always find the optimal point (or range of points) in convex set Si where C is largest. If this "sliding through the sets" is done sequentially by each pair of x and y's, the evaluated polynomial will ALWAYS increase in value until you hit a "Nash equilibrium" of sorts. (The nash eq exists because the polynomial value can be treated as a potential that is always increasing at every iteration, but is bounded above.) The question is: is this Nash equilibrium a local optimum (My intuition says yes, but I have no proof yet.)? And is this local optimum the global optimum?
If you can not prove it, some helpful references would be nice as well. =) I started attacking this problem because through simulations with various polynomials, it seemed that "sliding through sets" always converged to a unique point, regardless of the starting point. I just can't prove it. :eek: Thanks!
Suppose you have a polynomial function in 2n variables, say x1, x2, ..., xn, y1, y2, ... ,yn. The polynomial has degree k < n and can have several terms with both positive and negative coefficients, but each variable must be in at least one term. Each monomial term in the polynomial has degree at least 2, but is at most degree 1 in any variable (i.e. no squared, cubed, etc). Moreover, if a monomial has xi in it, it can NOT have yi in it, and vice versa. So for example:
Valid:
2*x1*x2 + y2*y3*x5
-x1*x3 + 3*x1*y2
Not Valid:
2*x1^2 (squared term not allowed)
x1+ x2*x3*x4 (degree 1 monomial)
x1*y1 - x2*y3 (x1 and y1 are in the same term)
Suppose I have a convex set described by the following properties: all variables lie between 0 and 1. Variables with different indices (e.g. x1 and y2) have no joint constraints. However, variables with same indices (i.e. x1 and y1) have a joint feasible region that can be described by a convex subset of the unit square. (For now, assume it is simply any convex subset. No further specification is allowed.) A simple way to formulate the constraints is as follows:
(x1,y1) is in S1, (x2,y2) is in S2, ...(xn,yn) is in Sn, where S1...Sn are convex subsets of the unit square. In addition, you have simple linear constraints 0<=xi <=1 and 0<=yi <=1 for all i.
The question: is there a UNIQUE local maximum for the polynomial in this set (i.e. the global maximum)?
You might be tempted to say "no" because the polynomial is not a convex function (In fact, a polynomial of this form with degree >= 2 never has a positive semidefinite Hessian.) However, let me provide a few hints (i.e. approaches or insights that I've thought about).
Hint #1: There are, at worst, saddle points in the polynomial function (in fact, only at the origin!), but no local maxima. Hence, you will expect to find the maxima at a boundary point of the entire set, i.e. it will be on the boundary of ALL sets S1, S2, ..., Sn.
Hint #2: Notice that if you fix all but one variable, the polynomial is a linear function of that variable. Hence if S1, S2, ... ,Sn were all unit squares (i.e. they impose no tighter constraints), you can always find the maximum value by "sliding along the edges," i.e. changing one variable at a time to increase the utility in a linear fashion. You will also find the maximum utility to lie on one of the vertices of the 2n-dimensional unit cube.
Hint #3: (The way I'm currently attacking it) Notice that while "sliding along the edges" can not be done in general, "sliding through the sets" (S1,...,Sn) using two variables at a time (xi, yi) can be done. This is because when fixing other variables, the polynomial becomes a linear function of (xi, yi) (Remember that xi and yi are never in the same monomial; hence linearity holds.) The consequence is that you have gradient lines a*xi+b*yi = C, and you can always find the optimal point (or range of points) in convex set Si where C is largest. If this "sliding through the sets" is done sequentially by each pair of x and y's, the evaluated polynomial will ALWAYS increase in value until you hit a "Nash equilibrium" of sorts. (The nash eq exists because the polynomial value can be treated as a potential that is always increasing at every iteration, but is bounded above.) The question is: is this Nash equilibrium a local optimum (My intuition says yes, but I have no proof yet.)? And is this local optimum the global optimum?
If you can not prove it, some helpful references would be nice as well. =) I started attacking this problem because through simulations with various polynomials, it seemed that "sliding through sets" always converged to a unique point, regardless of the starting point. I just can't prove it. :eek: Thanks!