Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a polynomial that I know to be convex. If I homogenize the polynomial, is the resulting homogeneous polynomial also convex? I know that the perspective of a convex function is convex, but cannot find a citation for the homogenization of a convex function.

The function whose convexity I would like to show in the variables $(a,p_1,\dots,p_N)$ for $a > 0$ and under some bound on the magnitudes of the $p_n$'s (I suspect the bound will be $\vert p_n \vert < a$) is

$a^2 \prod_{n=1}^N \left(1 + \vert p_n \vert^2/a^2\right)$.

The function $\prod_{n=1}^N \left(1 + \vert p_n \vert^2\right)$ is log-convex and therefore convex in the $p_n$'s, but I am having difficulty showing that the original function is convex. However, the original function is a homogenized version of this convex function.

Thank you!

share|improve this question
1  
Keep trying. It should work. –  Deane Yang Mar 3 '11 at 14:52
    
But are you trying to prove convexity directly or by computing the Hessian of the homogeneous function in terms of the Hessian of the inhomogeneous function. It seems to me that the latter is a straightforward computation. –  Deane Yang Mar 3 '11 at 16:25
    
Hi Deane, thanks for your response. I would like to prove convexity directly by invoking a result (that I presume to exist somewhere) about convexity of homogenized convex polynomials. This would be the most elegant way to show it I think. But I have also tried to show that x'Hx is >= 0 for the homogeneous function, which of course can be decomposed into a sum involving the Hessian of the inhomogeneous function plus the column/row for the variable a, but I was not successful in doing that, because it was not clear that the inner products involving x and that column+row were > 0. –  Will Mar 3 '11 at 16:36
    
Will, I agree that there should be a direct proof but I don't know it. With the Hessian, I don't recall all the details offhand, but I believe that you can show that the last diagonal term dominates the two terms arising from the last row and column. –  Deane Yang Mar 3 '11 at 18:11
add comment

2 Answers 2

It is definitely not true that the homogenization of a convex polynomial is convex. In fact, any convex polynomial that is not nonnegative will no longer be convex after homogenization. (This is because homogenization preserves lack of nonnegativity and convex homogeneous polynomials are always nonnegative.)

But even if the polynomial is nonnegative, the statement is still not true. Take e.g. the univariate polynomial $10x_1^4-5x_1+2$, which is convex and nonnegative, but its homogenization $10x_1^4-5x_1x_2^3+2x_2^4$ is not convex.

(Of course, for your specific polynomial the statement can be true, but I'm answering the general question that you raised.)

What is true generally is that the homogenization of a polynomial of degree d is convex if and only if the d-th root of the polynomial is convex. See Proposition 4.4 on p. 13 of the following nice paper of Reznick for the precise statement and a proof: http://www.math.uiuc.edu/~reznick/blenders2.pdf

share|improve this answer
add comment
up vote 1 down vote accepted

Amir - thanks for your nice answer. I did end up figuring this one out:

The function $a_0^2 \prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2/a_0^2 \right)$ is convex under certain bounds on $a_0$ and the $p_j$. Consider the function \begin{equation} \label{eq:sqrtabmag} \sqrt{\prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2 \right)}, \end{equation} whose logarithm is: \begin{equation} \label{eq:logsqrtabmag} \frac{1}{2}\sum_{j=1}^{N_t} \log\left(1 + \vert p_j \vert^2 \right). \end{equation} The logarithm's Hessian matrix is diagonal with entries \begin{equation} \begin{array}{ll} \frac{1 - \vert p_j \vert^2}{( 1 + \vert p_j \vert^2 )^2}, & j=1,\dots,N_t, \end{array} \end{equation} which are greater than or equal to zero if $\vert p_j \vert \leq 1$, so the logarithm is convex if $\vert p_j \vert \leq 1$. Because log-convex functions are themselves convex (Ref. \cite{Boyd:ConvexOpt}, \textsection 3.5.1), $\sqrt{\prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2 \right)}$ is also convex if $\vert p_j \vert \leq 1$. Convexity of the function $a_0 \sqrt{\prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2 / a_0^2 \right)}$ for $a_0 > 0$ and $\vert p_j \vert \leq a_0$ follows from the fact that the perspective of a convex function is convex (Ref. \cite{Boyd:ConvexOpt}, \textsection 3.2.6). Finally, because a nonnegative convex function raised to a power $b \geq 1$ is convex (Ref. \cite{Boyd:ConvexOpt}, \textsection 3.2.4), the original function $a_0^2 \prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2 / a_0^2 \right)$ is convex.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.