Let f:R^n --> R be a polynomial of n variables and non-negative coefficients and K := { (x_1, ..., x_n) \in R^n ; x_1+...+x_n = s } for some fixed s > 0. Are there any good characterizations for f being convex on K? Any that would be efficiently testable?
I could provide a few more structural information on f, if that would help.
Note that K is not an open set, so the characterization via positive semidefinite Hessian is not applicable.
<mailaddress_on_requ...@invalid.invalid> wrote: > Let f:R^n --> R be a polynomial of n variables and non-negative coefficients > and K := { (x_1, ..., x_n) \in R^n ; x_1+...+x_n = s } for some fixed s > 0. > Are there any good characterizations for f being convex on K? Any that would > be efficiently testable?
> I could provide a few more structural information on f, if that would help.
> Note that K is not an open set, so the characterization via positive > semidefinite Hessian is not applicable.
> Thank you!
Such issues appear in constrained optimization, where one needs to test for convexity on a linear subspace, using the *projected Hessian*. For example, you are in the subspace S = {x: <e,x> = s}, where e = (1,1,...,1) \in R^n Nd <,> = inner product. If H = hessian of f at a given point x0, you would like to have d^T H d >= 0 for all d \in T = {d : <e,d> = 0. Note that if d_1,...,d_{n-1} are considered as independent, d \in T if d = E*e, where e = (d_1,...,d_{n-1})^T and E = [1 0 0 .... 0] [0 1 0 .... 0] .......... [0 0 0 .... 1] [-1 -1 ... -1]
is an n x (n-1) matrix. Then, for d \in T we have d^T H d = e^T E^T H E e. The (n-1) x (n-1) matrix R = E^T H E is the projected hessian, which must be positive semidefinite. This allows "easy" testing if f is a quadratic with numerical coefficients. The general case (quadratic with symbolic coefficients or non-quadratic) is, of course, much harder and, unfortunately, is perhaps what you want.
On Sat, 5 Jul 2008 14:55:25 +0000 (UTC), "D. Snyder"
<mailaddress_on_requ...@invalid.invalid> wrote: >Let f:R^n --> R be a polynomial of n variables and non-negative coefficients >and K := { (x_1, ..., x_n) \in R^n ; x_1+...+x_n = s } for some fixed s > 0. >Are there any good characterizations for f being convex on K? Any that would >be efficiently testable?
>I could provide a few more structural information on f, if that would help.
>Note that K is not an open set, so the characterization via positive >semidefinite Hessian is not applicable.
Let K' be the inverse image of K under T. Note that K' is an open subset of R^(n-1), and that f is convex on K if and only if the composition f o T is convex on K'.
>Thank you!
David C. Ullrich
"Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
>> Let f:R^n --> R be a polynomial of n variables and non-negative coefficients >> and K := { (x_1, ..., x_n) \in R^n ; x_1+...+x_n = s } for some fixed s > 0. >> Are there any good characterizations for f being convex on K? Any that would >> be efficiently testable? > Such issues appear in constrained optimization, where one needs to > test for convexity on a linear subspace, using the *projected > Hessian*. For example, you are in the subspace S = {x: <e,x> = s}, > where e = (1,1,...,1) \in R^n Nd <,> = inner product. If H = hessian > of f at a given point x0, you would like to have d^T H d >= 0 for all > d \in T = {d : <e,d> = 0. Note that if d_1,...,d_{n-1} are considered > as independent, d \in T if d = E*e, where e = (d_1,...,d_{n-1})^T and > E = [1 0 0 .... 0] > [0 1 0 .... 0] > .......... > [0 0 0 .... 1] > [-1 -1 ... -1]
> is an n x (n-1) matrix. > Then, for d \in T we have d^T H d = e^T E^T H E e. The (n-1) x (n-1) > matrix R = E^T H E is the projected hessian, which must be positive > semidefinite. This allows "easy" testing if f is a quadratic with > numerical coefficients. The general case (quadratic with symbolic > coefficients or non-quadratic) is, of course, much harder and, > unfortunately, is perhaps what you want.
Thank you Ray and David! My application has numeric coefficients and its restriction to quadratic f (which I guess is required in order that the Hessian does not depend on the point x0) is already interesting, so this helps me a lot.
There is still a catch, however. I realized that I forgot to write an important additional constraint. In fact my set K is
K := { (x_1, ..., x_n) \in R^n ; x_1+...+x_n = s and x_i \geq 0 for all i }
Following the basic concept of the solution, it is now helpful to find a mapping g between some open subset in R^{n-1} and K that preserves convexity, in the sense that the composed mapping of f after g is convex if and only if f is convex. Maybe it would already suffice to find such a mapping g between an open subset of R^{n-1} and a set of which the *closure* equals K, but I am not sure. For instance, if n=2 and s=1, that could be from the real interval (0,1) into K where g(t)=(t, 1-t) \in R^2. But I do not see a straight-forward generalization of that to general n, at least none that looks like preserving convexity.
