Monday, November 8, 2021

Some animals are more equal than others: least-squares vs Euclidean norm

A user recently reached out to MOSEK support because the solver returned an UNKNOWN problem/solution status on their (constrained) Least-squares problem, that was implemented in CVXPY . The solver log looked as shown in the first MOSEK log shown below.

The solution we offered was to minimize the Euclidean norm instead of the sum-of-squares. Theoretically, both models are equivalent; their optimal points are the same. But as a great man once said: in theory, theory and practice are the same. In practice, well... Take a look at the MOSEK log for the problem that minimizes the Euclidean norm (second MOSEK log)

Note the following differences between the two MOSEK logs:

• The problem status in the norm problem is primal and dual feasible and the solution status is optimal, in contrast to the least-squares problem.
• The infinity-norm of the solutions in the norm problem are smaller by nearly 5 orders of magnitude compared to the solution of the least-squares problem. This is usually a desirable trait, as explained in the  debugging section of MOSEK docs
• The number of iterations taken by the norm problem is far fewer.
• The objective value of the norm problem is essentially the square root of the least-squares problem (the least-squares problem was not solved to optimality, hence the discrepancy)
Observe that the solution is only guaranteed to be unique if the objective is strictly convex. The objective function is strictly convex if and only if the A matrix (following  this notation) is of full column-rank. If this is not the case, then the two problems might output different optimal solution vectors (as is the case above), but as Orwell would put it, one of those solutions will be more equal than the other

So, at least for CVXPY-MOSEK users (and MOSEK Fusion users!), we recommend the Euclidean norm in place of the sum-of-squares, wherever possible.