CGAL::Quadratic_program< NT > Class Template Reference

#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

Quadratic_program()

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

set_a()

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 accommodate this entry.

set_b()

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 accommodate this entry.

set_c()

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 accommodate this entry.

set_c0()

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.

set_d()

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 accommodate these entries.

Precondition

j <= i

set_l()

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 accommodate this entry.

set_r()

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 accommodate this entry.

set_u()

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 accommodate this entry.