Geometric and numerical aspects of redundancy

[stephane-caron]

I propose to add the following problem to the github_ffa test set. The problem can be constructed as follows:

def get_problem(alpha: float):
    return Problem(
        P=np.eye(2),
        q=np.zeros(2),
        G=None,
        h=None,
        A=np.array([[1.0, 0.0], [1.0, alpha]]).reshape((1, 2)),
        b=np.array([0.0, 1.0]),
        lb=None,
        ub=None,
        name=f"weds_{alpha=}",
        optimal_cost=0.5 / (1 + alpha ** 2),
    )

Motivation

This problem is fully determined by its constraints, that is, the cost function is irrelevant. The condition number of the constraints matrix is $1/\alpha$, which can trip some solvers off depending on their algorithm.

For instance, OSQP solves the problem for $\alpha=10^{-3}$:

In [14]: P, q, A, b = get_problem(1e-3) 
    ...: solve_qp(P, q, A=A, b=b, solver="osqp")                                                                                                   
/home/frankd/src/qpsolvers/qpsolvers/solvers/conversions/warnings.py:35: UserWarning: Converted P to scipy.sparse.csc.csc_matrix
For best performance, build P as a scipy.sparse.csc_matrix rather than as a numpy.ndarray
  warnings.warn(
/home/frankd/src/qpsolvers/qpsolvers/solvers/conversions/warnings.py:35: UserWarning: Converted A to scipy.sparse.csc.csc_matrix
For best performance, build A as a scipy.sparse.csc_matrix rather than as a numpy.ndarray
  warnings.warn(
Out[14]: array([-1.29069624e-09,  1.00000000e+03])

But it wrongly asserts that the problem is unfeasible for $\alpha=10^{-4}$:

In [15]: P, q, A, b = get_problem(1e-4) 
    ...: solve_qp(P, q, A=A, b=b, solver="osqp")                                                                                                   
/home/frankd/src/qpsolvers/qpsolvers/solvers/conversions/warnings.py:35: UserWarning: Converted P to scipy.sparse.csc.csc_matrix
For best performance, build P as a scipy.sparse.csc_matrix rather than as a numpy.ndarray
  warnings.warn(
/home/frankd/src/qpsolvers/qpsolvers/solvers/conversions/warnings.py:35: UserWarning: Converted A to scipy.sparse.csc.csc_matrix
For best performance, build A as a scipy.sparse.csc_matrix rather than as a numpy.ndarray
  warnings.warn(
/home/frankd/src/qpsolvers/qpsolvers/solvers/osqp_.py:192: UserWarning: OSQP exited with status 'primal infeasible'
  warnings.warn(f"OSQP exited with status '{res.info.status}'")

Solution

The solution $(x^*, y^*)$ to this problem is $x^* = 0$, $y^* = \frac{1}{\alpha}$.

References

This problem is inspired from Geometric and numerical aspects of redundancy. GHFFA01 is a relaxed version of this problem.