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}$?

  • $\begingroup$ $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. $\endgroup$ – Gabriel Romon Sep 5 '17 at 16:57
  • $\begingroup$ @LeGrandDODOM Then this does that mean this nonconvex optimization problem becomes very difficult to solve? $\endgroup$ – Daeyoung Lim Sep 5 '17 at 17:00
  • $\begingroup$ 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). $\endgroup$ – Gabriel Romon Sep 5 '17 at 17:04
  • $\begingroup$ The objective is clearly bounded below, and feasible, so it definitely has a solution. $\endgroup$ – Michael Grant Sep 6 '17 at 1:50
  • $\begingroup$ Your composition rule is invalid. Please consult a convex optimization textbook like Boyd & Vandenberghe for valid examples of composition rules. $\endgroup$ – 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.

| cite | improve this answer | |

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.