Close some solver discrepancies - #24
Merged
Merged
Conversation
timholy
commented
Jul 16, 2026
timholy
commented
Member
- Solve the soft AbsLog{2} covers exactly and natively
- Add the asymmetric AbsLog{1} soft cover and back out promises about minimization and vertex selection
The soft AbsLog{2} objective ∑ (log a_i + log a_j - log|A_ij|)² is a linear
least-squares in log space, and the hard AbsLog{2} workers already solve it:
their first iterate is the unweighted solve that the penalty continuation then
departs from. `_soft_symcover_min_abslog2` and `_soft_cover_min_abslog2` expose
it, running no continuation (`κs=()`) and skipping the feasibility boost, which
the soft objective, constraining nothing, must not apply. The problem is convex,
so one linear solve settles it — no iteration and no multistart, unlike the
non-convex AbsLinear soft covers — and it inherits the workers' handling of a
singular signless Laplacian, of support-free rows and columns, and of both the
dense and LSQR inner solves.
The geometric mean minimizes this objective only where every entry of `A` is
nonzero; on a sparse support it is a Sherman-Morrison approximation of it. The
`:geomean` and soft-cover docstrings say so.
Convexity leaves a heuristic and a minimizer nothing to disagree about, so
`soft_symcover(AbsLog{2}, A)` and `soft_symcover_min(AbsLog{2}, A)` are one
function, as are `soft_cover(AbsLog{2}, A)` and `soft_cover_min(AbsLog{2}, A)`.
`soft_cover` accepts AbsLog{2}; AbsLog{1} remains symmetric-only.
`soft_symcover_min(AbsLog{2})` no longer routes through JuMP. HiGHS answers that
model — a QP carrying no constraints — with a point that is not stationary,
while reporting OPTIMAL.
The `*_min` workers allocate their scale vectors with `similar(Array{T}, ...)`:
the scales are dense objects, and `similar(A, ...)` yields a SparseVector for a
sparse `A`.
The tests check these covers against `pinv(M) * z`, which settles the
least-squares without a solver, and pin the geometric mean as strictly worse on
a sparse support. A fully supported `A` cannot tell the two apart.
Assisted-by: Claude Opus 4.8 <noreply@anthropic.com>
`soft_cover` accepts `AbsLog{1}`, refining the AbsLog{2} minimum by alternating
weighted-median row and column updates — the asymmetric counterpart of the
coordinate descent `soft_symcover` already runs. Row and column scales are
distinct variables, so no term is self-coupled and the symmetric solver's
double-weighted diagonal has no counterpart here; each half-sweep is an exact
block minimization, and the result is pinned to the balance convention.
Neither soft AbsLog{1} cover returns a minimizer, and both docstrings now say so.
The objective is convex, but its nonsmoothness couples `a[i]` with `b[j]`, so a
point that no single sweep improves need not minimize it: the descent reaches a
deterministic, scale-covariant fixed point that can sit materially above the
minimum.
`soft_symcover_min` and `soft_cover_min` still do not accept `AbsLog{1}`, and the
docstrings record why. The objective is an LP in log space whose optimum is a
face, but the lexicographic AbsLog{2} selection that pins one member of the
corresponding hard face does not carry over. A hard face is bounded by the
coverage constraints, so its L2-minimal member sits at or beside the vertex and
keeps nearly every tight residual. This face is a level set of an unconstrained
piecewise-linear objective; the quadratic pulls far across it and costs most of
the exactly tight residuals that make `AbsLog{1}` worth choosing over `AbsLog{2}`.
Assisted-by: Claude Opus 4.8 <noreply@anthropic.com>
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## main #24 +/- ##
==========================================
+ Coverage 98.20% 98.51% +0.31%
==========================================
Files 12 12
Lines 2001 2027 +26
==========================================
+ Hits 1965 1997 +32
+ Misses 36 30 -6 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.