QPALM
A proximal augmented Lagrangian method for QPs.
Functions
termination.c File Reference

Routines to check the termination and infeasibility criteria. More...

#include "termination.h"
#include "lin_alg.h"
#include "constants.h"
#include "global_opts.h"
#include "util.h"
#include "iteration.h"

Functions

c_int check_termination (QPALMWorkspace *work)
 Checks whether the problem is solved or infeasible and updates the status accordingly. More...
 
void calculate_residuals_and_tolerances (QPALMWorkspace *work)
 Calls the primal and dual residual and tolerance routines. More...
 
void calculate_primal_residual (QPALMWorkspace *work)
 Calculates the infinity norm of the primal residual and stores it in work->info->pri_res_norm. More...
 
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. More...
 
void calculate_primal_tolerance (QPALMWorkspace *work)
 Calculates the primal tolerance and stores it in work->eps_pri. More...
 
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. More...
 
c_int is_solved (QPALMWorkspace *work)
 Check whether the primal and dual residual norms are smaller than the primal and dual tolerances. More...
 
c_int is_primal_infeasible (QPALMWorkspace *work)
 Check whether the problem is primal infeasible. More...
 
c_int is_dual_infeasible (QPALMWorkspace *work)
 Check whether the problem is dual infeasible. More...
 
void store_solution (QPALMWorkspace *work)
 Helper function to store the (unscaled) solution in the solution struct. More...
 
c_int check_subproblem_termination (QPALMWorkspace *work)
 Check whether the subproblem is solved. More...
 

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.

Function Documentation

◆ 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
workWorkspace

◆ 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
workWorkspace

◆ 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
workWorkspace

◆ 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
workWorkspace

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.

◆ calculate_residuals_and_tolerances()

void calculate_residuals_and_tolerances ( QPALMWorkspace *  work)

Calls the primal and dual residual and tolerance routines.

Parameters
workWorkspace

◆ 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
workWorkspace
Returns
Exitflag indicating whether the subproblem is solved.

◆ check_termination()

c_int check_termination ( QPALMWorkspace *  work)

Checks whether the problem is solved or infeasible and updates the status accordingly.

The calculation of residuals and tolerances and infeasibility criteria is delegated to other functions. If the problem is solved, the primal/dual solution is stored in work->solution->x and work->solution->y. If the problem is primal infeasible, the certificate of primal infeasibility is stored in work->delta_y. If the problem is dual infeasible, the certificate of dual infeasibility is stored in work->delta_x.

Parameters
workWorkspace
Returns
Exitflag indicating the problem is solved or infeasible.

◆ 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
workWorkspace
Returns
Exitflag indicating whether the problem is dual infeasible.

◆ 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
workWorkspace
Returns
Exitflag indicating whether the problem is primal infeasible.

◆ 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
workWorkspace
Returns
Exitflag indicating whether the problem is solved.

◆ 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
workWorkspace
Generated by   doxygen 1.8.15