Optimization Utility and Helper Functions#

This subpackage provides various general-purpose utility and functions useful for optimization routines.

Utility functions for the optimization module. These are utility classes/functions for various optimization algorithms, but are not useful otherwise. Any utility function that is general will likely be moved to the utility module.

pseudo_random_binary_objective_function(x, scale=10.0, random_seed=1234)[source]#

A function that can be used to testing BinaryReinforceOptimizer The function creates a pseudo random number generator from a fixed seed. The passed binary state/vector x is transformed into an equivalent index which is one-to-one associated with the random number sequence generated by the random number generator

Parameters:

  • x – a binary vector state

  • scale (float) – a scalar quantity to magnify the range of the random values

  • random_seed – random seed for reproduction

Returns:

the value of the test function (deterministic) associated corresponding to the passed state

Return type:

float

backtracking_line_sesarch(x, f, g, max_step=1, d=None, tau=0.9, c=0.5, maxiter=10000)[source]#

Implement the backtracking line search algorithm

Parameters:

  • x – current state

  • f – objective function that accepts x, and return f(x)

  • g – the gradient function

  • max_step (float) – maximum step size. Default is 1.

  • d – search direction; if None, will be set to g

  • tau (float) – the reduction factor for the step size. Default is 0.9.

  • c (float) – the Armijo condition parameter. Default is 0.5.

  • maxiter (int) – maximum number of iterations. Default is 10000.

Raises:

AssertionError – if c and tau are not in the interval (0, 1)

Returns:

the step size satisfying Armijo condition

Return type:

float

box_projection(theta, l=0, u=1)[source]#

Apply a projection operator \(P\), which maps an arbitrary point onto the feasible region described by the box constraints as follows,

\[\begin{split}P(\theta) := \min\{u,\max\{l,\theta\}\} = \begin{cases} l, & \text{if } \theta < l \\ \theta, & \text{if } \theta \in [l,u] \\ u, & \text{if } \theta > u \end{cases}\end{split}\]
Parameters:

  • theta (np.ndarray) – input point, \(\theta\), on which the projection operator is applied

  • l (float) – lower bound for the box constraints. Default is 0.

  • u (float) – upper bound for the box constraints. Default is 1.

Returns:

the projection \(P(\theta)\)

Return type:

np.ndarray

projected_gradient(init_x, grad, step_size, l=None, u=None, verbose=False)[source]#

Projection operator of the gradient g on bound constraints, given a state, gradient, and a step size. Initial implementation uses piecewise search of bended segments

Parameters:

  • init_x – current state

  • grad – direction

  • step_size (float) – (maximum) step size

  • l (float) – lower bounds. Default will be set to -infty

  • u (float) – upper bounds. Default will be set to +infty

  • verbose (bool) – print debug information. Default is False

Returns:

A tuple containing the following values

  • \(y = \text{init_x} - \text{step_size} * \text{grad}\)

  • \(\text{Proj}(y)\)

  • The breakpoints, i.e. the points \(x(t)\) inside or at the boundaries, projected into the feasible domain given the box constraints.

Return type:

tuple[np.ndarray, np.ndarray, list[np.ndarray]]

Warning

  • Both l, u, must be of the same type/size/shape as x, or None

  • Currently, the local minima is looked-up only at the kinks/breakpoints

Note

  • References: J. Nocedal and S. Write “Numerical Optimization 2nd. ed.” Sec 16.7

stepsize_schedule(itr, def_step=1, method='constant')[source]#

Return a suitable step size at a given optimization iteration

Parameters:

  • itr (int) – iteration number

  • def_step (float) – default step size (see note). Default is 1.

  • method (str) – approach to choose the step size at a given iteration (see note). Default is ‘constant’.

Note

Step size is determined based on the selected method

  • ‘constant’: def_step is used at all iterations

  • ‘decay’: def_step/iter

Raises:

  • AssertionError – if the iteration number or if the default step size is not positive

  • ValueError – if the method is not recognized

Returns:

step size for the given iteration

Return type:

float

binary_bruteforce_objective(obj, size, num_active=None, objective_value_tracker=None, verbose=False)[source]#

Evaluate the value of the objective (obj) at all possible binary combinations;

Parameters:

  • obj – Objective function to evaluate.

  • size (int) – objective space dimension (design space)

  • num_active –

    If None, all sizes will be looped over, otherwise, it must be

    1. an integer <= size), only solutions with active subset (==1) equal to num_active will be calculated.

    2. list of integers (looped over as in (a) above)

  • objective_value_tracker (dict[int,float]) – an optional dictionary with partial information to lookup before evaluation. Keys are integer indexes of binary candidates.

  • verbose (bool) – print progress. Default is True.

Returns:

a dictionary holding an updated version (new if objective_value_tracker passed is None) of objective_value_tracker with additional results. If objective_value_tracker is passed, it will be updated (in-place).

Return type:

dict[int,float]

..note::

This is for testing and debugging only

binary_bruteforce_solution(obj, size, num_active=None, maximize=True, objective_value_tracker=None, verbose=False)[source]#

A wrapper around binary_bruteforce_objective() that Finds an optimal solution maximum/minimum of a binary optimization problem with optional budget constraints (described by num_active) by bruteforce search, that is by looking up all possible binary combination.

Parameters:

  • obj – Objective function to evaluate.

  • size (int) – objective space dimension (design space)

  • num_active –

    If None, all sizes will be looped over, otherwise, it must be

    1. an integer <= size), only solutions with active subset (==1) equal to num_active will be calculated.

    2. list of integers (looped over as in (a) above)

  • maximize (bool) – a flag that defines whther the maximum or the minimum is seeked.

  • objective_value_tracker (dict[int,float]) – an optional dictionary with partial information to lookup before evaluation. Keys are integer indexes of binary candidates.

  • verbose (bool) – print progress. Default is True.

Returns:

a list of optimal solutions (each is a numpy array of size size). If the global optimal solution is unique, the length of this list is 1.

Return type:

list[int]

..note::

This is for testing and debugging only

standardize_domain_bounds(size, bounds, min_lb=-inf, max_ub=inf, replace_none=True)[source]#

Standardize the bounds of a random variable of a given size.

Parameters:

  • size – dimension/size of the target variable (positiove integer)

  • bounds –

    desired bounds of the variable’s domain. The types/shapes allowed are as follows (otherwise a TypeError is raised):

    • None: In this case, the bounds are [(min_lb, max_ub), (min_lb, max_ub), …]

    • (lb, ub): In this case, the bounds are [(lb, ub), (lb, ub), …]

    • [(lb, ub)]: In this case, the bounds are [(lb, ub), (lb, ub), …]

    • [(lb_1, ub_1), (lb_2, ub_2), …]: the size is asserted, and a copy of the

      bounds (as a list of tuples) is returned

  • min_lb – smallest allowed lower bound; if not passed it is set to -inf

  • max_ub – largetst allowed upper bound; if not passed it is set to +inf

  • replace_none – If true, any bounds that is None is replaced with min_lb or max_ub for lb, ub, respectively.

Returns:

List of the form [(lb_1, ub_1), (lb_2, ub_2) , …] with length equal to size where (lb_i, ub_i) are the lower and upper bound of the ith entry of a given variable.

Note

If replace_none any `None value is replaced with proper bounds value so that it can be compared with float to test violation of bounds.