00001 // This is core/vnl/algo/vnl_solve_qp.h 00002 #ifndef vnl_solve_qp_h_ 00003 #define vnl_solve_qp_h_ 00004 00005 //: 00006 // \file 00007 // \brief Functions to solve various forms of constrained quadratic programming 00008 // \author Tim Cootes 00009 00010 #include <vnl/vnl_vector.h> 00011 #include <vnl/vnl_matrix.h> 00012 00013 //: Solve quadratic programming problem with linear constraints 00014 // Minimise F(x)=0.5x'Hx + g'x subject to Ax=b 00015 // \param H Hessian of F(x) - must be symmetric 00016 // \retval True if successful 00017 bool vnl_solve_qp_with_equality_constraints(const vnl_matrix<double>& H, 00018 const vnl_vector<double>& g, 00019 const vnl_matrix<double>& A, 00020 const vnl_vector<double>& b, 00021 vnl_vector<double>& x); 00022 00023 //: Solve quadratic programming problem with constraint sum(x)=0 00024 // Minimise F(x)=0.5x'Hx + g'x subject to sum(x)=0 00025 // Special case of quadratic programming (Equality constraint: x.1=0) 00026 // \param H Hessian of F(x) - must be symmetric 00027 // \retval True if successful 00028 bool vnl_solve_qp_zero_sum(const vnl_matrix<double>& H, 00029 const vnl_vector<double>& g, 00030 vnl_vector<double>& x); 00031 00032 //: Find non-negative solution to a constrained quadratic programming problem 00033 // Minimise F(x)=0.5x'Hx + g'x subject to Ax=b and x(i)>=0 for all i 00034 // 00035 // Uses a variant of the active set strategy to solve the problem. 00036 // This performs a sequence of unconstrained solutions. If the inequality 00037 // constraints are violated, the most violated x(i) is set to zero 00038 // and a slightly smaller problem is solved. 00039 // \param H Hessian of F(x) - must be symmetric 00040 // \param x On input, it must satisfy all constraints (Ax=b, x(i)>=0) 00041 // \param con_tol Tolerance for testing constraints: |Ax-b|^2<con_tol 00042 // \param verbose When true, output error messages to cerr if failed 00043 // \retval True if successful 00044 bool vnl_solve_qp_with_non_neg_constraints(const vnl_matrix<double>& H, 00045 const vnl_vector<double>& g, 00046 const vnl_matrix<double>& A, 00047 const vnl_vector<double>& b, 00048 vnl_vector<double>& x, 00049 double con_tol = 1e-8, 00050 bool verbose=true); 00051 00052 //: Find non-negative solution to a constrained quadratic programming problem 00053 // Minimise F(x)=0.5x'Hx + g'x subject to sum(x)=1 and x(i)>=0 for all i 00054 // 00055 // Uses a variant of the active set strategy to solve the problem. 00056 // This performs a sequence of unconstrained solutions. If the inequality 00057 // constraints are violated, the most violated x(i) is set to zero 00058 // and a slightly smaller problem is solved. 00059 // \param H Hessian of F(x) - must be symmetric 00060 // \param x On input, it must satisfy all constraints (sum(x)=1, x(i)>=0) 00061 // \param verbose When true, output error messages to cerr if failed 00062 // \retval True if successful 00063 bool vnl_solve_qp_non_neg_sum_one(const vnl_matrix<double>& H, 00064 const vnl_vector<double>& g, 00065 vnl_vector<double>& x, 00066 bool verbose=true); 00067 00068 #endif // vnl_solve_qp_h_ 00069
1.7.5.1