tf.contrib.constrained_optimization.find_best_candidate_distribution

View source on GitHub

Finds a distribution minimizing an objective subject to constraints.

tf.contrib.constrained_optimization.find_best_candidate_distribution(
    objective_vector, constraints_matrix, epsilon=0.0
)

This function deals with the constrained problem:

minimize f(w) s.t. g_i(w) <= 0 for all i in {0,1,...,m-1}

Here, f(w) is the "objective function", and g_i(w) is the ith (of m) "constraint function". Given a set of n "candidate solutions" {w_0,w1,...,w{n-1} }, this function finds a distribution over these n candidates that, in expectation, minimizes the objective while violating the constraints by the smallest possible amount (with the amount being found via bisection search).

The objective_vector parameter should be a numpy array with shape (n,), for which objective_vector[i] = f(w_i). Likewise, constraints_matrix should be a numpy array with shape (m,n), for which constraints_matrix[i,j] = g_i(w_j).

This function will return a distribution for which at most m+1 probabilities, and often fewer, are nonzero.

For more specifics, please refer to:

Cotter, Jiang and Sridharan. "Two-Player Games for Efficient Non-Convex Constrained Optimization". https://arxiv.org/abs/1804.06500

This function implements the approach described in Lemma 3.

objective_vector numpy array of shape (n,), where n is the number of "candidate solutions". Contains the objective function values.
constraints_matrix numpy array of shape (m,n), where m is the number of constraints and n is the number of "candidate solutions". Contains the constraint violation magnitudes.
epsilon nonnegative float, the threshold at which to terminate the binary search while searching for the minimal expected constraint violation magnitude.

The optimal distribution, as a numpy array of shape (n,).

ValueError If objective_vector and constraints_matrix have inconsistent shapes, or if epsilon is negative.
ImportError If we're unable to import scipy.optimize.