00001 00019 #ifndef _QUADPROGPP 00020 #define _QUADPROGPP 00021 00022 #include <vnl/vnl_matrix.h> 00023 #include <vnl/vnl_vector.h> 00024 00038 namespace QuadProgPP { 00039 00049 double solve_quadprog(vnl_matrix<double>& G, // nxn Matrix - Will be changed in the function! 00050 vnl_vector<double>& g0, // n 00051 const vnl_matrix<double>& CE, // nxp - Equality constraints, just a dummy 00052 const vnl_vector<double>& ce0, // p - Equality constraints, just a dummy 00053 const vnl_matrix<double>& CI, // nxm - Inequality constraints 00054 const vnl_vector<double>& ci0, // m 00055 vnl_vector<double>& x); // n - Solution of the QP problem 00056 } 00057 00058 #endif 00059 00060 // ## Comments by original author #################################################### 00061 /* 00062 00063 The quadprog_solve() function implements the algorithm of Goldfarb and Idnani 00064 for the solution of a (convex) Quadratic Programming problem 00065 by means of an active-set dual method. 00066 00067 The problem is in the form: 00068 00069 min 0.5 * x G x + g0 x 00070 s.t. 00071 CE^T x + ce0 = 0 00072 CI^T x + ci0 >= 0 00073 00074 The matrix and vectors dimensions are as follows: 00075 G: n * n 00076 g0: n 00077 CE: n * p 00078 ce0: p 00079 CI: n * m 00080 ci0: m 00081 x: n 00082 00083 The function will return the cost of the solution written in the x vector or 00084 std::numeric_limits::infinity() if the problem is infeasible. In the latter case 00085 the value of the x vector is not correct. 00086 00087 References: D. Goldfarb, A. Idnani. A numerically stable dual method for solving 00088 strictly convex quadratic programs. Mathematical Programming 27 (1983) pp. 1-33. 00089 00090 Notes: 00091 1. pay attention in setting up the vectors ce0 and ci0. 00092 If the constraints of your problem are specified in the form 00093 A^T x = b and C^T x >= d, then you should set ce0 = -b and ci0 = -d. 00094 2. The matrix G is modified within the function since it is used to compute 00095 the G = L^T L cholesky factorization for further computations inside the function. 00096 If you need the original matrix G you should make a copy of it and pass the copy 00097 to the function. 00098 00099 Author: Luca Di Gaspero 00100 DIEGM - University of Udine, Italy 00101 l.digaspero@uniud.it 00102 http://www.diegm.uniud.it/digaspero/ 00103 00104 The author will be grateful if the researchers using this software will 00105 acknowledge the contribution of this function in their research papers. 00106 00107 LICENSE 00108 00109 This file is part of QuadProg++: a C++ library implementing 00110 the algorithm of Goldfarb and Idnani for the solution of a (convex) 00111 Quadratic Programming problem by means of an active-set dual method. 00112 Copyright (C) 2007-2009 Luca Di Gaspero. 00113 Copyright (C) 2009 Eric Moyer. 00114 00115 QuadProg++ is free software: you can redistribute it and/or modify 00116 it under the terms of the GNU Lesser General Public License as published by 00117 the Free Software Foundation, either version 3 of the License, or 00118 (at your option) any later version. 00119 00120 QuadProg++ is distributed in the hope that it will be useful, 00121 but WITHOUT ANY WARRANTY; without even the implied warranty of 00122 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00123 GNU Lesser General Public License for more details. 00124 00125 You should have received a copy of the GNU Lesser General Public License 00126 along with QuadProg++. If not, see <http://www.gnu.org/licenses/>. 00127 00128 */