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 a constrained optimization problem - MathOverflow

Convexity of a constrained optimization problem