Convexity of certain objective polynomials?

39 Views Asked by At

We know $\sum_{i=1}^n a_ix_i^2$ is a convex polynomial if $a_i\in\mathbb Z_{\geq0}$ holds.

  1. Is $\sum_{i=1}^n a_ix_i^{2d}$ also convex at every $d\in\{1,2,\dots\}$ if $a_i\in\mathbb Z_{\geq0}$ holds?

  2. Is $\sum_{i=1}^n a_ix_i^{2d+1}$ also convex at every $d\in\{1,2,\dots\}$ if $a_i\in\mathbb Z_{\geq0}$ holds?

What is the easiest way to see this.

$\underline{Motivation}:$ I want to maximize polynomials $$\sum_{i=1}^n x_i^{2d}+M\sum_{j=1}^ma_jy_j$$ and $$\sum_{i=1}^n x_i^{2d}+M\sum_{j=1}^ma_jy_j^2$$ over a convex polytope where $M>0$ and $a_j\in\mathbb Z_{\geq0}$ are fixed and I want to know if these are convex since then the problem is in $P$.

1

There are 1 best solutions below

2
On BEST ANSWER
  1. This is true by looking at the Hessian matrix (which is diagonal and has nonnegative coefficients). This is a reference for convexity detection using the Hessian, this is a reference for checking positive semi-definiteness of your Hessian, and this is a reference for computing eigenvalues of a diagonal matrix.
  2. Clearly, this isn't always true because with $n = 1$, $d = 1$, and $a_1 = 1$, $x^3_1$ is not convex.

You might more generally be interested in sos-convexity