iteration.c File Reference

Detailed Description

QPALM main solver routines.

Author

Ben Hermans

This file contains the functions that make up the qpalm algorithm (the functions that qpalm_solve will use). These include the computation of the residuals at the start of the iteration, the update of the primal variables in an inner iteration, the update of the penalty factors and dual variables in an outer iteration, the computation of the primal and dual objective values, etc.

Definition in file iteration.c.

#include <qpalm/iteration.h>
#include <qpalm/lin_alg.h>
#include <qpalm/solver_interface.h>
#include <qpalm/newton.h>
#include <qpalm/linesearch.h>
#include <qpalm/nonconvex.h>
#include <qpalm/util.h>
#include <ladel.h>

Include dependency graph for iteration.c:

Go to the source code of this file.

Functions
void	compute_residuals (QPALMWorkspace *work, solver_common *c)
	Compute the residuals (in vector form)
void	initialize_sigma (QPALMWorkspace *work, solver_common *c)
	Initialize penalty factors from initial x.
void	update_sigma (QPALMWorkspace *work, solver_common *c)
	Update the penalty factors.
void	update_gamma (QPALMWorkspace *work)
	Update the proximal penalty.
void	boost_gamma (QPALMWorkspace *work, solver_common *c)
	Maximize the proximal penalty.
void	update_or_boost_gamma (QPALMWorkspace *work, solver_common *c, c_int iter_out)
void	update_proximal_point_and_penalty (QPALMWorkspace *work, solver_common *c, c_int iter_out, c_float *eps_k_abs, c_float *eps_k_rel)
void	update_dual_iterate_and_parameters (QPALMWorkspace *work, solver_common *c, c_int iter_out, c_float *eps_k_abs, c_float *eps_k_rel)
void	update_primal_iterate (QPALMWorkspace *work, solver_common *c)
	Update the primal iterate.
c_float	compute_objective (QPALMWorkspace *work)
	Compute the (unscaled) primal objective value at the current iterate.
c_float	compute_dual_objective (QPALMWorkspace *work, solver_common *c)
	Compute the (unscaled) dual objective value at the current iterate.

Function Documentation

compute_residuals()

void compute_residuals	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Compute the residuals (in vector form)

This routine is called at the start of every QPALM iteration. It computes the current residual vectors, which are required by the termination routines and by the other iteration routines.

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 22 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

initialize_sigma()

void initialize_sigma	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Initialize penalty factors from initial x.

The formula used here can be found in [2].

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 48 of file iteration.c.

Here is the call graph for this function:

update_sigma()

void update_sigma	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Update the penalty factors.

Constraints that are active are penalized in proportion to their constraint violation. If the number of changed penalty parameters is low, and the proximal penalty need not be further updated, then the factor LD is updated using a low-rank update based on the changed penalty factors.

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 73 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

update_gamma()

void update_gamma

(

QPALMWorkspace *

work

)

Update the proximal penalty.

The proximal penalty parameter is increased by a constant factor at every outer update, until a certain maximum value is reached.

Parameters

work

Workspace

Definition at line 126 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

boost_gamma()

void boost_gamma	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Maximize the proximal penalty.

The proximal penalty parameter can be increased when the primal residual is low and the number of active constraints no longer changes. Increasing the proximal penalty will significantly speed up the convergence of the dual residual in that case. First, the maximum allowed value is computed, based on the fact that \(Q+A^T \Sigma A + \frac{1}{\gamma}I\) should be sufficiently positive definite for the factorization routines.

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 138 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

update_or_boost_gamma()

void update_or_boost_gamma	(	QPALMWorkspace *	work,
		solver_common *	c,
		c_int	iter_out
	)

Definition at line 184 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

update_proximal_point_and_penalty()

void update_proximal_point_and_penalty	(	QPALMWorkspace *	work,
		solver_common *	c,
		c_int	iter_out,
		c_float *	eps_k_abs,
		c_float *	eps_k_rel
	)

NB Implementation detail: store Einv*Ax and Einv*z in temp_2m. The infinity norm of that vector is then equal to the maximum of both norms.

Definition at line 209 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

update_dual_iterate_and_parameters()

void update_dual_iterate_and_parameters	(	QPALMWorkspace *	work,
		solver_common *	c,
		c_int	iter_out,
		c_float *	eps_k_abs,
		c_float *	eps_k_rel
	)

Definition at line 249 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

update_primal_iterate()

void update_primal_iterate	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Update the primal iterate.

This function calls the functions that compute the newton direction and stepsize from exact linesearch, and applies the update.

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 269 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function:

compute_objective()

c_float compute_objective

(

QPALMWorkspace *

work

)

Compute the (unscaled) primal objective value at the current iterate.

Returns

The value of the primal objective at the current iterate.

Parameters

work

Workspace

Definition at line 287 of file iteration.c.

Here is the caller graph for this function:

compute_dual_objective()

c_float compute_dual_objective	(	QPALMWorkspace *	work,
		solver_common *	c
	)

Compute the (unscaled) dual objective value at the current iterate.

Returns

The value of the dual objective at the current iterate.

Parameters

work	Workspace
c	Linear systems solver environment

Definition at line 328 of file iteration.c.

Here is the call graph for this function:

Here is the caller graph for this function: