Cfrgtkky

I need to solve a convex quadratic problem numerically:

$min f(x) = frac{1}{2} x^top A x - b^top x$,

where $A$ is a very large and ill-conditioned semi positive definite matrix. Typical conjugate gradient method doesn't work well. SGD is too slow.

I'm looking for a good numerical method with relatively less computational effort.

Any experience or suggestions? Thank you!

I assume you are looking to minimize $f(x)$, and that $A$ is symmetric and positive semi-definite.

• If $b notin Null(A)^{perp}$ then there is a vector $v in Null(A)$ such that $b^Tv neq 0$. Without loss of generality assume $b^Tv >0$ (else multiply $v$ by $-1$). Then for all real numbers $theta$ we get:
  $$ f(theta v) = 0 + (theta)(-b^Tv)$$
  so $lim_{thetarightarrowinfty} f(theta v) = -infty$ and no minimizer exists.



• 
  

  Else, $b in Null(A)^{perp} = Col(A^T) = Col(A)$. Just find any vector $r$ such that $Ar=b$. Then:
  begin{align}
  frac{1}{2}(x-r)^TA(x-r) &= frac{1}{2}x^TAx - x^TAr + frac{1}{2}r^TAr \
  &= f(x) + frac{1}{2}r^TAr
  end{align}
  and this is clearly minimized at $x^*=r$, so
  $$ f(x^*) = f(r) = -frac{1}{2}r^TAr$$

  
  
  

  ---

  
  

In other words, the problem reduces to Gaussian elimination: Find a vector $r$ such that $Ar=b$. If no such $r$ exists then no minimizer exists.