Quadratic_program_solution<ET>

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>.

Types

Creation

Example

Operations

Solution status

Solution values

Basic variables and constraints

Example

Output

Validity

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).

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<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.

if the i-th constraint is of type ≤ ( ≥ , respectively), then λ_i ≥ 0 (λ_i ≤ 0, respectively).
λ^T(Ax^*-b) = 0.
≥ 0, if x^*_j = l_j < u_j
(c^T + λ^T A + 2x^*^TD)_j = 0, if l_j < x^*_j < u_j
≤ 0, if l_j < u_j = x^*_j.

Proof: Let x be any feasible solution. We need to prove that

c^Tx+ x^TDx ≥ c^Tx^* + x^*^TDx^*.

For this, we argue as follows.

c^Tx+ 2x^*^TDx	≥	c^Tx+ 2x^*^TDx+ λ^T(Ax-b)	(by Ax ⋛ b and 1.)
	=	(c^T + λ^T A + 2x^*^TD)x- λ^Tb
	≥	(c^T + λ^T A + 2x^^TD)x^ - λ^Tb	(by l ≤ x ≤ u and 3.)
	=	c^Tx^* + 2x^^TDx^	(by 2.)

After adding x^TDx- x^TDx- x^*^TDx^* = -x^*^TDx^* to both sides of this inequality, we get

c^Tx+ x^TDx- (x-x^*)^TD(x-x^*) ≥ c^Tx^* + x^*^TDx^*,

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

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.

Precondition:

sol.is_optimal()

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.

Example

QP_solver/optimality_certificate.cpp

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

if the i-th constraint is of type ≤ ( ≥ , respectively), then λ_i ≥ 0 (λ_i ≤ 0, respectively).
≥ 0 if u_j=∞
λ^T A_j
≤ 0 if l_j=-∞.
λ^Tb <
∑
j: λ^TA_j <0
λ^TA_j u_j
+
∑
j: λ^TA_j >0
λ^TA_j l_j
.

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

≥

λ^T(Ax-b)

(by Ax ⋛ b and 1.)

∑

j: λ^TA_j <0

λ^TA_j x_j

∑

j: λ^TA_j >0

λ^TA_j x_j

- λ^T b

≥

∑

j: λ^TA_j <0

λ^TA_j u_j

∑

j: λ^TA_j >0

λ^TA_j l_j

- λ^T b

(by l ≤ x ≤ u and 2.)

(by 3.),

and this is the desired contradiction 0>0.

Infeasibility_certificate_iterator

sol.infeasibility_certificate_begin () const

returns a random access iterator over the infeasibility certificate λ as given in Lemma 2. The value type is ET, and the valid iterator range has length m.

Precondition:

sol.is_infeasible()

Infeasibility_certificate_iterator

sol.infeasibility_certificate_end () const

returns the corresponding past-the-end iterator.

Example

QP_solver/infeasibility_certificate.cpp

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.

if the i-th constraint is of type ≤ ( ≥ , =, respectively), then (Aw)_i ≤ 0 ((Aw)_i ≥ 0, (Aw)_i=0, respectively).
≥ 0 if l_j is finite
w_j
≤ 0 if u_j is finite.
w^TDw=0 and (c^T+2x^*^TD)w<0.

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

c^T x(t) + x(t)^TD x(t)	=	c^Tx^* + tc^Tw+ x^^TDx^ + 2tx^*^TDw+ t² w^TDw
	=	c^Tx^* + x^^TDx^ + t(c^T + 2x^*^TD)w+ t²w^TDw.

By condition 3., this tends to -∞ for t → ∞, so the problem is indeed unbounded.

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.

Precondition:

sol.is_unbounded()

Unboundedness_certificate_iterator

sol.unboundedness_certificate_end ()

returns the corresponding past-the-end iterator.

Example

QP_solver/unboundedness_certificate.cpp

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.

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.

CGAL::Quadratic_program_solution<ET>

Definition

Example

Terminology

Types

Creation

Example

Operations

Solution status

Solution values

Basic variables and constraints

Example

Example

Output

Validity

Certificates

Example

Example

Example

See Also

Quadratic_program_solution<ET> sol;
	constructs a void instance of Quadratic_program_solution<ET> that is associated to no program.

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>.

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().

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().

bool	sol.is_valid () const	returns false iff the validation through one of the previous four functions has failed.

std::string	sol.get_error () const	returns an error message in case any of the previous four validation functions has returned false.