File numerics/src/tools/Newton_methods.h

Go to the source code of this file

Data structure and function for using Newton based solvers.

The reference used for the implementation is “Finite-Dimensional Variational

Inequalities and Complementarity Problems” by Facchinei and Pang.

More precisely, the function newton_LSA() is algorithm VFBLSA.

Defines

NEWTON_STATS_DESC_DIR
NEWTON_STATS_ITERATION
NEWTON_STATS_NEWTON_STEP

Typedefs

typedef void (*compute_F_merit_ptr)(void *data_opaque, double *z, double *F, double *F_merit)
typedef void (*compute_F_ptr)(void *data_opaque, double *z, double *F)

Enums

enum NEWTON_SOLVER

Values:

SICONOS_NEWTON_LSA = 10000
enum SICONOS_GOLDSTEIN_IPARAM

Values:

SICONOS_IPARAM_GOLDSTEIN_ITERMAX = 7
enum SICONOS_NEWTON_DPARAM

Values:

SICONOS_DPARAM_LSA_ALPHA_MIN = 2

line-search

SICONOS_DPARAM_GOLDSTEIN_C = 3
SICONOS_DPARAM_GOLDSTEIN_ALPHAMAX = 4
enum SICONOS_NEWTON_IPARAM

Values:

SICONOS_IPARAM_LSA_NONMONOTONE_LS = 3

line search based algo use this

SICONOS_IPARAM_LSA_NONMONOTONE_LS_M = 4
SICONOS_IPARAM_LSA_FORCE_ARCSEARCH = 5
SICONOS_IPARAM_LSA_SEARCH_CRITERION = 6
SICONOS_IPARAM_STOPPING_CRITERION = 10
enum SICONOS_NMS_DPARAM

Values:

SICONOS_DPARAM_NMS_DELTA = 2

non-monotone specific part

SICONOS_DPARAM_NMS_DELTA_VAR = 3
SICONOS_DPARAM_NMS_SIGMA = 4
SICONOS_DPARAM_NMS_ALPHA_MIN_WATCHDOG = 5
SICONOS_DPARAM_NMS_ALPHA_MIN_PGRAD = 6
SICONOS_DPARAM_NMS_MERIT_INCR = 7
enum SICONOS_NMS_IPARAM

Values:

SICONOS_IPARAM_NMS_WATCHDOG_TYPE = 7

non-monotone specific part

SICONOS_IPARAM_NMS_PROJECTED_GRADIENT_TYPE = 8
SICONOS_IPARAM_NMS_N_MAX = 9
enum SICONOS_STOPPING_CRITERION

Values:

SICONOS_STOPPING_CRITERION_RESIDU = 0
SICONOS_STOPPING_CRITERION_STATIONARITY = 1
SICONOS_STOPPING_CRITERION_RESIDU_AND_STATIONARITY = 2
SICONOS_STOPPING_CRITERION_USER_ROUTINE = 3

Functions

static void init_lsa_functions(functions_LSA *functions, compute_F_ptr compute_F, compute_F_merit_ptr merit_function)

Set the functions to compute F and F_merit and all the other pointers to NULL.

Parameters
  • functions: structure to fill

  • compute_F: function to compute F

  • merit_function: function to compute F_merit

void newton_LSA(unsigned n, double *z, double *w, int *info, void *data, SolverOptions *options, functions_LSA *functions)

Newton algorithm for finding the zero of a function with a line search.

Mainly used for equation-based reformulation of CP or VI.

Parameters
  • n: size of the problem

  • z: variable

  • w: value of F(z)

  • info: solver-specific values

  • data: opaque problem definition

  • options: options for this solver

  • functions: struct of function pointers to compute F, H and the error

void newton_LSA_free_solverOptions(SolverOptions *options)

clear the solver-specific data

Parameters
  • options: the SolverOption structure

void newton_lsa_set_default(SolverOptions *options)
void set_lsa_params_data(SolverOptions *options, NumericsMatrix *mat)

Set the parameters and data for newton_LSA.

Parameters
  • options: the solver option

  • mat: the

Variables

const char *const SICONOS_NEWTON_LSA_STR
struct functions_LSA
#include <Newton_methods.h>

Struct holding the necessary pointers to functions needed by the newton_LSA() procedure.

Public Members

int (*compute_descent_direction)(void *data_opaque, double *z, double *w, double *descent_dir, SolverOptions *options)

function to get the descent direction, used for instance in the Newton-Josephy method

void (*compute_error)(void *data_opaque, double *z, double *w, double *nabla_theta, double tol, double *err)

function to compute the error

compute_F_ptr compute_F

function to evaluate w = F(z)

compute_F_merit_ptr compute_F_merit

function to evaluate F_merit(z) (e.g.

F_FB, F_{min}, …)

void (*compute_H)(void *data_opaque, double *z, double *w, double *workV1, double *workV2, NumericsMatrix *H)

function to get an element H of T

void (*compute_H_desc)(void *data_opaque, double *z, double *w, double *workV1, double *workV2, NumericsMatrix *H_desc)

function to get an element H_desc of T_desc, optional

void (*compute_JacTheta_merit)(void *data_opaque, double *z, double *w, double *F_merit, double *workV, double *JacThetaF_merit, SolverOptions *options)

function to get the descent direction, used for instance in the Newton-Josephy method

void (*compute_RHS_desc)(void *data_opaque, double *z, double *w, double *F_desc)

function to evaluate F_desc(z) (e.g.

F_FB, F_{min}, …), optional

void *(*get_set_from_problem_data)(void *problem)

Function returning the set description from the.

int (*ls_failure_fn)(void *problem, double *z, double *w, double *descent_dir, double err, size_t status)

Function to call when the line search fails.

struct newton_LSA_data

Public Members

NumericsMatrix *H

matrix

struct newton_LSA_param

Public Members

bool check_dir_quality

Check the quality of the descent direction (Eqn 9.1.6 p.

805 in Facchinei & Pang)

bool keep_H

keep the matrix H untouched.

Only used in the dense case, where a copy of the matrix is factorized

double p

p value for the acceptance test of the direction solution of the linear system

double rho

coefficient for the direction check

double sigma

ratio for the decrease in norm of the C-function ( \(gamma'\) in VFBLSA)

struct newton_stats

Public Members

double alpha

value of the LS parameter

int id

id of this structure

double merit_value

value of the merit function at the end of the iteration

unsigned int status

status of this newton iteration