Newton Search

Root Finding Module

This module provides Newton’s method and related numerical root-finding algorithms for locating equilibrium points in adaptive dynamics systems. It includes trust region and adaptive step methods for robust convergence, as well as parallel grid search capabilities for exploring multiple initial conditions.

The module is designed to work with the AdaptiveEnv class and provides efficient methods for finding gradient zeros, which correspond to equilibria in influencer game environments.

Dependencies:

• InflGame.utils.validation

• InflGame.adaptive.jacobian

• NumPy, PyTorch

• concurrent.futures (for parallel processing)

Usage:

The newton_method class can be used to find equilibrium positions by solving for gradient zeros using Newton’s method with various step control strategies. It supports parallel grid searches for systematic exploration of the equilibrium landscape.

Examples

from InflGame.adaptive.root_finding import newton_method
from InflGame.adaptive.grad_func_env import AdaptiveEnv
import torch
import numpy as np

# Initialize adaptive environment
field = AdaptiveEnv(
    num_agents=3,
    agents_pos=np.array([0.2, 0.5, 0.8]),
    parameters=torch.tensor([0.1, 0.1, 0.1]),
    resource_distribution=torch.tensor([10.0, 20.0, 30.0]),
    bin_points=np.array([0.1, 0.4, 0.7]),
    infl_configs={'infl_type': 'gaussian'},
    domain_type='1d',
    domain_bounds=[0, 1]
)

# Initialize Newton method
newton = newton_method(
    field=field,
    num_agents=3,
    agents_pos=np.array([0.2, 0.5, 0.8]),
    parameters=torch.tensor([0.1, 0.1, 0.1]),
    resource_distribution=torch.tensor([10.0, 20.0, 30.0]),
    bin_points=np.array([0.1, 0.4, 0.7]),
    infl_configs={'infl_type': 'gaussian'},
    domain_type='1d',
    domain_bounds=[0, 1]
)

# Find equilibrium
initial_guess = torch.tensor([0.3, 0.5, 0.7])
result = newton.newton_root_finder(
    initial_guess=initial_guess,
    tolerance=1e-6,
    method='trust_region'
)

if result['converged']:
    print(f"Found equilibrium at: {result['final_position']}")

Classes

class InflGame.adaptive.newton_search.newton_method(field, num_agents, agents_pos, parameters, resource_distribution, bin_points, infl_configs={'infl_type': 'gaussian'}, learning_rate_type='cosine', learning_rate=[0.0001, 0.01, 15], time_steps=100, fp=0, infl_cshift=False, cshift=0, infl_fshift=False, Q=0, domain_type='1d', domain_bounds=[0, 1], tolerance=1e-05, tolerated_agents=None, ignore_zero_infl=False)

Newton’s method for finding gradient zeros in adaptive dynamics.

This class implements Newton’s method with various step control strategies (trust region, adaptive stepping) for robustly finding equilibrium points in adaptive dynamics systems. Equilibria correspond to points where the gradient of the agents’ objective functions equals zero, which represent Nash equilibria in the influencer game framework.

The class supports:

• Multiple step control methods (trust region, adaptive)

• Parallel grid search over initial conditions

• Stagnation detection and handling

• Bounded optimization for constrained domains

• Comprehensive convergence diagnostics

This class is designed to work with InflGame.adaptive.grad_func_env.AdaptiveEnv and uses Jacobian matrices computed by InflGame.adaptive.jacobian for Newton steps.

Methods

grid_search_newton_4player_xyz_over_reach(...)	Grid search Newton optimization over a range of reach parameters.
grid_search_newton_hyperplane_xyz([...])	Perform parallel grid search Newton optimization for symmetric N-player equilibria.
newton_adaptive(initial_guess, **kwargs)	Convenience method for adaptive step Newton optimization.
newton_root_finder(initial_guess[, ...])	Newton's method for finding gradient zeros with trust region or adaptive stepping.
newton_trust_region(initial_guess, **kwargs)	Convenience method for trust region Newton optimization.

grid_search_newton_4player_xyz_over_reach(reach_parameters, tolerance, tolerated_agents, percentage=1.0)

Grid search Newton optimization over a range of reach parameters.

Warning

This method is a placeholder and is not yet implemented.

Parameters:

reach_parametersUnion[List[float], np.ndarray]

Array of reach/influence parameter values to iterate over.

tolerancefloat

Convergence tolerance for Newton method.

tolerated_agentsint

Number of agents that must converge.

percentagefloat

Percentage parameter (usage to be determined).

Returns:

None

None (placeholder)

Raises:

NotImplementedError

This method is not yet implemented.

grid_search_newton_hyperplane_xyz(grid_points_per_dim=5, bounds=(0, 1), max_workers=None, verbose=True, position_tolerance=0.0001, **newton_kwargs)

Perform parallel grid search Newton optimization for symmetric N-player equilibria.

This method systematically explores the equilibrium landscape by running Newton’s method from a grid of initial positions with a symmetric structure. The position format constrains middle agents to have the same position, which is appropriate for symmetric influence games.

Position Format:

For N agents (N ≥ 3):

• Agent 1: position x (varies independently)

• Agents 2 to N-1: all share position y (vary together)

• Agent N: position z (varies independently)

This gives a 3D grid search over (x, y, z) regardless of the number of agents.

Algorithm:

1. Generate grid of (x, y, z) combinations

2. For each grid point, create initial position vector (x, y, y, …, y, z)

3. Run Newton’s method from each initial position (in parallel)

4. Collect and deduplicate converged equilibria

5. Compute statistics on convergence behavior

Parameters:

grid_points_per_dimint

Number of grid points per dimension (x, y, z).

boundsTuple[float, float]

Tuple of (min, max) bounds for grid coordinates.

max_workersOptional[int]

Number of parallel workers (defaults to CPU count).

verbosebool

Whether to print progress information.

position_tolerancefloat

Tolerance for considering two positions as unique.

**newton_kwargs

Additional arguments passed to newton_root_finder.

Returns:

Dict

Dictionary containing: - ‘all_results’: All Newton trial results - ‘unique_final_positions’: List of unique equilibria found - ‘successful_results’: All converged positions (including duplicates) - ‘statistics’: Convergence statistics (mean/std gradient norms, iterations) - ‘convergence_rate’: Fraction of grid points that converged - ‘grid_info’: Grid configuration details

Raises:

ValueError

If num_agents < 3.

Examples

# Find equilibria for 4-player game
results = newton.grid_search_newton_4player_xyz(
    grid_points_per_dim=10,
    bounds=(0, 1),
    max_workers=8,
    verbose=True,
    tolerance=1e-6,
    max_iter=1000,
    method='trust_region'
)

print(f"Found {results['unique_points']} unique equilibria")
for i, eq in enumerate(results['unique_final_positions']):
    print(f"Equilibrium {i+1}: {eq}")

newton_adaptive(initial_guess, **kwargs)

Convenience method for adaptive step Newton optimization.

Calls newton_root_finder with method=’adaptive’.

Parameters:

initial_guesstorch.Tensor

Initial agent positions.

**kwargs

Additional arguments passed to newton_root_finder.

Returns:

Dict

Newton method results dictionary.

newton_root_finder(initial_guess, tolerance=None, max_iter=20000, verbose=True, enforce_bounds=True, method='trust_region', tolerated_agents=None, stagnation_window=50, stagnation_tolerance=1e-05, return_detailed_history=False, tolerance_grad=1e-05)

Newton’s method for finding gradient zeros with trust region or adaptive stepping.

This method implements Newton’s method to find equilibrium points by solving for positions where the gradient equals zero. It uses the Jacobian matrix (computed via InflGame.adaptive.jacobian.jacobian_matrix) to determine Newton steps and includes sophisticated step control mechanisms for robust convergence.

The algorithm:

1. Computes gradient at current position

2. Computes Jacobian matrix with stability checks

3. Solves linear system for Newton direction

4. Applies step control (trust region or adaptive)

5. Enforces domain bounds if specified

6. Checks convergence criteria

7. Detects and handles stagnation

Step Control Methods:

• trust_region: Limits step size to maximum radius, prevents overshooting

• adaptive: Tries multiple step sizes, accepts one that reduces gradient norm

Parameters:

initial_guesstorch.Tensor

Initial agent positions from which to start Newton iteration.

toleranceOptional[float]

Convergence tolerance for position changes (default: instance tolerance).

max_iterint

Maximum number of Newton iterations.

verbosebool

Whether to print progress information during iteration.

enforce_boundsbool

Whether to clamp positions to domain bounds.

methodstr

Step control method (‘trust_region’ or ‘adaptive’).

tolerated_agentsOptional[int]

Number of agents that must satisfy convergence criteria.

stagnation_windowint

Number of iterations to check for lack of improvement.

stagnation_tolerancefloat

Minimum improvement required to avoid stagnation detection.

return_detailed_historybool

If True, return full position/gradient history; if False, save memory.

tolerance_gradfloat

Convergence tolerance for gradient magnitude.

Returns:

Dict[str, Union[torch.Tensor, bool, List]]

Dictionary containing: - ‘final_position’: Converged position - ‘converged’: Whether convergence criteria were met - ‘final_gradient_norm’: Gradient norm at final position - ‘iterations’: Number of iterations performed - ‘termination_reason’: Why iteration stopped (‘converged’, ‘stagnation’, ‘max_iterations’) - ‘position_matrix’: (if return_detailed_history=True) Full position history - ‘gradient_history’: (if return_detailed_history=True) Full gradient history

Raises:

RuntimeError

If linear solve fails during Newton step computation.

Examples

initial_guess = torch.tensor([0.3, 0.5, 0.7])
result = newton.newton_root_finder(
    initial_guess=initial_guess,
    tolerance=1e-6,
    max_iter=1000,
    method='trust_region',
    verbose=True
)

if result['converged']:
    equilibrium = result['final_position']
    print(f"Equilibrium found: {equilibrium}")
    print(f"Gradient norm: {result['final_gradient_norm']:.2e}")

newton_trust_region(initial_guess, **kwargs)

Convenience method for trust region Newton optimization.

Calls newton_root_finder with method=’trust_region’.

Parameters:

initial_guesstorch.Tensor

Initial agent positions.

**kwargs

Additional arguments passed to newton_root_finder.

Returns:

Dict

Newton method results dictionary.