00001 /* 00002 File QuadProg++.hh 00003 00004 The quadprog_solve() function implements the algorithm of Goldfarb and Idnani 00005 for the solution of a (convex) Quadratic Programming problem 00006 by means of a dual method. 00007 00008 The problem is in the form: 00009 00010 min 0.5 * x G x + g0 x 00011 s.t. 00012 CE^T x + ce0 = 0 00013 CI^T x + ci0 >= 0 00014 00015 The matrix and vectors dimensions are as follows: 00016 G: n * n 00017 g0: n 00018 00019 CE: n * p 00020 ce0: p 00021 00022 CI: n * m 00023 ci0: m 00024 00025 x: n 00026 00027 The function will return the cost of the solution written in the x vector or 00028 std::numeric_limits::infinity() if the problem is infeasible. In the latter case 00029 the value of the x vector is not correct. 00030 00031 References: D. Goldfarb, A. Idnani. A numerically stable dual method for solving 00032 strictly convex quadratic programs. Mathematical Programming 27 (1983) pp. 1-33. 00033 00034 Notes: 00035 1. pay attention in setting up the vectors ce0 and ci0. 00036 If the constraints of your problem are specified in the form 00037 A^T x = b and C^T x >= d, then you should set ce0 = -b and ci0 = -d. 00038 2. The matrices have column dimension equal to MATRIX_DIM, 00039 a constant set to 20 in this file (by means of a #define macro). 00040 If the matrices are bigger than 20 x 20 the limit could be 00041 increased by means of a -DMATRIX_DIM=n on the compiler command line. 00042 3. The matrix G is modified within the function since it is used to compute 00043 the G = L^T L cholesky factorization for further computations inside the function. 00044 If you need the original matrix G you should make a copy of it and pass the copy 00045 to the function. 00046 00047 Author: Luca Di Gaspero 00048 DIEGM - University of Udine, Italy 00049 [email protected] 00050 http://www.diegm.uniud.it/digaspero/ 00051 00052 The author will be grateful if the researchers using this software will 00053 acknowledge the contribution of this function in their research papers. 00054 00055 LICENSE 00056 00057 Copyright 2006 Luca Di Gaspero 00058 00059 This file is part of QuadProg++. 00060 00061 QuadProg++ is free software; you can redistribute it and/or modify 00062 it under the terms of the GNU General Public License as published by 00063 the Free Software Foundation; either version 2 of the License, or 00064 (at your option) any later version. 00065 00066 QuadProg++ is distributed in the hope that it will be useful, 00067 but WITHOUT ANY WARRANTY; without even the implied warranty of 00068 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00069 GNU General Public License for more details. 00070 00071 You should have received a copy of the GNU General Public License 00072 along with QuadProg++; if not, write to the Free Software 00073 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00074 00075 */ 00076 00077 #ifndef _QUADPROGPP_H_ 00078 #define _QUADPROGPP_H_ 00079 00080 #include "REAL.H" 00081 00082 #ifndef MATRIX_DIM 00083 #define MATRIX_DIM 25 00084 #endif 00085 00086 Real solve_quadprog(Real **G, Real g0[], int n, 00087 Real **CE, Real ce0[], int p, 00088 Real **CI, Real ci0[], int m, 00089 Real x[]); 00090 00091 #endif // #define _QUADPROGPP_H_
1.5.5