CGAL 6.1 - Linear and Quadratic Programming Solver

Loading...
Searching...
No Matches
List of all members
CGAL::Quadratic_program_from_iterators< A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it > Class Template Reference
Reference Manual » Classes

`#include <CGAL/QP_models.h>`

## Definition

template<typename A_it, typename B_it, typename R_it, typename FL_it, typename L_it, typename FU_it, typename U_it, typename D_it, typename C_it>
class CGAL::Quadratic_program_from_iterators< A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it >

An object of class `Quadratic_program_from_iterators` 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.

This class is simply a wrapper for existing iterators, and it does not copy the program data.

It frequently happens that all values in one of the vectors from above are the same, for example if the system \( Ax\qprel b\) is actually a system of equations \( Ax=b\). To get an iterator over such a vector, it is not necessary to store multiple copies of the value in some container; an instance of the class `Const_oneset_iterator<T>`, constructed from the value in question, does the job more efficiently.

Is model of
  `QuadraticProgram`

Example

QP_solver/first_qp_from_iterators.cpp

The following example for the simpler model `Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>` should give you a flavor of the use of this model in practice.

QP_solver/solve_convex_hull_containment_lp.h

QP_solver/convex_hull_containment.cpp

See also
  `QuadraticProgram`
  `Quadratic_program<NT>`
  `Quadratic_program_from_mps<NT>`

Examples
  QP_solver/first_qp_from_iterators.cpp.

## Creation
| Quadratic_program_from_iterators (int n, int m, const A_it &a, const B_it &b, const R_it &r, const FL_it &fl, const L_it &l, const FU_it &fu, const U_it &u, const D_it &d, const C_it &c, const std::iterator_traits< C_it >value_type &c0=0)
| constructs `qp` from given random-access iterators and the constant `c0`.

## Constructor & Destructor Documentation

## ◆ Quadratic_program_from_iterators()

template<typename A_it , typename B_it , typename R_it , typename FL_it , typename L_it , typename FU_it , typename U_it , typename D_it , typename C_it >

CGAL::Quadratic_program_from_iterators< A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it >::Quadratic_program_from_iterators | ( | int | n,
|  | int | m,
|  | const A_it & | a,
|  | const B_it & | b,
|  | const R_it & | r,
|  | const FL_it & | fl,
|  | const L_it & | l,
|  | const FU_it & | fu,
|  | const U_it & | u,
|  | const D_it & | d,
|  | const C_it & | c,
|  | const std::iterator_traits< C_it >value_type & | c0 = `0`
| ) |  |

constructs `qp` from given random-access iterators and the constant `c0`.

The passed iterators are merely stored, no copying of the program data takes place. How these iterators are supposed to encode the quadratic program is described in `QuadraticProgram`.