1
$\begingroup$

Let $\mathbf{A}$ and $\mathbf{b}$ be a symmetric $N\times N$ real matrix and $N\times 1$ real vector respectively. Then consider the set of points in $\mathbb{R}^2$ defined as \begin{align} \mathbb{S}=\{\left(\mathbf{u}^T\mathbf{A}\mathbf{u},\mathbf{b}^T\mathbf{u}\right)\in\mathbb{R}^2,\mathbf{u}^T\mathbf{u}=1\} \end{align} That $\mathbb{S}$ is bounded is obvious. I was wondering if it had any other properties. In particular I am looking at convexity, similar to numerical ranges. If not, what are the conditions on $\mathbf{A}$ and $\mathbf{b}$ for the convexity and so on.

Motivation: Consider the optimization problem \begin{align} &\min_{\mathbf{u}\in \mathbb{R}^N}\mathbf{u}^T\mathbf{A}\mathbf{u}+\mathbf{b}^T\mathbf{u} \\\ \mbox{subject to }\\\ &\mathbf{u}^T\mathbf{u}=1 \end{align} Then using the definition of $\mathbb{S}$ as earlier, I can write the above problem as \begin{align} \min_{(x,y)\in\mathbb{S}}x+y \end{align} Thus if $\mathbb{S}$ is convex, the above problem will be convex.

$\endgroup$
3
$\begingroup$

I don't know if your question admits a general answer, but for sure $\mathbb{S}$ is not always convex. Indeed, let us consider the following example: $$\mathbf{A} = \begin{bmatrix}1 & 0 \\ 0 & 2\end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix}1\\ 0\end{bmatrix}.$$ Then we have $\mathbb{S}=\{(u_1^2+2u_2^2,u_1): \mathbf{u}^T \mathbf{u} = 1\}$. With few simple manipulations, we can parametrize $\mathbb{S}$ in the following way: $$\mathbb{S} = \{(2-\cos^2(t),cos(t)): t \in [0,2\pi)\},$$ and this is a continuous section of the parabola $\{x = 2-y^2\}$, that is not convex in $\mathbb{R}^2$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I also run several random experiments with $N=2$ in Matlab, but I never found $\mathbb{S}$ to be convex... $\endgroup$ – Paglia Feb 26 '14 at 15:49
1
$\begingroup$

We can solve directly your problem. We assume that $b$ is not an eigenvector of $A$. Let $f:u\rightarrow u^TAu+b^Tu,\;g:u\rightarrow u^Tu-1$. There is a real $\lambda$ and a unitary $u=(u_i)_i$ s.t. $Df_u+\lambda Dg_u=0$, that is $(A+\lambda I)u=-b/2, \;u^Tu=1$. We may assume that $A=diag(\lambda_i)_i$ where the $\lambda_i$ are real. One obtains, for every $i$, $u_i=\dfrac{-b_i}{2(\lambda+\lambda_i)}$ with $\sum_i\dfrac{b_i^2}{(\lambda+\lambda_i)^2}=4$. Thus $\lambda$ is a root of a polynomial $P$ of degree $2N$. The sequel is easy.

EDIT: The degree of the previous polynomial $P$ is $2N$ (edited). Unfortunately, $P$ seems to have no special properties ; indeed numerical experiments, when $N=3,4$, give for $P$ a Galois group equal to $S_6,S_8$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ sorry, but what does the sequel prove? $\endgroup$ – dineshdileep Mar 4 '14 at 4:01
  • $\begingroup$ The sequel proves nothing ! I give a method to solve your optimization problem: $\min_{u^Tu=1}u^TAU+b^Tu$. This method needs the calculation of $spectrum(A)$ and to find the roots of a polynomial of degree $2N-2$. Thus we have $2N-2$ candidates and we choose the one that realizes the minimum of $f$. Remark: your problem is not a convex one, even if $b=0$, because $\{u^Tu=1\}$ is not convex and $A$ is not necessarily $\geq 0$ or $\leq 0$. $\endgroup$ – loup blanc Mar 4 '14 at 9:39
  • $\begingroup$ oh, I wrongly assumed you are talking about the question I posed rather than the source of it. Unfortunately, I already reached this point. See this math.stackexchange.com/questions/689894/…. $\endgroup$ – dineshdileep Mar 4 '14 at 12:10
  • $\begingroup$ I was trying to approach the problem from a different angle. $\endgroup$ – dineshdileep Mar 4 '14 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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