trust-constr optimization algorithm from the SciPy project that was originally implemented by Antonio Horta Ribeiro. This is a version of the trust-constr algorithm that does not depend on the rest of SciPy. The only dependency is NumPy. The goal is to have a version of the trust-constr algorithm that can run within the Pyodide environment.
pip install trust-constr
Since the trust-constr algorithm was extracted from the scipy.optimize library, it uses the same interface as scipy.optimize.minimize. The main different is that everything is imported from trust_constr rather than from scipy.optimize. The other difference is that the only optimization method available is 'trust-const'. The examples below show how to use trust-constr with a variety of different types of constraints.
import numpy as np
from trust_constr import minimize, NonlinearConstraint, LinearConstraint, Bounds, check_gradExample 15.1 from [1]
Solve:
Solution:
First solve without defining gradient (finite difference gradient will be used):
def objective(x):
return 0.5*(x[0]-2)**2+0.5*(x[1]-0.5)**2
def ineq_constraint(x):
return 1/(x[0]+1)-x[1]-0.25
# Use np.inf of -np.inf to define a single sided constraint
# If there are more than one constraint, that constraints will
# be a list containing all of the constraints
constraints = NonlinearConstraint(ineq_constraint, 0, np.inf)
# set bounds on the variables
# only a lower bound is needed so the upper bound for both variables is set to np.inf
bounds = Bounds([0,0], [np.inf, np.inf])
# define starting point for optimization
x0 = np.array([5.0, 1.0])
res = minimize(objective, x0, bounds=bounds, constraints=constraints)
print("Solution =", res.x)
print(f"Obtained using {res.nfev} objective function evaluations.")Solution = [1.95282327 0.08865882]
Obtained using 42 objective function evaluations.Now define the gradient for objective and constraint and check gradients:
def objective_gradient(x):
return np.array([(x[0]-2), (x[1]-0.5)])
def ineq_gradient(x):
return np.array([-1/((x[0]+1)**2), -1])
# check analytical gradients against finite difference gradient
# an incorrect analytical gradient is a common cause for lack of convergence to a true minimum
for x in np.random.uniform(low=[0,0], high=[10,10], size=(5,2)):
print("objective difference: ", check_grad(objective, objective_gradient, x))
print("constraint difference:", check_grad(ineq_constraint, ineq_gradient, x))
objective difference: 7.24810320719611e-08
constraint difference: 2.1805555505335916e-08
objective difference: 1.5409355031965243e-08
constraint difference: 1.8387489794657874e-10
objective difference: 8.16340974645582e-08
constraint difference: 2.2211865402521624e-08
objective difference: 1.51975085661403e-07
constraint difference: 5.070987015715067e-10
objective difference: 1.7113557964841567e-07
constraint difference: 4.981334539820581e-08Finally, minimize using the gradient functions that were just test:
constraints = NonlinearConstraint(ineq_constraint, 0, np.inf, jac=ineq_gradient)
res = minimize(objective, x0, jac=objective_gradient, bounds=bounds, constraints=constraints)
print("Solution =", res.x)
print(f"Obtained using {res.nfev} objective function evaluations.")Solution = [1.95282328 0.08865881]
Obtained using 14 objective function evaluations.Example 15.2 from [1]
Solve:
Subject to:
Solution:
objective2 = lambda x: x[0]**2 + x[1]**2
objective2_gradient = lambda x: np.array([2*x[0], 2*x[1]])
eq_constraint = lambda x: (x[0]-1)**3 - x[1]**2
eq_gradient = lambda x: np.array([3*(x[0]-1)**2, -2*x[1]])
# Make the upper and lower bound both zero to define an equality constraint
constraints = NonlinearConstraint(eq_constraint, 0, 0, jac=eq_gradient)
x0 = np.array([5, 2])
res = minimize(objective2, x0, jac=objective2_gradient, constraints=constraints)
print("Solution =", res.x)
print(f"Obtained using {res.nfev} objective function evaluations.")Solution = [9.99966899e-01 3.36074169e-09]
Obtained using 181 objective function evaluations.Example problem from [2]
Solve:
Subject to:
Solution:
objective3 = lambda x: 100.0*(x[1] - x[0]**2)**2.0 + (1 - x[0])**2
objective3_gradient = lambda x: np.array([-400*(x[1]-x[0]**2)*x[0]-2*(1-x[0]),
200*(x[1]-x[0]**2)])
# define the linear constraint
A = np.array([[1,2]])
constraints = LinearConstraint(A, [-np.inf], [1])
x0 = np.array([-1, 2])
res = minimize(objective3, x0, jac=objective3_gradient, constraints=constraints)
print("Solution =", res.x)
print(f"Obtained using {res.nfev} objective function evaluations.")Solution = [0.50220246 0.24889838]
Obtained using 45 objective function evaluations.Example problem from [3]
Solve:
$$\min_{\mathbf{x}} \sum^{N/2}{i=1}\left[100\left(x^2{2i-1}-x_{2i}\right)^2+\left(x_{2i-1}-1\right)^2\right]$$
Solution for
def rosenbrock_function(x):
result = 0
for i in range(len(x) - 1):
result += 100 * (x[i + 1] - x[i] ** 2) ** 2 + (1 - x[i]) ** 2
return result
x0 = np.array([0.1, -0.5, -5.0])
res = minimize(rosenbrock_function, x0)
print("Solution =", res.x)
print(f"Obtained using {res.nfev} objective function evaluations.")Solution = [0.99999729 0.99999458 0.99998915]
Obtained using 224 objective function evaluations.[1] Nocedal, Jorge, and Stephen J. Wright. Numerical Optimization. 2nd ed. Springer Series in Operations Research. New York: Springer, 2006.