Convexity of a constrained optimization problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:22:41Z http://mathoverflow.net/feeds/question/66233 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66233/convexity-of-a-constrained-optimization-problem Convexity of a constrained optimization problem Will 2011-05-27T21:40:46Z 2011-05-30T06:50:53Z <p>Hi, this is a continuation of a previous question I asked about the convexity of an optimization problem I am working with. </p> <p>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 &amp; -p_{N}^*/a_0 \\ p_{N}/a_0 &amp; 1 \end{array}\right) \left(\begin{array}{cc} 1 &amp; 0 \\ 0 &amp; z_{N}(\vec{x}_i) \end{array}\right) \cdots \\ \left(\begin{array}{cc} 1 &amp; -p_1^*/a_0 \\ p_1/a_0 &amp; 1 \end{array}\right) \left(\begin{array}{cc} 1 &amp; 0 \\ 0 &amp; 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 &amp; \cdots &amp; 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. </p> <p>Here is the optimization problem: $$\begin{array}{lll} \textrm{maximize} &amp; a_0 &amp; \\ \textrm{subject to} &amp; 0 \leq a_0 \leq 1 &amp; \\ &amp; \vert p_j \vert \leq a_0, &amp; j = 1,\dots,N \\ &amp; \vert B^d_i - B_i(a_0,\mathbf{p}) \vert \leq \delta_i, &amp; i = 1,\dots,N_s \\ &amp; a_0^2 \prod_{j=1}^N(1+\vert p_j \vert^2/a_0^2) \leq 1, &amp; \end{array}$$ 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}$. </p> <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:</p> <p>$$\begin{array}{lll} \textrm{minimize} &amp; r &amp; \\ \textrm{subject to} &amp; \delta_i^{-2} \vert B^d_i - B_i(\mathbf{p};a_0) \vert^2 \leq r, &amp; i = 1,\dots,N_s \\ &amp; \vert p_j \vert \leq 1, &amp; j = 1,\dots,N \\ &amp; a_0^2\prod_{j=1}^{N}\left(1 + \vert p_j \vert^2/a_0^2\right) \leq 1, \end{array}.$$ I solve this subproblem using the barrier method, with Quasi-Newton search directions for $\mathbf{p}$.</p> <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.</p> <p>My question: Is this problem convex? </p> <p>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?</p>