User will - MathOverflow

Convexity of a constrained optimization problem

2011-05-27T21:40:46Z

Hi, this is a continuation of a previous question I asked about the convexity of an optimization problem I am working with.

Consider the function \begin{multline} B_i(a_0,\mathbf{p}) \equiv B(\vec{x}_i,a_0,\mathbf{p}) = \left(\begin{array}{cc} 1 & -p_{N}^*/a_0 \\ p_{N}/a_0 & 1 \end{array}\right) \left(\begin{array}{cc} 1 & 0 \\ 0 & z_{N}(\vec{x}_i) \end{array}\right) \cdots \\ \left(\begin{array}{cc} 1 & -p_1^*/a_0 \\ p_1/a_0 & 1 \end{array}\right) \left(\begin{array}{cc} 1 & 0 \\ 0 & z_1(\vec{x}_i) \end{array}\right) \left(\begin{array}{cc} a_0 \\ 0 \end{array} \right), \end{multline} where the variable $a_0$ is between 0 and 1, and the variables $\mathbf{p} = [\begin{array}{ccc} p_1 & \cdots & p_N \end{array}]$ satisfy $\vert p_j \vert \leq a_0$. The $z_j(\vec{x}_i)$'s are complex exponentials, e.g., $z_j(\vec{x}_i) = e^{\imath \vec{x}_i \cdot \vec{k}_j}$, where $\vec{x}_i$ is a spatial location and $\vec{k}_j$ is a spatial frequency location.

Here is the optimization problem: \begin{equation} \begin{array}{lll} \textrm{maximize} & a_0 & \\ \textrm{subject to} & 0 \leq a_0 \leq 1 & \\ & \vert p_j \vert \leq a_0, & j = 1,\dots,N \\ & \vert B^d_i - B_i(a_0,\mathbf{p}) \vert \leq \delta_i, & i = 1,\dots,N_s \\ & a_0^2 \prod_{j=1}^N(1+\vert p_j \vert^2/a_0^2) \leq 1, & \end{array} \end{equation} where $B^d_i$ is a target spatial pattern I want to achieve at spatial location $\vec{x}_i$, with maximum error $\delta_i$, and $N_s$ is the number of spatial locations I consider. $B^d_i$ has a maximum magnitude of 1. The variables are $a_0$ and $\mathbf{p}$.

Here is how I solve it, using bisection on $a_0$. I set initial lower and upper bounds on $a_0$ based on the result of a much faster, approximate optimization method. Then, for the initial lower-bound $a_0$ value, I solve the following feasibility problem, holding $a_0$ fixed:

\begin{equation} \begin{array}{lll} \textrm{minimize} & r & \\ \textrm{subject to} & \delta_i^{-2} \vert B^d_i - B_i(\mathbf{p};a_0) \vert^2 \leq r, & i = 1,\dots,N_s \\ & \vert p_j \vert \leq 1, & j = 1,\dots,N \\ & a_0^2\prod_{j=1}^{N}\left(1 + \vert p_j \vert^2/a_0^2\right) \leq 1, \end{array}. \end{equation} I solve this subproblem using the barrier method, with Quasi-Newton search directions for $\mathbf{p}$.

If that problem is solved with $r \leq 1$, then these values of $a_0$ and $\mathbf{p}$ are feasible, and I can set the lower $a_0$ bound to this value of $a_0$, and repeat the problem at the midway point between this value of $a_0$ and the upper bound $a_0$. If $r > 1$, then these $a_0$ and $\mathbf{p}$ are infeasible, and I set the upper bound $a_0$ to this $a_0$, and solve the problem again for the midway point between the lower bound $a_0$ and the new upper bound $a_0$. I stop when $a_0$ stops changing by very much.

My question: Is this problem convex?

I have already proven that $a_0^2 \prod_{j=1}^N(1+\vert p_j \vert^2/a_0^2) \leq 1$ is convex in the domain of this problem, so it remains to be answered whether the $B_i$ error functions are convex. In a response to a previous question I asked it was shown that when $B^d_i = 0$, $\vec{x}_i = 0$ and $N=3$, then $\vert B^d_i - B_i(a_0,\mathbf{p})\vert $ is NOT convex. So, is it possible that when I use, for example, the barrier method to solve this problem, that the sum of the log-barriers for the $B_i$ error functions is a convex function?

Convexity of $\frac{1}{2}\vert x_1 + x_2 + x_3 - x_1x_2x_3\vert^2$

2011-05-26T13:40:35Z

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!

Answer by Will for Convex polynomial homogenization and convexity

2011-05-26T14:57:07Z

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.

Convex polynomial homogenization and convexity

2011-03-03T13:32:50Z

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!

Comment by Will

2011-05-30T06:51:24Z

Hi Fedja - just updated with a description of the algorithm. Thanks!

Comment by Will

2011-05-28T08:05:20Z

Hi fedja, thanks for spending some time on it. As mentioned, I currently solve this problem (well, find some local minimum I suppose) using the barrier method. I remain hopeful that there is something provable about the optimality of my solutions, given that the solutions i get are simply very good and much better than competing methods. Furthermore, the algorithm always achieves the correct solutions for toy problems to which I know the answer a priori.

Comment by Will

2011-05-27T20:49:07Z

Hi Fedja - there isn't sufficient space in the comments to write the whole problem out, so I will make a new question... Thanks!

Comment by Will

2011-05-26T16:27:28Z

Ok, I have fixed a bug in my Monte-Carlo sim and now see the non-convexity there as well. Thanks for all the responses! This was very helpful. This question is certainly answered, however, I now need to pose the next logical question...

Comment by Will

2011-05-26T15:55:05Z

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.

Comment by Will

2011-05-26T15:40:48Z

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?

Comment by Will

2011-05-26T14:44:20Z

Ah, thank you for doing that!

Comment by Will

2011-05-26T14:19:52Z

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.

Comment by Will

2011-03-03T16:36:35Z

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.