Auxilary.c File Reference

#include "Auxilary.h"

Include dependency graph for Auxilary.c:

Functions
void	formkktmatrix_U (smat *P, smat *G, smat *Gt, smat *kkt)
void	formkktmatrix_full (smat *P, smat *G, smat *A, smat *Gt, smat *At, smat *kkt)
	Assembles the KKT matrix. More...
void	updatekktmatrix (smat *kkt, qp_real *s, qp_real *z, qp_real *delta_s, qp_real *delta_z, qp_real alpha_p, qp_real alpha_d, qp_int m, qp_int n, qp_int p, qp_int indicator)
	Updates the lower diagonal part of the kkt Matrix,. More...
void	updatevariables (qp_real *x, qp_real *delta_x, qp_real alpha, qp_int count)
	Performs scalar vector addition. More...
void	updatekktmatrix_b (qp_real *b, qp_real *rx, qp_real *ry, qp_real *rz, qp_real *ds, qp_real *z, qp_int n, qp_int m, qp_int p)
	Updates the right hand side of the KKT linear system of equations. More...
void	form_ds (qp_real *ds, qp_real *lambda, qp_real *delta_s, qp_real *delta_z, qp_real sigma, qp_real mu, qp_int m, qp_int selector)
	Updates the ds vector based on the selector. More...
void	findsteplength (qp_real *s, qp_real *delta_s, qp_real *z, qp_real *delta_z, qp_int m, qp_real *alpha_p, qp_real *alpha_d)
	Calculates the step length. More...
qp_int	checksign (qp_real *x, qp_real *delta_x, qp_real alpha, qp_int count)
	Checks if x + alpha*delta_x < 0. More...
qp_real	norm (qp_real *p, qp_int n)
	Calculates the Eucledian two norm of vector. More...
qp_real	innerproduct (qp_real *x, qp_real *y, qp_int n)
	Calculates the inner product of two vectors. More...
qp_int	kktsolve_1 (QP *myQP)
	Solves the KKT linear systems and updates delta_z and delta_s. More...
void	kktsolve_2 (QP *myQP)
	Solves the kktlinear system from results of kktsolve_1 and updates delta_x, delta_y, delta_z and delta_s. More...
qp_int	ldlinitialsolve (kkt *mykkt, qp_real *delta)
	Solves the kkt linear system to find initial conditions. More...
void	formlambda (qp_real *lambda, qp_real *s, qp_real *z, qp_int n)
	Computes the scaling point lambda. More...
void	SparseMatrixSetup (qp_int m, qp_int n, qp_int nnz, qp_int *jc, qp_int *ir, qp_real *pr, smat *sparse)
	Sets up the Sparse Matrix in Column Compressed Storage Format based on inputs. More...
void	Transpose_Row_Count (qp_int m, qp_int n, qp_int *Li, qp_int *Lp, qp_int *Lti, qp_int *Ltp)
	Computes the ir and jc of transpose of a Matrix. More...
void	computeresiduals (QP *myQP)
	Computes the residuals rx, ry and rz. More...
void	SparseMatrixTransMultiply (smat *A, qp_real *x, qp_real *y, qp_int start)
	Performs Sparse Matrix Transpose Vector Multiplication as. More...
void	SparseMatrixMultiply (smat *A, qp_real *x, qp_real *y, qp_int start)
	Performs Sparse Matrix Vector Multiplication as. More...
qp_real	formrho (qp_real *s, qp_real *delta_s, qp_real *z, qp_real *delta_z, qp_real alpha_p, qp_real alpha_d, qp_int n)
	Computes the scalar rho as. More...
void	SparseMatrixTranspose (smat *A, smat *At)
	Computes the sparse matrix transpose. More...
void	findminmax (qp_real *z, long n, qp_real *min, qp_real *max)
	Computes the minimum and maximum of the vector. More...
qp_int	kkt_initialize (QP *myQP)
	Computes the initial condition for the QP problem. More...
void	test_reach (qp_int *Parent, qp_int *Pinv, qp_int *UPattern, qp_int n, qp_int m, qp_int p)
	Computes the nodes to be updated at each iteration. More...
qp_real	obj_value (smat *P, qp_real *c, qp_real *x, qp_real *temp)
	Computes the objective function value f = x'Px + c'x. More...
void	densetosparse (qp_int m, qp_int n, qp_real *pr, smat *A)
	Converts dense matrix in column major format to CCS format. More...
void	densetosparse_ROWMAJOR (qp_int m, qp_int n, qp_real *pr, smat *A)
	Converts dense matrix in row major format to CCS format. More...

Function Documentation

checksign()

qp_int checksign	(	qp_real *	x,
		qp_real *	delta_x,
		qp_real	alpha,
		qp_int	count
	)

Checks if x + alpha*delta_x < 0.

Parameters

[out]	Flag	0 : Failure 1 : Success
[in]	x	primal variable
[in]	delta_x	search direction
[in]	alpha	scalar value

computeresiduals()

void computeresiduals

(

QP *

myQP

)

Computes the residuals rx, ry and rz.

Parameters

[out]

myQP

QP Structure

rx = Px + G'z +c
ry = Ax - b
rz = -s - Gx + h
mu = s'z/m

densetosparse()

void densetosparse	(	qp_int	m,
		qp_int	n,
		qp_real *	pr,
		smat *	A
	)

Converts dense matrix in column major format to CCS format.

Parameters

[out]	A	Sparse Matrix A
[in]	m	number of rows of A
[in]	n	number of columns of A
[in]	pr	pointer to matrix in column major format

densetosparse_ROWMAJOR()

void densetosparse_ROWMAJOR	(	qp_int	m,
		qp_int	n,
		qp_real *	pr,
		smat *	A
	)

Converts dense matrix in row major format to CCS format.

Parameters

[out]	A	Sparse Matrix A
[in]	m	number of rows of A
[in]	n	number of columns of A
[in]	pr	pointer to matrix in row major format

findminmax()

void findminmax	(	qp_real *	z,
		long	n,
		qp_real *	min,
		qp_real *	max
	)

Computes the minimum and maximum of the vector.

Parameters

[out]	min	Minimum of the vector z
[in]	max	Maximum of the vector z
[in]	n	Vector z
[in]	nnz	Length of the vector z

findsteplength()

void findsteplength	(	qp_real *	s,
		qp_real *	delta_s,
		qp_real *	z,
		qp_real *	delta_z,
		qp_int	m,
		qp_real *	alpha_p,
		qp_real *	alpha_d
	)

Calculates the step length.

Parameters

[out]	alpha_p	Primal step length
[out]	alpha_d	Dual step length
[in]	s	Primal slack variable
[in]	delta_s	Search Direction
[in]	z	Dual slack variable
[in]	delta_z	Search Direction
[in]	m	# of inequality constraints

form_ds()

void form_ds	(	qp_real *	ds,
		qp_real *	lambda,
		qp_real *	delta_s,
		qp_real *	delta_z,
		qp_real	sigma,
		qp_real	mu,
		qp_int	m,
		qp_int	selector
	)

Updates the ds vector based on the selector.

Parameters

[out]	ds	vector
[in]	lambda	Scaling Point
[in]	delta_s	Search Direction
[in]	delta_z	Search Direction
[in]	sigma	centering parameter
[in]	mu	complementary condition
[in]	m	# of inequality constraints
[in]	selector	selector

selector = 1 => ds = -lambda*lambda; \n
selector = 2 => ds = -lambda*lambda - (delta_s*delta_z) + (sigma*mu); \n
selector = 3 => ds = -lambda*lambda + (sigma*mu); \n

formkktmatrix_full()

void formkktmatrix_full	(	smat *	P,
		smat *	G,
		smat *	A,
		smat *	Gt,
		smat *	At,
		smat *	kkt
	)

Assembles the KKT matrix.

Parameters

[out]	kkt	KKT Matrix
[in]	P	Cost Function Matrix
[in]	A	Equality Constraint Matrix
[in]	A'	Transpose of A
[in]	G	Inequality Constraint Matrix
[in]	G'	Transpose of G

KKT = [P    A'   G']
      [A    0    0]
      [G    0   -I]

formkktmatrix_U()

void formkktmatrix_U	(	smat *	P,
		smat *	G,
		smat *	Gt,
		smat *	kkt
	)

Forms the Upper triangular part of the kkt matrix

Status: Inactive

formlambda()

void formlambda	(	qp_real *	lambda,
		qp_real *	s,
		qp_real *	z,
		qp_int	n
	)

Computes the scaling point lambda.

Parameters

[out]	lambda	Scaling Point
[in]	s	Primal slack variable
[in]	z	Dual variable
[in]	n	length of the vector

lambda = sqrt(s/z)

formrho()

qp_real formrho	(	qp_real *	s,
		qp_real *	delta_s,
		qp_real *	z,
		qp_real *	delta_z,
		qp_real	alpha_p,
		qp_real	alpha_d,
		qp_int	n
	)

Computes the scalar rho as.

Parameters

[out]	rho	scalar value rho
[in]	s	Primal slack variable
[in]	delta_s	delta_s
[in]	z	Dual Variable
[in]	delta_z	delta_z
[in]	alpha_p	Primal Step length
[in]	alpha_d	Dual Step length
[in]	n	length of vectors s,z,delta_s and delta_z (# of ineq. constraints)

Computes the scalar rho as
rho = (s+alpha_p*delta_s)*(z+alpha_d*delta_z)/s'z;

innerproduct()

qp_real innerproduct	(	qp_real *	x,
		qp_real *	y,
		qp_int	n
	)

Calculates the inner product of two vectors.

Parameters

[out]	value	Inner Product of the vectors x and y i.e, <x,y>
[in]	x	vector x
[in]	y	vector y
[in]	n	length of vectors x and y

kkt_initialize()

qp_int kkt_initialize

(

QP *

myQP

)

Computes the initial condition for the QP problem.

Parameters

[in]

myQP

QP Matrix Structure

Solves a closely related QP of the form
min. 0.5*x'Px + c'x + s's
s.t     Ax = b
        Gx + s = h

kktsolve_1()

qp_int kktsolve_1

(

QP *

myQP

)

Solves the KKT linear systems and updates delta_z and delta_s.

Parameters

[out]	Flag	Flag indicating status of the function; 0 : Failure 1 : Successful
[in]	myQP	QP Structure

kktsolve_2()

void kktsolve_2

(

QP *

myQP

)

Solves the kktlinear system from results of kktsolve_1 and updates delta_x, delta_y, delta_z and delta_s.

Parameters

[in]

myQP

QP Structure

ldlinitialsolve()

qp_int ldlinitialsolve	(	kkt *	mykkt,
		qp_real *	delta
	)

Solves the kkt linear system to find initial conditions.

Parameters

[in]	mykkt	KKT Structure
[in]	delta	delta varible

Invoked by kkt_initialize
Creates and updates the LDL workspace variables
Performs ldl_symbolic and stores the results
Also Performs LDL_numeric ; LDL_perm; LDL_lsolve; LDL_dsolve; LDL_ltsolve; LDL_permt in the same order

norm()

qp_real norm	(	qp_real *	p,
		qp_int	n
	)

Calculates the Eucledian two norm of vector.

Parameters

[out]	value	Norm of the vector
[in]	p	Vector
[in]	n	Length of the vector

obj_value()

qp_real obj_value	(	smat *	P,
		qp_real *	c,
		qp_real *	x,
		qp_real *	temp
	)

Computes the objective function value f = x'Px + c'x.

Parameters

[out]	fval	Objective Value of QP
[in]	P	cost Function : quadratic part
[in]	c	cost function : linear term
[in]	x	primal solution
[in]	temp	temporary workspace variable

SparseMatrixMultiply()

void SparseMatrixMultiply	(	smat *	A,
		qp_real *	x,
		qp_real *	y,
		qp_int	start
	)

Performs Sparse Matrix Vector Multiplication as.

Parameters

[out]	y	Outut vector y
[in]	A	Sparse Matrix structure
[in]	x	Number of rows of the matrix
[in]	start	Selection index

Computes y = y - Ax
start = 0 ; do nothing
start !=0 ; intialize y=0

SparseMatrixSetup()

void SparseMatrixSetup	(	qp_int	m,
		qp_int	n,
		qp_int	nnz,
		qp_int *	jc,
		qp_int *	ir,
		qp_real *	pr,
		smat *	sparse
	)

Sets up the Sparse Matrix in Column Compressed Storage Format based on inputs.

Parameters

[out]	sparse	Sparse Matrix structure
[in]	m	Number of rows of the matrix
[in]	n	Number of Columns of the matrix
[in]	nnz	Number of Non zeros of the matrix
[in]	jc	Vector to store column count ; Dim [n+1]
[in]	ir	Vector to store row indices in column major format ; Dim[nnz]
[in]	pr	Vector to store matrix values in column major format ; Dim[nnz]

SparseMatrixTransMultiply()

void SparseMatrixTransMultiply	(	smat *	A,
		qp_real *	x,
		qp_real *	y,
		qp_int	start
	)

Performs Sparse Matrix Transpose Vector Multiplication as.

Parameters

[out]	y	Outut vector y
[in]	A	Sparse Matrix structure
[in]	x	Number of rows of the matrix
[in]	start	Selection index

Computes y = y - A'x
start = 0 ; do nothing
start !=0 ; intialize y=0

SparseMatrixTranspose()

void SparseMatrixTranspose	(	smat *	A,
		smat *	At
	)

Computes the sparse matrix transpose.

Parameters

[out]	A	Sparse Matrix
[in]	At	Transpose of the Sparse Matrix

test_reach()

void test_reach	(	qp_int *	Parent,
		qp_int *	Pinv,
		qp_int *	UPattern,
		qp_int	n,
		qp_int	m,
		qp_int	p
	)

Computes the nodes to be updated at each iteration.

Parameters

[out]	UPattern	Reach of the nodes of the lower diagonal part of KKT Matrix
[in]	n	# of decision variables
[in]	m	# of inequality constraints
[in]	p	# of equality constraints
[in]	Parent	Parent tree of the KKT Matrix
[in]	Pinv	Inverse of Permutation vector

Transpose_Row_Count()

void Transpose_Row_Count	(	qp_int	m,
		qp_int	n,
		qp_int *	Li,
		qp_int *	Lp,
		qp_int *	Lti,
		qp_int *	Ltp
	)

Computes the ir and jc of transpose of a Matrix.

Parameters

[out]	Lti	ir vector of the transpose of sparse choelsky matrix L (Lt->ir)
[out]	Ltp	jc vector of the transpose of sparse choelsky matrix L (Lt->jc)
[in]	m	Number of rows the matrix L
[in]	n	Number of columns of the matrix L
[in]	Li	ir vector of the sparse choelsky matrix L (L->ir)
[in]	Lp	jc vector of the sparse choelsky matrix L (L->jc)

updatekktmatrix()

void updatekktmatrix	(	smat *	kkt,
		qp_real *	s,
		qp_real *	z,
		qp_real *	delta_s,
		qp_real *	delta_z,
		qp_real	alpha_p,
		qp_real	alpha_d,
		qp_int	m,
		qp_int	n,
		qp_int	p,
		qp_int	indicator
	)

Updates the lower diagonal part of the kkt Matrix,.

Parameters

[out]	kkt	KKT Matrix
[in]	s	Primal Slack Variables
[in]	z	Dual Variables
[in]	delta_s	Primal slack direction
[in]	delta_z	Dual slack direction
[in]	alpha_p	Primal step Length
[in]	alpha_d	Dual step length
[in]	m	# of ineqaulity constraints
[in]	n	# of decision variables
[in]	p	# of equality constraints
[in]	indicator	selection vector

indicator = 1 : Pure Affine Direction
indicator = 2 : Pure Centering Direction
indicator = 3 : Pure Newton Direction

updatekktmatrix_b()

void updatekktmatrix_b	(	qp_real *	b,
		qp_real *	rx,
		qp_real *	ry,
		qp_real *	rz,
		qp_real *	ds,
		qp_real *	z,
		qp_int	n,
		qp_int	m,
		qp_int	p
	)

Updates the right hand side of the KKT linear system of equations.

Parameters

[out]	b	KKT Matrix right-hand side vector
[in]	rx	Residual
[in]	ry	Residual
[in]	rz	Residual
[in]	ds	vector ds
[in]	z	Residual
[in]	m	# of inequality constraints
[in]	n	# of decision variables
[in]	p	# of equality constraints

b = [rx]
    [ry]
    [rz] - [ds]/[z]

updatevariables()

void updatevariables	(	qp_real *	x,
		qp_real *	delta_x,
		qp_real	alpha,
		qp_int	count
	)

Performs scalar vector addition.

Parameters

[out]	x	vector
[in]	x	vector
[in]	alpha	scalar value
[in]	delta_x	search direction

x = x + alpha*delta_x