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, alpha]).reshape((1, 2)),
        b=np.array([1.0]),
        lb=None,
        ub=None,
        name=f"weds_{alpha=}",
        optimal_cost=0.5 / (1 + alpha ** 2),
    )

Motivation

This problem tries to minimize $x^2 + y^2$ while staying on the line $y = \frac{1}{\alpha} - \frac{x}{\alpha}$, which becomes more and more vertical as $\alpha \to 0$. Some solvers get to it exactly, some others with good precision, and some of them miss it completely:

In [1]: P, q, A, b = get_problem(1e-20) 
    ...: solve_qp(P, q, A=A, b=b, solver="quadprog")                                                                                                                          
Out[1]: array([1.e+00, 1.e-20])

In [2]: P, q, A, b = get_problem(1e-20) 
    ...: solve_qp(P, q, A=A, b=b, solver="proxqp")                                                                                                                            
Out[2]: array([9.99999003e-01, 9.99999003e-21])

In [3]: P, q, A, b = get_problem(1e-20) 
    ...: solve_qp(P, q, A=A, b=b, solver="qpoases")                                                                                                                           
Out[3]: array([1., 0.])

Solution

The solution $(x^*, y^*)$ is

$$ \begin{align} x^* & = \frac{1}{1 + \alpha^2} & y^* & = \frac{\alpha}{1 + \alpha^2} \end{align} $$

References

This problem is inspired from Geometric and numerical aspects of redundancy.