"""
Code for maximizing a convex function over a polytope, as defined
by a set of linear equalities and inequalities.
"""
import numpy as np
import scipy
from .optutil import _as_full_rank
__all__ = ("maximize_convex_function",)
[docs]
def maximize_convex_function(f, A_ineq, b_ineq, A_eq=None, b_eq=None):
"""
Maximize a convex function over a polytope. This function uses the fact that
the maximum of a convex function over a polytope will be achieved at one of
the extreme points of the polytope.
The maximization is done by taking a system of linear inequalities, using the
pypoman library to create a list of extreme points, and then evaluating the
objective function on each point.
Parameters
----------
f : function
Objective function to maximize
A_ineq : matrix
Specifies inequalities matrix, should be num_inequalities x num_variables
b_ineq : array
Specifies inequalities vector, should be num_inequalities long
A_eq : matrix
Specifies equalities matrix, should be num_equalities x num_variables
b_eq : array
Specifies equalities vector, should be num_equalities long
Returns
-------
optimal_extreme_point : np.ndarray
The extreme point at which the maximum is attained.
maximum_function_value : float
The maximum value of ``f``.
"""
best_x, best_val = None, -np.inf
A_ineq = A_ineq.astype("float")
b_ineq = b_ineq.astype("float")
if A_eq is not None:
# pypoman doesn't support equality constraints. We remove equality
# constraints by doing a coordinate transformation.
A_eq = A_eq.astype("float")
b_eq = b_eq.astype("float")
A_eq, b_eq, _ = _as_full_rank(A_eq, b_eq)
# Get one solution that satisfies A x0 = b
x0 = np.linalg.lstsq(A_eq, b_eq, rcond=None)[0]
assert np.abs(A_eq.dot(x0) - b_eq).max() < 1e-5
# Get projector onto null space of A, it satisfies AZ=0 and Z^T Z=I
Z = scipy.linalg.null_space(A_eq)
# Now every solution can be written as x = x0 + Zq, since A x = A x0 = b
# Inequalities get transformed as
# A'x <= b' ---> A'(x0 + Zq) <= b --> (A'Z)q \le b - A'x0
b_ineq = b_ineq - A_ineq.dot(x0)
A_ineq = A_ineq.dot(Z)
transform = lambda q: Z.dot(q) + x0
else:
transform = lambda x: x
import pypoman
extreme_points = pypoman.compute_polytope_vertices(A_ineq, b_ineq)
for v in extreme_points:
x = transform(v)
val = f(x)
if val > best_val:
best_x, best_val = x, val
if best_x is None:
raise Exception("No extreme points found!")
return best_x, best_val