# How can I find the minimizer of the following optimization problem?

I want to know whether the following optimization problem falls under "convex optimization". The problem at hand is minimizing the following objective function, i.e., $$\left\{\min_{\boldsymbol{\beta}\in \mathbb{R}^{d}} \sum_{i=1}^{n} \left(y_{i}-\boldsymbol{\beta}^{T}\mathbf{A}\boldsymbol{\beta}\right)^{2}: y_{i}\in \mathbb{R}, \mathbf{A}\in \mathbb{R}^{d\times d} \right\}$$ where $\mathbf{A}$ is symmetric but not positive definite. I wish to find the minimizer $\boldsymbol{\beta}$ of the above optimization problem. At first glance, I thought because $f(\boldsymbol{\beta}) = \boldsymbol{\beta}^{T}\mathbf{A}\boldsymbol{\beta}$ is quadratic and $g(x) = x^{2}$ is also quadratic which are both convex, the composition $g \circ f$ will also be convex. How can I find the minimizer $\boldsymbol{\beta}$?

• $f(\boldsymbol{\beta}) = \boldsymbol{\beta}^{T}\mathbf{A}\boldsymbol{\beta}$ is not necessarily convex... Its Hessian at any $\boldsymbol{\beta}$ is $2A$, and since $A$ needs not be positive definite, it fails. – Gabriel Romon Sep 5 '17 at 16:57
• @LeGrandDODOM Then this does that mean this nonconvex optimization problem becomes very difficult to solve? – Daeyoung Lim Sep 5 '17 at 17:00
• It's possible your problem doesn't even have a solution to begin with ! Your objective function is continuous, but the constraint domain is not bounded, and I don't think your objective function is coercive either (see definition here). – Gabriel Romon Sep 5 '17 at 17:04
• The objective is clearly bounded below, and feasible, so it definitely has a solution. – Michael Grant Sep 6 '17 at 1:50
• Your composition rule is invalid. Please consult a convex optimization textbook like Boyd & Vandenberghe for valid examples of composition rules. – Michael Grant Sep 6 '17 at 1:51

This particular instance should be trivial to solve. Let $x = \beta^TA\beta$. Solve the scalar least-squares-problem that arises in $x$. Denote that solution $x^{\star}$. Let $v$ be any vector such that $x^{\star}$ and $v^TAv$ have the same sign (e.g., if positive let $v$ be an eigenvector associated to a positive eigenvalue). Now scale that vector suitably and pick $\beta = \frac{\sqrt{|x^{\star}|}}{\sqrt{v^TAv}}v$.
I assume $A$ is indefinite and thus has both negative and positive eigenvalues. If not, you would have to add constraints $x\geq 0$ or $x\leq 0$ in the first problem.