Functions to solve various forms of constrained quadratic programming. More...

#include "vnl_solve_qp.h"
#include <vnl/algo/vnl_svd.h>
#include <vnl/algo/vnl_cholesky.h>
#include <vcl_vector.h>
#include <vcl_cassert.h>
#include <vcl_iostream.h>

Functions
bool	vnl_solve_qp_with_equality_constraints (const vnl_matrix< double > &H, const vnl_vector< double > &g, const vnl_matrix< double > &A, const vnl_vector< double > &b, vnl_vector< double > &x)
	Solve quadratic programming problem with linear constraints.
bool	vnl_solve_qp_zero_sum (const vnl_matrix< double > &H, const vnl_vector< double > &g, vnl_vector< double > &x)
	Solve quadratic programming problem with constraint sum(x)=0.
bool	vnl_solve_qp_non_neg_step (const vnl_matrix< double > &H, const vnl_vector< double > &g, const vnl_matrix< double > &A, const vnl_vector< double > &b, vnl_vector< double > &x, vcl_vector< bool > &valid, unsigned &n_valid)
	Solve unconstrained problem and apply one extra constraint if necessary.
bool	vnl_solve_qp_non_neg_sum_one_step (const vnl_matrix< double > &H, const vnl_vector< double > &g, vnl_vector< double > &x, vcl_vector< bool > &valid, unsigned &n_valid)
	Solve unconstrained problem and apply one extra constraint if necessary.
bool	vnl_solve_qp_with_non_neg_constraints (const vnl_matrix< double > &H, const vnl_vector< double > &g, const vnl_matrix< double > &A, const vnl_vector< double > &b, vnl_vector< double > &x, double con_tol, bool verbose)
	Find non-negative solution to a constrained quadratic programming problem.
bool	vnl_solve_qp_non_neg_sum_one (const vnl_matrix< double > &H, const vnl_vector< double > &g, vnl_vector< double > &x, bool verbose)
	Find non-negative solution to a constrained quadratic programming problem.

Detailed Description

Functions to solve various forms of constrained quadratic programming.

Author:: Tim Cootes

Definition in file vnl_solve_qp.cxx.

Function Documentation

bool vnl_solve_qp_non_neg_step	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		const vnl_matrix< double > &	A,
		const vnl_vector< double > &	b,
		vnl_vector< double > &	x,
		vcl_vector< bool > &	valid,
		unsigned &	n_valid
	)

Solve unconstrained problem and apply one extra constraint if necessary.

Used by vnl_non_neg_constrained_qp Returns true if valid minimum found

Definition at line 166 of file vnl_solve_qp.cxx.

bool vnl_solve_qp_non_neg_sum_one	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		vnl_vector< double > &	x,
		bool	verbose
	)

Find non-negative solution to a constrained quadratic programming problem.

Minimise F(x)=0.5x'Hx + g'x subject to sum(x)=1 and x(i)>=0 for all i

Uses a variant of the active set strategy to solve the problem. This performs a sequence of unconstrained solutions. If the inequality constraints are violated, the most violated x(i) is set to zero and a slightly smaller problem is solved.

Parameters:

H	Hessian of F(x) - must be symmetric
x	On input, it must satisfy all constraints (sum(x)=1, x(i)>=0)
verbose	When true, output error messages to cerr if failed

Return values:

True	if successful

Definition at line 344 of file vnl_solve_qp.cxx.

bool vnl_solve_qp_non_neg_sum_one_step	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		vnl_vector< double > &	x,
		vcl_vector< bool > &	valid,
		unsigned &	n_valid
	)

Solve unconstrained problem and apply one extra constraint if necessary.

Returns true if valid minimum found

Definition at line 226 of file vnl_solve_qp.cxx.

bool vnl_solve_qp_with_equality_constraints	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		const vnl_matrix< double > &	A,
		const vnl_vector< double > &	b,
		vnl_vector< double > &	x
	)

Solve quadratic programming problem with linear constraints.

Minimise F(x)=0.5x'Hx + g'x subject to Ax=b

Parameters:

H	Hessian of F(x) - must be symmetric

Return values:

True	if successful

Definition at line 31 of file vnl_solve_qp.cxx.

bool vnl_solve_qp_with_non_neg_constraints	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		const vnl_matrix< double > &	A,
		const vnl_vector< double > &	b,
		vnl_vector< double > &	x,
		double	con_tol,
		bool	verbose
	)

Find non-negative solution to a constrained quadratic programming problem.

Minimise F(x)=0.5x'Hx + g'x subject to Ax=b and x(i)>=0 for all i

Uses a variant of the active set strategy to solve the problem. This performs a sequence of unconstrained solutions. If the inequality constraints are violated, the most violated x(i) is set to zero and a slightly smaller problem is solved.

Parameters:

H	Hessian of F(x) - must be symmetric
x	On input, it must satisfy all constraints (Ax=b, x(i)>=0)
con_tol	Tolerance for testing constraints: \|Ax-b\|^2<con_tol
verbose	When true, output error messages to cerr if failed

Return values:

True	if successful

Definition at line 285 of file vnl_solve_qp.cxx.

bool vnl_solve_qp_zero_sum	(	const vnl_matrix< double > &	H,
		const vnl_vector< double > &	g,
		vnl_vector< double > &	x
	)

Solve quadratic programming problem with constraint sum(x)=0.

Minimise F(x)=0.5x'Hx + g'x subject to sum(x)=0 Special case of quadratic programming (Equality constraint: x.1=0)

Parameters:

H	Hessian of F(x) - must be symmetric

Return values:

True	if successful

Definition at line 77 of file vnl_solve_qp.cxx.