4
$\begingroup$

Anybody have any tips on how to show that the function $\frac{1}{2}\vert x_1 + x_2 + x_3 - x_1x_2x_3\vert^2$ is convex in $\mathbf{x}$, where $\vert x_i \vert \leq 1$?

This comes from the following expression, for general N:

\begin{equation} \frac{1}{2}\left\vert (\begin{array}{cc} 0 & 1 \end{array}) \left(\begin{array}{cc} 1 & -x_N \\\ x_N & 1 \end{array}\right) \cdots \left(\begin{array}{cc} 1 & -x_1 \\\ x_1 & 1 \end{array} \right) \left(\begin{array}{c} 1 \\\ 0\end{array}\right)\right\vert^2 \end{equation}

It is of course straightforward to calculate the Hessian of this function for N = 3, but it is not readily apparent to me that the Hessian is positive semidefinite. A Monte Carlo simulation over the range of the function does not reveal any $\mathbf{x}$ for which the Hessian has negative eigenvalues. So I believe the above N=3 function is convex. However, what I am hoping is to find a way to show that the function is convex for any N.

Thanks!

$\endgroup$
3
  • 3
    $\begingroup$ In order to attract more potential solvers (who are coming from pure mathematics), it would probably be better to cut back on the jargon, particularly all the initializations (e.g., NMR, RF, PSD -- I at any rate am not familiar with these). Also, you might as well specify the precise function for any N, rather than use the hand-waving "similar". $\endgroup$
    – Todd Trimble
    May 26, 2011 at 14:11
  • $\begingroup$ Thanks - I removed the background info and tried to add the full expression for general N, but the LateX processing seems to fail on \array's? So there should be a newline between the $-x_N$ and the $x_N$, and also between the $-x_1$ and the $x_1$, and between the right 1 and 0. $\endgroup$
    – Will
    May 26, 2011 at 14:19
  • $\begingroup$ I fixed your arrays. You need to use triple backslashes \\\ instead of the usual double backslashes \\ because the backslashes are also escape characters here. $\endgroup$ May 26, 2011 at 14:42

1 Answer 1

5
$\begingroup$

The answer is NO. The restriction to the plane $x_1+x_2+x_3=0$ is the function $\frac12(x_1x_2x_3)^2$, that is $$(x_1,x_2)\mapsto\frac12x_1^2x_2^2(x_1+x_2)^2.$$ Edit. This function is not convex at $(\frac12,\frac12,-1)$, for instance. The Jacobian of the above map is negative at that point.

$\endgroup$
8
  • $\begingroup$ Hi Denis, thanks for your thoughtful reply. I think I understand your reasoning, but when I calculate the second derivative of the restricted function and substitute $(-1,\frac{1}{2})$, I get 1.375 as the second derivative with respect to $x_1$. Here is the expression for that second derivative that I get: \begin{equation} 6x_1^2 x_2^2 + x_2^4 + 6x_1x_2^3 \end{equation} What am I missing here? $\endgroup$
    – Will
    May 26, 2011 at 15:40
  • 3
    $\begingroup$ Or, better, notice that it is $0$ for $x_1=-x_2$ and $x_1=0$ and positive in between. $\endgroup$
    – fedja
    May 26, 2011 at 15:42
  • $\begingroup$ All you have to do is take a different point. Try $x_1=-1/2$, $x_2=1$. $\endgroup$ May 26, 2011 at 15:47
  • $\begingroup$ @ Will I doubt you need the convexity just for the sake of it. What are you really after? $\endgroup$
    – fedja
    May 26, 2011 at 15:48
  • $\begingroup$ Hi fedja - this function is a component of the objective in an optimization problem, in which I seek to find the vector $\mathbf{x}$ which minimizes the maximum squared error between the function in the norm and a target, e.g., $\vert x_1 + x_2 + x_3 - x_1 x_2 x_3 - d\vert^2$, where $d$ is a constant. $\endgroup$
    – Will
    May 26, 2011 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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