File simulated_annealing.hpp

Defines

CONSTANT_1

Number of sample points for diameter estimation When estimating the diameter of the spectrahedron, sample 100 + sqrt(dimension) points to estimate it

Functions

template<typename NT>
NT computePolynomialTemperature(int step, NT T0, NT Tmin, int dimension, NT k)

Compute temperature using polynomial cooling schedule Calculates temperature at a given step using the formula: T_i = T_0 * alpha^i where alpha = 1 - 1/(d*k) The decay factor alpha is clamped to [0.5, 0.999] to ensure stable cooling. The computed temperature is always at least T_min.

Template Parameters:

NT – Numeric type for calculations

Parameters:

  • step – [in] Current optimization step (iteration number)

  • T0 – [in] Initial temperature

  • Tmin – [in] Minimum allowed temperature

  • dimension – [in] Dimension of the optimization space

  • k – [in] Polynomial schedule parameter controlling cooling rate

Returns:

Temperature at the given step, constrained to be >= Tmin

template<typename Spectrahedron, typename Point, typename Settings>
Point::FT solve_sdp(Spectrahedron &spectrahedron, Point const &objectiveFunction, Settings const &settings, Point const &interiorPoint, Point &solution, bool verbose = false)

Solve semidefinite programming problem using simulated annealing Minimizes a linear objective function c^T * x subject to a linear matrix inequality constraint (spectrahedron). Uses Hamiltonian Monte Carlo (HMC) random walk with Boltzmann distribution for sampling, combined with simulated annealing temperature schedule for optimization. Algorithm outline:

  1. Normalize objective function and estimate feasible region diameter

  2. Initialize temperature schedule (T_0 = diameter)

  3. At each step:

    • Update temperature according to schedule (polynomial or exponential)

    • Sample new point using HMC with current temperature

    • Update best solution if improvement found

    • Check for convergence if early stopping enabled

  4. Return best solution found

Template Parameters:

  • Spectrahedron – Type representing the feasible region (linear matrix inequality)

  • Point – Point type representing vectors in optimization space

  • Settings – Settings type (must be SimulatedAnnealingSettings or compatible)

Parameters:

  • spectrahedron – [in] The feasible region defined by LMI constraints

  • objectiveFunction – [in] Linear objective function to minimize (c^T * x)

  • settings – [in] Algorithm parameters controlling optimization behavior

  • interiorPoint – [in] Initial feasible solution (must be strictly interior)

  • solution – [out] Output parameter storing the best solution found

  • verbose – [in] If true, print progress information during optimization

Throws:

std::runtime_error – if objective function has zero norm or diameter estimation fails

Returns:

Objective function value at the best solution found

template<class Point>
struct SimulatedAnnealingSettings
#include <simulated_annealing.hpp>

Configuration parameters for the simulated annealing algorithm Contains all tunable parameters for controlling the optimization process, including convergence criteria, temperature schedule, and random walk settings.

Template Parameters:

Point – Point type representing vectors in the optimization space

Public Types

typedef Point::FT NT

Numeric type.

Public Functions

inline SimulatedAnnealingSettings(NT error_ = NT(1e-6), int walkLength_ = 3, int maxSteps_ = 5000, NT decFactor_ = NT(0.98), NT tempMinRatio_ = NT(1e-8), bool usePolynomialSchedule_ = true, NT polynomialK_ = NT(0.5), bool enableEarlyConvergence_ = true, int convergenceWindow_ = 20)

Construct settings with default or custom parameters Validates all parameters and throws exceptions if constraints are violated.

Parameters:

  • error_ – [in] Convergence tolerance (must be > 0)

  • walkLength_ – [in] HMC walk length per iteration (must be > 0)

  • maxSteps_ – [in] Maximum optimization steps (must be > 0)

  • decFactor_ – [in] Exponential decay factor (must be in (0,1))

  • tempMinRatio_ – [in] Minimum temperature ratio (must be > 0)

  • usePolynomialSchedule_ – [in] Enable polynomial cooling schedule

  • polynomialK_ – [in] Polynomial schedule parameter (must be > 0)

  • enableEarlyConvergence_ – [in] Enable early stopping based on convergence

  • convergenceWindow_ – [in] Sliding window size for convergence detection

Throws:

std::invalid_argument – if any parameter violates its constraints

Public Members

NT error

Desired accuracy threshold for convergence (relative error tolerance)

int walkLength

Number of steps taken in each HMC random walk iteration.

int maxSteps

Maximum number of optimization steps before termination.

NT decFactor

Temperature decay factor for exponential cooling schedule (must be in (0,1))

NT tempMinRatio

Ratio of minimum temperature to initial temperature (T_min = T_0 * tempMinRatio)

bool usePolynomialSchedule

If true, use polynomial cooling schedule; otherwise use exponential schedule.

NT polynomialK

Parameter k for polynomial schedule: alpha = 1 - 1/(d*k) where d is dimension.

bool enableEarlyConvergence

If true, check for early convergence using sliding window analysis.

int convergenceWindow

Size of sliding window for tracking convergence (number of recent values to track)