Iterative Search

Random Search

Solver name is “Random”.

class flopt.solvers.random_search.RandomSearch[source]

Random Sampling Search

Examples

import flopt

x = flopt.Variable("x", lowBound=-1, upBound=1, cat="Continuous")
y = flopt.Variable("y", lowBound=-1, upBound=1, cat="Continuous")

prob = flopt.Problem()
prob += 2*x*x + x*y + y*y + x + y

status, log = prob.solve(solver="Random", msg=True, timelimit=1)

print("obj =", flopt.Value(prob.obj))
print("x =", flopt.Value(x))
print("y =", flopt.Value(y))

2-Opt (TwoOpt)

Solver name is “2-Opt”.

class flopt.solvers.two_opt.TwoOpt[source]

2-Opt: local search for permutation

2-Opt search explores neighborhood of current solution. In 2-Opt, the neighborhood of a perm = [0, 1, 2, …, n-1] are [0, 1, .., i-1, j, j-1, …, i+1, i, j+1, …, n], where i and j are in {0..n}, and i is less than j.

Steepest Descent Search

Solver name is “SteepestDescent”.

class flopt.solvers.steepest_descent.SteepestDescentSearch[source]

Steepest Descent Search

Update search points as x_{n+1} = x_n - alpha d, where d = -grad(x_n) and alpha is a step size calculated by Armijo’s method.

Examples

import flopt

x = flopt.Variable("x", lowBound=-1, upBound=1, cat="Continuous")
y = flopt.Variable("y", lowBound=-1, upBound=1, cat="Continuous")

prob = flopt.Problem()
prob += 2*x*x + x*y + y*y + x + y

status, log = prob.solve(solver="SteepestDescent", msg=True, timelimit=1)

print("obj =", flopt.Value(prob.obj))
print("x =", flopt.Value(x))
print("y =", flopt.Value(y))

Here is an example for visualization of optimization of \(f(x) = 2 x_0^2 + x_1^2 + x_0x_1`\).

We prepare the callback function for saving the search points.

path = [[x[0].value(), x[1].value()]]
def callback(solutions):
    path.append(solutions[0].value())

Then, we specify this to the callbacl argument of the Problem.solve().

status, log = prob.solve(solver, msg=True, timelimit=1, callback=callback)

Finally, we visualize the search path.

import flopt

x = flopt.Variable.array("x", 2, cat="Continuous")
x[0].setValue(1.5)
x[1].setValue(1.0)

def f(x):
    return 2*x[0]**2 + x[1]**2 + x[0]*x[1]

prob = flopt.Problem()
prob += f(x)

path = [[x[0].value(), x[1].value()]]
def callback(solutions):
    path.append(solutions[0].value())

solver = flopt.Solver("SteepestDescent")
solver.setParams(xi=0.9, tau=0.9)
status, log = prob.solve(solver, msg=True, timelimit=1, callback=callback)


import numpy as np
import matplotlib.pyplot as plt

X = Y = np.linspace(-2, 2, 21)
X_mesh, Y_mesh = np.meshgrid(X, Y)
Z = f(np.array((X_mesh, Y_mesh)))

fig, ax = plt.subplots()
cmap = plt.get_cmap("tab10")
color_i = 0

ax.contour(X, Y, Z, levels=np.logspace(-0.3, 1.2, 10))
path = np.array(path)
ax.plot(path[:,0], path[:,1], marker="o", linestyle="--", color=cmap(0), zorder=1)
ax.scatter(path[0, 0], path[0, 1], marker="o", color=cmap(1), label="initial point", zorder=2)
ax.scatter(path[-1, 0], path[-1, 1], marker="o", color=cmap(6), label="final point", zorder=2)
ax.set_aspect('equal')
ax.grid("--")
ax.legend()