Detailed Description

Routines to check the termination and infeasibility criteria.

Author: Ben Hermans

The routines in this file compute the primal and dual residuals, the primal and dual tolerances, check whether the problem is solved completely, unscale and store the solution if that is the case, check whether the intermediate problem is solved and whether one of the infeasibility criteria hold. In other words, all routines related to the termination of the optimization algorithm are grouped in this file.

Definition in file termination.c.

#include <qpalm/termination.h>
#include <qpalm/lin_alg.h>
#include <qpalm/constants.h>
#include <qpalm/global_opts.h>
#include <qpalm/util.h>
#include <qpalm/iteration.h>

Include dependency graph for termination.c:

Go to the source code of this file.

Functions
void	calculate_residual_norms_and_tolerances (QPALMWorkspace *work)
	Calls the routines that compute the norm of the residuals and the tolerances.

void	calculate_primal_residual (QPALMWorkspace *work)
	Calculates the infinity norm of the primal residual and stores it in work->info->pri_res_norm.

void	calculate_dual_residuals (QPALMWorkspace *work)
	Calculates the infinity norm of the dual residual and the residual of the subproblem and stores them in work->info->dua_res_norm and work->info->dua2_res_norm respectively.

void	calculate_primal_tolerance (QPALMWorkspace *work)
	Calculates the primal tolerance and stores it in work->eps_pri.

void	calculate_dual_tolerances (QPALMWorkspace *work)
	Calculates the dual tolerance for the problem and current subproblem and stores them in work->eps_dua and worl->eps_dua_in respectively.

c_int	is_solved (QPALMWorkspace *work)
	Check whether the primal and dual residual norms are smaller than the primal and dual tolerances.

c_int	is_primal_infeasible (QPALMWorkspace *work)
	Check whether the problem is primal infeasible.

c_int	is_dual_infeasible (QPALMWorkspace *work)
	Check whether the problem is dual infeasible.

void	store_solution (QPALMWorkspace *work)
	Helper function to store the (unscaled) solution in the solution struct.

c_int	check_subproblem_termination (QPALMWorkspace *work)
	Check whether the subproblem is solved.

Function Documentation

◆ calculate_residual_norms_and_tolerances()

void calculate_residual_norms_and_tolerances ( QPALMWorkspace * work )

Calls the routines that compute the norm of the residuals and the tolerances.

Parameters

work Workspace

Definition at line 19 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calculate_primal_residual()

void calculate_primal_residual ( QPALMWorkspace * work )

Calculates the infinity norm of the primal residual and stores it in work->info->pri_res_norm.

The primal residual is given by \(Ax-z\). In the scaled case, the residual used for checking is unscaled and is \(E^{-1}(Ax-z)\) instead.

Parameters

work Workspace

Definition at line 26 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calculate_dual_residuals()

void calculate_dual_residuals ( QPALMWorkspace * work )

Calculates the infinity norm of the dual residual and the residual of the subproblem and stores them in work->info->dua_res_norm and work->info->dua2_res_norm respectively.

The dual residual is given by \(\nabla \varphi\). In the scaled case, the residual used for checking is unscaled and is \(D^{-1}\nabla \varphi\) instead. If the work->settings->proximal is true, then the dual residual is \(\nabla \varphi - \frac{1}{\gamma}(x-x_0)\). If work->settings->proximal is true and the problem is scaled, then the dual residual is \(D^{-1}(\nabla \varphi - \frac{1}{\gamma}(x-x_0))\). The residual of the subproblem is \(\nabla \varphi\) or \(D^{-1}\nabla \varphi\) in the scaled case.

Parameters

work Workspace

Definition at line 36 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calculate_primal_tolerance()

void calculate_primal_tolerance ( QPALMWorkspace * work )

Calculates the primal tolerance and stores it in work->eps_pri.

For the primal tolerance an absolute and relative contribution are added. It is given by \(\epsilon_\textrm{abs} + \epsilon_\textrm{rel} \textrm{max}(\|Ax\|_\infty, \|z\|_\infty)\). In the scaled case, the relative contributions are unscaled and the primal tolerance is given by \(\epsilon_\textrm{abs} + \epsilon_\textrm{rel} \textrm{max}(\|E^{-1}Ax\|_\infty, \|E^{-1}z\|_\infty)\).

Parameters

work Workspace

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

Definition at line 67 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calculate_dual_tolerances()

void calculate_dual_tolerances ( QPALMWorkspace * work )

Calculates the dual tolerance for the problem and current subproblem and stores them in work->eps_dua and worl->eps_dua_in respectively.

For the dual tolerance an absolute and relative contribution are added. It is given by \(\epsilon_\textrm{abs} + \epsilon_\textrm{rel} \textrm{max}(\|Qx\|_\infty, \|q\|_\infty, \|A^T y\|_\infty)\). In the scaled case, the relative contributions are unscaled and the primal tolerance is given by \(\epsilon_\textrm{abs} + \epsilon_\textrm{rel}c^{-1}\textrm{max}(\|D^{-1}Qx\|_\infty, \|D^{-1}q\|_\infty, \|D^{-1}A^T y\|_\infty)\). The tolerance for the subproblem is given by the same formulas, with \(\epsilon_\textrm{abs,in}\) and \(\epsilon_\textrm{rel,in}\) instead of \(\epsilon_\textrm{abs}\) and \(\epsilon_\textrm{rel}\).

Parameters

work Workspace

Definition at line 83 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_solved()

c_int is_solved ( QPALMWorkspace * work )

Check whether the primal and dual residual norms are smaller than the primal and dual tolerances.

Parameters

work Workspace

Returns: Exitflag indicating whether the problem is solved.

Definition at line 106 of file termination.c.

Here is the caller graph for this function:

◆ is_primal_infeasible()

c_int is_primal_infeasible ( QPALMWorkspace * work )

Check whether the problem is primal infeasible.

The infeasibility criterion used here was introduced in [1]. The problem is primal infeasible if for \(\delta y = \Sigma\bigl(Ax-z)\bigr) \neq 0\), with \(\Sigma = \textrm{diag}(\sigma)\) the following condtions hold:

\begin{align*} \|A^T \delta y\|_\infty & \leq \varepsilon_\textrm{prim,inf} \|\delta y\|_\infty, \\ b_\textrm{max}^T [\delta y]_+ + b_\textrm{min}^T [\delta y]_- & \leq -\varepsilon_\textrm{prim,inf} \|\delta y\|_\infty. \end{align*}

In case the problems is scaled the conditions turn into the following:

\begin{align*} \|D^{-1}A^T \delta y\|_\infty & \leq \varepsilon_\textrm{prim,inf} \|E\delta y\|_\infty, \\ b_\textrm{max}^T [\delta y]_+ + b_\textrm{min}^T [\delta y]_- & \leq -\varepsilon_\textrm{prim,inf} \|E\delta y\|_\infty. \end{align*}

If the above conditions hold, \(\delta y\), or in the scaled case \(c^{-1} E\delta y\), is the certificate of primal infeasibility.

Parameters

work Workspace

Returns: Exitflag indicating whether the problem is primal infeasible.

Definition at line 111 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_dual_infeasible()

c_int is_dual_infeasible ( QPALMWorkspace * work )

Check whether the problem is dual infeasible.

The infeasibility criterion used here was introduced in [1]. The problem is dual infeasible if for \(\delta x = x-x_\textrm{prev} \neq 0\) the following condtions hold:

\begin{align*} \|Q\delta x\|_\infty &\leq \varepsilon_\textrm{dua, inf} \|\delta x\|_\infty, \\ q^T \delta x & \leq - \varepsilon_\textrm{dua, inf} \|\delta x\|_\infty, \end{align*}

\begin{align*} (A\delta x)_i = \begin{cases} \geq \varepsilon_{\rm dua,inf} \|\delta x\|_\infty & \textrm{if } b_{\textrm{max},i} = +\infty \\ \leq -\varepsilon_{\rm dua,inf} \|\delta x\|_\infty & \textrm{if } b_{\textrm{min},i} = -\infty \\ \in [-\varepsilon_{\rm dua,inf},\varepsilon_{\rm dua,inf}] \|\delta x\|_\infty & \textrm{if } b_{\textrm{max},i}, b_{\textrm{min},i} \in {\rm I\!R}. \end{cases} \end{align*}

In case the problems is scaled the conditions turn into the following:

\begin{align*} \|D^{-1}Q\delta x\|_\infty &\leq c \cdot \varepsilon_\textrm{dua, inf} \|D\delta x\|_\infty, \\ q^T \delta x & \leq - c \cdot \varepsilon_\textrm{dua, inf} \|D\delta x\|_\infty, \end{align*}

\begin{align*} (E^{-1}A\delta x)_i = \begin{cases} \geq \varepsilon_{\rm dua,inf} \|D\delta x\|_\infty & \textrm{if } b_{\textrm{max},i} = +\infty \\ \leq -\varepsilon_{\rm dua,inf} \|D\delta x\|_\infty & \textrm{if } b_{\textrm{min},i} = -\infty \\ \in [-\varepsilon_{\rm dua,inf},\varepsilon_{\rm dua,inf}] \|D\delta x\|_\infty & \textrm{if } b_{\textrm{max},i}, b_{\textrm{min},i} \in {\rm I\!R}. \end{cases} \end{align*}

If the above conditions hold, \(\delta x\), or in the scaled case \(D\delta x\), is the certificate of dual infeasibility.

Parameters

work Workspace

Returns: Exitflag indicating whether the problem is dual infeasible.

Definition at line 159 of file termination.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ store_solution()

void store_solution ( QPALMWorkspace * work )

Helper function to store the (unscaled) solution in the solution struct.

The primal/dual solution \(x,y\) is copied to work->solution->x, work->solution->y. In case the problem is scaled, the soltution is first unscaled, and the solution vectors \(Dx, c^{-1}Ey\) are stored in work->solution->x, work->solution->y.

Parameters

work Workspace

Definition at line 217 of file termination.c.

Here is the call graph for this function:

◆ check_subproblem_termination()

c_int check_subproblem_termination ( QPALMWorkspace * work )

Check whether the subproblem is solved.

This amounts to checking whether the residual of the subproblem smaller than or equal is to the tolerance of the subproblem, as mentioned in calculate_dual_residuals and calculate_dual_tolerances.

Parameters

work Workspace

Returns: Exitflag indicating whether the subproblem is solved.

Definition at line 229 of file termination.c.

Here is the caller graph for this function:

Detailed Description

Functions

Function Documentation

◆ calculate_residual_norms_and_tolerances()

◆ calculate_primal_residual()

◆ calculate_dual_residuals()

◆ calculate_primal_tolerance()

◆ calculate_dual_tolerances()

◆ is_solved()

◆ is_primal_infeasible()

◆ is_dual_infeasible()

◆ store_solution()

◆ check_subproblem_termination()