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.

Example:

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([...])	Perform parallel grid search Newton optimization for symmetric N-player equilibria.
grid_search_newton_4player_xyz_over_reach(...)	Grid search Newton optimization over a range of reach parameters.
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(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_dim (int) – Number of grid points per dimension (x, y, z).

• bounds (Tuple[float, float]) – Tuple of (min, max) bounds for grid coordinates.

• max_workers (Optional[int]) – Number of parallel workers (defaults to CPU count).

• verbose (bool) – Whether to print progress information.

• position_tolerance (float) – Tolerance for considering two positions as unique.

• **newton_kwargs –

  Additional arguments passed to newton_root_finder.

Returns:

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

Return type:

Dict

Raises:

ValueError – If num_agents < 3.

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_parameters (Union[List[float], np.ndarray]) – Array of reach/influence parameter values to iterate over.

• tolerance (float) – Convergence tolerance for Newton method.

• tolerated_agents (int) – Number of agents that must converge.

• percentage (float) – Percentage parameter (usage to be determined).

Returns:

None (placeholder)

Return type:

None

Raises:

NotImplementedError – This method is not yet implemented.

newton_adaptive(initial_guess, **kwargs)

Convenience method for adaptive step Newton optimization.

Calls newton_root_finder with method=’adaptive’.

Parameters:

• initial_guess (torch.Tensor) – Initial agent positions.

• **kwargs –

  Additional arguments passed to newton_root_finder.

Returns:

Newton method results dictionary.

Return type:

Dict

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_guess (torch.Tensor) – Initial agent positions from which to start Newton iteration.

• tolerance (Optional[float]) – Convergence tolerance for position changes (default: instance tolerance).

• max_iter (int) – Maximum number of Newton iterations.

• verbose (bool) – Whether to print progress information during iteration.

• enforce_bounds (bool) – Whether to clamp positions to domain bounds.

• method (str) – Step control method (‘trust_region’ or ‘adaptive’).

• tolerated_agents (Optional[int]) – Number of agents that must satisfy convergence criteria.

• stagnation_window (int) – Number of iterations to check for lack of improvement.

• stagnation_tolerance (float) – Minimum improvement required to avoid stagnation detection.

• return_detailed_history (bool) – If True, return full position/gradient history; if False, save memory.

• tolerance_grad (float) – Convergence tolerance for gradient magnitude.

Returns:

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

Return type:

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

Raises:

RuntimeError – If linear solve fails during Newton step computation.

newton_trust_region(initial_guess, **kwargs)

Convenience method for trust region Newton optimization.

Calls newton_root_finder with method=’trust_region’.

Parameters:

• initial_guess (torch.Tensor) – Initial agent positions.

• **kwargs –

  Additional arguments passed to newton_root_finder.

Returns:

Newton method results dictionary.

Return type:

Dict