CCA2

Computational Convex Analysis for bivariate piecewise linear-quadratic (PLQ) functions.

CCA2 computes Fenchel conjugates, convex envelopes and the operators derived from them for bivariate PLQ functions — including nonconvex ones — in exact/closed form rather than on a grid. No LLT or other grid-based algorithms are used.

Copyright (C) 2008–2026, Yves Lucet. Licensed under GPL-3 (see LICENSE); contributors listed in copyright.txt.

CCA2's goal is the conjugate and biconjugate of a QuaPol. That is the design target, and it is what determines which cases are implemented.

Everything downstream of a QuaPol is a special case, and the special-ness is load-bearing: the convex envelope of a QuaPol triangle is a very special RatPol, and the conjugate of those triangles is a very special QuaPar (for instance, a parabolic edge only ever occurs surrounded by two parallel rays). Hyperbolic edges therefore never arise and are not representable — not as a limitation, but because no QuaPol conjugate/biconjugate or intermediate computation can produce one.

This matters when reading the source: several notImplemented guards protect unreachable branches. They are assertions, not missing features. SUPPORT_MATRIX.md classifies every guard as OK / GAP / not reachable / internal invariant, generated from the code itself.

Alpha — not yet released. The API is still changing; there is no tagged version.

Test suite: 262 passed / 1 failed across 22 suites — the 17 CCA2 suites (*Test.m) are 187 / 0, and the single failure is testRegion/testCreation in the vendored cPLQ suites, a longstanding toolbox-compatibility issue unrelated to the conjugate pipeline.

Before depending on CCA2, read SUPPORT_MATRIX.md §8 — the summary of what actually blocks a general release. The largest gaps today: partialConj is unimplemented for every engine; the 'pqp' and 'graph' conjugate engines do not exist; unbounded multi-face domains error; and conj of a triangle whose envelope splits into 4 faces stops in cPLQ's Step 3.

A piecewise function is built from two independent choices: the function type and the subdivision type. Each is an axis with a general case and one specialization:

The four named types are the four cells of that grid, and inheritance is the grid's own partial order — a genuine diamond, because that is what a product lattice is:

             RatPar        rational on parabolic     (abstract; nothing produces one yet)
             /    \
        RatPol    QuaPar   rational on polyhedral / quadratic on parabolic
             \    /
             QuaPol       quadratic on polyhedral  — the input type

        QuaParCPLQ         same maths as QuaPar, still in symbolic form (no mesh)

g = f.conj();          % always a RatPar
g.kind()               % 'QuaPol' | 'RatPol' | 'QuaPar' | 'QuaParCPLQ'
g.isMeshed()           % false only for the symbolic QuaParCPLQ form

isa(g, 'Qua')          % ask about ONE axis: is the function a polynomial?
isa(g, 'Pol')          % ...is the subdivision polyhedral?

The axis markers are what let you query one axis without enumerating combinations, and they keep working when a type is added. All data lives on RatPar alone — MATLAB makes a property defined in two superclasses fatal and unresolvable, so QuaPol < RatPol & QuaPar requires it. Each type's pinned values are enforced instead by validators that read the object's own traits, so no type can be made to lie about itself. kind() is derived from the real class, never stored, so it cannot drift. See RETURN_TYPE.md and RatPar.m.

Renamed 2026-07-27: QuaPoly → QuaPol (and with it addQuaPoly → addQuaPol, quaPolyToPlq → quaPolToPlq), so all four type names are the uniform 3+3 combinations of the two axes. No shim was left for the old name — CCA2 has no tagged release, so nothing external can depend on it. PLQVC, which was released, keeps its alias.

Not modelled as a type: the numerator's degree. f is stored in the 10-wide cubic basis, but nothing dispatches on degree — every consumer either rejects a cubic outright or ignores the distinction. A type should track what changes the algorithm, not what changes the data's shape, so degree stays a runtime check rather than becoming a Cub class (which would double the lattice for no dispatch benefit).

addpath('/path/to/CCA2');

% f(x,y) = x*y over the triangle (0,0),(1,0),(0,1) — nonconvex on that domain
V = [0 0; 1 0; 0 1];
E = [1 2 1; 2 3 1; 3 1 1];      % [from to isSegment]
F = [1 0; 1 0; 1 0];            % [leftFace rightFace], 0 = +infinity
f = QuaPol(V, E, [0 1 0 0 0 0], F);   % coeffs [x^2 xy y^2 x y 1]

g = f.conj();                   % Fenchel conjugate  -> RatPar (kind 'QuaPar')
g.eval([0.3 0.7])               % ans = 0.7

% full-domain strictly convex quadratic
q = QuaPol([1 0 1 0 0 0]);     % (x^2 + y^2)/2
q.conj().kind()                 % 'QuaPol'
q.biconj().kind()               % 'QuaPol' -- back to itself

biconj works for every bounded domain; an unbounded one still errors. It is not always the literal conj∘conj: for a single bounded triangle the conjugate is finite everywhere — an unbounded multi-face domain conjCPLQ does not handle — but f** = conv(q + I_T) for a compact T, which is exactly Step 1's convex envelope, so no second conjugation is needed. Current coverage:

The envelope route also succeeds on the triangles whose conjugate the pipeline cannot yet compute. When Step 1 has to split an indefinite triangle it emits a rational face, which CCA2's own Step 2 cannot conjugate; conj then falls back to cPLQ's symbolic Step 2/3. That closes the 2-face split end to end. For a 4-face split Step 2 completes but cPLQ's Step 3 (cross-piece maximum) does not yet. See biconjCPLQ.m, ratPolToPlq.m, and SUPPORT_MATRIX.md §1.2 and §3.

The 'cplq' engine implements the linear-time algorithms of:

• [COAP] Karmarkar & Lucet, Computing the convex envelope of bivariate PLQ functions in linear time, Comput. Optim. Appl. 94 (2026) 747–780.
• [JOGO] Karmarkar & Lucet, A linear-time algorithm to compute the conjugate of nonconvex bivariate PLQ functions, J. Glob. Optim. 94 (2026) 3–34.

Both handle nonconvex PLQ. DESIGN.md lists the full lineage of predecessor work (convex-only methods: parametric-QP, graph-matrix, and Kumar's convex-envelope front-end) and maps each to the engine it would supply.

On the original cPLQ package. CCA2 contains a substantially rewritten version of the symbolic per-piece machinery (plq.m, region.m, functionNDomain.m, symbolicFunction.m, and companions). The original cPLQ package is deliberately not bundled: it is GPL-3 too, so there is no licensing obstacle — the reason is that CCA2's rewrite supersedes it, and shipping both would leave users wondering which to use.

runtests('RatParTest')        % the type hierarchy contract
runtests('conjCPLQTest')      % the conjugate pipeline end to end
runtests('maxQuaParTest')     % Step 3, including curved edges

Run everything with runtests over the *Test.m / test*.m files in the repository root.