A basic Primal-Dual Interior-Point Method solver class. More...

#include <PrimalDualIPM.h>

Inheritance diagram for PrimalDualIPM:

Public Member Functions
	PrimalDualIPM ()
	Constructor.

virtual	~PrimalDualIPM ()
	Destructor.

void	setLog (std::ostream *pOuts)
	Sets output destination of internal calculation log. More...

Protected Member Functions
void	logWarn (const char *str)
	Logs a warning message. More...

void	logVector (const char *str, IPM_Vector_IN v)
	Logs values of a vector, transposing if it is a colomn vector. More...

void	logMatrix (const char *str, IPM_Matrix_IN m)
	Logs values of a matrix. More...

IPM_Error	start (const IPM_uint n, const IPM_uint m, const IPM_uint p)
	Starts to solve a optimization problem by primal-dual interior-point method. More...

virtual IPM_Error	initialPoint (IPM_Vector_IO x)=0
	Produces the initial values of \(x\). More...

virtual IPM_Error	finalPoint (IPM_Vector_IN x, IPM_Vector_IN lmd, IPM_Vector_IN nu, bool converged)=0
	Obtains the final solution values of \(x\). More...

virtual IPM_Error	objective (IPM_Vector_IN x, IPM_Single_IO f_o)=0
	Calculates the objective function \(f_{\rm obj}(x)\). More...

virtual IPM_Error	Dobjective (IPM_Vector_IN x, IPM_Vector_IO Df_o)=0
	Calculates first derivatives of the objective function \(\nabla f_{\rm obj}(x)\). More...

virtual IPM_Error	DDobjective (IPM_Vector_IN x, IPM_Matrix_IO DDf_o)=0
	Calculates second derivatives of the objective function \(\nabla^2 f_{\rm obj}(x)\). More...

virtual IPM_Error	inequality (IPM_Vector_IN x, IPM_Vector_IO f_i)=0
	Calculates the inequality constraint functions \(f_i(x)\). More...

virtual IPM_Error	Dinequality (IPM_Vector_IN x, IPM_Matrix_IO Df_i)=0
	Calculates first derivatives of the inequality constraint functions \(Df(x)\). More...

virtual IPM_Error	DDinequality (IPM_Vector_IN x, IPM_Matrix_IO DDf_i, const IPM_uint of_i)=0
	Calculates second derivatives of the inequality constraint functions \(\nabla^2 f_i(x)\). More...

virtual IPM_Error	equality (IPM_Matrix_IO A, IPM_Vector_IO b)=0
	Produces the equality constraints affine parameters \(A\) and \(b\). More...

Static Protected Member Functions
static IPM_Scalar	max (const IPM_Scalar a, const IPM_Scalar b)
	Returns the larger of a and b.

static IPM_Scalar	min (const IPM_Scalar a, const IPM_Scalar b)
	Returns the smaller of a and b.

static IPM_Scalar	abs (const IPM_Scalar x)
	Returns the absolute value of x.

Protected Attributes
IPM_Scalar	m_margin
	Initial margin value for dual variables of inequalities.

IPM_Scalar	m_loop
	Max iteration number of outer-loop for the Newton step.

IPM_Scalar	m_bloop
	Max iteration number of inner-loop for the backtracking line search.

IPM_Scalar	m_eps_feas
	Tolerance of the primal and dual residuals.

IPM_Scalar	m_eps
	Tolerance of the surrogate duality gap.

IPM_Scalar	m_mu
	The factor to squeeze complementary slackness.

IPM_Scalar	m_alpha
	The factor to decrease residuals in the backtracking line search.

IPM_Scalar	m_beta
	The factor to decrease a step size in the backtracking line search.

IPM_Scalar	m_s_coef
	The factor to determine an initial step size in the backtracking line search.

Detailed Description

A basic Primal-Dual Interior-Point Method solver class.

This class abstracts a solver of continuous scalar convex optimization problem: \[ \begin{array}{ll} {\rm minimize} & f_{\rm obj}(x) \\ {\rm subject \ to} & f_i(x) \le 0 \quad (i = 0, \ldots, m - 1) \\ & A x = b, \end{array} \] where

variables \( x \in {\bf R}^n \)
\( f_{\rm obj}: {\bf R}^n \rightarrow {\bf R} \), convex and twice differentiable
\( f_i: {\bf R}^n \rightarrow {\bf R} \), convex and twice differentiable
\( A \in {\bf R}^{p \times n} \), \( {\bf rank} A = p < n \), \( b \in {\bf R}^p \).

The solution gives optimal values of primal variables \(x\) as well as dual variables \(\lambda \in {\bf R}^m\) and \(\nu \in {\bf R}^p\).

Member Function Documentation

void PrimalDualIPM::setLog ( std::ostream * pOuts )

inline

Sets output destination of internal calculation log.

Parameters

pOuts is a pointer of output stream. NULL means no output.

void PrimalDualIPM::logWarn ( const char * str )

protected

Logs a warning message.

Parameters

str	is a pointer of the message string.

See also: setLog.

void PrimalDualIPM::logVector	(	const char *	str,
		IPM_Vector_IN	v
	)

protected

Logs values of a vector, transposing if it is a colomn vector.

Parameters

str	is a pointer of the name string of v.
v	is the logged vector.

See also: setLog.

Here is the caller graph for this function:

void PrimalDualIPM::logMatrix	(	const char *	str,
		IPM_Matrix_IN	m
	)

protected

Logs values of a matrix.

Parameters

str	is a pointer of the name string of m.
m	is the logged matrix.

See also: setLog.

IPM_Error PrimalDualIPM::start	(	const IPM_uint	n,
		const IPM_uint	m,
		const IPM_uint	p
	)

protected

Starts to solve a optimization problem by primal-dual interior-point method.

This is the main function of this class. All pure virtual functions are called within this method.

Parameters

n	is \(n\), the dimension of the variable \(x\).
m	is \(m\), the number of inequality constraints \(f_i\).
p	is \(p\), the number of rows of equality constraints \(A\) and \(b\).

Returns: an error string. NULL means no error.

See also: initialPoint, finalPoint, objective, Dobjective, DDobjective, inequality, Dinequality, Dinequality, DDinequality and equality.

Here is the call graph for this function:

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::initialPoint ( IPM_Vector_IO x )

protectedpure virtual

Produces the initial values of \(x\).

The initial values must satisfy all inequality constraints strictly: \(f_i(x)<0\). This may seem a hard requirement, but introducing slack variables helps in many cases. Refer QCQP implementation for example.

Parameters

x	[OUT] is a column vector containing the initial values of \(x\).

Returns: an error string. NULL means no error.

See also: inequality.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::finalPoint	(	IPM_Vector_IN	x,
		IPM_Vector_IN	lmd,
		IPM_Vector_IN	nu,
		bool	converged
	)

protectedpure virtual

Obtains the final solution values of \(x\).

Dual variables \(\lambda, \nu\) can be obtained as well.

Parameters

x	[IN] is a column vector containing the final values of \(x\).
lmd	[IN] is a column vector containing the final values of \(\lambda\).
nu	[IN] is a column vector containing the final values of \(\nu\).
converged	is true when the solution ends with termination criteria satisfied. false means that x, lmd and nu are not optimal.

Returns: an error string. NULL means no error.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::objective	(	IPM_Vector_IN	x,
		IPM_Single_IO	f_o
	)

protectedpure virtual

Calculates the objective function \(f_{\rm obj}(x)\).

Parameters

x	[IN] is a column vector containing values of \(x\).
f_o	[OUT] is a single element matrix containing a value of \(f_{\rm obj}(x)\).

Returns: an error string. NULL means no error.

See also: Dobjective, DDobjective.

virtual IPM_Error PrimalDualIPM::Dobjective	(	IPM_Vector_IN	x,
		IPM_Vector_IO	Df_o
	)

protectedpure virtual

Calculates first derivatives of the objective function \(\nabla f_{\rm obj}(x)\).

Parameters

x	[IN] is a column vector containing values of \(x\).
Df_o	[OUT] is a column vector containing values of \(\nabla f_{\rm obj}(x)\).

Returns: an error string. NULL means no error.

See also: objective, DDobjective.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::DDobjective	(	IPM_Vector_IN	x,
		IPM_Matrix_IO	DDf_o
	)

protectedpure virtual

Calculates second derivatives of the objective function \(\nabla^2 f_{\rm obj}(x)\).

Parameters

x	[IN] is a column vector containing values of \(x\).
DDf_o	[OUT] is a matrix containing values of \(\nabla^2 f_{\rm obj}(x)\).

Returns: an error string. NULL means no error.

See also: objective, Dobjective.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::inequality	(	IPM_Vector_IN	x,
		IPM_Vector_IO	f_i
	)

protectedpure virtual

Calculates the inequality constraint functions \(f_i(x)\).

Parameters

x	[IN] is a column vector containing values of \(x\).
f_i	[OUT] is a column vector containing values of \(\left[\matrix{f_0(x) & \cdots & f_{m-1}(x)}\right]^T\).

Returns: an error string. NULL means no error.

See also: Dinequality, DDinequality.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::Dinequality	(	IPM_Vector_IN	x,
		IPM_Matrix_IO	Df_i
	)

protectedpure virtual

Calculates first derivatives of the inequality constraint functions \(Df(x)\).

NOTE: \(Df(x) = \left[\matrix{\nabla f_0(x) & \cdots & \nabla f_{m-1}(x)}\right]^T\).

Parameters

x	[IN] is a column vector containing values of \(x\).
Df_i	[OUT] is a matrix containing values of \(Df(x)\).

Returns: an error string. NULL means no error.

See also: inequality, DDinequality.

Here is the caller graph for this function:

virtual IPM_Error PrimalDualIPM::DDinequality	(	IPM_Vector_IN	x,
		IPM_Matrix_IO	DDf_i,
		const IPM_uint	of_i
	)

protectedpure virtual

Calculates second derivatives of the inequality constraint functions \(\nabla^2 f_i(x)\).

Parameters

x	[IN] is a column vector containing values of \(x\).
DDf_i	[OUT] is a matrix containing values of \(\nabla^2 f_i(x)\).
of_i	indicates an index \(i\) of \(f_i\).