\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Linear and Quadratic Programming Solver
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
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

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.