tf.contrib.constrained_optimization.find_best_candidate_distribution

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.

Args
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.

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

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