SubmodularFn¶
- class disropt.functions.submodular_func.SubmodularFn(input_shape)[source]¶
Bases:
disropt.functions.abstract_function.AbstractFunction
Submodular AbstractFunction abstract class
- V¶
ground set
- input_shape¶
cardinality of the ground set
- Parameters
input_shape – cardinality of the ground set
- Raises
ValueError – input_shape must be an integer positive number
- greedy_polyhedron(self, w)[source]¶
Greedy algorithm for finding a maximizer \(x\) of
(1)¶\[\begin{split} \max_{x\in B(F)} & w^\top x \\\end{split}\]where \(B(F)\) is the base polyhedron associated to the submodular function \(F\)
- Parameters
w – cost direction
- Returns
maximizer of (1)
- Return type
- Raises
ValueError – Input must be a numpy.ndarray with input_shape elements
- subgradient(self, x)[source]¶
Evaluate a subgradient of the Lovasz extension of the submodular function at \(x\)
- Parameters
x – vector
- Returns
subgradient of the Lovasz extension of \(F\) at \(x\)
- Return type
- Raises
ValueError – Input must be a numpy.ndarray with input_shape elements
- blocksubgradient(x, block)[source]¶
Evaluate a subgradient of the Lovasz extension of the submodular function at \(x\)
- Parameters
x – vector
block – vector
- Returns
block subgradient of the Lovasz extension of \(F\) at \(x\)
- Return type
- Raises
ValueError – Input must be a numpy.ndarray with input_shape elements
- eval(set)[source]¶
Evaluate the submodular function at a given set
- Parameters
set (numpy.ndarray(, dtype='int')) – vector