File EigenvaluesProblems.h

template<typename NT, typename MT = Eigen::Matrix<NT, Eigen::Dynamic, Eigen::Dynamic>, typename VT = Eigen::Matrix<NT, Eigen::Dynamic, 1>> class EigenvaluesProblems

#include <EigenvaluesProblems.h>

Solver for various eigenvalue problems arising in convex optimization Provides methods for quadratic eigenvalue problems (QEP), generalized eigenvalue problems, and negative definiteness checks via eigenvalue analysis.

Template Parameters:

NT – Numeric type for scalar values
MT – Matrix type (defaults to Eigen::Matrix with dynamic dimensions)
VT – Vector type (defaults to Eigen::Matrix column vector with dynamic size)

Public Functions

inline NT minPosQuadraticEigenvalue(const MT &A, const MT &B, const MT &C, MT&, MT&, VT &eigvec, bool = false, int = 0)

Find minimum positive eigenvalue for quadratic eigenvalue problem Solves (A + t*B + t²*C)v = 0 to find smallest positive t Used in convex optimization for barrier function step size computation

Parameters:

A – [in] Constant coefficient matrix
B – [in] Linear coefficient matrix
C – [in] Quadratic coefficient matrix
X – [inout] Auxiliary matrix (unused, kept for API compatibility)
Y – [inout] Auxiliary matrix (unused, kept for API compatibility)
eigvec – [out] Eigenvector corresponding to minimum positive eigenvalue
updateOnly – [in] Unused flag (kept for API compatibility)
num_constraints – [in] Unused parameter (kept for API compatibility)

Returns:

Minimum positive t satisfying the QEP, or infinity if none exists

inline NT minPosLinearEigenvalue(const MT &A, const MT &B, VT &eigvec) const

Find minimum positive t such that (A + t*B)v = 0 for some v ≠ 0 Solves the generalized eigenvalue problem using Eigen’s self-adjoint solver. Requires one of A or -A to be positive definite.

Parameters:

A – [in] Constant coefficient matrix (typically lmi(p) — positive semidefinite)
B – [in] Linear coefficient matrix (typically directional derivative)
eigvec – [out] Eigenvector corresponding to minimum positive t

Returns:

Minimum positive t, or infinity if none exists

inline NT minPosLinearEigenvalue_EigenSymSolver(const MT &A, const MT &B, VT &eigvec) const

Variant of minPosLinearEigenvalue using the symmetric generalized approach Solves (A + t*B)v = 0 for the smallest positive t Uses solver(B, A) → Bv = λAv → Av + (1/λ)Bv = 0 → t = 1/λ (largest λ) The caller typically passes A = -precomputedValues.A, B = precomputedValues.B so the internal call is ges(B, -precomputedValues.A).

Parameters:

A – [in] Coefficient matrix (as-is from caller, no sign change)
B – [in] Coefficient matrix
eigvec – [out] Eigenvector for the minimum positive t

Returns:

Minimum positive t, or infinity if none exists

inline bool isPositiveSemidefinite(const MT &A) const

Check if symmetric matrix A is positive semidefinite Uses LDLT decomposition which handles semidefinite matrices gracefully

Parameters:: A – [in] Symmetric matrix
Returns:: true if A is positive semidefinite, false otherwise

inline bool is_correlation_matrix(const MT &matrix, const double tol = 1e-8)

Check if a matrix is a correlation matrix Returns true if all diagonal elements are 1 and the matrix is PSD

Parameters:

matrix – [in] Input matrix
tol – [in] Tolerance for checking unit diagonal

Returns:

true if matrix is a valid correlation matrix

Public Static Functions

static inline std::pair<NT, NT> symGeneralizedProblem(const MT &A, const MT &B)

Solve generalized symmetric eigenvalue problem B*v = λ*(-A)*v Returns intersection distances t = 1/λ for the positive and negative directions of the generalized problem (A + t*B)v = 0.

Parameters:

A – [in] Symmetric matrix (multiplied by -1 in problem formulation)
B – [in] Symmetric matrix

Returns:

Pair (t_pos, t_neg) — distances to boundary in ± coordinate directions

static inline NT findSymEigenvalue(const MT &M)

Check if symmetric matrix M is negative definite and return an estimate of the largest eigenvalue (most negative)

Parameters:: M – [in] Symmetric matrix
Returns:: Estimated largest eigenvalue if M is negative definite, infinity otherwise

Private Static Functions

static inline constexpr NT eps(): Machine epsilon for numeric type NT.

static inline constexpr NT sqrt_eps(): Square root of machine epsilon (used for moderate tolerance checks)

static inline constexpr NT LARGE_VAL(): Largest representable value for numeric type NT.

static inline constexpr NT EPS(): Machine epsilon alias for consistency with existing code.

static inline NT solveQEP(const MT &B0, const MT &B1, const MT &B2, VT &eigvec)

Solve quadratic eigenvalue problem to find smallest positive parameter Solves (B0 + t*B1 + t²*B2)v = 0 for the smallest positive t Uses Spectra library with linearization approach via QEPOperator

Parameters:

B0 – [in] Constant coefficient matrix
B1 – [in] Linear coefficient matrix
B2 – [in] Quadratic coefficient matrix
eigvec – [out] Eigenvector corresponding to smallest positive t

Returns:

Smallest positive value of t, or infinity if none exists

class QEPOperator

Operator for structured quadratic eigenvalue problem (QEP) linearization Implements the matrix-vector product for the linearized system C1^{-1}C0 where the original QEP is: (A + λB + λ²C)v = 0

Public Types

using Scalar = NT : Scalar type required by Spectra library.

Public Functions

inline QEPOperator(const MT &A, const MT &B, const MT &C)

Construct QEP operator from coefficient matrices

Parameters:

A – [in] Constant term matrix
B – [in] Linear term matrix
C – [in] Quadratic term matrix (should be positive definite)

inline int rows() const: Number of rows in linearized system (twice original dimension)

inline int cols() const: Number of columns in linearized system (twice original dimension)

inline void perform_op(const NT *x_in, NT *y_out) const

Perform matrix-vector product y = Op * x for Spectra eigenvalue solver Implements the linearized QEP system operator using efficient factorizations

Parameters:

x_in – [in] Input vector of size 2*n
y_out – [out] Output vector of size 2*n

Private Members

const MT &A_: Coefficient matrix A in QEP.

const MT &B_: Coefficient matrix B in QEP.

const MT &C_: Coefficient matrix C in QEP (must be positive definite)

const int n_: Dimension of original problem.

mutable Eigen::LLT<MT> lltC_: Cholesky decomposition of C (LLT)

mutable Eigen::LDLT<MT> ldltC_: LDLT decomposition of C (fallback)

mutable bool chol_computed_ = false: Flag indicating if decomposition is computed.

mutable bool use_llt_ = false: Flag indicating which decomposition to use.