DualQP

org.appliedtopology.tda4j.alpha.DualQP
final class DualQP(val n: Int, workingSetCapacity: Int, settings: AlphaDQPSettings)

Solves

maximise d(lambda) = -1/2 lambda^t B lambda + U^t lambda subject to lambda_i >= 0 for i not in J

which is the Lagrangian dual of Eq. (9) with H = I. Optimum equals the primal optimum c* = 1/2 ||y* - x||^2; the primal solution is recovered from the KKT conditions (12) as y* = x - sum_i lambda_i (x_i - x).

Reused across every candidate simplex sharing the same base vertex x -- only J changes, which is exactly the observation in the paper that lets B and U be assembled once per vertex rather than once per simplex.

The instance is stateful and not thread safe; give each worker its own.

Attributes

Experimental
true
Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Value members

Concrete methods

def activeIndex(t: Int): Int

Index (into 0 until n) of the t-th active constraint.

Index (into 0 until n) of the t-th active constraint.

Attributes

def activeSetSize: Int

Size of the final working set (the "active set" of Fig. 3).

Size of the final working set (the "active set" of Fig. 3).

Attributes

def multiplier(t: Int): Double

Multiplier of the t-th active constraint.

Multiplier of the t-th active constraint.

Attributes

def solve(b: Array[Double], u: Array[Double], eq: Array[Int], nEq: Int, c1: Double): Double

Value parameters

b

flat n x n Gram matrix, row major

c1

cutoff (a1 + p(x))/2; the solve aborts as soon as the dual objective provably exceeds it

eq

indices of the equality constraints, i.e. the vertices of sigma other than the base vertex

nEq

number of valid entries in eq

u

the vector U of Eq. (11)

Attributes

Returns

c* if c* <= c1, otherwise Double.PositiveInfinity

Concrete fields

var iterationCount: Long

Total active-set iterations, useful for benchmarking against Delaunay.

Total active-set iterations, useful for benchmarking against Delaunay.

Attributes

val n: Int