SHOGUN v0.9.0
|
00001 /*----------------------------------------------------------------------- 00002 * libqp.h: Library for Quadratic Programming optimization. 00003 * 00004 * The library provides two solvers: 00005 * 1. Solver for QP task with simplex constraints. 00006 * See function ./lib/libqp_splx.c for definition of the QP task. 00007 * 00008 * 2. Solver for QP task with box constraints and a single linear 00009 * equality constraint. 00010 * See function ./lib/libqp_gsmo.c for definiton of the QP task. 00011 * 00012 * Copyright (C) 2006-2008 Vojtech Franc, xfrancv@cmp.felk.cvut.cz 00013 * Center for Machine Perception, CTU FEL Prague 00014 * 00015 * This program is free software; you can redistribute it and/or 00016 * modify it under the terms of the GNU General Public 00017 * License as published by the Free Software Foundation; 00018 * Version 3, 29 June 2007 00019 *-------------------------------------------------------------------- */ 00020 00021 #ifndef libqp_h 00022 #define libqp_h 00023 00024 #include <math.h> 00025 00026 #include "lib/common.h" 00027 namespace shogun 00028 { 00029 #define LIBQP_PLUS_INF (-log(0.0)) 00030 #define LIBQP_CALLOC(x,y) calloc(x,y) 00031 #define LIBQP_FREE(x) free(x) 00032 #define LIBQP_INDEX(ROW,COL,NUM_ROWS) ((COL)*(NUM_ROWS)+(ROW)) 00033 #define LIBQP_MIN(A,B) ((A) > (B) ? (B) : (A)) 00034 #define LIBQP_MAX(A,B) ((A) < (B) ? (B) : (A)) 00035 #define LIBQP_ABS(A) ((A) < 0 ? -(A) : (A)) 00036 00037 /* QP solver return value */ 00038 typedef struct { 00039 uint32_t nIter; /* number of iterations */ 00040 float64_t QP; /* primal objective value */ 00041 float64_t QD; /* dual objective value */ 00042 int8_t exitflag; /* -1 ... not enough memory 00043 0 ... nIter >= MaxIter 00044 1 ... QP - QD <= TolRel*ABS(QP) 00045 2 ... QP - QD <= TolAbs 00046 3 ... QP <= QP_TH 00047 4 ... eps-KKT conditions satisfied */ 00048 } libqp_state_T; 00049 00050 /* QP solver for tasks with simplex constraints */ 00051 libqp_state_T libqp_splx_solver(const float64_t* (*get_col)(uint32_t), 00052 float64_t *diag_H, 00053 float64_t *f, 00054 float64_t *b, 00055 uint32_t *I, 00056 uint8_t *S, 00057 float64_t *x, 00058 uint32_t n, 00059 uint32_t MaxIter, 00060 float64_t TolAbs, 00061 float64_t TolRel, 00062 float64_t QP_TH, 00063 void (*print_state)(libqp_state_T state)); 00064 00065 /* Generalized SMO algorithm */ 00066 libqp_state_T libqp_gsmo_solver(const float64_t* (*get_col)(uint32_t), 00067 float64_t *diag_H, 00068 float64_t *f, 00069 float64_t *a, 00070 float64_t b, 00071 float64_t *LB, 00072 float64_t *UB, 00073 float64_t *x, 00074 uint32_t n, 00075 uint32_t MaxIter, 00076 float64_t TolKKT, 00077 void (*print_state)(libqp_state_T state)); 00078 00079 } 00080 #endif /* libqp_h */