Solves equality constrained linear programs with positivity constraints via the log-barrier method. More...

Public Member Functions
	drwnLPSolver (const VectorXd &c, const MatrixXd &A, const VectorXd &b)
	construct a problem $min. c^T x \text{ s.t. } Ax = b, x \geq 0$

	drwnLPSolver (const VectorXd &c, const MatrixXd &A, const VectorXd &b, const VectorXd &lb, const VectorXd &ub)
	construct a problem $min. c^T x \text{ s.t. } Ax = b, l \leq x \leq u$

	~drwnLPSolver ()
	destructor

void	initialize (const VectorXd &x)
	initialization of a feasible point

double	solve ()
	solve and return objective (solution can be obtained from solution function) More...

const VectorXd &	solution () const
	return the current estimate of the solution

int	size () const
	return the number of dimensions of the state space

double	operator[] (unsigned i) const
	access the `i-th` dimension of the current solution

Static Public Attributes
static double	t0 = 1.0e-3
	initial barrier function multiplier

static double	mu = 10.0
	barrier function multiplier update

static double	eps = 1.0e-6
	stopping tolerance

static unsigned	maxiters = 1000
	maximum number of newton steps per iteration

static double	alpha = 0.01
	line search stopping criterion in (0, 1/2)

static double	beta = 0.5
	line search backtracking parameter in (0, 1)

Protected Member Functions
bool	isUnbounded (unsigned i) const
	returns true if the i-th variable is unbounded

bool	isWithinBounds (const VectorXd &x) const
	returns true if a point is strictly within the lower and upper bounds

double	barrierFunction (const VectorXd &x) const
	computes the barrier function for a given assignment

Protected Attributes
VectorXd	_c
	linear term in the objective function

MatrixXd	_A
	linear equality constraint matrix

VectorXd	_b
	linear equality constraint vector

VectorXd	_lb
	lower bound for each variable (-DRWN_DBL_MAX for unbounded below)

VectorXd	_ub
	upped bound for each variable (DRWN_DBL_MAX for unbounded above)

VectorXd	_x
	current estimate of solution

Detailed Description

Solves equality constrained linear programs with positivity constraints via the log-barrier method.

Solves linear programs of the form:

$\begin{array}{ll} \textrm{minimize (over $x$)} & c^T x \\ \textrm{subject to} & Ax = b \\ & x \geq 0 \end{array}$

or, more generally,

$\begin{array}{ll} \textrm{minimize (over $x$)} & c^T x \\ \textrm{subject to} & Ax = b \\ & l \leq x \leq u \\ \end{array}$

General inequality constraints of the form $g^T x \leq h$ can be handled by introducing slack variables, e.g., $g^T x + z = h$ with $z \geq 0$ .

The following code snippet shows an example of solving the problem $min. \sum_i x_i \text{ s.t. } x_1 + x_2 = 1, x_2 + x_3 = 1, x_i \geq 0$ .

VectorXd b(2), c(3);
MatrixXd A(2, 3);
c << 1, 1, 1;
A << 1, 1, 0, 0, 1, 1;
b << 1, 1;
drwnLPSolver solver(c, A, b);
double p_star = solver.solve();
DRWN_LOG_MESSAGE("optimal value is " << p_star);
VectorXd x_star = solver.solution();
DRWN_LOG_MESSAGE("solution is " << x_star.transpose());

See:

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

Member Function Documentation

double drwnLPSolver::solve ( )

solve and return objective (solution can be obtained from solution function)

Todo:: solve with blockwise elimination

The documentation for this class was generated from the following files:

drwnLPSolver.h
drwnLPSolver.cpp

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation