#include <CGAL/QP_solution.h>
|
If D=0, the program is a linear program; if the variable bounds are x ≥ 0, we have a nonnegative program. Objects of type Quadratic_program_solution<ET> are returned by any of the four functions solve_quadratic_program, solve_linear_program, solve_nonnegative_quadratic_program, and solve_nonnegative_linear_program.
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 x* 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<ET>.
Quadratic_program_solution<ET>::ET | |
The exact number type that was used to solve the
program.
| |
Quadratic_program_solution<ET>::Variable_value_iterator | |
An iterator type with value type
Quotient<ET> to go over the values of the variables in the solution.
| |
Quadratic_program_solution<ET>::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.
| |
Quadratic_program_solution<ET>::Index_iterator | |
An iterator type with value type int
to go over the indices of the basic variables and the basic constraints.
| |
Quadratic_program_solution<ET>::Optimality_certificate_iterator | |
An iterator type with
value type Quotient<ET> to go over an m-vector λ that proves
optimality of the solution.
| |
Quadratic_program_solution<ET>::Optimality_certificate_numerator_iterator | |
An iterator type
with value type ET to go over the numerators of the vector λ
with respect to a common denominator.
| |
Quadratic_program_solution<ET>::Infeasibility_certificate_iterator | |
An iterator type with
value type ET to go over an m-vector λ that proves
infeasibility of the solution.
| |
Quadratic_program_solution<ET>::Unboundedness_certificate_iterator | |
An iterator type with
value type ET to go over an n-vector w that proves unboundedness
of the solution.
|
Quadratic_program_solution<ET> sol; | |
constructs a void instance of Quadratic_program_solution<ET> that is associated to
no program.
|
Objects of type Quadratic_program_solution<ET> can be copied and assigned.
Objects of type Quadratic_program_solution<ET> 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.
bool | sol.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. |
bool | sol.is_optimal () const | returns true iff sol is an optimal solution of the associated program. |
bool | sol.is_infeasible () const | returns true iff the associated program is infeasible. |
bool | sol.is_unbounded () const | returns true iff the associated program is unbounded. |
Quadratic_program_status | sol.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 | sol.number_of_iterations () const | returns the number of iterations that it took to solve the program asociated to sol. |
Quotient<ET> | sol.objective_value () const | returns the objective function value of sol. |
ET | sol.objective_value_numerator () const | |
returns the numerator of the objective function value of sol. | ||
ET | sol.objective_value_denominator () const | |
returns the denominator of the objective function value of sol. | ||
Variable_value_iterator | sol.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. | ||
Variable_value_iterator | sol.variable_values_end () const | returns the corresponding past-the-end iterator. |
Variable_numerator_iterator | sol.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_numerator_iterator | sol.variable_numerators_end () const | |
returns the corresponding past-the-end iterator. | ||
ET | sol.variables_common_denominator () const | |
returns the common denominator of the variable values as referred to by the previous two methods. |
Index_iterator | sol.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 x ≥ 0, all non-basic variables have value 0. | ||
Index_iterator | sol.basic_variable_indices_end () const | |
returns the corresponding past-the-end iterator. | ||
int | sol.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 | sol.basic_constraint_indices_begin () const | |
returns a random access iterator over the indices of the basic constraints in the system Ax ⋛ b. The value type is int. It is guaranteed that any basic constraint is satisfied with equality. In particular, if the system is of type Ax=b, all constraints are basic. | ||
Index_iterator | sol.basic_constraint_indices_end () const | |
returns the corresponding past-the-end iterator. | ||
int | sol.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& | std::ostream& out << sol | 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>. |
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).
template <class QuadraticProgram> | ||
bool | sol.solves_quadratic_program ( 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 <class LinearProgram> | ||
bool | sol.solves_linear_program ( 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 <class NonnegativeQuadraticProgram> | ||
bool | sol.solves_nonnegative_quadratic_program ( 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(). |
QP_solver/first_nonnegative_qp.cpp
template <class NonnegativeLinearProgram> | ||
bool | sol.solves_nonnegative_linear_program ( 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(). |
QP_solver/first_nonnegative_lp.cpp
A certificate is a vector that admits a simple proof for the correctness of the solution. Any non-void object of Quadratic_program_solution<ET> comes with such a certificate.
Lemma 1 (optimality certificate): A feasible n-vector x* is an optimal solution of (QP) if an m-vector λ with the following properties exist.
|
Proof: Let x be any feasible solution. We need to prove that
cTx+ xTDx ≥ cTx* + x*TDx*. |
For this, we argue as follows.
|
After adding xTDx- xTDx- x*TDx* = -x*TDx* to both sides of this inequality, we get
cTx+ xTDx- (x-x*)TD(x-x*) ≥ cTx* + x*TDx*, |
Optimality_certificate_iterator | sol.optimality_certifcate_begin () const | |||
returns a random access iterator over the optimality certificate
λ as given in Lemma 1, with respect to the solution x*
obtained from sol.variable_values_begin(). The value type
is Quotient<ET>, and the valid iterator range has length m.
| ||||
Optimality_certificate_iterator | sol.optimality_certificate_end () const | |||
returns the corresponding past-the-end iterator. | ||||
Optimality_certificate_numerator_iterator | ||||
sol.optimality_certifcate_numerators_begin () const | ||||
returns a random access iterator over the numerator values of the optimality certificate λ, 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_certificate_numerator_iterator | ||||
sol.optimality_certificate_numerators_end () const | ||||
returns the corresponding past-the-end iterator. |
Lemma 2 (infeasibility certificate): The program (QP) is infeasible if an m-vector λ with the following properties exist.
|
λTb < |
| + |
| . |
Proof: Let us assume for the purpose of obtaining a contradiction that there is a feasible solution x. Then we get
|
Lemma 3 (unboundedness certificate:) Let x* be a feasible solution of (QP). The program (QP) is unbounded if an n-vector w with the following properties exist.
|
The vector w is called an unbounded direction.
Proof: For a real number t, consider the vector x(t):=x*+tw. By 1. and 2., x(t) is feasible for all t ≥ 0. The objective function value of x(t) is
|
Unboundedness_certificate_iterator | ||||
sol.unboundedness_certificate_begin () const | ||||
returns a random acess iterator over the unbounded direction w
as given in Lemma 3,with respect to the solution x*
obtained from sol.variable_values_begin(). The value type
is ET, and the valid iterator range has length n.
| ||||
Unboundedness_certificate_iterator | ||||
sol.unboundedness_certificate_end () | ||||
returns the corresponding past-the-end iterator. |
The program concepts
QuadraticProgram
LinearProgram
NonnegativeQuadraticProgram
NonnegativeLinearProgram
and the functions that compute objects of class Quadratic_program_solution<ET> from models of these concepts:
solve_quadratic_program
solve_linear_program
solve_nonnegative_quadratic_program
solve_nonnegative_linear_program