User will - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:09:05Z http://mathoverflow.net/feeds/user/13385 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> http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2 Convexity of $\frac{1}{2}\vert x_1 + x_2 + x_3 - x_1x_2x_3\vert^2$ Will 2011-05-26T13:40:35Z 2011-05-26T19:33:15Z <p>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$? </p> <p>This comes from the following expression, for general N:</p> <p>$$\frac{1}{2}\left\vert (\begin{array}{cc} 0 &amp; 1 \end{array}) \left(\begin{array}{cc} 1 &amp; -x_N \\ x_N &amp; 1 \end{array}\right) \cdots \left(\begin{array}{cc} 1 &amp; -x_1 \\ x_1 &amp; 1 \end{array} \right) \left(\begin{array}{c} 1 \\ 0\end{array}\right)\right\vert^2$$</p> <p>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.</p> <p>Thanks!</p> http://mathoverflow.net/questions/57252/convex-polynomial-homogenization-and-convexity/66067#66067 Answer by Will for Convex polynomial homogenization and convexity Will 2011-05-26T14:57:07Z 2011-05-26T14:57:07Z <p>Amir - thanks for your nice answer. I did end up figuring this one out:</p> <p>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 $$\label{eq:sqrtabmag} \sqrt{\prod_{j=1}^{N_t} \left( 1 + \vert p_j \vert^2 \right)},$$ whose logarithm is: $$\label{eq:logsqrtabmag} \frac{1}{2}\sum_{j=1}^{N_t} \log\left(1 + \vert p_j \vert^2 \right).$$ The logarithm's Hessian matrix is diagonal with entries $$\begin{array}{ll} \frac{1 - \vert p_j \vert^2}{( 1 + \vert p_j \vert^2 )^2}, &amp; j=1,\dots,N_t, \end{array}$$ 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.</p> http://mathoverflow.net/questions/57252/convex-polynomial-homogenization-and-convexity Convex polynomial homogenization and convexity Will 2011-03-03T13:32:50Z 2011-05-26T14:57:07Z <p>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.</p> <p>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 &lt; a$) is</p> <p>$a^2 \prod_{n=1}^N \left(1 + \vert p_n \vert^2/a^2\right)$.</p> <p>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.</p> <p>Thank you!</p> http://mathoverflow.net/questions/66233/convexity-of-a-constrained-optimization-problem Comment by Will Will 2011-05-30T06:51:24Z 2011-05-30T06:51:24Z Hi Fedja - just updated with a description of the algorithm. Thanks! http://mathoverflow.net/questions/66233/convexity-of-a-constrained-optimization-problem Comment by Will Will 2011-05-28T08:05:20Z 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. http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2/66063#66063 Comment by Will Will 2011-05-27T20:49:07Z 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! http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2/66063#66063 Comment by Will Will 2011-05-26T16:27:28Z 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... http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2/66063#66063 Comment by Will Will 2011-05-26T15:55:05Z 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. http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2/66063#66063 Comment by Will Will 2011-05-26T15:40:48Z 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: $$6x_1^2 x_2^2 + x_2^4 + 6x_1x_2^3$$ What am I missing here? http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2 Comment by Will Will 2011-05-26T14:44:20Z 2011-05-26T14:44:20Z Ah, thank you for doing that! http://mathoverflow.net/questions/66056/convexity-of-frac12-vert-x-1-x-2-x-3-x-1x-2x-3-vert2 Comment by Will Will 2011-05-26T14:19:52Z 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. http://mathoverflow.net/questions/57252/convex-polynomial-homogenization-and-convexity Comment by Will Will 2011-03-03T16:36:35Z 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 &gt;= 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 &gt; 0.