#include <CGAL/QP_models.h>

Definition

$\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}}$

An object of class Quadratic_program describes a convex quadratic program of the form

$\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})$ .

Here,

$A$ is an $m\times n$ matrix (the constraint matrix),
$\qpb$ is an $m$ -dimensional vector (the right-hand side),
$\qprel$ is an $m$ -dimensional vector of relations from $\{\leq, =, \geq\}$ ,
$\qpl$ is an $n$ -dimensional vector of lower bounds for $\qpx$ , where $l_j\in\mathbb{R}\cup\{-\infty\}$ for all $j$
$\qpu$ is an $n$ -dimensional vector of upper bounds for $\qpx$ , where $u_j\in\mathbb{R}\cup\{\infty\}$ for all $j$
$D$ is a symmetric positive-semidefinite $n\times n$ matrix (the quadratic objective function),
$\qpc$ is an $n$ -dimensional vector (the linear objective function), and
$c_0$ is a constant.

If $D=0$ , the program is a linear program; if the variable bounds are $x\geq 0$ , we have a nonnegative program.

This class allows you to build your program entry by entry, using the set-methods below.

If you only need to wrap existing (random-access) iterators over your own data, then you may use any of the four models Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>, Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>, Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>, and Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>.

If you want to read a quadratic program in MPSFormat from a stream, please use the model Quadratic_program_from_mps<NT>.

Is Model Of:

QuadraticProgram

LinearProgram

NonnegativeQuadraticProgram

NonnegativeLinearProgram

Example

QP_solver/first_qp.cpp

QP_solver/first_lp.cpp

QP_solver/first_nonnegative_qp.cpp

QP_solver/first_nonnegative_lp.cpp

QP_solver/invert_matrix.cpp

See Also: Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>; Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>; Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>; Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>; Quadratic_program_from_mps<NT>

Examples:: QP_solver/first_lp.cpp, QP_solver/first_nonnegative_lp.cpp, QP_solver/first_nonnegative_qp.cpp, QP_solver/first_qp.cpp, QP_solver/first_qp_basic_constraints.cpp, QP_solver/invert_matrix.cpp, QP_solver/print_first_lp.cpp, QP_solver/print_first_nonnegative_lp.cpp, QP_solver/print_first_nonnegative_qp.cpp, and QP_solver/print_first_qp.cpp.

Types
typedef unspecified_type	NT
	The number type of the program entries.

Creation
	Quadratic_program (CGAL::Comparison_result default_r=CGAL::EQUAL, bool default_fl=true, const NT &default_l=0, bool default_fu=false, const NT &default_u=0)
	constructs a quadratic program with no variables and no constraints, ready for data to be added. More...

Operations
bool	is_linear () const
	returns `true` if and only if `qp` is a linear program.

bool	is_nonnegative () const
	returns `true` if and only if `qp` is a nonnegative program.

void	set_a (int j, int i, const NT &val)
	sets the entry $A_{ij}$ in column $j$ and row $i$ of the constraint matrix $A$ of `qp` to `val`. More...

void	set_b (int i, const NT &val)
	sets the entry $b_i$ of `qp` to `val`. More...

void	set_r (int i, CGAL::Comparison_result rel)
	sets the entry $\qprel_i$ of `qp` to `rel`. More...

void	set_l (int j, bool is_finite, const NT &val=NT(0))
	if `is_finite`, this sets the entry $l_j$ of `qp` to `val`, otherwise it sets $l_j$ to $-\infty$ . More...

void	set_u (int j, bool is_finite, const NT &val=NT(0))
	if `is_finite`, this sets the entry $u_j$ of `qp` to `val`, otherwise it sets $u_j$ to $\infty$ . More...

void	set_c (int j, const NT &val)
	sets the entry $c_j$ of `qp` to `val`. More...

void	set_c0 (const NT &val)
	sets the entry $c_0$ of `qp` to `val`. More...

void	set_d (int i, int j, const NT &val)
	sets the entries $2D_{ij}$ and $2D_{ji}$ of `qp` to `val`. More...

Constructor & Destructor Documentation

template<typename NT >

CGAL::Quadratic_program< NT >::Quadratic_program	(	CGAL::Comparison_result	default_r = `CGAL::EQUAL`,
		bool	default_fl = `true`,
		const NT &	default_l = `0`,
		bool	default_fu = `false`,
		const NT &	default_u = `0`
	)

constructs a quadratic program with no variables and no constraints, ready for data to be added.

Unless relations are explicitly set, they will be of type default_r. Unless bounds are explicitly set, they will be as specified by default_fl (finite lower bound?), default_l (lower bound value if lower bound is finite), default_fu (finite upper bound?), and default_l (upper bound value if upper bound is finite). If all parameters take their default values, we thus get equality constraints and bounds $x\geq0$ by default. Numerical entries that are not explicitly set will default to $0$ .

Precondition: if default_fl == default_fu == true, then default_l <= default_u.

Member Function Documentation

template<typename NT >

void CGAL::Quadratic_program< NT >::set_a	(	int	j,
		int	i,
		const NT &	val
	)

sets the entry $A_{ij}$ in column $j$ and row $i$ of the constraint matrix $A$ of qp to val.

An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_b	(	int	i,
		const NT &	val
	)

sets the entry $b_i$ of qp to val.

An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_c	(	int	j,
		const NT &	val
	)

sets the entry $c_j$ of qp to val.

An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_c0 ( const NT & val)

sets the entry $c_0$ of qp to val.

An existing entry is overwritten.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_d	(	int	i,
		int	j,
		const NT &	val
	)

sets the entries $2D_{ij}$ and $2D_{ji}$ of qp to val.

Existing entries are overwritten. qp is enlarged if necessary to accomodate these entries.

Precondition: j <= i

template<typename NT >

void CGAL::Quadratic_program< NT >::set_l	(	int	j,
		bool	is_finite,
		const NT &	val = `NT(0)`
	)

if is_finite, this sets the entry $l_j$ of qp to val, otherwise it sets $l_j$ to $-\infty$ .

An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_r	(	int	i,
		CGAL::Comparison_result	rel
	)

sets the entry $\qprel_i$ of qp to rel.

CGAL::SMALLER means that the $i$ -th constraint is of type "\f$ \leq\f$", CGAL::EQUAL means "\f$ =\f$", and CGAL::LARGER encodes "\f$ \geq\f$". An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

template<typename NT >

void CGAL::Quadratic_program< NT >::set_u	(	int	j,
		bool	is_finite,
		const NT &	val = `NT(0)`
	)

if is_finite, this sets the entry $u_j$ of qp to val, otherwise it sets $u_j$ to $\infty$ .

An existing entry is overwritten. qp is enlarged if necessary to accomodate this entry.

Definition

Example

Types

Creation

Operations

Constructor & Destructor Documentation

Member Function Documentation