|
CGAL 4.7 - Linear and Quadratic Programming Solver
|
|
CGAL 4.7 - Linear and Quadratic Programming Solver
|
#include <CGAL/QP_solution.h>
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.
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
and the functions that compute objects of class Quadratic_program_solution from models of these concepts:
solve_quadratic_program solve_linear_program solve_nonnegative_quadratic_program solve_nonnegative_linear_program 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 Objects of type | |
| 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 | |
| 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< ET > | objective_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 ET & | variables_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 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 | |
| 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 | |
| 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... | |
| 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.
| 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\).
| 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\).
sol.is_infeasible().Lemma 2 (infeasibility certificate): The program (QP) is infeasible if an \(m\)-vector \(\qplambda\) with the following properties exist.
\[ \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} \]
\[\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\).
| Infeasibility_certificate_iterator CGAL::Quadratic_program_solution< ET >::infeasibility_certificate_end | ( | ) | const |
returns the corresponding past-the-end iterator.
| 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.
| 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\).
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.
\[ \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.
| 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\).
optimality_certifcate_begin() | Optimality_certificate_iterator CGAL::Quadratic_program_solution< ET >::optimality_certificate_end | ( | ) | const |
returns the corresponding past-the-end iterator.
optimality_certifcate_begin() | Optimality_certificate_numerator_iterator CGAL::Quadratic_program_solution< ET >::optimality_certificate_numerators_end | ( | ) | const |
returns the corresponding past-the-end iterator.
optimality_certifcate_begin() | 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().
| 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().
| 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().
| 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().
| 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\).
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.
\[ \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} \]
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.
| Unboundedness_certificate_iterator CGAL::Quadratic_program_solution< ET >::unboundedness_certificate_end | ( | ) |
returns the corresponding past-the-end iterator.
| 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\).
| 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\).
|
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>.
1.8.4