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.

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)

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

bool newton_LSA_check_solverId(int solverId)

Check whether the solver uses the Newton_LSA framework or not.

Return
true if the solver is using newton_LSA, false otherwise
Parameters
  • solverId: the solver id

void newton_lsa_default_SolverOption(SolverOptions *options)

Set some default values in the SolverOption when the solver is based on newton_LSA()

Parameters
  • options: the struct to modify

void newton_LSA_free_solverOptions(SolverOptions *options)

clear the solver-specific data

Parameters
  • options: the SolverOption structure

void set_lsa_params_data(SolverOptions *options, NumericsMatrix *mat)

Set the parameters and data for newton_LSA.

Parameters
  • options: the solver option
  • mat: the

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