Check Polynomial for Convexity
D. Snyder
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!
Ray Vickson
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.
R.G. Vickson
David C. Ullrich
Define T : R^(n-1) -> R^n by
T(x) = (x_1, ..., x_{n-1}, s - (x_1 + ... + x_{n-1}).
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.)
D. Snyder
>> 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.
Maybe someone knows a hint.
Thank you!