_SharedProjQCQP#

class _SharedProjQCQP(A0, s0, c0, A1, A2, s1, Plist, Pstruct=None, B_j=None, s_2j=None, c_2j=None, verbose=0)[source]#

Bases: ABC

Represents a quadratically constrained quadratic program (QCQP).

QCQP has a set of projection-structured (shared) constraints and (optionally) a separate list of general quadratic constraints.

Primal problem (maximization form):: maximize_x - x^† A0 x + 2 Re(x^† s0) + c0 subject to Re( - x^† A1 P_j A2 x + 2 x^† A2^† P_j^† s1 ) = 0

Re( - x^† A2^† B_j A2 x + 2 x^† A2^† s_2j + c_2j ) = 0

where the P_j are projection matrices with shared sparsity structure. The matrices used internally for the shared (projector) constraints are symmetrized via Sym(A1 P_j A2) to ensure Hermitian structure.

Dual feasibility relies on the existence of (at least) one projector column such that A0 + λ A1 P_j A2 becomes positive semidefinite for sufficiently large λ > 0 (by convention this is often column index 1, but the code does not enforce or check which column satisfies this).

Parameters:

A0 (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | csc_array)
s0 (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes])
c0 (float)
A1 (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | csc_array)
A2 (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | csc_array)
s1 (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes])
Plist (list[ndarray[tuple[int, ...], dtype[complexfloating]] | sparray])
Pstruct (ndarray[tuple[int, ...], dtype[complexfloating]] | sparray | None)
B_j (list[ndarray[tuple[int, ...], dtype[complexfloating]] | sparray] | None)
s_2j (list[_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]] | None)
c_2j (_Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None)
verbose (int)

A0#

Quadratic matrix in the objective.

Type:: sp.csc_array | ArrayLike

s0#

Linear term vector in the objective.

Type:: ArrayLike

c0#

Constant term in the objective.

Type:: float

A1#

Left quadratic factor in projector constraints.

Type:: sp.csc_array | ArrayLike

A2#

Right quadratic factor in projector and general constraints.

Type:: sp.csc_array | ArrayLike

s1#

Linear term vector for projector constraints.

Type:: ArrayLike

B_j#

List of general constraint middle matrices (between A2^† and A2).

Type:: list[sp.csc_array | ArrayLike]

s_2j#

Linear term vectors for general constraints.

Type:: list[ArrayLike]

c_2j#

Constant terms for general constraints.

Type:: ArrayLike

Proj#

dolphindes Projectors object representing all projector matrices P_j.

Type:: dolphindes.util.Projectors

verbose#

Verbosity level (0 = silent).

Type:: int

Acho#

Most recent numeric factorization object (of the last A(lags) that was factorized), set by _store_factor/_get_factorization and used by _Acho_solve. None until the first factorization.

Type:: Any | None

current_dual#

Cached dual value after solve_current_dual_problem().

Type:: float | None

current_lags#

Cached optimal Lagrange multipliers.

Type:: FloatNDArray | None

current_grad#

Gradient of the dual at the cached solution.

Type:: FloatNDArray | None

current_hess#

Hessian of the dual at the cached solution (if computed).

Type:: FloatNDArray | None

current_xstar#

Primal maximizer x* corresponding to current_lags.

Type:: ComplexArray | None

use_precomp#

Whether precomputed constraint matrices (A_k) and Fs vectors are used.

Type:: bool

precomputed_As#

Symmetrized matrices A_k = Sym(A1 P_k A2) plus general constraint blocks.

Type:: list[sp.csc_array | ComplexArray]

Fs#

Matrix with columns (A2^† P_k^† s1) for each projector constraint k.

Type:: ComplexArray

Notes

General (B_j) constraints are appended after projector constraints in precomputed_As order.

Methods Summary

`add_constraints`(added_Pdata_list[, ...])	Append additional projector constraints.
`compute_precomputed_values`()	Precompute per-constraint symmetrized matrices and projector-source terms.
`find_feasible_lags`([start, limit])	Heuristically find a dual feasible (PSD) set of Lagrange multipliers.
`get_dual`(lags[, get_grad, get_hess, ...])	Evaluate dual function and optional derivatives at lags.
`get_number_constraints`()	Return total number of constraints (projector + general).
`is_dual_feasible`(lags)	Check positive semidefiniteness of A(lags).
`iterative_splitting_step`([method, ...])	Generate successive solutions by refining projectors and solving the dual.
`merge_lead_constraints`([merged_num, metric])	Merge first 'merged_num' projector constraints into one (GCD utility).
`refine_projectors`()	Refine projector constraints by splitting each projector into two projectors.
`run_gcd`([gcd_params])	Run GCD to approach tightest dual bound for this QCQP.
`solve_current_dual_problem`(method[, ...])	Optimize the dual problem using 'newton' or 'bfgs'.

Methods Documentation

add_constraints(added_Pdata_list, orthonormalize=True, metric='hilbert_schmidt')[source]#

Append additional projector constraints.

Parameters:

added_Pdiag_list (list[ComplexArray]) – List of new projector diagonals.
orthonormalize (bool, default True) – Whether to orthonormalize constraint set after insertion.
metric (str, default "hilbert_schmidt") – Orthonormalization metric (“hilbert_schmidt” or “euclidean”); see dolphindes.cvxopt.gcd.add_constraints().
added_Pdata_list (list[ndarray[tuple[int, ...], dtype[complexfloating]]])

Return type:

None

compute_precomputed_values()[source]#

Precompute per-constraint symmetrized matrices and projector-source terms.

Precomputes:

precomputed_As are the quadratic forms for x in the constraints = Sym(A1 P_k A2) for each projector constraint k = Sym(A2^† B_j A2) for each general constraint j
Fs are the linear forms for x in the constraints = A2^† P_k^† s1 for each projector constraint k = A2^† s_2j for each general constraint j

This speeds up repeated assembly of A(lags) and derivative-related operations when the number of constraints is moderate.

Return type:: None

find_feasible_lags(start=0.1, limit=100000000.0)[source]#

Heuristically find a dual feasible (PSD) set of Lagrange multipliers.

Assumes scaling up (typically) the second projector multiplier eventually yields a PSD A matrix.

Parameters:

start (float, default 0.1) – Initial value assigned to lags[1] (must have ≥ 2 projector constraints).
limit (float, default 1e8) – Upper bound before giving up.

Returns:

Feasible initial lags (projector first, then zeros for general constraints).

Return type:

FloatNDArray

get_dual(lags, get_grad=False, get_hess=False, penalty_vectors=None)[source]#

Evaluate dual function and optional derivatives at lags.

Parameters:

lags (FloatNDArray) – Lagrange multipliers (projector first, then general).
get_grad (bool, default False) – If True, compute gradient w.r.t. lags.
get_hess (bool, default False) – If True, compute Hessian (only supported when no general constraints).
penalty_vectors (list[ComplexArray] | None) – Optional PSD-boundary penalty vectors.

Returns:

dualval (float) – Dual objective value (with penalties if provided).
grad (FloatNDArray | None) – Gradient (None if not requested).
hess (FloatNDArray | None) – Hessian (None if not requested).
dual_aux (namedtuple) – Auxiliary components (raw + penalty-separated parts).

Return type:

Tuple[float, ndarray[tuple[int, …], dtype[float64]] | None, ndarray[tuple[int, …], dtype[float64]] | None, Any]

Notes

Penalty adjustment adds Σ_j v_j^† A^{-1} v_j and its derivatives.

get_number_constraints()[source]#

Return total number of constraints (projector + general).

Return type:: int

abstract is_dual_feasible(lags)[source]#

Check positive semidefiniteness of A(lags).

Parameters:: lags (FloatNDArray) – Full Lagrange multiplier vector (projector part first, then general).
Returns:: True if A(lags) is PSD (dual feasible).
Return type:: bool

iterative_splitting_step(method='bfgs', max_proj_cstrt_num=inf)[source]#

Generate successive solutions by refining projectors and solving the dual.

Stop when: - each projector has at most one non-zero column (pixel level for diagonal), or - the number of constraints reaches max_proj_cstrt_num.

Yields:

tuple – (current_dual, current_lags, current_grad, current_hess, current_xstar)

Parameters:

method (str)
max_proj_cstrt_num (int | float)

Return type:

Iterator[Tuple[float, ndarray[tuple[int, …], dtype[float64]], ndarray[tuple[int, …], dtype[float64]], ndarray[tuple[int, …], dtype[float64]] | None, ndarray[tuple[int, …], dtype[complexfloating]]]]

merge_lead_constraints(merged_num=2, metric='hilbert_schmidt')[source]#

Merge first ‘merged_num’ projector constraints into one (GCD utility).

Parameters:

merged_num (int, default 2) – Number of leading projector constraints to merge.
metric (str, default "hilbert_schmidt") – Normalization metric for the merged constraint (“hilbert_schmidt” or “euclidean”); see the module-level gcd.merge_lead_constraints.

Return type:

None

refine_projectors()[source]#

Refine projector constraints by splitting each projector into two projectors.

Strategy (diagonal):

Identify non-empty column support of P (columns with nnz > 0).
If support size <= 1: keep P as is.
Else, build two diagonal column masks S1, S2 that partition the support roughly in half, and define P1 = P @ S1, P2 = P @ S2 so that P = P1 + P2.
Duplicate the parent multiplier on both children so Σ λ P remains unchanged.

General constraints (B_j, s_2j, c_2j) are left unchanged.

Return type:: self.Proj, self.current_lags

run_gcd(gcd_params=None)[source]#

Run GCD to approach tightest dual bound for this QCQP.

See module-level run_gcd() for details. Modifies the existing QCQP object.

Parameters:: gcd_params (GCDHyperparameters | None) – GCD hyperparameters; if None, defaults are used.
Return type:: None

solve_current_dual_problem(method, opt_params=None, init_lags=None)[source]#

Optimize the dual problem using ‘newton’ or ‘bfgs’.

Parameters:

method (str) – ‘newton’ (alternating Newton / GD) or ‘bfgs’.
opt_params (OptimizationHyperparameters | None) – Optimization hyperparameters (if None, default values are used).
init_lags (ArrayLike | None) – Initial feasible lags; if None, a feasible point is searched.

Returns:

current_dual (float) – Optimal dual value.
current_lags (FloatNDArray) – Optimal Lagrange multipliers.
current_grad (FloatNDArray) – Gradient at optimum.
current_hess (FloatNDArray | None) – Hessian (if computed by Newton variant).
current_xstar (ComplexArray) – Primal maximizer corresponding to current_lags.

Return type:

Tuple[float, ndarray[tuple[int, …], dtype[float64]], ndarray[tuple[int, …], dtype[float64]], ndarray[tuple[int, …], dtype[float64]] | None, ndarray[tuple[int, …], dtype[complexfloating]]]