# File numerics/src/tools/NMS.h#

Go to the source code of this file

Non-Monotone Stabilisation Scheme for path search.

Main reference for this implementation: Linear Algebra Enhancements to the PATH Solver, by Li, Ferris and Munson

Functions

int NMS(NMS_data *data_NMS, void *data, functions_LSA *functions, double *z, double *z_N, int force_watchdog_step, int force_d_step_merit_check, double check_ratio)#

Non-Monotone Stabilisation scheme.

Parameters:
• data_NMS – the NMS data

• data – opaque data for the computation of the problem

• functions – struct holding the functions for the computation of F, the merit function

• z[inout] on input, current iterate of the solution; on output, the new iterate

• z_N – proposed iterate for the solution

• force_watchdog_step – force a watchdog step if the path search failed!

• force_d_step_merit_check – accept the point at d_step even if the merit function increases. Usually this means that the normal map norm decreases a lot

• check_ratio – if the norm of the normal map decreases, allow the merit to increase by that much

Returns:

0 if succeeded, 1 if failed

NMS_data *create_NMS_data(unsigned size, int matrix_type, int *iparam, double *dparam)#

create (allocate) a NMS_data struct and do some allocation work

Parameters:
• size – size of the problem

• matrix_type – type of the NumericsMatrix used: dense, sparse, …

• iparam – vector of integer parameters from a SolverOptions struct

• dparam – vector of double parameters from a SolverOptions struct

Returns:

the allocated struct

void free_NMS_data(NMS_data *data)#

free a NMS_data struct

Parameters:

data – the structure to free

static inline double *NMS_get_F(double *workspace, int n)#

Get the F vector from the workspace data.

Parameters:
• workspace – the workspace holding the allocated vectors

• n – size of vector

Returns:

the F vector

static inline double *NMS_get_F_merit(double *workspace, int n)#

Get the F_merit vector from the workspace data.

Parameters:
• workspace – the workspace holding the allocated vectors

• n – size of vector

Returns:

the F_merit vector

static inline double *NMS_get_JacTheta_F_merit(double *workspace, int n)#

Get the JacTheta_F_merit vector from the workspace data.

Parameters:
• workspace – the workspace holding the allocated vectors

• n – size of vector

Returns:

the JacTheta_F_merit vector

static inline double *NMS_get_dir(double *workspace, int n)#

Get the vector for the descent direction from the workspace data.

Parameters:
• workspace – the workspace holding the allocated vectors

• n – size of vector

Returns:

the vector for the descent direction

static inline double *NMS_get_generic_workV(double *workspace, int n)#

Get the workV vector from the workspace data.

Parameters:
• workspace – the workspace holding the allocated vectors

• n – size of vector

Returns:

the workV vector

static inline double *NMS_checkpoint_0(NMS_data *data_NMS, unsigned n)#

Get the z_c(0) from the workspace data.

Parameters:
• data_NMS – the data for the NMS scheme

• n – size of vector

Returns:

the checkpoint z_c(0)

static inline double *NMS_checkpoint_T(NMS_data *data_NMS, unsigned n)#

Get the z_c(T) from the workspace data.

Parameters:
• data_NMS – the data for the NMS scheme

• n – size of vector

Returns:

the checkpoint z_c(T)

static inline double *NMS_bestpoint(NMS_data *data_NMS, unsigned n)#

Parameters:
• data_NMS – the data for the NMS scheme

• n – size of vector

Returns:

the bestpoint z_b

static inline int check_nmd_criterion(double theta_iter, double ref_merit, double sigma, double dotprod)#

check the non-monotone descent criterion

Parameters:
• theta_iter – current theta value

• ref_merit – the reference value for the merit function

• sigma – the $$\sigma$$ parameter

• dotprod – the value of the inner product between JacThetaF_merit and the descent direction

Returns:

0 if the step is accepted, 1 otherwise

struct path_record#
#include <NMS.h>

Save the path generated by the algorithm.

Public Members

int *final_basis#

last basis before exit

int *basis_change#

record of the changes in the basis (leaving variable and index) use to reconstruct the path.

it is used as a circular buffer

int circular_indx#

index to mark the current position in the buffer

struct NMS_data#
#include <NMS.h>

Data for the Non-Monotone Stabilisation scheme.

Public Members

unsigned size#

dimension of the space

int watchdog_search_type#

type of search for the watchdog step: 0 -> line search, 1 -> arcsearch, 2 -> path search

type of search for the projected gradient step: 0 -> line search, 1 -> arc search

double delta#

acceptable distance between 2 iterates to qualify as d-step.

Value is updated at each iteration

double delta_var#

variation of delta

double sigma#

value for the line search decrease test

double alpha_min_watchdog#

min value for alpha in line or arc search

min value for alpha in line or arc search

int n#

current number of d_step taken

int n_max#

max number of d_step taken without checking the merit value (m-step)

double ref_merit#

reference value for the merit function

double merit_incr#

allowed increment in the merit function for d_step

void *ref_merit_data#

data struct containing the data to update the reference value

double *checkpoint#

checkpoint (z_c(0), z_c(T)), of size 2*n

double delta_checkpoint#

value of delta at checkpoint

double *bestpoint#

best point, used for projected gradient step

double merit_bestpoint#

value of the merit function at the best point

double delta_bestpoint#

value of delta at best point

double *workspace#

allocation memory for all the necessary computations

NumericsMatrix *H#

NumericsMatrix for the computation of the jacobian matrix.

void *set#

set where z is constrained

path_record *path_data#

record of the path generated by the algorithm

search_data *ls_data#

data for the line search