Validation utilities for solvers.proto. More...

Namespaces
namespace	internal
	Utility functions for internal use only.

Classes
class	DiagonalTrustRegionProblem

struct	IterationCallbackInfo

struct	LagrangianPart

struct	LocalizedLagrangianBounds

struct	PrimalAndDualSolution

struct	QuadraticProgram

struct	QuadraticProgramBoundNorms

struct	RelativeConvergenceInformation

struct	RescalingOptions

struct	ScalingVectors

class	Scheduler
	Thread scheduling interface. More...

class	ShardedQuadraticProgram

class	ShardedWeightedAverage

class	Sharder

struct	SingularValueAndIterations

struct	SolverResult

struct	TerminationReasonAndPointType

struct	TrustRegionResult

Enumerations
enum class	IterationType { kNormal , kPrimalFeasibility , kDualFeasibility , kPresolveTermination , kNormalTermination , kFeasibilityPolishingTermination }

enum class	PrimalDualNorm { kMaxNorm , kEuclideanNorm }

Functions
ConvergenceInformation	ComputeConvergenceInformation (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &scaled_sharded_qp, const Eigen::VectorXd &col_scaling_vec, const Eigen::VectorXd &row_scaling_vec, const Eigen::VectorXd &scaled_primal_solution, const Eigen::VectorXd &scaled_dual_solution, const double componentwise_primal_residual_offset, const double componentwise_dual_residual_offset, PointType candidate_type)

InfeasibilityInformation	ComputeInfeasibilityInformation (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &scaled_sharded_qp, const Eigen::VectorXd &col_scaling_vec, const Eigen::VectorXd &row_scaling_vec, const Eigen::VectorXd &scaled_primal_ray, const Eigen::VectorXd &scaled_dual_ray, const Eigen::VectorXd &primal_solution_for_residual_tests, PointType candidate_type)

ConvergenceInformation	ComputeScaledConvergenceInformation (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &sharded_qp, const VectorXd &primal_solution, const VectorXd &dual_solution, const double componentwise_primal_residual_offset, const double componentwise_dual_residual_offset, PointType candidate_type)

VectorXd	ReducedCosts (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &sharded_qp, const VectorXd &primal_solution, const VectorXd &dual_solution, bool use_zero_primal_objective)

std::optional< ConvergenceInformation >	GetConvergenceInformation (const IterationStats &stats, PointType candidate_type)

std::optional< InfeasibilityInformation >	GetInfeasibilityInformation (const IterationStats &stats, PointType candidate_type)

std::optional< PointMetadata >	GetPointMetadata (const IterationStats &stats, const PointType point_type)

void	SetRandomProjections (const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_solution, const std::vector< int > &random_projection_seeds, PointMetadata &metadata)

ConvergenceInformation	ComputeScaledConvergenceInformation (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_solution, double componentwise_primal_residual_offset, double componentwise_dual_residual_offset, PointType candidate_type)

Eigen::VectorXd	ReducedCosts (const PrimalDualHybridGradientParams &params, const ShardedQuadraticProgram &scaled_sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_solution, bool use_zero_primal_objective=false)

SolverResult	PrimalDualHybridGradient (QuadraticProgram qp, const PrimalDualHybridGradientParams &params, const std::atomic< bool > *interrupt_solve, std::function< void(const std::string &)> message_callback, IterationStatsCallback iteration_stats_callback)

SolverResult	PrimalDualHybridGradient (QuadraticProgram qp, const PrimalDualHybridGradientParams &params, std::optional< PrimalAndDualSolution > initial_solution, const std::atomic< bool > *interrupt_solve, std::function< void(const std::string &)> message_callback, IterationStatsCallback iteration_stats_callback)

SolverResult	PrimalDualHybridGradient (QuadraticProgram qp, const PrimalDualHybridGradientParams &params, const std::atomic< bool > *interrupt_solve=nullptr, std::function< void(const std::string &)> message_callback=nullptr, std::function< void(const IterationCallbackInfo &)> iteration_stats_callback=nullptr)

SolverResult	PrimalDualHybridGradient (QuadraticProgram qp, const PrimalDualHybridGradientParams &params, std::optional< PrimalAndDualSolution > initial_solution, const std::atomic< bool > *interrupt_solve=nullptr, std::function< void(const std::string &)> message_callback=nullptr, std::function< void(const IterationCallbackInfo &)> iteration_stats_callback=nullptr)

absl::Status	ValidateQuadraticProgramDimensions (const QuadraticProgram &qp)

absl::StatusOr< QuadraticProgram >	QpFromMpModelProto (const MPModelProto &proto, bool relax_integer_variables, bool include_names)

absl::Status	CanFitInMpModelProto (const QuadraticProgram &qp)

absl::StatusOr< MPModelProto >	QpToMpModelProto (const QuadraticProgram &qp)

std::string	ToString (const QuadraticProgram &qp, int64_t max_size)

void	SetEigenMatrixFromTriplets (std::vector< Eigen::Triplet< double, int64_t > > triplets, Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix)

bool	IsLinearProgram (const QuadraticProgram &qp)

QuadraticProgram	ReadQuadraticProgramOrDie (const std::string &filename, bool include_names)

QuadraticProgram	ReadMPModelProtoFileOrDie (const std::string &mpmodel_proto_file, bool include_names)

absl::Status	WriteLinearProgramToMps (const QuadraticProgram &linear_program, const std::string &mps_file)

absl::Status	WriteQuadraticProgramToMPModelProto (const QuadraticProgram &quadratic_program, const std::string &mpmodel_proto_file)

absl::StatusOr< QuadraticProgram >	ReadMpsLinearProgram (const std::string &lp_file, bool include_names)

QuadraticProgram	ReadMpsLinearProgramOrDie (const std::string &lp_file, bool include_names)

QuadraticProgramStats	ComputeStats (const ShardedQuadraticProgram &qp)
	Returns a `QuadraticProgramStats` for a `ShardedQuadraticProgram`.

void	LInfRuizRescaling (const ShardedQuadraticProgram &sharded_qp, const int num_iterations, VectorXd &row_scaling_vec, VectorXd &col_scaling_vec)

void	L2NormRescaling (const ShardedQuadraticProgram &sharded_qp, VectorXd &row_scaling_vec, VectorXd &col_scaling_vec)

ScalingVectors	ApplyRescaling (const RescalingOptions &rescaling_options, ShardedQuadraticProgram &sharded_qp)

LagrangianPart	ComputePrimalGradient (const ShardedQuadraticProgram &sharded_qp, const VectorXd &primal_solution, const VectorXd &dual_product)

double	DualSubgradientCoefficient (const double constraint_lower_bound, const double constraint_upper_bound, const double dual, const double primal_product)

LagrangianPart	ComputeDualGradient (const ShardedQuadraticProgram &sharded_qp, const VectorXd &dual_solution, const VectorXd &primal_product)

SingularValueAndIterations	EstimateMaximumSingularValueOfConstraintMatrix (const ShardedQuadraticProgram &sharded_qp, const std::optional< VectorXd > &primal_solution, const std::optional< VectorXd > &dual_solution, const double desired_relative_error, const double failure_probability, std::mt19937 &mt_generator)

bool	HasValidBounds (const ShardedQuadraticProgram &sharded_qp)

void	ProjectToPrimalVariableBounds (const ShardedQuadraticProgram &sharded_qp, VectorXd &primal, const bool use_feasibility_bounds)

void	ProjectToDualVariableBounds (const ShardedQuadraticProgram &sharded_qp, VectorXd &dual)

void	LInfRuizRescaling (const ShardedQuadraticProgram &sharded_qp, int num_iterations, Eigen::VectorXd &row_scaling_vec, Eigen::VectorXd &col_scaling_vec)

void	L2NormRescaling (const ShardedQuadraticProgram &sharded_qp, Eigen::VectorXd &row_scaling_vec, Eigen::VectorXd &col_scaling_vec)

LagrangianPart	ComputePrimalGradient (const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_product)

LagrangianPart	ComputeDualGradient (const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &dual_solution, const Eigen::VectorXd &primal_product)

SingularValueAndIterations	EstimateMaximumSingularValueOfConstraintMatrix (const ShardedQuadraticProgram &sharded_qp, const std::optional< Eigen::VectorXd > &primal_solution, const std::optional< Eigen::VectorXd > &dual_solution, double desired_relative_error, double failure_probability, std::mt19937 &mt_generator)

void	ProjectToPrimalVariableBounds (const ShardedQuadraticProgram &sharded_qp, Eigen::VectorXd &primal, bool use_feasibility_bounds=false)

void	ProjectToDualVariableBounds (const ShardedQuadraticProgram &sharded_qp, Eigen::VectorXd &dual)

VectorXd	TransposedMatrixVectorProduct (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const VectorXd &vector, const Sharder &sharder)

void	SetZero (const Sharder &sharder, VectorXd &dest)

VectorXd	ZeroVector (const Sharder &sharder)
	Like `VectorXd::Zero(sharder.NumElements())`.

VectorXd	OnesVector (const Sharder &sharder)
	Like `VectorXd::Ones(sharder.NumElements())`.

void	AddScaledVector (const double scale, const VectorXd &increment, const Sharder &sharder, VectorXd &dest)

void	AssignVector (const VectorXd &vec, const Sharder &sharder, VectorXd &dest)

VectorXd	CloneVector (const VectorXd &vec, const Sharder &sharder)

void	CoefficientWiseProductInPlace (const VectorXd &scale, const Sharder &sharder, VectorXd &dest)

void	CoefficientWiseQuotientInPlace (const VectorXd &scale, const Sharder &sharder, VectorXd &dest)

double	Dot (const VectorXd &v1, const VectorXd &v2, const Sharder &sharder)

double	LInfNorm (const VectorXd &vector, const Sharder &sharder)

double	L1Norm (const VectorXd &vector, const Sharder &sharder)

double	SquaredNorm (const VectorXd &vector, const Sharder &sharder)

double	Norm (const VectorXd &vector, const Sharder &sharder)

double	SquaredDistance (const VectorXd &vector1, const VectorXd &vector2, const Sharder &sharder)

double	Distance (const VectorXd &vector1, const VectorXd &vector2, const Sharder &sharder)

double	ScaledLInfNorm (const VectorXd &vector, const VectorXd &scale, const Sharder &sharder)

double	ScaledSquaredNorm (const VectorXd &vector, const VectorXd &scale, const Sharder &sharder)

double	ScaledNorm (const VectorXd &vector, const VectorXd &scale, const Sharder &sharder)

VectorXd	ScaledColLInfNorm (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const VectorXd &row_scaling_vec, const VectorXd &col_scaling_vec, const Sharder &sharder)

VectorXd	ScaledColL2Norm (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const VectorXd &row_scaling_vec, const VectorXd &col_scaling_vec, const Sharder &sharder)

Eigen::VectorXd	TransposedMatrixVectorProduct (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const Eigen::VectorXd &vector, const Sharder &sharder)

void	SetZero (const Sharder &sharder, Eigen::VectorXd &dest)

void	AddScaledVector (double scale, const Eigen::VectorXd &increment, const Sharder &sharder, Eigen::VectorXd &dest)
	Like `dest += scale * increment`.

void	AssignVector (const Eigen::VectorXd &vec, const Sharder &sharder, Eigen::VectorXd &dest)
	Like `dest = vec`. `dest` is resized if needed.

Eigen::VectorXd	CloneVector (const Eigen::VectorXd &vec, const Sharder &sharder)
	Returns a copy of `vec`.

void	CoefficientWiseProductInPlace (const Eigen::VectorXd &scale, const Sharder &sharder, Eigen::VectorXd &dest)
	Like `dest = dest.cwiseProduct(scale)`.

void	CoefficientWiseQuotientInPlace (const Eigen::VectorXd &scale, const Sharder &sharder, Eigen::VectorXd &dest)
	Like `dest = dest.cwiseQuotient(scale)`.

double	Dot (const Eigen::VectorXd &v1, const Eigen::VectorXd &v2, const Sharder &sharder)
	Like `v1.dot(v2)`.

double	LInfNorm (const Eigen::VectorXd &vector, const Sharder &sharder)
	Like `vector.lpNorm<Eigen::Infinity>()`, a.k.a. LInf norm.

double	L1Norm (const Eigen::VectorXd &vector, const Sharder &sharder)
	Like `vector.lpNorm<1>()`, a.k.a. L_1 norm.

double	SquaredNorm (const Eigen::VectorXd &vector, const Sharder &sharder)
	Like `vector.squaredNorm()`.

double	Norm (const Eigen::VectorXd &vector, const Sharder &sharder)
	Like `vector.norm()`.

double	SquaredDistance (const Eigen::VectorXd &vector1, const Eigen::VectorXd &vector2, const Sharder &sharder)
	Like `(vector1 - vector2).squaredNorm()`.

double	Distance (const Eigen::VectorXd &vector1, const Eigen::VectorXd &vector2, const Sharder &sharder)
	Like `(vector1 - vector2).norm()`.

double	ScaledLInfNorm (const Eigen::VectorXd &vector, const Eigen::VectorXd &scale, const Sharder &sharder)
	`ScaledL1Norm` is omitted because it's not needed (yet).

double	ScaledSquaredNorm (const Eigen::VectorXd &vector, const Eigen::VectorXd &scale, const Sharder &sharder)

double	ScaledNorm (const Eigen::VectorXd &vector, const Eigen::VectorXd &scale, const Sharder &sharder)
	L2 norm of a rescaled vector, i.e., `vector.cwiseProduct(scale).norm()`.

Eigen::VectorXd	ScaledColLInfNorm (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const Eigen::VectorXd &row_scaling_vec, const Eigen::VectorXd &col_scaling_vec, const Sharder &sharder)
	Computes the LInf norm of each column of a scaled `matrix`.

Eigen::VectorXd	ScaledColL2Norm (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, const Eigen::VectorXd &row_scaling_vec, const Eigen::VectorXd &col_scaling_vec, const Sharder &sharder)
	Computes the L2 norm of each column of a scaled `matrix`.

absl::Status	CheckNonNegative (const double value, const absl::string_view name)

absl::Status	ValidateTerminationCriteria (const TerminationCriteria &criteria)

absl::Status	ValidateAdaptiveLinesearchParams (const AdaptiveLinesearchParams &params)

absl::Status	ValidateMalitskyPockParams (const MalitskyPockParams &params)

absl::Status	ValidatePrimalDualHybridGradientParams (const PrimalDualHybridGradientParams &params)

bool	ObjectiveGapMet (const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats)

bool	OptimalityCriteriaMet (const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats, OptimalityNorm optimality_norm, const QuadraticProgramBoundNorms &bound_norms)
	Determines if the optimality criteria are met.

TerminationCriteria::DetailedOptimalityCriteria	EffectiveOptimalityCriteria (const TerminationCriteria &termination_criteria)
	Computes the effective optimality criteria for a `TerminationCriteria`.

TerminationCriteria::DetailedOptimalityCriteria	EffectiveOptimalityCriteria (const TerminationCriteria::SimpleOptimalityCriteria &simple_criteria)

std::optional< TerminationReasonAndPointType >	CheckSimpleTerminationCriteria (const TerminationCriteria &criteria, const IterationStats &stats, const std::atomic< bool > *interrupt_solve)

std::optional< TerminationReasonAndPointType >	CheckIterateTerminationCriteria (const TerminationCriteria &criteria, const IterationStats &stats, const QuadraticProgramBoundNorms &bound_norms, const bool force_numerical_termination)

QuadraticProgramBoundNorms	BoundNormsFromProblemStats (const QuadraticProgramStats &stats)

double	EpsilonRatio (const double epsilon_absolute, const double epsilon_relative)

RelativeConvergenceInformation	ComputeRelativeResiduals (const TerminationCriteria::DetailedOptimalityCriteria &optimality_criteria, const ConvergenceInformation &stats, const QuadraticProgramBoundNorms &bound_norms)

QuadraticProgram	TestLp ()

void	VerifyTestLp (const QuadraticProgram &qp, bool maximize=false)
	Verifies that the given QuadraticProgram equals TestLp().

QuadraticProgram	TinyLp ()

QuadraticProgram	CorrelationClusteringLp ()
	\| /

QuadraticProgram	CorrelationClusteringStarLp ()

QuadraticProgram	TestDiagonalQp1 ()

QuadraticProgram	TestDiagonalQp2 ()

QuadraticProgram	TestDiagonalQp3 ()

QuadraticProgram	SmallInvalidProblemLp ()

QuadraticProgram	SmallInconsistentVariableBoundsLp ()

QuadraticProgram	SmallPrimalInfeasibleLp ()

QuadraticProgram	SmallDualInfeasibleLp ()

QuadraticProgram	SmallPrimalDualInfeasibleLp ()

QuadraticProgram	SmallInitializationLp ()

QuadraticProgram	LpWithoutConstraints ()

void	VerifyTestDiagonalQp1 (const QuadraticProgram &qp, bool maximize)

::Eigen::ArrayXXd	ToDense (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &sparse_mat)

TrustRegionResult	SolveTrustRegion (const VectorXd &objective_vector, const VectorXd &variable_lower_bounds, const VectorXd &variable_upper_bounds, const VectorXd &center_point, const VectorXd &norm_weights, const double target_radius, const Sharder &sharder)

dual_gradient	T (y - `dual_solution`) class DiagonalTrustRegionProblemFromQp

template<typename DiagonalTrustRegionProblem >
double	ProjectedValueOfScaledDifference (const DiagonalTrustRegionProblem &problem, const int64_t index, const double scaling_factor)

template<typename DiagonalTrustRegionProblem >
double	NormOfDeltaProjection (const DiagonalTrustRegionProblem &problem, const Sharder &sharder, const double scaling_factor)

template<typename DiagonalTrustRegionProblem >
double	FindScalingFactor (const DiagonalTrustRegionProblem &problem, const Sharder &sharder, const double target_radius, const double solve_tol)

template<typename DiagonalTrustRegionProblem >
TrustRegionResult	SolveDiagonalTrustRegionProblem (const DiagonalTrustRegionProblem &problem, const Sharder &sharder, const double target_radius, const double solve_tol)

TrustRegionResult	SolveDiagonalTrustRegion (const VectorXd &objective_vector, const VectorXd &objective_matrix_diagonal, const VectorXd &variable_lower_bounds, const VectorXd &variable_upper_bounds, const VectorXd &center_point, const VectorXd &norm_weights, const double target_radius, const Sharder &sharder, const double solve_tolerance)

TrustRegionResult	SolveDiagonalQpTrustRegion (const ShardedQuadraticProgram &sharded_qp, const VectorXd &primal_solution, const VectorXd &dual_solution, const VectorXd &primal_gradient, const VectorXd &dual_gradient, const double primal_weight, double target_radius, const double solve_tolerance)

LocalizedLagrangianBounds	ComputeLocalizedLagrangianBounds (const ShardedQuadraticProgram &sharded_qp, const VectorXd &primal_solution, const VectorXd &dual_solution, const PrimalDualNorm primal_dual_norm, const double primal_weight, const double radius, const VectorXd primal_product, const VectorXd dual_product, const bool use_diagonal_qp_trust_region_solver, const double diagonal_qp_trust_region_solver_tolerance)

TrustRegionResult	SolveTrustRegion (const Eigen::VectorXd &objective_vector, const Eigen::VectorXd &variable_lower_bounds, const Eigen::VectorXd &variable_upper_bounds, const Eigen::VectorXd &center_point, const Eigen::VectorXd &norm_weights, double target_radius, const Sharder &sharder)

TrustRegionResult	SolveDiagonalTrustRegion (const Eigen::VectorXd &objective_vector, const Eigen::VectorXd &objective_matrix_diagonal, const Eigen::VectorXd &variable_lower_bounds, const Eigen::VectorXd &variable_upper_bounds, const Eigen::VectorXd &center_point, const Eigen::VectorXd &norm_weights, double target_radius, const Sharder &sharder, double solve_tolerance)

TrustRegionResult	SolveDiagonalQpTrustRegion (const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_solution, const Eigen::VectorXd &primal_gradient, const Eigen::VectorXd &dual_gradient, const double primal_weight, double target_radius, double solve_tolerance)

double	BoundGap (const LocalizedLagrangianBounds &bounds)

*x LocalizedLagrangianBounds	ComputeLocalizedLagrangianBounds (const ShardedQuadraticProgram &sharded_qp, const Eigen::VectorXd &primal_solution, const Eigen::VectorXd &dual_solution, PrimalDualNorm primal_dual_norm, double primal_weight, double radius, const Eigen::VectorXd primal_product, const Eigen::VectorXd dual_product, bool use_diagonal_qp_trust_region_solver, double diagonal_qp_trust_region_solver_tolerance)

Variables
constexpr double	kInfinity = std::numeric_limits<double>::infinity()

const double	kTinyDouble = 1.0e-50

const double	kHugeDouble = 1.0e50

x_0 x_1 x_2	x_3

*x	primal_solution

Detailed Description

Validation utilities for solvers.proto.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. These are internal helper functions and classes that implicitly or explicitly operate on a ShardedQuadraticProgram. Utilities that are purely linear algebra operations (e.g., norms) should be defined in sharder.h instead.

Enumeration Type Documentation

◆ IterationType

enum class operations_research::pdlp::IterationType

strong

Identifies the iteration type in a callback. The callback is called both for intermediate iterations and upon termination.

Enumerator
kNormal	An intermediate iteration in the "main" phase.
kPrimalFeasibility	An intermediate iteration during a primal feasibility polishing phase.
kDualFeasibility	An intermediate iteration during a dual feasibility polishing phase.
kPresolveTermination	Terminating with a solution found by presolve.
kNormalTermination	Terminating with a solution found by the "main" phase.
kFeasibilityPolishingTermination	Terminating with a solution found by feasibility polishing.

Definition at line 75 of file primal_dual_hybrid_gradient.h.

◆ PrimalDualNorm

enum class operations_research::pdlp::PrimalDualNorm

strong

Defines a norm on a vector partitioned as (x, y) where x is the primal and y is the dual. The enum values define a joint norm as a function of |x|_P and |y|_D, whose definition depends on the context.

Enumerator
kMaxNorm	The joint norm \|\|(x,y)\|\|_PD = max{\|`x`\|_P, \|`y`\|_D}.
kEuclideanNorm	The joint norm (\|\|(x,y)\|\|_PD)^2 = (\|`x`\|_P)^2 + (\|`y`\|_D)^2.

Definition at line 120 of file trust_region.h.

Function Documentation

◆ AddScaledVector() [1/2]

void operations_research::pdlp::AddScaledVector	(	const double	scale,
		const VectorXd &	increment,
		const Sharder &	sharder,
		VectorXd &	dest )

Definition at line 197 of file sharder.cc.

◆ AddScaledVector() [2/2]

void operations_research::pdlp::AddScaledVector	(	double	scale,
		const Eigen::VectorXd &	increment,
		const Sharder &	sharder,
		Eigen::VectorXd &	dest )

Like dest += scale * increment.

◆ ApplyRescaling()

ScalingVectors operations_research::pdlp::ApplyRescaling	(	const RescalingOptions &	rescaling_options,
		ShardedQuadraticProgram &	sharded_qp )

Applies the rescaling specified by rescaling_options to sharded_qp (in place). Returns the scaling vectors that were applied.

Definition at line 423 of file sharded_optimization_utils.cc.

◆ AssignVector() [1/2]

void operations_research::pdlp::AssignVector	(	const Eigen::VectorXd &	vec,
		const Sharder &	sharder,
		Eigen::VectorXd &	dest )

Like dest = vec. dest is resized if needed.

◆ AssignVector() [2/2]

void operations_research::pdlp::AssignVector	(	const VectorXd &	vec,
		const Sharder &	sharder,
		VectorXd &	dest )

Definition at line 204 of file sharder.cc.

◆ BoundGap()

double operations_research::pdlp::BoundGap ( const LocalizedLagrangianBounds & bounds )

inline

Definition at line 113 of file trust_region.h.

◆ BoundNormsFromProblemStats()

QuadraticProgramBoundNorms operations_research::pdlp::BoundNormsFromProblemStats ( const QuadraticProgramStats & stats )

Extracts the norms needed for the termination criteria from the full problem stats.

Definition at line 221 of file termination.cc.

◆ CanFitInMpModelProto()

absl::Status operations_research::pdlp::CanFitInMpModelProto ( const QuadraticProgram & qp )

Returns InvalidArgumentError if qp is too large to convert to MPModelProto and OkStatus otherwise.

Definition at line 218 of file quadratic_program.cc.

◆ CheckIterateTerminationCriteria()

std::optional< TerminationReasonAndPointType > operations_research::pdlp::CheckIterateTerminationCriteria	(	const TerminationCriteria &	criteria,
		const IterationStats &	stats,
		const QuadraticProgramBoundNorms &	bound_norms,
		bool	force_numerical_termination = false )

Checks if any iterate-based termination criteria (i.e., the criteria not checked by CheckSimpleTerimationCriteria()) are satisfied by the solution state described by stats (see definitions of termination criteria in solvers.proto). bound_norms provides the instance-dependent data required for the relative convergence criteria. Returns a termination reason and a point type if so (if multiple criteria are satisfied, the optimality and infeasibility conditions are checked first). If force_numerical_termination is true, returns TERMINATION_REASON_NUMERICAL_ERROR if no other criteria are satisfied. The return value is empty in any other case. If the output is not empty, the PointType indicates which entry prompted termination. If no entry prompted termination, e.g. TERMINATION_REASON_NUMERICAL_ERROR is returned, then the PointType is set to POINT_TYPE_NONE. NOTE: This function assumes that the solution used to compute the stats satisfies the primal and dual variable bounds; see https://developers.google.com/optimization/lp/pdlp_math#dual_variable_bounds.

Definition at line 186 of file termination.cc.

◆ CheckNonNegative()

absl::Status operations_research::pdlp::CheckNonNegative	(	const double	value,
		const absl::string_view	name )

Definition at line 34 of file solvers_proto_validation.cc.

◆ CheckSimpleTerminationCriteria()

std::optional< TerminationReasonAndPointType > operations_research::pdlp::CheckSimpleTerminationCriteria	(	const TerminationCriteria &	criteria,
		const IterationStats &	stats,
		const std::atomic< bool > *	interrupt_solve = nullptr )

Checks if any of the simple termination criteria are satisfied by stats, and returns a termination reason if so, and nullopt otherwise. The "simple" termination criteria are time_sec_limit, iteration_limit, kkt_matrix_pass_limit, and interrupt_solve. The corresponding fields of stats (cumulative_time_sec, iteration_number, cumulative_kkt_matrix_passes) are the only ones accessed. If returning a termination reason, the PointType will be set to POINT_TYPE_NONE.

Definition at line 161 of file termination.cc.

◆ CloneVector() [1/2]

Eigen::VectorXd operations_research::pdlp::CloneVector	(	const Eigen::VectorXd &	vec,
		const Sharder &	sharder )

Returns a copy of vec.

◆ CloneVector() [2/2]

VectorXd operations_research::pdlp::CloneVector	(	const VectorXd &	vec,
		const Sharder &	sharder )

Definition at line 210 of file sharder.cc.

◆ CoefficientWiseProductInPlace() [1/2]

void operations_research::pdlp::CoefficientWiseProductInPlace	(	const Eigen::VectorXd &	scale,
		const Sharder &	sharder,
		Eigen::VectorXd &	dest )

Like dest = dest.cwiseProduct(scale).

◆ CoefficientWiseProductInPlace() [2/2]

void operations_research::pdlp::CoefficientWiseProductInPlace	(	const VectorXd &	scale,
		const Sharder &	sharder,
		VectorXd &	dest )

Definition at line 216 of file sharder.cc.

◆ CoefficientWiseQuotientInPlace() [1/2]

void operations_research::pdlp::CoefficientWiseQuotientInPlace	(	const Eigen::VectorXd &	scale,
		const Sharder &	sharder,
		Eigen::VectorXd &	dest )

Like dest = dest.cwiseQuotient(scale).

◆ CoefficientWiseQuotientInPlace() [2/2]

void operations_research::pdlp::CoefficientWiseQuotientInPlace	(	const VectorXd &	scale,
		const Sharder &	sharder,
		VectorXd &	dest )

Definition at line 223 of file sharder.cc.

◆ ComputeConvergenceInformation()

ConvergenceInformation operations_research::pdlp::ComputeConvergenceInformation	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	col_scaling_vec,
		const Eigen::VectorXd &	row_scaling_vec,
		const Eigen::VectorXd &	scaled_primal_solution,
		const Eigen::VectorXd &	scaled_dual_solution,
		double	componentwise_primal_residual_offset,
		double	componentwise_dual_residual_offset,
		PointType	candidate_type )

Returns convergence statistics about a primal/dual solution pair. It is assumed that scaled_sharded_qp has been transformed from the original qp by ShardedQuadraticProgram::RescaleQuadraticProgram(col_scaling_vec, / row_scaling_vec). scaled_primal_solution and scaled_dual_solution are solutions for the scaled problem. The stats are computed with respect to the implicit original problem. componentwise_primal_residual_offset and componentwise_dual_residual_offset are the offsets (i.e., eps_ratio) used for computing the l_inf_componentwise residual norms.

Note: This function assumes that scaled_primal_solution satisfies the variable bounds and scaled_dual_solution satisfies the dual variable bounds; see https://developers.google.com/optimization/lp/pdlp_math#dual_variable_bounds.

See https://developers.google.com/optimization/lp/pdlp_math#rescaling for notes describing the connection between the scaled and unscaled problem.

This is the dual objective from https://developers.google.com/optimization/lp/pdlp_math minus the last term (involving r). All scaling terms cancel out.

Definition at line 383 of file iteration_stats.cc.

◆ ComputeDualGradient() [1/2]

LagrangianPart operations_research::pdlp::ComputeDualGradient	(	const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	dual_solution,
		const Eigen::VectorXd &	primal_product )

Computes the value of the dual part of the Lagrangian function defined at https://developers.google.com/optimization/lp/pdlp_math, i.e., -h^*(y) and the gradient of the Lagrangian with respect to the dual variables y, i.e., -Ax - \grad_y h^*(y). Note the asymmetry with ComputePrimalGradient: the term -y^T Ax is not part of the value. Because h^*(y) is piece-wise linear, a subgradient is returned at a point of non-smoothness. primal_product is Ax. The result is undefined and invalid if any duals violate their bounds.

◆ ComputeDualGradient() [2/2]

LagrangianPart operations_research::pdlp::ComputeDualGradient	(	const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	dual_solution,
		const VectorXd &	primal_product )

Definition at line 502 of file sharded_optimization_utils.cc.

◆ ComputeInfeasibilityInformation()

InfeasibilityInformation operations_research::pdlp::ComputeInfeasibilityInformation	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	scaled_sharded_qp,
		const Eigen::VectorXd &	col_scaling_vec,
		const Eigen::VectorXd &	row_scaling_vec,
		const Eigen::VectorXd &	scaled_primal_ray,
		const Eigen::VectorXd &	scaled_dual_ray,
		const Eigen::VectorXd &	primal_solution_for_residual_tests,
		PointType	candidate_type )

Returns infeasibility statistics about a primal/dual infeasibility certificate estimate. It is assumed that scaled_sharded_qp has been transformed from the original qp by ShardedQuadraticProgram::RescaleQuadraticProgram(col_scaling_vec, / row_scaling_vec). scaled_primal_ray and scaled_dual_ray are potential certificates for the scaled problem. The stats are computed with respect to the implicit original problem. primal_solution_for_residual_tests is used instead of scaled_primal_ray when deciding whether or not to treat a primal gradient as a dual residual or not.

Compute primal infeasibility information.

We don't use dual_residuals.l_inf_componentwise_residual, so don't need to set componentwise_residual_offset to a meaningful value.

Compute dual infeasibility information. We don't use primal_residuals.l_inf_componentwise_residual, so don't need to set componentwise_residual_offset to a meaningful value.

The primal ray should have been projected onto the feasibility bounds, so that it has the correct signs.

Definition at line 486 of file iteration_stats.cc.

◆ ComputeLocalizedLagrangianBounds() [1/2]

*x LocalizedLagrangianBounds operations_research::pdlp::ComputeLocalizedLagrangianBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_solution,
		PrimalDualNorm	primal_dual_norm,
		double	primal_weight,
		double	radius,
		const Eigen::VectorXd *	primal_product,
		const Eigen::VectorXd *	dual_product,
		bool	use_diagonal_qp_trust_region_solver,
		double	diagonal_qp_trust_region_solver_tolerance )

subject to ||(x - primal_solution, y - dual_solution)||_PD <= radius. use_diagonal_qp_trust_region_solver == true assumes that primal_dual_norm is the Euclidean norm and the objective matrix is diagonal. See SolveDiagonalTrustRegion() above for the meaning of diagonal_qp_trust_region_solver_tolerance.

In the context of primal_dual_norm, the primal norm ||.||_P is defined as (|x|_P)^2 = (1 / 2) * primal_weight * |x|_2^2, and the dual norm ||.||_D is defined as (|y|_D)^2 = (1 / 2) * (1 / primal_weight) * |y|_2^2.

Given an optimal solution (x, y) to the above problem, the lower bound is computed as L(primal_solution, dual_solution) + ∇_x L(primal_solution, dual_solution)^T (x - primal_solution) and the upper bound is computed as L(primal_solution, dual_solution) + ∇_y L(primal_solution, dual_solution)^T (y - dual_solution).

The bounds are "localized" because they are guaranteed to bound OPT only if the ||.||_PD ball contains an optimal solution. primal_product and dual_product optionally specify the values of constraint_matrix * primal_solution and constraint_matrix.transpose() * dual_solution, respectively. If set to nullptr, they will be computed.

◆ ComputeLocalizedLagrangianBounds() [2/2]

LocalizedLagrangianBounds operations_research::pdlp::ComputeLocalizedLagrangianBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	primal_solution,
		const VectorXd &	dual_solution,
		const PrimalDualNorm	primal_dual_norm,
		const double	primal_weight,
		const double	radius,
		const VectorXd *	primal_product,
		const VectorXd *	dual_product,
		const bool	use_diagonal_qp_trust_region_solver,
		const double	diagonal_qp_trust_region_solver_tolerance )

Definition at line 978 of file trust_region.cc.

◆ ComputePrimalGradient() [1/2]

LagrangianPart operations_research::pdlp::ComputePrimalGradient	(	const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_product )

Computes the value of the primal part of the Lagrangian function defined at https://developers.google.com/optimization/lp/pdlp_math, i.e., c^T x + (1/2) x^T Qx - y^T Ax and its gradient with respect to the primal variables x, i.e., c + Qx - A^T y. dual_product is A^T y. Note: The objective constant is omitted. The result is undefined and invalid if any primal bounds are violated.

◆ ComputePrimalGradient() [2/2]

LagrangianPart operations_research::pdlp::ComputePrimalGradient	(	const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	primal_solution,
		const VectorXd &	dual_product )

Note: using auto instead of VectorXd for the type of objective_product causes eigen to defer the matrix product until it is used (twice).

Definition at line 446 of file sharded_optimization_utils.cc.

◆ ComputeRelativeResiduals()

RelativeConvergenceInformation operations_research::pdlp::ComputeRelativeResiduals	(	const TerminationCriteria::DetailedOptimalityCriteria &	optimality_criteria,
		const ConvergenceInformation &	stats,
		const QuadraticProgramBoundNorms &	bound_norms )

Definition at line 239 of file termination.cc.

◆ ComputeScaledConvergenceInformation() [1/2]

ConvergenceInformation operations_research::pdlp::ComputeScaledConvergenceInformation	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_solution,
		double	componentwise_primal_residual_offset,
		double	componentwise_dual_residual_offset,
		PointType	candidate_type )

Returns convergence statistics about a primal/dual solution pair. The stats are with respect to sharded_qp (which is typically scaled). This function is equivalent to ComputeConvergenceInformation given scaling vectors uniformly equal to one.

◆ ComputeScaledConvergenceInformation() [2/2]

ConvergenceInformation operations_research::pdlp::ComputeScaledConvergenceInformation	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	primal_solution,
		const VectorXd &	dual_solution,
		const double	componentwise_primal_residual_offset,
		const double	componentwise_dual_residual_offset,
		PointType	candidate_type )

Definition at line 566 of file iteration_stats.cc.

◆ ComputeStats()

QuadraticProgramStats operations_research::pdlp::ComputeStats ( const ShardedQuadraticProgram & qp )

Returns a QuadraticProgramStats for a ShardedQuadraticProgram.

Caution: if the constraint matrix is empty, elementwise operations (like .coeffs().maxCoeff() or .minCoeff()) will fail.

Definition at line 270 of file sharded_optimization_utils.cc.

◆ CorrelationClusteringLp()

QuadraticProgram operations_research::pdlp::CorrelationClusteringLp ( )

| /

Returns a correlation clustering LP. This is the LP for minimizing disagreements for correlation clustering for the 4-vertex graph In integer solutions x_ij is 1 if i and j are in the same cluster and 0 otherwise. The 6 variables are in the order x_12, x_13, x_14, x_23, x_24, x_34. For any distinct i,j,k there's a triangle inequality (1-x_ik) <= (1-x_ij) + (1-x_jk) i.e. -x_ij - x_jk + x_ik >= -1. For brevity we only include 3 out of the 12 possible triangle inequalities: two needed in the optimal solution and 1 other.

Optimal solutions: Primal: [1, 1, 0, 1, 0, 0] Dual: Multiple. Value: 1.

Definition at line 89 of file test_util.cc.

◆ CorrelationClusteringStarLp()

QuadraticProgram operations_research::pdlp::CorrelationClusteringStarLp ( )

Returns another 4-vertex correlation clustering LP.

The variables are x_12, x_13, x_14, x_23, x_24, and x_34. This time the graph is a star centered at vertex 1. Only the three triangle inequalities that are needed are included. Optimal solutions: Primal: [0.5, 0.5, 0.5, 0.0, 0.0, 0.0] Dual: [0.5, 0.5, 0.5] Value: 1.5

Definition at line 110 of file test_util.cc.

◆ Distance() [1/2]

double operations_research::pdlp::Distance	(	const Eigen::VectorXd &	vector1,
		const Eigen::VectorXd &	vector2,
		const Sharder &	sharder )

Like (vector1 - vector2).norm().

◆ Distance() [2/2]

double operations_research::pdlp::Distance	(	const VectorXd &	vector1,
		const VectorXd &	vector2,
		const Sharder &	sharder )

Definition at line 264 of file sharder.cc.

◆ Dot() [1/2]

double operations_research::pdlp::Dot	(	const Eigen::VectorXd &	v1,
		const Eigen::VectorXd &	v2,
		const Sharder &	sharder )

Like v1.dot(v2).

◆ Dot() [2/2]

double operations_research::pdlp::Dot	(	const VectorXd &	v1,
		const VectorXd &	v2,
		const Sharder &	sharder )

Definition at line 230 of file sharder.cc.

◆ DualSubgradientCoefficient()

double operations_research::pdlp::DualSubgradientCoefficient	(	double	constraint_lower_bound,
		double	constraint_upper_bound,
		double	dual,
		double	primal_product )

Returns a subderivative of the concave dual penalty function that appears in the Lagrangian: -p(dual; -constraint_upper_bound, -constraint_lower_bound) = { constraint_upper_bound * dual when dual < 0, 0 when dual == 0, and constraint_lower_bound * dual when dual > 0} (as defined at https://developers.google.com/optimization/lp/pdlp_math). The subderivative is not necessarily unique when dual == 0. In this case, if only one of the bounds is finite, we return that one. If both are finite, we return primal_product projected onto the bounds, which causes the dual Lagrangian gradient to be zero when the constraint is not violated. If both are infinite, we return zero. The value returned is valid only when the function is finite-valued.

Definition at line 476 of file sharded_optimization_utils.cc.

◆ EffectiveOptimalityCriteria() [1/2]

TerminationCriteria::DetailedOptimalityCriteria operations_research::pdlp::EffectiveOptimalityCriteria ( const TerminationCriteria & termination_criteria )

Computes the effective optimality criteria for a TerminationCriteria.

Definition at line 126 of file termination.cc.

◆ EffectiveOptimalityCriteria() [2/2]

TerminationCriteria::DetailedOptimalityCriteria operations_research::pdlp::EffectiveOptimalityCriteria ( const TerminationCriteria::SimpleOptimalityCriteria & simple_criteria )

Like the previous overload but takes a SimpleOptimalityCriteria. Useful in unit tests where no TerminationCriteria is naturally available.

Definition at line 143 of file termination.cc.

◆ EpsilonRatio()

double operations_research::pdlp::EpsilonRatio	(	double	epsilon_absolute,
		double	epsilon_relative )

Returns epsilon_absolute / epsilon_relative, returning 1.0 if epsilon_absolute and epsilon_relative are equal (even if they are both 0.0 or infinity, which would normally yield NAN).

Handling epsilon_absolute == epsilon_relative explicitly avoids NANs when both values are zero or infinite.

Definition at line 230 of file termination.cc.

◆ EstimateMaximumSingularValueOfConstraintMatrix() [1/2]

SingularValueAndIterations operations_research::pdlp::EstimateMaximumSingularValueOfConstraintMatrix	(	const ShardedQuadraticProgram &	sharded_qp,
		const std::optional< Eigen::VectorXd > &	primal_solution,
		const std::optional< Eigen::VectorXd > &	dual_solution,
		double	desired_relative_error,
		double	failure_probability,
		std::mt19937 &	mt_generator )

Estimates the maximum singular value of A by applying the method of power iteration to A^T A. If primal_solution or dual_solution is provided, restricts to the "active" part of A, that is, the columns (rows) for variables that are not at their bounds in the solution. The estimate will have desired_relative_error with probability at least 1 - failure_probability. The number of iterations will be approximately log(primal_size / failure_probability^2)/(2 * desired_relative_error). Uses a mersenne-twister portable random number generator to generate the starting point for the power method, in order to have deterministic results.

◆ EstimateMaximumSingularValueOfConstraintMatrix() [2/2]

SingularValueAndIterations operations_research::pdlp::EstimateMaximumSingularValueOfConstraintMatrix	(	const ShardedQuadraticProgram &	sharded_qp,
		const std::optional< VectorXd > &	primal_solution,
		const std::optional< VectorXd > &	dual_solution,
		const double	desired_relative_error,
		const double	failure_probability,
		std::mt19937 &	mt_generator )

Definition at line 676 of file sharded_optimization_utils.cc.

◆ FindScalingFactor()

template<typename DiagonalTrustRegionProblem >

double operations_research::pdlp::FindScalingFactor	(	const DiagonalTrustRegionProblem &	problem,
		const Sharder &	sharder,
		const double	target_radius,
		const double	solve_tol )

Finds an approximately optimal scaling factor for the solution of the trust region subproblem, which can be passed on to ProjectedCoordinate() to find an approximately optimal solution to the trust region subproblem. The value returned is guaranteed to be within solve_tol * max(1, s*) of the optimal scaling s*.

Todo: (user): figure out what accuracy is useful to callers and redo the stopping criterion accordingly.

Determine a search interval using monotonicity of the squared norm of the candidate solution with respect to the scaling factor.

Invariant: scaling_factor_upper_bound >= scaling_factor_lower_bound.

Norm is monotonically non-increasing as a function of scaling_factor.

Definition at line 663 of file trust_region.cc.

◆ GetConvergenceInformation()

std::optional< ConvergenceInformation > operations_research::pdlp::GetConvergenceInformation	(	const IterationStats &	stats,
		PointType	candidate_type )

Finds and returns the ConvergenceInformation with the specified candidate_type, or std::nullopt if no such candidate exists.

Definition at line 595 of file iteration_stats.cc.

◆ GetInfeasibilityInformation()

std::optional< InfeasibilityInformation > operations_research::pdlp::GetInfeasibilityInformation	(	const IterationStats &	stats,
		PointType	candidate_type )

Finds and returns the InfeasibilityInformation with the specified candidate_type, or std::nullopt if no such candidate exists.

Definition at line 605 of file iteration_stats.cc.

◆ GetPointMetadata()

std::optional< PointMetadata > operations_research::pdlp::GetPointMetadata	(	const IterationStats &	stats,
		PointType	point_type )

Finds and returns the PointMetadata with the specified point_type, or std::nullopt if no such point exists.

Definition at line 616 of file iteration_stats.cc.

◆ HasValidBounds()

bool operations_research::pdlp::HasValidBounds ( const ShardedQuadraticProgram & sharded_qp )

Checks if the lower and upper bounds of the problem are consistent, i.e. for each variable and constraint bound we have lower_bound <= upper_bound, lower_bound < inf, and upper_bound > -inf. If the input is consistent the method returns true, otherwise it returns false.

Definition at line 701 of file sharded_optimization_utils.cc.

◆ IsLinearProgram()

bool operations_research::pdlp::IsLinearProgram ( const QuadraticProgram & qp )

inline

Definition at line 157 of file quadratic_program.h.

◆ L1Norm() [1/2]

double operations_research::pdlp::L1Norm	(	const Eigen::VectorXd &	vector,
		const Sharder &	sharder )

Like vector.lpNorm<1>(), a.k.a. L_1 norm.

◆ L1Norm() [2/2]

double operations_research::pdlp::L1Norm	(	const VectorXd &	vector,
		const Sharder &	sharder )

Definition at line 243 of file sharder.cc.

◆ L2NormRescaling() [1/2]

void operations_research::pdlp::L2NormRescaling	(	const ShardedQuadraticProgram &	sharded_qp,
		Eigen::VectorXd &	row_scaling_vec,
		Eigen::VectorXd &	col_scaling_vec )

L2NormRescaling divides row_scaling_vec (col_scaling_vec) by the sqrt of the row (col) L2 norm of the current (scaled) constraint matrix. Unlike LInfRescaling, this function does only one iteration because the scaling procedure does not converge in general. This is not Ruiz rescaling for the L2 norm.

◆ L2NormRescaling() [2/2]

void operations_research::pdlp::L2NormRescaling	(	const ShardedQuadraticProgram &	sharded_qp,
		VectorXd &	row_scaling_vec,
		VectorXd &	col_scaling_vec )

Definition at line 416 of file sharded_optimization_utils.cc.

◆ LInfNorm() [1/2]

double operations_research::pdlp::LInfNorm	(	const Eigen::VectorXd &	vector,
		const Sharder &	sharder )

Like vector.lpNorm<Eigen::Infinity>(), a.k.a. LInf norm.

◆ LInfNorm() [2/2]

double operations_research::pdlp::LInfNorm	(	const VectorXd &	vector,
		const Sharder &	sharder )

Definition at line 235 of file sharder.cc.

◆ LInfRuizRescaling() [1/2]

void operations_research::pdlp::LInfRuizRescaling	(	const ShardedQuadraticProgram &	sharded_qp,
		const int	num_iterations,
		VectorXd &	row_scaling_vec,
		VectorXd &	col_scaling_vec )

Definition at line 409 of file sharded_optimization_utils.cc.

◆ LInfRuizRescaling() [2/2]

void operations_research::pdlp::LInfRuizRescaling	(	const ShardedQuadraticProgram &	sharded_qp,
		int	num_iterations,
		Eigen::VectorXd &	row_scaling_vec,
		Eigen::VectorXd &	col_scaling_vec )

LInfRuizRescaling and L2NormRescaling rescale the (scaled) constraint matrix of the LP by updating the scaling vectors in-place. More specifically, the (scaled) constraint matrix always has the format: diag(row_scaling_vec) / * sharded_qp.Qp().constraint_matrix * diag(col_scaling_vec), and row_scaling_vec and col_scaling_vec are updated in-place. On input, row_scaling_vec and col_scaling_vec provide the initial scaling. With each iteration of LInfRuizRescaling scaling, row_scaling_vec (col_scaling_vec) is divided by the sqrt of the row (col) LInf norm of the current (scaled) constraint matrix. The (scaled) constraint matrix approaches having all row and column LInf norms equal to 1 as the number of iterations goes to infinity. This convergence is fast (linear). More details of Ruiz rescaling algorithm can be found at: http://www.numerical.rl.ac.uk/reports/drRAL2001034.pdf.

◆ LpWithoutConstraints()

QuadraticProgram operations_research::pdlp::LpWithoutConstraints ( )

Definition at line 253 of file test_util.cc.

◆ Norm() [1/2]

double operations_research::pdlp::Norm	(	const Eigen::VectorXd &	vector,
		const Sharder &	sharder )

Like vector.norm().

◆ Norm() [2/2]

double operations_research::pdlp::Norm	(	const VectorXd &	vector,
		const Sharder &	sharder )

Definition at line 253 of file sharder.cc.

◆ NormOfDeltaProjection()

template<typename DiagonalTrustRegionProblem >

double operations_research::pdlp::NormOfDeltaProjection	(	const DiagonalTrustRegionProblem &	problem,
		const Sharder &	sharder,
		const double	scaling_factor )

Computes the norm of the projection of the difference vector, x - center_point, to the corresponding box constraints. We are using the standard Euclidean norm (instead of the weighted norm) because the solver implicitly reformulates the problem to one with a Euclidean ball constraint first.

Definition at line 636 of file trust_region.cc.

◆ ObjectiveGapMet()

bool operations_research::pdlp::ObjectiveGapMet	(	const TerminationCriteria::DetailedOptimalityCriteria &	optimality_criteria,
		const ConvergenceInformation &	stats )

Definition at line 26 of file termination.cc.

◆ OnesVector()

Eigen::VectorXd operations_research::pdlp::OnesVector ( const Sharder & sharder )

Like VectorXd::Ones(sharder.NumElements()).

Definition at line 190 of file sharder.cc.

◆ OptimalityCriteriaMet()

bool operations_research::pdlp::OptimalityCriteriaMet	(	const TerminationCriteria::DetailedOptimalityCriteria &	optimality_criteria,
		const ConvergenceInformation &	stats,
		const OptimalityNorm	optimality_norm,
		const QuadraticProgramBoundNorms &	bound_norms )

Determines if the optimality criteria are met.

Definition at line 43 of file termination.cc.

◆ PrimalDualHybridGradient() [1/4]

SolverResult operations_research::pdlp::PrimalDualHybridGradient	(	QuadraticProgram	qp,
		const PrimalDualHybridGradientParams &	params,
		const std::atomic< bool > *	interrupt_solve,
		std::function< void(const std::string &)>	message_callback,
		IterationStatsCallback	iteration_stats_callback )

Definition at line 2911 of file primal_dual_hybrid_gradient.cc.

◆ PrimalDualHybridGradient() [2/4]

SolverResult operations_research::pdlp::PrimalDualHybridGradient	(	QuadraticProgram	qp,
		const PrimalDualHybridGradientParams &	params,
		const std::atomic< bool > *	interrupt_solve = nullptr,
		std::function< void(const std::string &)>	message_callback = nullptr,
		std::function< void(const IterationCallbackInfo &)>	iteration_stats_callback = nullptr )

Solves the given QP using PDLP (Primal-Dual hybrid gradient enhanced for LP).

All operations that are repeated each iteration are executed in parallel using params.num_threads() threads.

The algorithm generally follows the description in https://arxiv.org/pdf/2106.04756.pdf, with further enhancements for QP. Notation here and in the implementation follows Chambolle and Pock, "On the ergodic convergence rates of a first-order primal-dual algorithm" (http://www.optimization-online.org/DB_FILE/2014/09/4532.pdf). That paper doesn't explicitly use the terminology "primal-dual hybrid gradient" but their Theorem 1 is analyzing PDHG. See https://developers.google.com/optimization/lp/pdlp_math#saddle-point_formulation for the saddle-point formulation of the QP we use that is compatible with Chambolle and Pock.

We use 0.5 ||.||^2 for both the primal and dual distance functions.

We parameterize the primal and dual step sizes (tau and sigma in Chambolle and Pock) as: primal_stepsize = step_size / primal_weight dual_stepsize = step_size * primal_weight where step_size and primal_weight are parameters. params.linesearch_rule determines the update rule for step_size. params.initial_primal_weight specifies how primal_weight is initialized and params.primal_weight_update_smoothing controls how primal_weight is updated.

If interrupt_solve is not nullptr, then the solver will periodically check if interrupt_solve->load() is true, in which case the solve will terminate with TERMINATION_REASON_INTERRUPTED_BY_USER.

If message_callback is not nullptr, solver logging will be passed to message_callback. Otherwise solver logging will be written to stdout. In either case, the amount of logging is controlled by verbosity_level. In particular, if verbosity_level == 0, there will be no logging in either case.

If iteration_stats_callback is not nullptr, then at each termination step (when iteration stats are logged), iteration_stats_callback will also be called with those iteration stats.

Callers MUST check solve_log.termination_reason before using the vectors in the SolverResult. See the comment on SolverResult for interpreting the termination reason.

All objective values reported by the algorithm are transformed by using QuadraticProgram::ApplyObjectiveScalingAndOffset.

Note: qp is intentionally passed by value, because PrimalDualHybridGradient modifies its copy.

◆ PrimalDualHybridGradient() [3/4]

SolverResult operations_research::pdlp::PrimalDualHybridGradient	(	QuadraticProgram	qp,
		const PrimalDualHybridGradientParams &	params,
		std::optional< PrimalAndDualSolution >	initial_solution,
		const std::atomic< bool > *	interrupt_solve,
		std::function< void(const std::string &)>	message_callback,
		IterationStatsCallback	iteration_stats_callback )

Definition at line 2921 of file primal_dual_hybrid_gradient.cc.

◆ PrimalDualHybridGradient() [4/4]

SolverResult operations_research::pdlp::PrimalDualHybridGradient	(	QuadraticProgram	qp,
		const PrimalDualHybridGradientParams &	params,
		std::optional< PrimalAndDualSolution >	initial_solution,
		const std::atomic< bool > *	interrupt_solve = nullptr,
		std::function< void(const std::string &)>	message_callback = nullptr,
		std::function< void(const IterationCallbackInfo &)>	iteration_stats_callback = nullptr )

Like above but optionally starts with the given initial_solution. If no initial_solution is given the zero vector is used. In either case initial_solution is projected onto the primal and dual variable bounds before use. Convergence should be faster if initial_solution is close to an optimal solution. NOTE: initial_solution is intentionally passed by value.

◆ ProjectedValueOfScaledDifference()

template<typename DiagonalTrustRegionProblem >

double operations_research::pdlp::ProjectedValueOfScaledDifference	(	const DiagonalTrustRegionProblem &	problem,
		const int64_t	index,
		const double	scaling_factor )

Computes a single coordinate projection of the scaled difference, sqrt(NormWeight(i)) * (x[i] - CenterPoint(i)), to the corresponding box constraints. As a function of scaling_factor, the difference is equal to (Q[i, i] / NormWeight(i)) + scaling_factor)^{-1} * (-c[i] / sqrt(NormWeight(i))), where Q, c are the objective matrix and vector, respectively.

Definition at line 616 of file trust_region.cc.

◆ ProjectToDualVariableBounds() [1/2]

void operations_research::pdlp::ProjectToDualVariableBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		Eigen::VectorXd &	dual )

Projects dual onto the dual variable bounds; see https://developers.google.com/optimization/lp/pdlp_math#dual_variable_bounds.

◆ ProjectToDualVariableBounds() [2/2]

void operations_research::pdlp::ProjectToDualVariableBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		VectorXd &	dual )

Todo: (user): Investigate whether it is more efficient to use .cwiseMax() + .cwiseMin() with unaryExpr(s) that map upper_bound_shard and lower_bound_shard to appropriate values.

Definition at line 749 of file sharded_optimization_utils.cc.

◆ ProjectToPrimalVariableBounds() [1/2]

void operations_research::pdlp::ProjectToPrimalVariableBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		Eigen::VectorXd &	primal,
		bool	use_feasibility_bounds = false )

Projects primal onto the variable bounds constraints. If use_feasibility_bounds == true, all finite variable bounds are replaced by zero.

◆ ProjectToPrimalVariableBounds() [2/2]

void operations_research::pdlp::ProjectToPrimalVariableBounds	(	const ShardedQuadraticProgram &	sharded_qp,
		VectorXd &	primal,
		const bool	use_feasibility_bounds )

Definition at line 725 of file sharded_optimization_utils.cc.

◆ QpFromMpModelProto()

absl::StatusOr< QuadraticProgram > operations_research::pdlp::QpFromMpModelProto	(	const MPModelProto &	proto,
		bool	relax_integer_variables,
		bool	include_names = false )

Converts an MPModelProto into a QuadraticProgram. Returns an error if general constraints are present. If relax_integer_variables is true integer variables are relaxed to continuous; otherwise integer variables are an error. If include_names is true (the default is false), the problem, constraint, and variable names are included in the QuadraticProgram; otherwise they are left empty. Maximization problems are converted to minimization by negating the objective and setting objective_scaling_factor to -1, which preserves the reported objective values.

To reduce peak RAM usage we construct the constraint matrix in-place. According to the documentation of SparseMatrix::insert() it's efficient to construct a matrix with insert()s as long as reserve() is called first and the non-zeros are inserted in increasing order of inner index. The non-zeros in each input constraint may not be sorted so this is only efficient with column major format.

We use triplets-based initialization for the objective matrix because the objective non-zeros may be in arbitrary order in the input.

Note: QuadraticProgram has an implicit "1/2" in front of the quadratic term.

Definition at line 99 of file quadratic_program.cc.

◆ QpToMpModelProto()

absl::StatusOr< MPModelProto > operations_research::pdlp::QpToMpModelProto ( const QuadraticProgram & qp )

Converts a QuadraticProgram into an MPModelProto. To preserve objective values in the conversion, objective_vector, objective_matrix, and objective_offset are scaled by objective_scaling_factor, and if objective_scaling_factor is negative, then the proto is a maximization problem (otherwise it's a minimization problem). Returns InvalidArgumentError if objective_scaling_factor is zero or if CanFitInMpModelProto() fails.

To avoid reallocs during the inserts, we could count the nonzeros and reserve() before filling.

Some OR tools decide the objective is quadratic based on has_quadratic_objective() rather than on quadratic_objective_size() == 0, so don't create the quadratic objective for linear programs.

Undo the implicit (1/2) term in QuadraticProgram's objective.

Definition at line 242 of file quadratic_program.cc.

◆ ReadMPModelProtoFileOrDie()

QuadraticProgram operations_research::pdlp::ReadMPModelProtoFileOrDie	(	const std::string &	mpmodel_proto_file,
		bool	include_names = false )

The input may be MPModelProto in text format, binary format, or JSON, possibly gzipped.

Definition at line 69 of file quadratic_program_io.cc.

◆ ReadMpsLinearProgram()

absl::StatusOr< QuadraticProgram > operations_research::pdlp::ReadMpsLinearProgram	(	const std::string &	lp_file,
		bool	include_names )

Collect MPS format, sizes and names.

Populate the QP with pre-allocated sizes.

Definition at line 364 of file quadratic_program_io.cc.

◆ ReadMpsLinearProgramOrDie()

QuadraticProgram operations_research::pdlp::ReadMpsLinearProgramOrDie	(	const std::string &	lp_file,
		bool	include_names )

Definition at line 399 of file quadratic_program_io.cc.

◆ ReadQuadraticProgramOrDie()

QuadraticProgram operations_research::pdlp::ReadQuadraticProgramOrDie	(	const std::string &	filename,
		bool	include_names )

Todo: (user): Update internal helper functions to use references instead of pointers.

Reads a quadratic program, determining the type based on the filename's suffix: *.mps, *.mps.gz, *.mps.bz2 -> ReadMpsLinearProgramOrDie *.pb, *.textproto, *.json, *.json.gz -> ReadMPModelProtoFileOrDie otherwise CHECK-fails.

Definition at line 52 of file quadratic_program_io.cc.

◆ ReducedCosts() [1/2]

Eigen::VectorXd operations_research::pdlp::ReducedCosts	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	scaled_sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_solution,
		bool	use_zero_primal_objective = false )

Computes the reduced costs vector, objective_matrix * primal_solution + objective_vector - constraint_matrix * dual_solution, when use_zero_primal_objective is false, and -constraint_matrix * dual_solution when use_zero_primal_objective is true. See https://developers.google.com/optimization/lp/pdlp_math#reduced_costs_dual_residuals_and_the_corrected_dual_objective.

◆ ReducedCosts() [2/2]

VectorXd operations_research::pdlp::ReducedCosts	(	const PrimalDualHybridGradientParams &	params,
		const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	primal_solution,
		const VectorXd &	dual_solution,
		bool	use_zero_primal_objective )

Definition at line 579 of file iteration_stats.cc.

◆ ScaledColL2Norm() [1/2]

Eigen::VectorXd operations_research::pdlp::ScaledColL2Norm	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const Eigen::VectorXd &	row_scaling_vec,
		const Eigen::VectorXd &	col_scaling_vec,
		const Sharder &	sharder )

Computes the L2 norm of each column of a scaled matrix.

◆ ScaledColL2Norm() [2/2]

VectorXd operations_research::pdlp::ScaledColL2Norm	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const VectorXd &	row_scaling_vec,
		const VectorXd &	col_scaling_vec,
		const Sharder &	sharder )

Definition at line 313 of file sharder.cc.

◆ ScaledColLInfNorm() [1/2]

Eigen::VectorXd operations_research::pdlp::ScaledColLInfNorm	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const Eigen::VectorXd &	row_scaling_vec,
		const Eigen::VectorXd &	col_scaling_vec,
		const Sharder &	sharder )

Computes the LInf norm of each column of a scaled matrix.

The functions below compute norms of the columns of a scaled matrix. The (i,j) entry of the scaled matrix equals matrix[i,j] * row_scaling_vec[i] / * col_scaling_vec[j]. To ensure good parallelization matrix should have (roughly) the same location of non-zeros as the matrix used to construct sharder. The size of sharder must match the number of columns in matrix.

◆ ScaledColLInfNorm() [2/2]

VectorXd operations_research::pdlp::ScaledColLInfNorm	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const VectorXd &	row_scaling_vec,
		const VectorXd &	col_scaling_vec,
		const Sharder &	sharder )

Definition at line 291 of file sharder.cc.

◆ ScaledLInfNorm() [1/2]

double operations_research::pdlp::ScaledLInfNorm	(	const Eigen::VectorXd &	vector,
		const Eigen::VectorXd &	scale,
		const Sharder &	sharder )

ScaledL1Norm is omitted because it's not needed (yet).

LInf norm of a rescaled vector, i.e., vector.cwiseProduct(scale).lpNorm<Eigen::Infinity>().

◆ ScaledLInfNorm() [2/2]

double operations_research::pdlp::ScaledLInfNorm	(	const VectorXd &	vector,
		const VectorXd &	scale,
		const Sharder &	sharder )

Definition at line 269 of file sharder.cc.

◆ ScaledNorm() [1/2]

double operations_research::pdlp::ScaledNorm	(	const Eigen::VectorXd &	vector,
		const Eigen::VectorXd &	scale,
		const Sharder &	sharder )

L2 norm of a rescaled vector, i.e., vector.cwiseProduct(scale).norm().

◆ ScaledNorm() [2/2]

double operations_research::pdlp::ScaledNorm	(	const VectorXd &	vector,
		const VectorXd &	scale,
		const Sharder &	sharder )

Definition at line 286 of file sharder.cc.

◆ ScaledSquaredNorm() [1/2]

double operations_research::pdlp::ScaledSquaredNorm	(	const Eigen::VectorXd &	vector,
		const Eigen::VectorXd &	scale,
		const Sharder &	sharder )

Squared L2 norm of a rescaled vector, i.e., vector.cwiseProduct(scale).squaredNorm().

◆ ScaledSquaredNorm() [2/2]

double operations_research::pdlp::ScaledSquaredNorm	(	const VectorXd &	vector,
		const VectorXd &	scale,
		const Sharder &	sharder )

Definition at line 279 of file sharder.cc.

◆ SetEigenMatrixFromTriplets()

void operations_research::pdlp::SetEigenMatrixFromTriplets	(	std::vector< Eigen::Triplet< double, int64_t > >	triplets,
		Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix )

Like matrix.setFromTriplets(triplets), except that setFromTriplets results in having three copies of the nonzeros in memory at the same time, because it first fills one matrix from triplets, and then transposes it into another. This avoids having the third copy in memory by sorting the triplets, reserving space in the matrix, and then inserting in sorted order. Compresses the matrix (SparseMatrix.makeCompressed()) after loading it.

Note: This intentionally passes triplets by value, because it modifies them. To avoid the copy, pass a move reference.

The triplets are allowed to contain duplicate entries (and intentionally do for the diagonals of the objective matrix). For efficiency of insert and reserve, merge the duplicates first.

Note: reserve() takes column counts because matrix is in column major order.

Definition at line 431 of file quadratic_program.cc.

◆ SetRandomProjections()

void operations_research::pdlp::SetRandomProjections	(	const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_solution,
		const std::vector< int > &	random_projection_seeds,
		PointMetadata &	metadata )

For each entry in random_projection_seeds, computes a random projection of the primal/dual solution pair onto pseudo-random vectors generated from that seed and adds the results to random_primal_projections/random_dual_projections in metadata.

Definition at line 626 of file iteration_stats.cc.

◆ SetZero() [1/2]

void operations_research::pdlp::SetZero	(	const Sharder &	sharder,
		Eigen::VectorXd &	dest )

The following functions use sharder to compute a vector operation in parallel. sharder should have the same size as the vector(s). For best performance sharder should have been created with the Sharder(int64_t, / int, ThreadPool*) constructor. Like dest.setZero(sharder.NumElements()). Note that if dest.size() != / sharder.NumElements(), dest will be resized.

◆ SetZero() [2/2]

void operations_research::pdlp::SetZero	(	const Sharder &	sharder,
		VectorXd &	dest )

Definition at line 178 of file sharder.cc.

◆ SmallDualInfeasibleLp()

QuadraticProgram operations_research::pdlp::SmallDualInfeasibleLp ( )

Definition at line 224 of file test_util.cc.

◆ SmallInconsistentVariableBoundsLp()

QuadraticProgram operations_research::pdlp::SmallInconsistentVariableBoundsLp ( )

Definition at line 195 of file test_util.cc.

◆ SmallInitializationLp()

QuadraticProgram operations_research::pdlp::SmallInitializationLp ( )

Definition at line 237 of file test_util.cc.

◆ SmallInvalidProblemLp()

QuadraticProgram operations_research::pdlp::SmallInvalidProblemLp ( )

Definition at line 182 of file test_util.cc.

◆ SmallPrimalDualInfeasibleLp()

QuadraticProgram operations_research::pdlp::SmallPrimalDualInfeasibleLp ( )

Definition at line 231 of file test_util.cc.

◆ SmallPrimalInfeasibleLp()

QuadraticProgram operations_research::pdlp::SmallPrimalInfeasibleLp ( )

Definition at line 208 of file test_util.cc.

◆ SolveDiagonalQpTrustRegion() [1/2]

TrustRegionResult operations_research::pdlp::SolveDiagonalQpTrustRegion	(	const ShardedQuadraticProgram &	sharded_qp,
		const Eigen::VectorXd &	primal_solution,
		const Eigen::VectorXd &	dual_solution,
		const Eigen::VectorXd &	primal_gradient,
		const Eigen::VectorXd &	dual_gradient,
		const double	primal_weight,
		double	target_radius,
		double	solve_tolerance )

Like SolveDiagonalTrustRegion, but extracts the problem data from a ShardedQuadraticProgram and implicitly concatenates the primal and dual parts before solving the trust-region subproblem.

◆ SolveDiagonalQpTrustRegion() [2/2]

TrustRegionResult operations_research::pdlp::SolveDiagonalQpTrustRegion	(	const ShardedQuadraticProgram &	sharded_qp,
		const VectorXd &	primal_solution,
		const VectorXd &	dual_solution,
		const VectorXd &	primal_gradient,
		const VectorXd &	dual_gradient,
		const double	primal_weight,
		double	target_radius,
		const double	solve_tolerance )

Definition at line 768 of file trust_region.cc.

◆ SolveDiagonalTrustRegion() [1/2]

TrustRegionResult operations_research::pdlp::SolveDiagonalTrustRegion	(	const Eigen::VectorXd &	objective_vector,
		const Eigen::VectorXd &	objective_matrix_diagonal,
		const Eigen::VectorXd &	variable_lower_bounds,
		const Eigen::VectorXd &	variable_upper_bounds,
		const Eigen::VectorXd &	center_point,
		const Eigen::VectorXd &	norm_weights,
		double	target_radius,
		const Sharder &	sharder,
		double	solve_tolerance )

Solves the following trust-region problem with bound constraints: min_x (1/2) * (x - center_point)^T * Q * (x - center_point)

objective_vector^T * (x - center_point) s.t. variable_lower_bounds <= x <= variable_upper_bounds || x - center_point ||_W <= target_radius where |y|_W = sqrt(sum_i norm_weights[i] * y[i]^2). It replaces the ball constraint || x - center_point ||_W <= target_radius with the equivalent constraint 0.5 * || x - center_point ||_W^2 <= 0.5 * target_radius^2 and does a binary search for a Lagrange multiplier for the latter constraint that is at most (solve_tolerance * max(1, lambda*)) away from the optimum Lagrange multiplier lambda*. sharder should have the same size as the number of variables in the problem. Assumes that there is always a feasible solution, that is, that variable_lower_bounds <= center_point <= variable_upper_bounds, and that norm_weights > 0, for 0 <= i < sharder.NumElements().

◆ SolveDiagonalTrustRegion() [2/2]

TrustRegionResult operations_research::pdlp::SolveDiagonalTrustRegion	(	const VectorXd &	objective_vector,
		const VectorXd &	objective_matrix_diagonal,
		const VectorXd &	variable_lower_bounds,
		const VectorXd &	variable_upper_bounds,
		const VectorXd &	center_point,
		const VectorXd &	norm_weights,
		const double	target_radius,
		const Sharder &	sharder,
		const double	solve_tolerance )

Definition at line 755 of file trust_region.cc.

◆ SolveDiagonalTrustRegionProblem()

template<typename DiagonalTrustRegionProblem >

TrustRegionResult operations_research::pdlp::SolveDiagonalTrustRegionProblem	(	const DiagonalTrustRegionProblem &	problem,
		const Sharder &	sharder,
		const double	target_radius,
		const double	solve_tol )

Solves the diagonal trust region problem using a binary search algorithm. See comment above SolveDiagonalTrustRegion() in trust_region.h for the meaning of solve_tol.

Definition at line 694 of file trust_region.cc.

◆ SolveTrustRegion() [1/2]

TrustRegionResult operations_research::pdlp::SolveTrustRegion	(	const Eigen::VectorXd &	objective_vector,
		const Eigen::VectorXd &	variable_lower_bounds,
		const Eigen::VectorXd &	variable_upper_bounds,
		const Eigen::VectorXd &	center_point,
		const Eigen::VectorXd &	norm_weights,
		double	target_radius,
		const Sharder &	sharder )

Solves the following trust-region problem with bound constraints: min_x objective_vector^T * (x - center_point) s.t. variable_lower_bounds <= x <= variable_upper_bounds || x - center_point ||_W <= target_radius where |y|_W = sqrt(sum_i norm_weights[i] * y[i]^2) using an exact linear-time method. sharder should have the same size as the number of variables in the problem. Assumes that there is always a feasible solution, that is, that variable_lower_bounds <= center_point <= variable_upper_bounds, and that norm_weights > 0, for 0 <= i < sharder.NumElements().

◆ SolveTrustRegion() [2/2]

TrustRegionResult operations_research::pdlp::SolveTrustRegion	(	const VectorXd &	objective_vector,
		const VectorXd &	variable_lower_bounds,
		const VectorXd &	variable_upper_bounds,
		const VectorXd &	center_point,
		const VectorXd &	norm_weights,
		const double	target_radius,
		const Sharder &	sharder )

Definition at line 453 of file trust_region.cc.

◆ SquaredDistance() [1/2]

double operations_research::pdlp::SquaredDistance	(	const Eigen::VectorXd &	vector1,
		const Eigen::VectorXd &	vector2,
		const Sharder &	sharder )

Like (vector1 - vector2).squaredNorm().

◆ SquaredDistance() [2/2]

double operations_research::pdlp::SquaredDistance	(	const VectorXd &	vector1,
		const VectorXd &	vector2,
		const Sharder &	sharder )

Definition at line 257 of file sharder.cc.

◆ SquaredNorm() [1/2]

double operations_research::pdlp::SquaredNorm	(	const Eigen::VectorXd &	vector,
		const Sharder &	sharder )

Like vector.squaredNorm().

◆ SquaredNorm() [2/2]

double operations_research::pdlp::SquaredNorm	(	const VectorXd &	vector,
		const Sharder &	sharder )

Definition at line 248 of file sharder.cc.

◆ T()

dual_gradient operations_research::pdlp::T ( y - `dual_solution` )

DiagonalTrustRegionProblemFromQp accepts a diagonal quadratic program and information about the current solution and gradient and sets up the following trust-region subproblem: min_{x, y} (x - primal_solution)^T Q (x - primal_solution)

primal_gradient^T (x - primal_solution) s.t. l <= x - primal_solution <= u l_implicit <= y - dual_solution <= u_implicit ||(x, y) - (primal_solution, dual_solution)||_W <= r, where ||(x, y)||_W = sqrt(0.5 * primal_weight |x|^2 + (0.5 / primal_weight) |y|^2). This class implements the same methods as DiagonalTrustRegionProblem, but without the need to explicitly copy vectors.

A reference to the objects passed in the constructor is kept, so they must outlive the DiagonalTrustRegionProblemFromQp instance.

Definition at line 529 of file trust_region.cc.

◆ TestDiagonalQp1()

QuadraticProgram operations_research::pdlp::TestDiagonalQp1 ( )

Definition at line 131 of file test_util.cc.

◆ TestDiagonalQp2()

QuadraticProgram operations_research::pdlp::TestDiagonalQp2 ( )

Definition at line 148 of file test_util.cc.

◆ TestDiagonalQp3()

QuadraticProgram operations_research::pdlp::TestDiagonalQp3 ( )

Definition at line 165 of file test_util.cc.

◆ TestLp()

QuadraticProgram operations_research::pdlp::TestLp ( )

Definition at line 35 of file test_util.cc.

◆ TinyLp()

QuadraticProgram operations_research::pdlp::TinyLp ( )

Returns a "tiny" test LP. min 5 x_1 + 2 x_2 + x_3 + x_4 - 14 s.t. 2 x_1 + x_2 + x_3 + 2 x_4 = 12 x_1 + x_3 >= 7 x_3 - x_4 >= 1 0 <= x_1 <= 2 0 <= x_2 <= 4 0 <= x_3 <= 6 0 <= x_4 <= 3

Optimum solutions: Primal: x_1 = 1, x_2 = 0, x_3 = 6, x_4 = 2. Value: 5 + 0 + 6 + 2 - 14 = -1. Dual: [0.5, 4.0, 0.0] Value: 6 + 28 - 3.5*6 - 14 = -1 Reduced costs: [0.0, 1.5, -3.5, 0.0]

Definition at line 69 of file test_util.cc.

◆ ToDense()

::Eigen::ArrayXXd operations_research::pdlp::ToDense ( const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > & sparse_mat )

Definition at line 276 of file test_util.cc.

◆ ToString()

std::string operations_research::pdlp::ToString	(	const QuadraticProgram &	qp,
		int64_t	max_size = 1 '000 '000 )

Returns a "pretty" version of qp, truncating to at most max_size characters. This is for debugging purposes only - the format may change without notice. Although this output is vaguely similar to "LP format", it is not actually compatible with "LP format".

Closes the objective matrix expression.

Closes the objective scaling factor expression.

Definition at line 322 of file quadratic_program.cc.

◆ TransposedMatrixVectorProduct() [1/2]

Eigen::VectorXd operations_research::pdlp::TransposedMatrixVectorProduct	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const Eigen::VectorXd &	vector,
		const Sharder &	sharder )

Like matrix.transpose() * vector but executed in parallel using sharder. The size of sharder must match the number of columns in matrix. To ensure good parallelization matrix should have (roughly) the same location of non-zeros as the matrix used when constructing sharder.

◆ TransposedMatrixVectorProduct() [2/2]

VectorXd operations_research::pdlp::TransposedMatrixVectorProduct	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		const VectorXd &	vector,
		const Sharder &	sharder )

Note: For very sparse columns, assignment to shard(answer) incurs a measurable overhead compared to using a constructor (i.e. VectorXd temp = ...). It is not clear why this is the case, nor how to avoid it.

Definition at line 163 of file sharder.cc.

◆ ValidateAdaptiveLinesearchParams()

absl::Status operations_research::pdlp::ValidateAdaptiveLinesearchParams ( const AdaptiveLinesearchParams & params )

Returns InvalidArgumentError if the proto contains invalid values. Returns OkStatus otherwise.

Definition at line 120 of file solvers_proto_validation.cc.

◆ ValidateMalitskyPockParams()

absl::Status operations_research::pdlp::ValidateMalitskyPockParams ( const MalitskyPockParams & params )

Returns InvalidArgumentError if the proto contains invalid values. Returns OkStatus otherwise.

Definition at line 141 of file solvers_proto_validation.cc.

◆ ValidatePrimalDualHybridGradientParams()

absl::Status operations_research::pdlp::ValidatePrimalDualHybridGradientParams ( const PrimalDualHybridGradientParams & params )

Returns InvalidArgumentError if the proto contains invalid values. Returns OkStatus otherwise.

Definition at line 171 of file solvers_proto_validation.cc.

◆ ValidateQuadraticProgramDimensions()

absl::Status operations_research::pdlp::ValidateQuadraticProgramDimensions ( const QuadraticProgram & qp )

Returns InvalidArgumentError if vector or matrix dimensions are inconsistent. Returns OkStatus otherwise.

Definition at line 38 of file quadratic_program.cc.

◆ ValidateTerminationCriteria()

absl::Status operations_research::pdlp::ValidateTerminationCriteria ( const TerminationCriteria & criteria )

Returns InvalidArgumentError if the proto contains invalid values. Returns OkStatus otherwise.

Definition at line 45 of file solvers_proto_validation.cc.

◆ VerifyTestDiagonalQp1()

void operations_research::pdlp::VerifyTestDiagonalQp1	(	const QuadraticProgram &	qp,
		bool	maximize )

Definition at line 261 of file test_util.cc.

◆ VerifyTestLp()

void operations_research::pdlp::VerifyTestLp	(	const QuadraticProgram &	qp,
		bool	maximize )

Verifies that the given QuadraticProgram equals TestLp().

Definition at line 51 of file test_util.cc.

◆ WriteLinearProgramToMps()

absl::Status operations_research::pdlp::WriteLinearProgramToMps	(	const QuadraticProgram &	linear_program,
		const std::string &	mps_file )

Note: This will fail if linear_program is actually a quadratic program (that is, has a non-empty quadratic objective term).

Definition at line 80 of file quadratic_program_io.cc.

◆ WriteQuadraticProgramToMPModelProto()

absl::Status operations_research::pdlp::WriteQuadraticProgramToMPModelProto	(	const QuadraticProgram &	quadratic_program,
		const std::string &	mpmodel_proto_file )

Definition at line 95 of file quadratic_program_io.cc.

◆ ZeroVector()

Eigen::VectorXd operations_research::pdlp::ZeroVector ( const Sharder & sharder )

Like VectorXd::Zero(sharder.NumElements()).

Definition at line 184 of file sharder.cc.

Variable Documentation

◆ kHugeDouble

const double operations_research::pdlp::kHugeDouble = 1.0e50

Definition at line 32 of file solvers_proto_validation.cc.

◆ kInfinity

double operations_research::pdlp::kInfinity = std::numeric_limits<double>::infinity()

constexpr

Definition at line 37 of file sharded_optimization_utils.cc.

◆ kTinyDouble

const double operations_research::pdlp::kTinyDouble = 1.0e-50

Definition at line 31 of file solvers_proto_validation.cc.

◆ primal_solution

* x operations_research::pdlp::primal_solution

Recall the saddle-point formulation OPT = min_x max_y L(x, y) defined at https://developers.google.com/optimization/lp/pdlp_math#saddle-point_formulation. This function computes lower and upper bounds on OPT with an additional ball or "trust-region" constraint on the domains of x and y.

The bounds are derived from the solution of the following problem: min_{x,y} ∇_x L(primal_solution, dual_solution)^T (x - primal_solution)

∇_y L(primal_solution, dual_solution)^T (y - dual_solution) subject to ||(x - primal_solution, y - dual_solution)||_PD <= radius, where x and y are constrained to their respective bounds and ||(x,y)||_PD is defined by primal_dual_norm. When use_diagonal_qp_trust_region_solver is true, the solver instead solves the following problem: min_{x,y} ∇_x L(primal_solution, dual_solution)^T (x - primal_solution)
∇_y L(primal_solution, dual_solution)^T (y - dual_solution)
(1 / 2) * (x - primal_solution)^T * objective_matrix

Definition at line 146 of file trust_region.h.

◆ x_3

x_0 x_1 x_2 operations_research::pdlp::x_3

Initial value:

= 12
 
 4 x_0                            >=  -4
 -1 <=            1.5 x_2 -   x_3  <= 1
 
 -2 <= x_1 <= infinity
 
 2.5 <= x_3 <= 3.5
 
QuadraticProgram TestLp()

Returns a small LP with all 4 patterns of which lower and upper bounds on the constraints are finite and similarly for the variables. min 5.5 x_0 - 2 x_1 - x_2 + x_3 - 14 s.t.

Definition at line 36 of file test_util.h.

Namespaces

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ IterationType

◆ PrimalDualNorm

Function Documentation

◆ AddScaledVector() [1/2]

◆ AddScaledVector() [2/2]

◆ ApplyRescaling()

◆ AssignVector() [1/2]

◆ AssignVector() [2/2]

◆ BoundGap()

◆ BoundNormsFromProblemStats()

◆ CanFitInMpModelProto()

◆ CheckIterateTerminationCriteria()

◆ CheckNonNegative()

◆ CheckSimpleTerminationCriteria()

◆ CloneVector() [1/2]

◆ CloneVector() [2/2]

◆ CoefficientWiseProductInPlace() [1/2]

◆ CoefficientWiseProductInPlace() [2/2]

◆ CoefficientWiseQuotientInPlace() [1/2]

◆ CoefficientWiseQuotientInPlace() [2/2]

◆ ComputeConvergenceInformation()

◆ ComputeDualGradient() [1/2]

◆ ComputeDualGradient() [2/2]

◆ ComputeInfeasibilityInformation()

◆ ComputeLocalizedLagrangianBounds() [1/2]

◆ ComputeLocalizedLagrangianBounds() [2/2]

◆ ComputePrimalGradient() [1/2]

◆ ComputePrimalGradient() [2/2]

◆ ComputeRelativeResiduals()

◆ ComputeScaledConvergenceInformation() [1/2]

◆ ComputeScaledConvergenceInformation() [2/2]

◆ ComputeStats()

◆ CorrelationClusteringLp()

◆ CorrelationClusteringStarLp()

◆ Distance() [1/2]

◆ Distance() [2/2]

◆ Dot() [1/2]

◆ Dot() [2/2]

◆ DualSubgradientCoefficient()

◆ EffectiveOptimalityCriteria() [1/2]

◆ EffectiveOptimalityCriteria() [2/2]

◆ EpsilonRatio()

◆ EstimateMaximumSingularValueOfConstraintMatrix() [1/2]

◆ EstimateMaximumSingularValueOfConstraintMatrix() [2/2]

◆ FindScalingFactor()

◆ GetConvergenceInformation()

◆ GetInfeasibilityInformation()

◆ GetPointMetadata()

◆ HasValidBounds()

◆ IsLinearProgram()

◆ L1Norm() [1/2]

◆ L1Norm() [2/2]

◆ L2NormRescaling() [1/2]

◆ L2NormRescaling() [2/2]

◆ LInfNorm() [1/2]

◆ LInfNorm() [2/2]

◆ LInfRuizRescaling() [1/2]

◆ LInfRuizRescaling() [2/2]

◆ LpWithoutConstraints()

◆ Norm() [1/2]

◆ Norm() [2/2]

◆ NormOfDeltaProjection()

◆ ObjectiveGapMet()

◆ OnesVector()

◆ OptimalityCriteriaMet()

◆ PrimalDualHybridGradient() [1/4]

◆ PrimalDualHybridGradient() [2/4]

◆ PrimalDualHybridGradient() [3/4]

◆ PrimalDualHybridGradient() [4/4]

◆ ProjectedValueOfScaledDifference()

◆ ProjectToDualVariableBounds() [1/2]

◆ ProjectToDualVariableBounds() [2/2]

◆ ProjectToPrimalVariableBounds() [1/2]