lily/include/ineq-constrained-qp.hh

   1 /*
   2   ineq-constrained-qp.hh -- declare Ineq_constrained_qp
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c)  1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef INEQ_CONSTRAINED_QP_HH
  11 #define INEQ_CONSTRAINED_QP_HH
  12
  13
  14
  15 #include "matrix.hh"
  16
  17 /** inequality constrained quadratic program
  18
  19     It takes the form of
  20
  21     optimise for x : x*quad_ *x + lin_* x + const_term_
  22
  23     subject to for all i:  cons_[i] * x >= consrhs_[i]
  24
  25
  26     @usage:
  27     instantiate Ineq_constrained_qp.
  28
  29     Modify quad_, lin_ and const_term_ directly. Use
  30     add_inequality_cons () to add constraints.  Call solve () with a
  31     feasible solution
  32
  33
  34  */
  35 class Ineq_constrained_qp {
  36     friend class Active_constraints;
  37
  38     Array<Vector> cons_;
  39     Array<Real> consrhs_;
  40 public:
  41     Matrix quad_;
  42     Vector lin_;
  43     Real const_term_;
  44
  45
  46     /**
  47       use a KKT method to assert optimality of sol
  48       */
  49     void assert_solution (Vector sol) const;
  50     /// solve the problem using a projected gradient method
  51     Vector constraint_solve (Vector) const;
  52     /**
  53       Solve it. First try it the easy way.
  54      */
  55     Vector solve (Vector start) const;
  56
  57     /**
  58       @return the number of variables in the problem
  59       */
  60     int dim() const;
  61
  62     /**
  63       add a constraint
  64
  65
  66         c*vars >= r
  67
  68       PRE
  69       c.dim() == dim ();
  70
  71       */
  72     void add_inequality_cons (Vector c, double r);
  73
  74     /** set up matrices to go with the problem. */
  75     Ineq_constrained_qp (int novars);
  76
  77     /**
  78     evaluate the quadratic function for input #v#
  79     */
  80     Real eval (Vector v);
  81
  82     void eliminate_var (int idx, Real value);
  83     void OK() const;
  84     void print() const;
  85
  86 };
  87
  88 // ugh
  89 const Real EPS=1e-7;
  90
  91 #endif // INEQ_CONSTRAINED_QP_HH