\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.9 - Linear and Quadratic Programming Solver
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Quadratic_program_solution< ET > Class Template Reference

#include <CGAL/QP_solution.h>

Definition

An object of class Quadratic_program_solution represents the solution of a linear or convex quadratic program of the general form.

\( \newcommand{\qprel}{\gtreqless} \newcommand{\qpx}{\mathbf{x}} \newcommand{\qpl}{\mathbf{l}} \newcommand{\qpu}{\mathbf{u}} \newcommand{\qpc}{\mathbf{c}} \newcommand{\qpb}{\mathbf{b}} \newcommand{\qpy}{\mathbf{y}} \newcommand{\qpw}{\mathbf{w}} \newcommand{\qplambda}{\mathbf{\lambda}} \)

\begin{eqnarray*} \mbox{(QP)}& \mbox{minimize} & \qpx^{T}D\qpx+\qpc^{T}\qpx+c_0 \\ &\mbox{subject to} & A\qpx\qprel \qpb, \\ & & \qpl \leq \qpx \leq \qpu \end{eqnarray*}

in \( n\) real variables \( \qpx=(x_0,\ldots,x_{n-1})\).

If \( D=0\), the program is a linear program; if the variable bounds are \( \qpx\geq 0\), we have a nonnegative program. Objects of type Quadratic_program_solution are returned by any of the four functions solve_quadratic_program, solve_linear_program, solve_nonnegative_quadratic_program, and solve_nonnegative_linear_program.

Example

QP_solver/first_qp.cpp

Terminology

If there is no \( \qpx\) that satisfies all the (in)equalities, the program is called infeasible, otherwise, it is feasible, and any \( \qpx\) that satisfies all (in)equalities is called a feasible solution.

If the objective function value becomes arbitrarily small over the feasible region (the set of feasible solutions), the program is called unbounded, and bounded otherwise.

Any program that is both feasible and bounded has at least one feasible solution \( \qpx^*\) whose objective function value is not larger than that of any other feasible solution. This is called an optimal solution.

Every convex quadratic program (even if it is infeasible or unbounded) has a 'solution' in form of an object of the class Quadratic_program_solution.

The program concepts

See Also
QuadraticProgram
LinearProgram
NonnegativeQuadraticProgram
NonnegativeLinearProgram

and the functions that compute objects of class Quadratic_program_solution from models of these concepts:

See Also
solve_quadratic_program
solve_linear_program
solve_nonnegative_quadratic_program
solve_nonnegative_linear_program
Examples:
QP_solver/convex_hull_containment.cpp, QP_solver/convex_hull_containment2.cpp, QP_solver/cycling.cpp, QP_solver/first_lp.cpp, QP_solver/first_lp_from_iterators.cpp, QP_solver/first_lp_from_mps.cpp, QP_solver/first_nonnegative_lp.cpp, QP_solver/first_nonnegative_lp_from_iterators.cpp, QP_solver/first_nonnegative_lp_from_mps.cpp, QP_solver/first_nonnegative_qp.cpp, QP_solver/first_nonnegative_qp_from_iterators.cpp, QP_solver/first_nonnegative_qp_from_mps.cpp, QP_solver/first_qp.cpp, QP_solver/first_qp_basic_constraints.cpp, QP_solver/first_qp_from_iterators.cpp, QP_solver/first_qp_from_mps.cpp, QP_solver/important_variables.cpp, QP_solver/infeasibility_certificate.cpp, QP_solver/invert_matrix.cpp, QP_solver/optimality_certificate.cpp, QP_solver/solve_convex_hull_containment_lp.h, QP_solver/solve_convex_hull_containment_lp2.h, QP_solver/solve_convex_hull_containment_lp3.h, and QP_solver/unboundedness_certificate.cpp.

Types

typedef unspecified_type ET
 The exact number type that was used to solve the program.
 
typedef unspecified_type Variable_value_iterator
 An iterator type with value type Quotient<ET> to go over the values of the variables in the solution.
 
typedef unspecified_type Variable_numerator_iterator
 An iterator type with value type ET to go over the numerators of the variable values with respect to a common denominator.
 
typedef unspecified_type Index_iterator
 An iterator type with value type int to go over the indices of the basic variables and the basic constraints.
 
typedef unspecified_type Optimality_certificate_iterator
 An iterator type with value type Quotient<ET> to go over an \( m\)-vector \( \qplambda\) that proves optimality of the solution.
 
typedef unspecified_type Optimality_certificate_numerator_iterator
 An iterator type with value type ET to go over the numerators of the vector \( \qplambda\) with respect to a common denominator.
 
typedef unspecified_type Infeasibility_certificate_iterator
 An iterator type with value type ET to go over an \( m\)-vector \( \qplambda\) that proves infeasibility of the solution.
 
typedef unspecified_type Unboundedness_certificate_iterator
 An iterator type with value type ET to go over an \( n\)-vector \( \qpw\) that proves unboundedness of the solution.
 

Creation

Objects of type Quadratic_program_solution can be copied and assigned.

Objects of type Quadratic_program_solution that are associated to an actual program are returned by any of the four functions solve_quadratic_program, solve_linear_program, solve_nonnegative_quadratic_program, and solve_nonnegative_linear_program. Example: QP_solver/first_qp.cpp

 Quadratic_program_solution ()
 constructs a void instance of Quadratic_program_solution that is associated to no program.
 

Operations

bool is_void () const
 returns true iff sol is not associated to a program. More...
 

Solution status

Here are the access methods for the status of the solution.

bool is_optimal () const
 returns true iff sol is an optimal solution of the associated program.
 
bool is_infeasible () const
 returns true iff the associated program is infeasible.
 
bool is_unbounded () const
 returns true iff the associated program is unbounded.
 
Quadratic_program_status status () const
 returns the status of the solution; this is one of the values QP_OPTIMAL, QP_INFEASIBLE, and QP_UNBOUNDED, depending on whether the program asociated to sol has an optimal solution, is infeasible, or is unbounded.
 
int number_of_iterations () const
 returns the number of iterations that it took to solve the program asociated to sol.
 

Solution values

The actual solution (variable and objective function values) can be accessed as follows.

Quotient< ETobjective_value () const
 returns the objective function value of sol.
 
ET objective_value_numerator () const
 returns the numerator of the objective function value of sol.
 
ET objective_value_denominator () const
 returns the denominator of the objective function value of sol.
 
Variable_value_iterator variable_values_begin () const
 returns a random-access iterator over the values of the variables in sol. More...
 
Variable_value_iterator variable_values_end () const
 returns the corresponding past-the-end iterator.
 
Variable_numerator_iterator variable_numerators_begin () const
 returns a random-access iterator it over the values of the variables in sol, with respect to a common denominator of all variables. More...
 
Variable_numerator_iterator variable_numerators_end () const
 returns the corresponding past-the-end iterator.
 
const ETvariables_common_denominator () const
 returns the common denominator of the variable values as referred to by the previous two methods.
 

Basic variables and constraints

The solution of a linear or quadratic program distinguishes 'important' variables (the ones not attaining one of their bounds), and 'important' constraints (the ones being satisfied with equality).

The following methods grant access to them. QP_solver/important_variables.cpp QP_solver/first_qp_basic_constraints.cpp

Index_iterator basic_variable_indices_begin () const
 returns a random access iterator over the indices of the basic variables. More...
 
Index_iterator basic_variable_indices_end () const
 returns the corresponding past-the-end iterator.
 
int number_of_basic_variables () const
 returns the number of basic variables, equivalently the length of the range determined by the previous two iterators.
 
Index_iterator basic_constraint_indices_begin () const
 returns a random access iterator over the indices of the basic constraints in the system \( A\qpx\qprel\qpb\). More...
 
Index_iterator basic_constraint_indices_end () const
 returns the corresponding past-the-end iterator.
 
int number_of_basic_constraints () const
 returns the number of basic constraint, equivalently the length of the range determined by the previous two iterators.
 
template<typename ET >
std::ostream & operator<< (std::ostream &out, const Quadratic_program_solution< ET > &sol)
 writes the status of sol to the stream out. More...
 

Validity

The following four methods allow you to check whether sol indeed solves the program that you intended to solve.

The methods use the certificates described in the advanced section below and thus save you from validating the certificates yourself (if you believe in the correctness of these methods; otherwise, you can look at their implementation to convince yourself). By passing a suitable option to the solution function, you can make sure that this check is done automatically after the solution of the program, see Quadratic_program_options. If the check fails, a logfile is generated that contains the details, and an error message is written to std::cerr (see QP_solver/cycling.cpp for an example that uses this option). QP_solver/first_qp.cpp QP_solver/first_lp.cpp QP_solver/first_nonnegative_qp.cpp QP_solver/first_nonnegative_lp.cpp

template<class QuadraticProgram >
bool solves_quadratic_program (const QuadraticProgram &qp)
 returns true iff sol solves the quadratic program qp. More...
 
template<class LinearProgram >
bool solves_linear_program (const LinearProgram &lp)
 returns true iff sol solves the linear program lp. More...
 
template<class NonnegativeQuadraticProgram >
bool solves_nonnegative_quadratic_program (const NonnegativeQuadraticProgram &qp)
 returns true iff sol solves the nonnegative quadratic program qp. More...
 
template<class NonnegativeLinearProgram >
bool solves_nonnegative_linear_program (const NonnegativeLinearProgram &lp)
 returns true iff sol solves the nonnegative linear program lp. More...
 
bool is_valid () const
 returns false iff the validation through one of the previous four functions has failed.
 
const std::string & get_error () const
 returns an error message in case any of the previous four validation functions has returned false.
 

Certificates

A certificate is a vector that admits a simple proof for the correctness of the solution.

Any non-void object of Quadratic_program_solution comes with such a certificate.

Optimality_certificate_iterator optimality_certifcate_begin () const
 returns a random access iterator over the optimality certificate \( \qplambda\) as given in Lemma 1, with respect to the solution \( \qpx^*\) obtained from sol.variable_values_begin(). More...
 
Optimality_certificate_iterator optimality_certificate_end () const
 returns the corresponding past-the-end iterator. More...
 
Optimality_certificate_numerator_iterator optimality_certifcate_numerators_begin () const
 returns a random access iterator over the numerator values of the optimality certificate \( \qplambda\), with respect to the common denominator returned by sol. More...
 
Optimality_certificate_numerator_iterator optimality_certificate_numerators_end () const
 returns the corresponding past-the-end iterator. More...
 
Infeasibility_certificate_iterator infeasibility_certificate_begin () const
 returns a random access iterator over the infeasibility certificate \( \qplambda\) as given in Lemma 2. More...
 
Infeasibility_certificate_iterator infeasibility_certificate_end () const
 returns the corresponding past-the-end iterator. More...
 
Unboundedness_certificate_iterator unboundedness_certificate_begin () const
 returns a random acess iterator over the unbounded direction \( \qpw\) as given in Lemma 3,with respect to the solution \( \qpx^*\) obtained from sol.variable_values_begin(). More...
 
Unboundedness_certificate_iterator unboundedness_certificate_end ()
 returns the corresponding past-the-end iterator. More...
 

Member Function Documentation

template<typename ET>
Index_iterator CGAL::Quadratic_program_solution< ET >::basic_constraint_indices_begin ( ) const

returns a random access iterator over the indices of the basic constraints in the system \( A\qpx\qprel\qpb\).

The value type is int. It is guaranteed that any basic constraint is satisfied with equality. In particular, if the system is of type \( A\qpx=\qpb\), all constraints are basic.

template<typename ET>
Index_iterator CGAL::Quadratic_program_solution< ET >::basic_variable_indices_begin ( ) const

returns a random access iterator over the indices of the basic variables.

The value type is int. It is guaranteed that any variable that is not basic in sol attains one of its bounds. In particular, if the bounds are of type \( \qpx\geq0\), all non-basic variables have value \( 0\).

template<typename ET>
Infeasibility_certificate_iterator CGAL::Quadratic_program_solution< ET >::infeasibility_certificate_begin ( ) const

returns a random access iterator over the infeasibility certificate \( \qplambda\) as given in Lemma 2.

The value type is ET, and the valid iterator range has length \( m\).

Precondition
sol.is_infeasible().

Lemma 2 (infeasibility certificate): The program (QP) is infeasible if an \(m\)-vector \(\qplambda\) with the following properties exist.

  1. if the \(i\)-th constraint is of type \(\leq\) ( \(\geq\), respectively), then \(\lambda_i\geq 0\) ( \(\lambda_i\leq 0\), respectively).
  2. \[ \begin{array}{llll} &&\geq 0 & \mbox{if \f$u_j=\infty\f$} \\ \qplambda^T A_j &\quad \\ &&\leq 0 & \mbox{if \f$l_j=-\infty\f$.} \end{array} \]

  3. \[\qplambda^T\qpb \quad<\quad \ccSum{j: \qplambda^TA_j <0}{}{ \qplambda^TA_j u_j } \quad+\quad \ccSum{j: \qplambda^TA_j >0}{}{ \qplambda^TA_j l_j}.\]

Proof: Let us assume for the purpose of obtaining a contradiction that there is a feasible solution \(\qpx\). Then we get

\[ \begin{array}{lcll} 0 &\geq& \qplambda^T(A\qpx -\qpb) & \mbox{(by \f$A\qpx\qprel \qpb\f$ and 1.)} \\ &=& \ccSum{j: \qplambda^TA_j <0}{}{ \qplambda^TA_j x_j } \quad+\quad \ccSum{j: \qplambda^TA_j >0}{}{ \qplambda^TA_j x_j} - \qplambda^T \qpb \\ &\geq& \ccSum{j: \qplambda^TA_j <0}{}{ \qplambda^TA_j u_j } \quad+\quad \ccSum{j: \qplambda^TA_j >0}{}{ \qplambda^TA_j l_j} - \qplambda^T \qpb & \mbox{(by \f$\qpl\leq \qpx \leq \qpu\f$ and 2.)} \\ &>& 0 & \mbox{(by 3.)}, \end{array} \]

and this is the desired contradiction \(0>0\).

See Also
QP_solver/infeasibility_certificate.cpp
template<typename ET>
Infeasibility_certificate_iterator CGAL::Quadratic_program_solution< ET >::infeasibility_certificate_end ( ) const

returns the corresponding past-the-end iterator.

See Also
infeasibility_certificate_begin()
template<typename ET>
bool CGAL::Quadratic_program_solution< ET >::is_void ( ) const

returns true iff sol is not associated to a program.

The condition !sol.is_void() is a precondition for all access methods below.

template<typename ET>
Optimality_certificate_iterator CGAL::Quadratic_program_solution< ET >::optimality_certifcate_begin ( ) const

returns a random access iterator over the optimality certificate \( \qplambda\) as given in Lemma 1, with respect to the solution \( \qpx^*\) obtained from sol.variable_values_begin().

The value type is Quotient<ET>, and the valid iterator range has length \( m\).

Precondition
sol.is_optimal().

Lemma 1(optimality certificate): A feasible \( n\)-vector \(\qpx^*\) is an optimal solution of (QP) if an \( m\)-vector \( \qplambda\) with the following properties exist.

  1. if the \( i\)-th constraint is of type \( \leq\) ( \( \geq\), respectively), then \(\lambda_i\geq 0\) ( \(\lambda_i\leq 0\), respectively).
  2. \(\qplambda^T(A\qpx^*-\qpb) = 0\)
  3. \[ \begin{array}{llll} &&\geq 0, & \mbox{if $x^*_j = l_j < u_j$} \\ (\qpc^T + \qplambda^T A + 2{\qpx^*}^TD)_j& \quad &= 0, & \mbox{if $l_j < x^*_j < u_j$} \\ &&\leq 0, & \mbox{if $l_j < u_j = x^*_j$.} \end{array} \]

Proof: Let \(\qpx\) be any feasible solution. We need to prove that

\[\qpc^T\qpx + \qpx^TD\qpx \geq \qpc^T\qpx^* + {\qpx^*}^TD\qpx^*.\]

For this, we argue as follows.

\[ \begin{array}{lcll} \qpc^T\qpx + 2{\qpx^*}^TD\qpx &\geq& \qpc^T\qpx + 2{\qpx^*}^TD\qpx + \qplambda^T(A\qpx-\qpb) & \mbox{(by $A\qpx\qprel \qpb$ and 1.)} \\ &=& (\qpc^T + \qplambda^T A + 2{\qpx^*}^TD)\qpx - \qplambda^Tb \\ &\geq& (\qpc^T + \qplambda^T A + 2{\qpx^*}^TD)\qpx^* - \qplambda^Tb & \mbox{(by $\qpl\leq \qpx \leq \qpu$ and 3.)} \\ &=& \qpc^T\qpx^* + 2{\qpx^*}^TD\qpx^* & \mbox{(by 2.)} \end{array} \]

After adding \(\qpx^TD\qpx - \qpx^TD\qpx - {\qpx^*}^TD\qpx^* = -{\qpx^*}^TD\qpx^*\) to both sides of this inequality, we get

\[ \qpc^T\qpx + \qpx^TD\qpx - (\qpx-\qpx^*)^TD(\qpx-\qpx^*) \geq \qpc^T\qpx^* + {\qpx^*}^TD\qpx^*, \]

and since \(D\) is positive semidefinite, we have \((\qpx-\qpx^*)^TD(\qpx-\qpx^*)\geq 0\) and the lemma follows.

See Also
QP_solver/optimality_certificate.cpp
template<typename ET>
Optimality_certificate_numerator_iterator CGAL::Quadratic_program_solution< ET >::optimality_certifcate_numerators_begin ( ) const

returns a random access iterator over the numerator values of the optimality certificate \( \qplambda\), with respect to the common denominator returned by sol.

variables_common_denominator(). The value type is ET, and the valid iterator range has length \( m\).

See Also
optimality_certifcate_begin()
template<typename ET>
Optimality_certificate_iterator CGAL::Quadratic_program_solution< ET >::optimality_certificate_end ( ) const

returns the corresponding past-the-end iterator.

See Also
optimality_certifcate_begin()
template<typename ET>
Optimality_certificate_numerator_iterator CGAL::Quadratic_program_solution< ET >::optimality_certificate_numerators_end ( ) const

returns the corresponding past-the-end iterator.

See Also
optimality_certifcate_begin()
template<typename ET>
template<class LinearProgram >
bool CGAL::Quadratic_program_solution< ET >::solves_linear_program ( const LinearProgram lp)

returns true iff sol solves the linear program lp.

If the result is false, you can get a message that describes the problem, through the method get_error().

template<typename ET>
template<class NonnegativeLinearProgram >
bool CGAL::Quadratic_program_solution< ET >::solves_nonnegative_linear_program ( const NonnegativeLinearProgram lp)

returns true iff sol solves the nonnegative linear program lp.

If the result is false, you can get a message that describes the problem, through the method get_error().

template<typename ET>
template<class NonnegativeQuadraticProgram >
bool CGAL::Quadratic_program_solution< ET >::solves_nonnegative_quadratic_program ( const NonnegativeQuadraticProgram qp)

returns true iff sol solves the nonnegative quadratic program qp.

If the result is false, you can get a message that describes the problem, through the method get_error().

template<typename ET>
template<class QuadraticProgram >
bool CGAL::Quadratic_program_solution< ET >::solves_quadratic_program ( const QuadraticProgram qp)

returns true iff sol solves the quadratic program qp.

If the result is false, you can get a message that describes the problem, through the method get_error().

template<typename ET>
Unboundedness_certificate_iterator CGAL::Quadratic_program_solution< ET >::unboundedness_certificate_begin ( ) const

returns a random acess iterator over the unbounded direction \( \qpw\) as given in Lemma 3,with respect to the solution \( \qpx^*\) obtained from sol.variable_values_begin().

The value type is ET, and the valid iterator range has length \( n\).

Precondition
sol.is_unbounded().

Lemma 3 (unboundedness certificate:) Let \(\qpx^*\) be a feasible solution of (QP). The program (QP) is unbounded if an \(n\)-vector \(\qpw\) with the following properties exist.

  1. if the \(i\)-th constraint is of type \(\leq\) ( \(\geq, =\), respectively), then \((A\qpw)_i\leq 0\) ( \((A\qpw)_i\geq 0, (A\qpw)_i=0\), respectively).
  2. \[ \begin{array}{llll} &&\geq 0 & \mbox{if \f$l_j\f$ is finite} \\ w_j &\quad \\ &&\leq 0 & \mbox{if \f$u_j\f$ is finite.} \end{array} \]

  3. \(\qpw^TD\qpw=0\) and \((\qpc^T+2{\qpx^*}^TD)\qpw<0\).

The vector \(\qpw\) is called an unbounded direction.

Proof: For a real number \(t\), consider the vector \(\qpx(t):=\qpx^*+t\qpw\). By 1. and 2., \(\qpx(t)\) is feasible for all \(t\geq 0\). The objective function value of \(\qpx(t)\) is

\begin{eqnarray*} \qpc^T \qpx(t) + \qpx(t)^TD \qpx(t) &=& \qpc^T\qpx^* + t\qpc^T\qpw + {\qpx^*}^TD\qpx^* + 2t{\qpx^*}^TD\qpw + t^2 \qpw^TD\qpw \\ &=& \qpc^T\qpx^* + {\qpx^*}^TD\qpx^* + t(\qpc^T + 2{\qpx^*}^TD)\qpw + t^2\qpw^TD\qpw. \end{eqnarray*}

By condition 3., this tends to \(-\infty\) for \(t\rightarrow\infty\), so the problem is indeed unbounded.

template<typename ET>
Unboundedness_certificate_iterator CGAL::Quadratic_program_solution< ET >::unboundedness_certificate_end ( )

returns the corresponding past-the-end iterator.

See Also
unboundedness_certificate_begin()
template<typename ET>
Variable_numerator_iterator CGAL::Quadratic_program_solution< ET >::variable_numerators_begin ( ) const

returns a random-access iterator it over the values of the variables in sol, with respect to a common denominator of all variables.

The value type is ET, and the valid iterator range has length \( n\).

template<typename ET>
Variable_value_iterator CGAL::Quadratic_program_solution< ET >::variable_values_begin ( ) const

returns a random-access iterator over the values of the variables in sol.

The value type is Quotient<ET>, and the valid iterator range has length \( n\).

Friends And Related Function Documentation

template<typename ET>
template<typename ET >
std::ostream& operator<< ( std::ostream &  out,
const Quadratic_program_solution< ET > &  sol 
)
related

writes the status of sol to the stream out.

In case the status is QP_OPTIMAL, the optimal objective value and the values of the variables at the optimal solution are output as well. For more detailed information about the solution (like basic variables/constraints) please use the dedicated methods of Quadratic_program_solution<ET>.