Conversation
- Define _symcover_abslinear_init! (previously called but never
defined, breaking the default dense symcover/soft_symcover paths):
AbsLog{2} unconstrained minimum, then move along the eigenvector of
greatest curvature to feasibility, matching the sparse path.
- Add soft_symcover(::AbsLog{1}): log-space coordinate descent by
weighted median from the AbsLog{2} minimum. The AbsLog{1} objective
has a flat basin of minima; the lower-median tie-break returns a
deterministic, scale-covariant representative.
- soft_symcover(::AbsLinear{2}) refines from two starts and keeps the
lower objective: the geometric-mean minimum, and a leave-one-out
start that drops the support entry with the most negative
scale-invariant log-residual and minimizes the reduced-support
AbsLog{2} objective by Gauss-Seidel. The closed-form geometric-mean
formula is exactly scale-covariant only for rank-1 support patterns;
a Gauss-Seidel sweep is exactly covariant from a covariant iterate
for any pattern, so basin selection cannot depend on the frame. This
makes the soft cover continuous as an entry approaches zero while
preserving covariance. Residual ties are broken by ascending raw
magnitude: on exact ties -- including every symmetric 2x2, which is
scale-equivalent to its own index swap, making the competing basins
exactly degenerate -- scale-covariance, permutation-equivariance,
and continuity are mutually unsatisfiable, and the raw magnitude is
the only continuity-relevant information available.
- Solve the AbsLinear{2} coordinate cubic with bracketed safeguarded
Newton: the unique positive root always lies between sqrt(d) and
s2/s1, and geometric bisection handles brackets spanning hundreds of
orders of magnitude. The previous unbracketed 8-step iteration could
return non-minimizers on wide-dynamic-range matrices, silently
breaking coordinate-descent monotonicity.
- Tests: AbsLog{1} restored to the soft_symcover testsets, the
vanishing-entry continuity test is enabled, and new covariance
regression tests exercise the regime where the leave-one-out start
determines the result.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
symcover_min(AbsLog{2}(), A) now solves the symmetric MCM problem via a
one-sided quadratic penalty with κ-continuation and a damped semismooth
Newton iteration, replacing the JuMP/HiGHS requirement for this entry
point. The former HiGHS implementation is retained as the internal
symcover_min_jump reference for cross-checking in the test suite.
Zero-support rows and the bipartite gauge null space (e.g. [0 1; 1 0])
are handled by an identity row and a minimal range-orthogonal ridge, so
the solver is robust where a plain normal-equations solve is singular.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Implement cover_min(::AbsLog{2}, A) natively, replacing the JuMP/HiGHS
requirement for the asymmetric AbsLog{2} hard cover. Uses the same one-sided
quadratic penalty and damped semismooth Newton with κ-continuation as
symcover_min: stacked log-scales x = (α; β), the (e; −e) gauge fixed during the
solve by adding v0*v0ᵀ (v0 = [ones(m); -ones(n)]), then a closed-form gauge
shift pins the result to the balance convention Σ nzaᵢ log aᵢ = Σ nzbⱼ log bⱼ so
it is deterministic and matches the reference solver entrywise.
The prior JuMP AbsLog{2} method is renamed to the internal cover_min_jump, used
by the test suite to cross-check the native solver's objective and scales.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
symcover_min/cover_min gain a `linsolve` keyword (:auto/:dense/:lsqr) selecting the inner linear solve of the penalty-continuation Newton iteration. The reweighted normal equations are ill-conditioned at the final penalty strength (cond ≈ κ = 1e8), which makes conjugate gradients on that system unusable. The matrix-free path instead solves the underlying weighted least-squares problem with LSQR, whose accuracy tracks the condition number of the least-squares operator (≈ √κ) rather than its square. LSQR matches the dense factorization to ~4e-15 and the HiGHS reference to ~3e-8 across the committed symmetric and general libraries. The (e; −e) row/column gauge is a null vector of the least-squares operator for every connected support, so a single gauge row `v0ᵀx = 0` is appended to the system (the least-squares analog of the dense `v0*v0ᵀ` term); the post-solve balance shift then pins it deterministically. `:auto` and `:dense` use the dense factorization, which is faster for dense supports (a dense LSQR iteration costs O(nnz) = O(n²)); `:lsqr` is the O(nnz)-per-iteration path intended for large sparse supports. The native solvers are refactored into internal workers returning solve/iteration counts alongside the result. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Add the exported soft_cover(AbsLinear{2}(), A) and default soft_cover(A),
the asymmetric analog of soft_symcover. It minimizes the non-convex objective
∑ (1 − |A[i,j]|/(a[i]·b[j]))² by alternating least squares in the inverse-scale
variables u = 1/a, v = 1/b, where the objective is biconvex with closed-form
half-sweeps. Empty-support rows/columns receive scale 0. The internal core
_mscm_als! refines an incoming (a, b) in place so a future multistart wrapper
can own the full start list.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
soft_cover and soft_symcover (AbsLinear{2}) now default to a best-of-8
scale-covariant multistart via new `starts`, `σ`, and `rng` keywords, replacing
the single-start ALS and the internal best-of-2 symmetric descent. The candidate
starts — the geometric-mean minimum, the tightened hard cover, the
curvature-eigenvector and leave-one-out inits (symmetric), and log-normal
perturbations of the geometric-mean point — each co-vary with a rescaling of A,
so choosing the lowest-objective candidate is scale-covariant.
The perturbation RNG is a threaded `rng` keyword (default a fresh
MersenneTwister(0) per call) rather than a hidden internal seed: the default
keeps repeated calls and the two frames of a covariance check in agreement,
while callers can pass their own rng for reproducibility they control, since
default RNG streams are not stable across Julia versions.
A later start displaces the incumbent only on a genuine relative-objective
improvement (_MULTISTART_SWITCHTOL). Candidates in one basin converge to equal
objectives only to the descent tolerance, and selecting the raw argmin among
them injects ~1e-8 noise into the product a·bᵀ that breaks covariance;
requiring a margin above the tolerance keeps the covariant incumbent while
still capturing genuine, percent-scale basin improvements.
Random becomes a package dependency (was test-only) for the perturbations.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
The asymmetric AbsLog{2} hard-cover solver `cover_min` pins the (e; −e)
scale gauge with a single rank-1 `v0*v0ᵀ` term in the dense normal
equations. When the bipartite support graph splits into k connected
components it carries k independent gauges, so `v0*v0ᵀ` leaves k−1
directions singular and the dense solve throws `SingularException` — a
`Diagonal` (n singleton components) is the canonical failure.
Add the same minimal scale-relative ridge the symmetric solver already
uses to the supported diagonals of the asymmetric system. The
normal-equations RHS is orthogonal to every gauge null vector (each
component's edge contributions cancel), so the ridge leaves the recovered
scales essentially unperturbed, and the per-component gauge it fixes is
unobservable — no product a[i]*b[j] spans two components. The matrix-free
LSQR path already handled disconnected supports (its Krylov space stays in
range(Mᵀ), leaving per-component gauges at their warm-start value), so it
is unchanged.
Add sparse dispatch for the native AbsLog{2} MCM solvers: on a
`SparseMatrixCSC` or `Symmetric`/`Hermitian`-sparse input, `symcover_min`
and `cover_min` default to the matrix-free `linsolve=:lsqr` inner solve
(cost O(nnz) per iteration, conditioning √κ rather than κ) and return
dense scale `Vector`s, matching `cover`/`symcover`.
Tests: equivalence of `symcover_min`/`cover_min`/`soft_symcover`/
`soft_cover` against the dense reference on `Matrix(A)` across sparse,
Symmetric/Hermitian-sparse, Diagonal, and banded inputs; and a regression
covering `cover_min` on block-disconnected supports with the dense and
LSQR paths in agreement.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Fix a closure-capture box in `_abslog2_greatest_curvature_eigvec`: the Newton variable `λ` is reassigned in the loop, so the comprehension capturing it boxed it as `Core.Box` and the function inferred `Any`. That propagated into the O(n^2) feasibility loop of `_symcover_abslinear_init!`, where every `v[i]` access allocated. Copy `λ` to a never-reassigned binding before the comprehension and use explicit loops for the Newton sums. Gate the feasibility logarithm behind the cheap `A[i,j] <= a[i]*a[j]` check so already-covered pairs skip it. Add an opt-in `cache` matrix to `symcover`/`_symcover_abslinear_init!` (threaded to `unconstrained_min!` as `logcache`): the geometric-mean pass stores `log|A[i,j]|` and the feasibility step reuses it instead of recomputing. Reusing one buffer across many same-size matrices avoids the redundant logarithms with no per-call allocation. The result is identical to the no-cache path; both use deficit = log|A[i,j]| - log a[i] - log a[j]. For a 200x200 dense matrix, symcover drops from ~1.5 ms / 98k allocations to ~310 us / 14 allocations (~265 us with a reused cache). Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Two changes to the AbsLinear{2} hard-cover path:
- The symmetric tighten_cover! sweeps only the upper triangle. Each
pair's ratio updates both endpoints, so the sweep sees the same
multiset of ratios as a full-grid scan and the result is bitwise
identical for symmetric input, at half the cost. Like the other
symmetric paths, only the upper triangle of A is read.
- The feasibility scan in _symcover_abslinear_init! maintains a
monotone threshold exp(2*vmin*t_feas): an entry can raise the
running maximum only if its deficit exceeds s*t_feas >=
2*vmin*t_feas, so entries below the threshold are rejected with one
multiply-and-compare, and the logarithm and division are needed
only along the increasing-max chain. Overflow of exp falls back to
skipping only feasible entries, and a rounded-to-Inf threshold
product is conservative because the true product then exceeds
floatmax >= |A[i,j]|.
At n=200 the dense symcover drops from 311 to 165 microseconds and at
n=1000 from 7.9 to 3.9 ms (36x faster than multithreaded eigen); the
geometric-mean log pass is now the dominant cost.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
The three AbsLinear/AbsLog{1} coordinate-descent inner loops behind
`soft_symcover` ran a fixed sweep count with no convergence test, so a
solution that had already reached its fixed point kept sweeping until
`iter` was exhausted.
Each loop now exits early once a sweep stops moving the solution, still
capped by `iter`:
- `_abslinear2_iter!` (AbsLinear{2}) breaks when every coordinate's
stationarity residual r_k = s1/a[k] - s2/a[k]^2 + d/a[k]^2 - d^2/a[k]^4
(the gradient of the objective in log a[k]) is below `tol`. The residual
is formed from sums the update already computes, so the check is O(n)
per sweep rather than the O(n^2) of a full objective evaluation. Default
`tol=1e-8`.
- `_abslinear1_iter!` and `_abslog1_iter!` (the L1 penalties, whose median
updates have no smooth gradient) break when the largest relative
coordinate movement in a sweep is below `tol`. These updates reach an
exact fixed point, so movement falls to zero there. Default `tol=1e-12`.
Every criterion is scale-invariant (the residual's ratios and the relative
movement are unchanged by rescaling a coordinate), so the covariant restart
of a rescaled problem exits on the same sweep and the multistart selection
stays covariant.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Rewrite the manual page for the penalty-type API: document AbsLog and
AbsLinear as the penalty families behind cover_objective, replace the
removed *_lmin/*_qmin/symdiagcover references, and show symcover_min /
cover_min (native for AbsLog{2}, no external solver) in the algorithm
table and examples.
Correct the symcover_min/cover_min MethodError hint, which claimed all
AbsLog penalties require JuMP; AbsLog{2} is now solved natively.
Display the numerically-sensitive symcover and soft_symcover doctest
outputs via round(...): the tightened cover and the multistart differ
in the last few digits (the multistart's default RNG stream is not
stable across Julia versions), which the previous decimal filters could
not reconcile.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
soft_symcover allocated its scale vector with `similar(A, …)`, which is a
SparseVector for a SparseMatrixCSC or Symmetric/Hermitian-sparse input,
whereas every other solver (cover, symcover, cover_min, symcover_min, and
soft_cover) returns a dense Vector. The scale vectors are semantically dense,
so allocate `similar(Array{T}, ax)` — dense storage that still honors the
input's axes. Numerics are unchanged; only the container type differs.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
soft_cover now supports AbsLinear{1} (the asymmetric analog of
soft_symcover's AbsLinear{1}): the covariant multistart runs on the
AbsLinear{2} cover, then an alternating weighted-median block descent
refines. Each block update is an exact minimization, so the descent is
monotone; flat basins get a deterministic lower-median tie-break, keeping
the result scale-covariant. The weighted-self-median step is factored into
_weighted_self_median!, shared with the symmetric solver.
Document, in the manual, why AbsLog{1} hard-cover minimization stays
JuMP-backed rather than native: with r >= 1 it is an exact linear program,
the AbsLog{2} continuation-Newton scheme does not apply, and its optimum is
non-unique.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
`_abslinear2_linesearch` has no callers; only a stale import in the SparseArrays extension referenced it. The single-argument `tighten_cover!(a, ::Diagonal)` is also unreachable — `cover(::Diagonal)` tightens through the two-argument form. Drop both and the dangling import. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
`init_feasible!` builds a hard cover by a greedy diagonal sweep, reaching a
basin distinct from the geometric-mean-derived starts. Offer it as a
multistart candidate for `soft_symcover(AbsLinear{2})` when `A` has a zero
entry: on a fully dense `A` it never uniquely wins, and the zero-pattern
gate is invariant under a diagonal rescaling `D*A*D`, so the selection stays
scale-covariant. It takes a deterministic slot, so one fewer random start is
used and `starts` is unchanged.
Factor the candidate construction into `_soft_symcover_abslinear2_inits` and
the incumbent selection rule into `_multistart_select`, the single source of
that rule. `_soft_symcover_abslinear2` fills optional `labels`/`objs`
out-parameters, so a caller can audit which initialization earned the
selection through the production path, with no separate instrumented twin.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Give `_soft_cover_abslinear2` the same optional `labels`/`objs` out-parameters as its symmetric counterpart, filled in place with each candidate's label and final objective so a caller can audit which initialization earned the selection. Factor the candidate construction into `_soft_cover_abslinear2_inits` and route selection through the shared `_multistart_select`. There is no `feasible` start here, which is symmetric only; the labels are the geometric-mean init, the tightened hard cover, and the log-normal perturbations. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
`src/covers.jl` grew to cover four distinct roles with public entry
points and internal helpers interleaved. Split it by role, each file
ordered public interface first, internal helpers after:
- penalties.jl: `AbsLog`, `AbsLinear`, `cover_objective`.
- heuristic_covers.jl: the O(mn) hard covers `symcover`/`cover` and the
tightening and initialization routines they share.
- soft_covers.jl: `soft_symcover`/`soft_cover` and their multistart and
coordinate-descent machinery.
- minimal_covers.jl: the native AbsLog{2} objective-minimal covers plus
the JuMP/Ipopt extension stubs.
Pure code move; no behavior change.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #21 +/- ##
==========================================
+ Coverage 92.87% 96.96% +4.08%
==========================================
Files 5 9 +4
Lines 856 1613 +757
==========================================
+ Hits 795 1564 +769
+ Misses 61 49 -12 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
The "feasible start and provenance" test asserted that the `feasible` start beats every other start by a 0.1% margin. That holds only when no perturbed start reaches the same basin; on Julia 1.10's `randn` stream a random start lands in the `feasible` basin and ties it to within the descent tolerance, so the single-margin assertion fails there. Assert the actual invariant instead: `feasible` is co-optimal in the best basin (up to descent-tolerance ties) and that basin beats every start in a different basin by a wide margin. This holds on every RNG stream. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
On an exactly-coverable matrix (e.g. the diagonal `[2 0; 0 3]`) the
AbsLog{2} cover objective is mathematically zero, so the native and dense
reference solvers each return only floating-point roundoff (~1e-32). A
pure `rtol` comparison of two roundoff-level values is meaningless and
flips with the platform's rounding. Add `atol = 1e-10` — far above the
roundoff floor and far below any genuine objective — so both are accepted
as equal when the true objective is zero.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
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.
This branch reorganizes the cover API around explicit penalty functions,
adds soft covers that penalize under-coverage instead of forbidding it, and
provides native (no external solver) objective-minimal solvers for the
default quadratic penalty. The
AbsLog{1}andAbsLinearminimizers move toJuMP-backed extensions (HiGHS and Ipopt).
Penalty functions replace the fixed L1/L2 objectives
Cover quality is now expressed through the ratios
r_ij = |A[i,j]| / (a[i]*b[j])and a penalty type applied to them:
AbsLog{p}—ϕ(r) = |log r|^p(withϕ(0) = 0). Convex in log space; thenatural penalty for hard covers.
AbsLog{1}is L1 in log space,AbsLog{2}is L2.
AbsLinear{p}—ϕ(r) = |1 - r|^p(withϕ(0) = 1). Continuous atr = 0,non-convex; the penalty used by the soft covers.
cover_objective(ϕ, a, b, A)(and the symmetriccover_objective(ϕ, a, A))evaluates either penalty, replacing
cover_lobjective/cover_qobjective.Soft covers
New
soft_symcover/soft_coverallow uncovered entries (r > 1) butpenalize them, minimizing an
AbsLinear{2}objective by default (otherpenalties available). A scale-covariant multistart escapes poor local minima of
the non-convex objective; coordinate descent gets a convergence-based early
exit.
soft_symcover_minprovides the JuMP-backed exact soft solver.Native objective-minimal hard covers
symcover_min/cover_minminimize a penalty subject to the hard constraint.For the default
AbsLog{2}penalty they are now solved natively — noexternal solver — by penalty-continuation with a damped semismooth Newton
iteration (matrix-free LSQR inner solve for the general/sparse case). The
solution is near-exact (relative objective excess typically a few ×10⁻⁷) and
orders of magnitude faster than a general-purpose convex solver.
The other penalties remain JuMP-backed extensions, loaded on demand:
AbsLog{1}(an exact LP) → JuMP + HiGHS.AbsLinearvariants → JuMP + Ipopt (newSIAIpoptextension).AbsLog{1}is deliberately left to HiGHS: the Newton scheme does not transfer toa linear objective, and the L1 optimum is non-unique (a face of the polytope),
so a native solver would additionally need a canonical selection rule.
Renamed / removed API
cover_lmin,cover_qmin,symcover_lmin,symcover_qmin→cover_min(ϕ, A),symcover_min(ϕ, A).cover_lobjective,cover_qobjective→cover_objective(ϕ, ...).symdiagcoverand diagonalized covers (C = Diagonal(d) + a*a') are removed.Other changes
soft_symcoverreturns dense scale vectors on sparse input.cover_min.AbsLinearsymcover (optionallog cache), redundant init skipped in
soft_cover.src/covers.jlis split by role intopenalties.jl,heuristic_covers.jl,soft_covers.jl, andminimal_covers.jl, each ordered public interface first,internal helpers after.
Ipopt(weak);Randompromoted to a hard dependency.docs/src/index.md), and the test suite updatedfor the new API.