We analyze statistical features of the ``optimization landscape'' in a random version of one of the simplest constrained optimization problems of the least-square type: finding the best approximation for the solution of an overcomplete system of $M>N$ linear equations $({ \bf a}_k,{ \bf x})=b_k, \, k=1,\ldots,M$ on the $N-$sphere ${ \bf x}^2=N$. We treat both the $N-$component vectors ${ \bf a}_k$ and parameters $b_k$ as independent mean zero real Gaussian random variables. First, we derive the exact expressions for the mean number of stationary points of the least-square loss function in the framework of the Kac-Rice approach combined with the Random Matrix Theory for Wishart Ensemble, and then perform its asymptotic analysis as $N\to \infty$ at a fixed $\alpha=M/N>1$ in various regimes. In particular, this analysis allows to extract the Large Deviation Function for the density of the smallest Lagrange multiplier $\lambda_{ min}$ associated with the problem, and in this way to find its most probable value. This can be further used to predict the asymptotic minimal value ${ \cal E}_{ min}$ of the loss function as $N\to \infty$. Finally, we develop an alternative approach based on the replica trick to conjecture the form of the Large Deviation function for the density of ${ \cal E}_{ min}$ at $N\gg 1$. As a by-product, we find the value of the { \it compatibility threshold} $\alpha_c$ which is the minimal value of the asymptotic ratio $M/N$ such that the random linear system on the $N-$sphere is typically compatible.
Categories: math-ph cond-mat.dis-nn cond-mat.stat-mech math.MP