Overview of Trust-Region Methods, algorithms and implementation examples

Overview of Trust-Region Methods

Trust-Region Methods (Trust-Region Methods) are algorithms for solving non-linear optimisation problems, designed to overcome the challenges of gradient descent and the Newton method described in ‘Overview, algorithms and implementation of the Newton method’. In this method, the approach is to approximate the optimisation problem within a small region (the confidence region) and iterate to find the optimal solution within that region.

The confidence region here is a radius-constrained region defined around the current point, and the algorithm approximates the objective function only within this region to determine the next search point.

The non-linear objective function is represented by a second-order approximation model (e.g. up to the second-order term of the Taylor expansion), which approximates the objective function \( f(x) \) around the current point \( x_k \) as follows.
\[
m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p
\] – \( \nabla f(x_k) \): gradient
– \( B_k \): Hesse matrix or its approximation
– \( p \): search direction

The search direction \( p \) is optimised to the extent that the following constraints are satisfied.
\[
\| p \| \leq \Delta_k
\] – \( \Delta_k \): radius of the confidence region

Furthermore, based on the results of the evaluation at the new point, the radius of the confidence region \( \Delta_k \) is enlarged or reduced as follows

• If the approximate model is good, \( \Delta_k \) is enlarged.
• If it is not suitable, \( \Delta_k \) is reduced.

As a convergence decision, determine if the norm of the gradient or the radius of the confidence region is small enough and stop.

The flow of these algorithms can be summarised as follows.

1. set the initial point \( x_0 \) and the initial confidence region radius \( \Delta_0 \)
2. construct an approximate model \( m_k(p) \).
3. optimise \( m_k(p) \) within the confidence region and find the search direction \( p_k \).
4. calculate \( f(x_k + p_k) \) and calculate the ratio \( \rho_k \) to assess the reliability of the approximate model:
\[
\rho_k = \frac{f(x_k) – f(x_k + p_k)}{m_k(0) – m_k(p_k)}
\] 5. based on \( \rho_k \), determine that
– If \( \rho_k \) is large: enlarge the confidence region, \( x_{k+1} = x_k + p_k \).
– If \( \rho_k \) is small: reduce the confidence region and re-evaluate the point.
6. repeat until convergence conditions are met.

Features and advantages include.

• High stability: can be applied to problems where the objective function changes rapidly or is not convex, which is difficult with gradient descent and Newtonian methods.
• Robust: can cope adequately even when the Hesse matrix is non-positive definite.
• Robustness to local optimisation: the model approximates the objective function accurately within the confidence region and thus captures local behaviour well.

Reliability iteration methods have become one of the most widely used methods for solving complex constrained optimisation and non-linear problems.

implementation example

Below is a simple example of implementing Trust-Region Methods (Trust-Region Methods) in Python. The implementation makes use of the trust-region algorithm contained in the scipy.optimise library.

Objective function: minimises a non-linear function \(f(x,y)=(x-1)^2+2(y-2)^2\) as the objective function.

Code example.

import numpy as np
from scipy.optimize import minimize

# Objective function definition
def objective_function(x):
    # x[0] = x, x[1] = y
    return (x[0] - 1)**2 + 2 * (x[1] - 2)**2

# Gradient (first derivative of the objective function)
def gradient(x):
    grad_x = 2 * (x[0] - 1)
    grad_y = 4 * (x[1] - 2)
    return np.array([grad_x, grad_y])

# Setting the initial point
initial_guess = np.array([0.0, 0.0])  # Starts at x=0, y=0

# Perform optimisation
result = minimize(
    objective_function,         # Objective function
    initial_guess,              # Initial point
    method='trust-constr',      # Trust Region Method
    jac=gradient,               # Provision of gradients
    options={'verbose': 1}      # Output detailed logs.
)

# Show result
print("nOptimisation results:")
print(f"Optimised variables.: {result.x}")
print(f"minimum value: {result.fun}")
print(f"convergence status: {result.message}")

Running result: if the initial point is set to ([0.0,0.0]), the following results are obtained.

Optimization terminated successfully    (Exit mode 0)
            Current function value: 0.0
            Iterations: 7
            Function evaluations: 8
            Gradient evaluations: 7

Optimisation results: 
optimised variables: [1. 2.] 
Minimum value: 0.0 
Convergence status: Optimisation terminated successfully

Description.

1. Objective function: minimise \((x-1)^2+2(y-2)^2\), taking \((x,y)=(1,2)\)で\(f(x.y)=0\) as the minimum value.
2. Algorithm: use the trust region method by specifying method=‘trust-constr’. The gradient is explicitly specified to improve efficiency.
3. Result: the value of the best variable is displayed in result.x, the minimum value in result.fun and the convergence status in result.message.

Application: this code can also be applied to more complex constrained optimisation problems and multi-dimensional non-linear problems, where constraint conditions (equality or inequality constraints) can be included by setting the constraints argument.

Application examples

Confidence region methods are used in many fields due to the high robustness of non-linear optimisation. Typical applications are described below.

1. hyperparameter optimisation of machine learning models

• Abstract: Adjust hyper-parameters (e.g. learning rate, regularisation parameters, tree depth, etc.) to maximise the performance of a machine learning algorithm.
• Examples: optimising the learning rate and batch size of neural networks. A model with a non-convex loss function with unstable gradients, where a confidence region method is used.

2. constrained optimisation problems

• Abstract: Confidence region methods can be effective in problems with equality and inequality constraints.
• Examples.
  – Portfolio optimisation: applied to the problem of minimising risk while optimising asset allocation. Find optimal solutions that satisfy constraints (e.g. total investment or risk thresholds).
  – Industrial design: cost minimisation problems in plant layout design and resource allocation.

3. fluid dynamics and structural analysis

•  Deals with the non-linearity of fluid dynamics and structural analysis models in simulation-based design optimisation problems.
• Examples.
  – Aircraft design: optimising wing geometry (maximising the lift-drag ratio).
  – Bridge and building design: geometry optimisation of structures considering material strength and loading conditions.

4. medical applications

• Abstract: application of confidence region methods in medical data analysis and treatment plan optimisation to find the best treatment for individual patients.
• Examples.
  – Radiotherapy: optimising radiation dose while maximising the effect on the tumour and minimising the effect on normal tissue.
  – Medical equipment design: adjusting the parameters of ultrasound and MRI equipment.

5. robotics

• Abstract: Explore pathways to achieve goals while improving energy efficiency in robot control and motion planning.
• Examples.
  – Motion planning for arm robots: optimising the path to the target position while avoiding obstacles in the workspace.
  – Autonomous mobile robots: solving shortest path problems in dynamic environments.

6. energy

• Abstract: helps optimise the electricity grid and the efficient use of renewable energy.
• Examples.
  – Optimisation of the electricity supply system: adjusting the operating plan of power plants to maximise energy efficiency.
  – Wind power: optimise turbine layout.

7. natural science applications

• Abstract: used for experimental data analysis and modelling in chemistry and physics.
• Examples.
  – Molecular dynamics: energy minimisation problems for molecular structures.
  – Astronomy: orbit optimisation of celestial bodies based on observational data.

8. economics and marketing

• Abstract: Confidence region methods are used in marketing strategy optimisation and economic modelling.
• Examples.
  – Advertising budget optimisation: maximising ROI (return on investment) by adjusting budget allocations to different media.
  – Pricing: optimising prices in dynamic pricing problems (surge pricing) described in”Machine learning and algorithms used for surge pricing and examples of implementation“.

9. software engineering

• Abstract: trust region methods are used for software optimisation problems and resource allocation.
• Examples.
  – Scheduling: optimising the order of execution and allocation of tasks to increase overall throughput.
  – Cloud resource optimisation: optimise server utilisation and reduce costs.

The trust region method is a versatile algorithm for complex non-linear constraint optimisation problems in diverse fields, and its robustness and efficiency have led to its application in a wide range of settings, from industry to scientific research.

reference book

Learn about reference books and literature on Trust-Region Methods.

Basic books.

1. ‘Numerical Optimisation’ by Jorge Nocedal and Stephen Wright
– Abstract: Provides a detailed description of non-linear optimisation methods in general, including trust-region methods. Contains a good deal of theoretical background and information on implementation.
– Features: details of algorithms and variations of confidence region methods. Discusses real-world applications and software implementations.
– Publication: Springer.

2. ‘Practical Methods of Optimisation’ by R. Fletcher
– Abstract: A classic book covering the basics and applications of optimisation methods. It introduces the basic concepts and implementation examples of confidence region methods.
– Features: connection with quadratic programming. Application methods for constrained problems.
– Publication: Wiley.

3. ‘Introduction to Nonlinear Optimisation: Theory, Algorithms, and Applications with MATLAB’ by Amir Beck
– Abstract: Provides the fundamentals of non-linear optimisation and examples of MATLAB implementations. The confidence region method is also included.
– Features: concrete implementations of confidence region methods. Software-based optimisation problem solving.

4. ‘Nonlinear Programming’ by Dimitri P. Bertsekas
– Abstract: Book dedicated to non-linear optimisation. The theory and applications of confidence region methods are explored in depth.
– Features: discussion on asymptotic convergence. Applications to constrained optimisation problems.

Related papers.

1. ‘Trust Region Methods’ by A. R. Conn, N. I. M. Gould, and Ph. L. Toint
– Abstract: A comprehensive technical book on the theory, algorithms and applications of trust region methods. Intended for researchers and advanced users.
– DOI: 10.1137/1.9780898719857
– Publication: SIAM.

2. ‘Trust-Region Methods in Nonlinear Programming’ by Moré, J. J. and Sorensen, D. C.
– Abstract: A paper on basic concepts and applications in trust-region methods.
– Publication: Mathematical Programming.

3. ‘A Unified Approach to Trust Region Methods’ by Byrd, R. H., Schnabel, R. B., and Shultz, G. A.
– Abstract: A research paper dealing with the theoretical foundations of trust region methods in a unified manner.
– Paper link: for professional optimisation researchers.

Online resources.

1. MIT OpenCourseWare: Numerical Methods for Nonlinear Optimisation
– Abstract: Free lecture material on optimisation algorithms. Trust-region methods are also covered.

2. Python Libraries Documentation (SciPy.optimise)
– Abstract: Documentation of Python libraries that can be used to implement optimisation methods, including confidence region methods.

Application-specific reference books.

1. ‘Optimisation in Practice with MATLAB’ by Achille Messac
– Abstract: Provides detailed examples of applications of optimisation methods using MATLAB. Includes confidence region methods.

2. ‘Applied Optimisation with MATLAB Programming’ by P. Venkataraman
– Abstract: Provides practical examples of engineering optimisation, with trust-region methods playing an important role.