Why Optimization Is Faster than Solving Systems of Equations: A Qualitative Explanation

Most practical problems lead either to solving a system of equation or to optimization. From the computational viewpoint, both classes of problems can be reduced to each other: optimization can be reduced to finding points at which all partial derivatives are zeros, and solving systems of equations can be reduced to minimizing sums of squares. It is therefore natural to expect that, on average, both classes of problems have the same computational complexity -- i.e., require about the same computation time. However, empirically, optimization problems are much faster to solve. In this paper, we provide a possible explanation for this unexpected empirical phenomenon