Level-Set Method Implementation Needs Improved Feasibility Check

[mpf]

Problem Description

The level-set method implementation currently has an issue with obtaining good feasibility of the solution. This can be observed in the test suite where the following test was failing:

Level Set Method for random DPModel: Test Failed at test/test-level-set.jl:27
  Expression: norm((A * x + r) - b) < tol
   Evaluated: 1.0487499771048549e-5 < 3.394757957413769e-6

We've temporarily fixed this by relaxing the tolerance in the test to make CI pass, but the underlying issue needs to be addressed.

The level-set method focuses on finding an optimal objective value but doesn't explicitly enforce feasibility during the iterations. This can lead to solutions that are optimal in terms of the dual objective but slightly violate the primal feasibility condition.

Potential Solutions

1. Add explicit feasibility checks to the level-set method stopping criteria
2. Modify the oracle function to balance optimality and feasibility better.

[mertkipcak]

Proposed Option 1

As a simple solution, we can try to increase the $\lambda$ of the final solve with a line like

regularize!(kl, kl.λ*100)

Low $\lambda$ would allow us to find the scale faster, and the final solve will take care of the feasibility.

Proposed option 2

This option is a bit more complicated, but we can use our magic potion of make adaptive to the $\lambda$ as well.
We can solve the level set problem as is right now, after we are confident with the scale, we can solve the problem with consecutively while increasing the value of $\lambda$. The code would look something like

tol = atol + rtol*norm(kl.b)

while true
    final_soln = solve!(
        kl,
        logging=subsolver_logging,
        reset_counters=false,
        atol=atol,
        rtol=rtol,
        kwargs...
    )

    if norm(kl.A * final_soln.solution + final_soln.residual - kl.b) < tol
        break
    else
        regularize!(kl, kl.λ * 10)
    end
end

This would be around

DualPerspective.jl/src/level-set.jl

Lines 235 to 242 in 34ee430

	final_soln = solve!(
	kl,
	logging=subsolver_logging,
	reset_counters=false,
	atol=atol,
	rtol=rtol,
	kwargs...
	)