CGAL 5.5 - Linear and Quadratic Programming Solver
CGAL::Quadratic_program< NT > Class Template Reference

#include <CGAL/QP_models.h>

## Definition

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

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 )

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.

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