source/quadratic_programs.h

   1 /* This file is part of Shapes.
   2  *
   3  * Shapes is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * any later version.
   7  *
   8  * Shapes is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  * Copyright 2009 Henrik Tidefelt
  17  */
  18
  19 #pragma once
  20
  21 #include <iostream>
  22 #include <gsl/gsl_matrix.h>
  23
  24 namespace Shapes
  25 {
  26
  27         namespace Computation
  28         {
  29
  30                 typedef enum { QP_OK, QP_WARNING, QP_ERROR, QP_FAIL, QP_BAD } QPSolverExit;
  31                 typedef enum { QP_OK_LM, QP_OK_GAP_ABS, QP_OK_GAP_REL, QP_OK_UPPER, QP_OK_LOWER } QPSolverTermination;
  32                 typedef enum { QP_WARNING_NEGATIVE_LM, QP_WARNING_EARLY_EXIT } QPSolverWarning;
  33                 typedef enum { QP_ERROR_UNDEFINED, QP_ERROR_ALLOCATE,
  34                                                                          QP_ERROR_DIMENSIONS_X, QP_ERROR_DIMENSIONS_LM } QPSolverError;
  35                 typedef enum { QP_FAIL_ITER } QPSolverFailure;
  36                 typedef enum { QP_BAD_INCONSISTENT_EQ, QP_BAD_INCONSISTENT_INEQ, QP_BAD_INCONSISTENT_BOX, QP_BAD_INCONSISTENT_ACTIVE,
  37                                                                          QP_BAD_POSITIVE_DEFINITE, QP_BAD_LINEAR_DEPENDENT,
  38                                                                          QP_BAD_INITIAL_INFEASIBLE } QPSolverBadProblem;
  39                 struct QPSolverStatus
  40                 {
  41                         QPSolverExit code;
  42                         union
  43                         {
  44                                 QPSolverTermination termination;
  45                                 QPSolverWarning warning;
  46                                 QPSolverError error;
  47                                 QPSolverFailure failure;
  48                                 QPSolverBadProblem bad;
  49                         };
  50                         int param; /* Parameter that can be used to give more detaild information. */
  51                         size_t iterations; /* Number of iterations used. */
  52                         const char * code_str( ) const;
  53                         const char * sub_str( ) const;
  54                 };
  55
  56                 void polytope_distance_generator_form( const size_t dim,
  57                                                                                                                                                                          /* Generators are stored with generator <i> occupying (start+dim*i) and the following (dim-1) positions. */
  58                                                                                                                                                                          const size_t n1, const double * g1, /* Generators for first polytope.*/
  59                                                                                                                                                                          const size_t n2, const double * g2, /* Generators for second polytope. */
  60                                                                                                                                                                          double * costLower, /* Pass 0 if lower bound shall not be computed. */
  61                                                                                                                                                                          double * costUpper, /* Returned bounds on the suared distance. */
  62                                                                                                                                                                          double stopLower, /* Stop if *costLower becomes lower than this value. Only used if positive and costLower != 0. */
  63                                                                                                                                                                          double stopUpper, /* Stop if *costUpper becomes lower than this value.  Only used if positive and costUpper != 0. */
  64                                                                                                                                                                          double gapTolAbs, /* Stop if ( *costUpper - *costLower ) < galTolAbs.  Only used if positive and costLower != 0 and costUpper != 0. */
  65                                                                                                                                                                          double gapTolRel, /* Stop if ( *costUpper - *costLower ) < galTolRel * (*costUpper).  Only used if positive and costLower != 0 and costUpper != 0. */
  66                                                                                                                                                                          double lmTol, /* Lagrange multiplier tolerance (for sign tests), use 0 for a default of 1e-14.
  67                                                                                                                                                                                                                                         * Note that this tolerance may be interpreted as a gap tolerance which is linear in the distance,
  68                                                                                                                                                                                                                                         * not distance squared.
  69                                                                                                                                                                                                                                         */
  70                                                                                                                                                                          double xTol, /* Tolerance to be compared with squared norm of primal step, use 0 for a default of 1e-8. */
  71                                                                                                                                                                          double sigmaTol, /* Truncate singular values below sigmaTol times max(sigma), use 0 for 1e-3. */
  72                                                                                                                                                                          double * y1, double * y2, /* Optimal point in each polytope.  Pass 0 unless needed! */
  73                                                                                                                                                                          QPSolverStatus * status );
  74
  75                 void polytope_distance_generator_form_write_data( std::ostream & os,
  76                                                                                                                                                                                                                         const size_t dim,
  77                                                                                                                                                                                                                         const size_t n1, const double * g1,
  78                                                                                                                                                                                                                         const size_t n2, const double * g2 );
  79                 void polytope_distance_generator_form_write_binary_data( const char * oFilename,
  80                                                                                                                                                                                                                                                  const size_t dim,
  81                                                                                                                                                                                                                                                  const size_t n1, const double * g1,
  82                                                                                                                                                                                                                                                  const size_t n2, const double * g2 );
  83
  84         }
  85
  86 }