ppopt package

Subpackages

Submodules

ppopt.critical_region module

class ppopt.critical_region.CriticalRegion(A: ~numpy.ndarray, b: ~numpy.ndarray, C: ~numpy.ndarray, d: ~numpy.ndarray, E: ~numpy.ndarray, f: ~numpy.ndarray, active_set: ~typing.List[int] | ~numpy.ndarray, omega_set: ~typing.List[int] | ~numpy.ndarray = <factory>, lambda_set: ~typing.List[int] | ~numpy.ndarray = <factory>, regular_set: ~typing.List[int] | ~numpy.ndarray = <factory>, y_fixation: ~numpy.ndarray | None = None, y_indices: ~numpy.ndarray | None = None, x_indices: ~numpy.ndarray | None = None)

Bases: object

Critical region is a polytope that defines a region in the uncertainty space with an associated optimal value, active set, lagrange multipliers and constraints

\[\begin{split}\begin{align} x(\theta) &= A\theta + b\\ \lambda(\theta) &= C\theta + d\\ \Theta &:= \{\forall \theta \in \mathbf{R}^m: E\theta \leq f\} \end{align}\end{split}\]

equality_indices: numpy array of indices

constraint_set: if this is an A@x = b + F@theta boundary

lambda_set: if this is a λ = 0 boundary

boundary_set: if this is an Eθ <= f boundary

A: ndarray

C: ndarray

E: ndarray

active_set: List[int] | ndarray

b: ndarray

d: ndarray

evaluate(theta: ndarray) → ndarray: Evaluates x(θ) = Aθ + b.

f: ndarray

get_constraints()

An assessor function to quickly access the fields of the extends of the critical region

Returns:: a list with E, and f as elements

is_full_dimension() → bool

Tests dimensionality of critical region. This is done by checking the radius of the chebyshev ball inside the region

Returns:: a boolean value, of whether the critical region is full dimensional

is_inside(theta: ndarray) → ndarray: Tests if point θ is inside the critical region.

lagrange_multipliers(theta: ndarray) → ndarray: Evaluates λ(θ) = Cθ + d.

lambda_set: List[int] | ndarray

omega_set: List[int] | ndarray

regular_set: List[int] | ndarray

x_indices: ndarray = None

y_fixation: ndarray = None

y_indices: ndarray = None

ppopt.mplp_program module

class ppopt.mplp_program.MPLP_Program(A, b, c, H, A_t, b_t, F, c_c=None, c_t=None, Q_t=None, equality_indices=None, solver=None)

Bases: object

The standard class for multiparametric linear programming

\[\begin{split}\begin{align} \min_x \quad \theta^TH^Tx& + c^Tx\\ \text{s.t.} \quad Ax &\leq b + F\theta\\ A_{eq}x &= b_{eq}\\ A_\theta \theta &\leq b_\theta\\ x &\in R^n\\ \end{align}\end{split}\]

A: ndarray

A_t: ndarray

F: ndarray

H: ndarray

Q_t: ndarray

b: ndarray

b_t: ndarray

c: ndarray

c_c: ndarray

c_t: ndarray

check_active_set_rank(active_set)

Checks the rank of the matrix is equal to the cardinality of the active set

\[\textrm{Rank}(A_{\mathcal{A}}) = |\mathcal{A}|\]

Parameters:: active_set – an active set combination
Returns:: True if full rank otherwise false

check_feasibility(active_set, check_rank=True) → bool

Checks the feasibility of an active set combination w.r.t. a multiparametric program.

\[\begin{split}\begin{align} \min_{x,\theta} \quad \quad &0\\ \text{s.t.}\quad Ax &\leq b + F\theta\\ A_{i}x &= b_{i} + F_{i}\theta, \quad \forall i \in \mathcal{A}\\ A_\theta \theta &\leq b_\theta\\ x &\in R^n\\ \theta &\in R^m \end{align}\end{split}\]

Parameters:

active_set – an active set combination
check_rank – Checks the rank of the LHS matrix for a violation of LINQ if True (default)

Returns:

True if active set is feasible else False

check_optimality(active_set)

Tests if the active set is optimal for the provided mpLP program

\[\max_{x, \theta, \lambda, s, t} \quad t\]

\[\begin{split}\begin{align*} H \theta + (A_{A_i})^T \lambda_{A_i} + c &= 0\\ A_{A_i}x - b_ai-F_{a_i}\theta &= 0\\ A_{A_j}x - b_{A_j}-F_{A_j}\theta + s{j_k} &= 0\\ t*e_1 &\leq \lambda_{A_i}\\ t*e_2 &\leq s_{J_i}\\ t &\geq 0\\ \lambda_{A_i} &\geq 0\\ s_{J_i} &\geq 0\\ A_t\theta &\leq b_t \end{align*}\end{split}\]

Parameters:: active_set – active set being considered in the optimality test
Returns:: dictionary of parameters, or None if active set is not optimal

constraint_datatype_conversion() → None: Makes sure that all the data types of the problem are in fp64, this is important as some solvers do not accept integral data types.

display_latex() → None: Displaces Latex text of the multiparametric problem.

display_warnings() → None: Displaces warnings.

equality_indices: List[int] | ndarray

evaluate_objective(x: ndarray, theta_point: ndarray)

feasible_space_chebychev_ball()

Formulates and solves the (x, Θ) chebychev ball of the multiparametric program.

Returns:: the lp solution object of the chebychev ball

feasible_theta_point() → ndarray | None

This generates a feasible theta point for the multiparametric problem

Returns:

gen_optimal_active_set() → List[int] | None

Self contained method to geometrically sample the theta feasible space to generate an optimal active set.

Returns:: an optimal active set

latex() → List[str]

Generates latex of the multiparametric problem

Returns:: returns latex of the

num_constraints() → int: Returns number of constraints.

num_equality_constraints() → int

num_inequality_constraints() → int

num_t() → int: Returns number of uncertain variables.

num_x() → int: Returns number of parameters.

optimal_control_law(active_set: List[int]) → Tuple

This function calculates the optimal control law corresponding to an active set combination

Parameters:: active_set – an active set combination
Returns:: a tuple of the optimal x* and λ* functions in the following form(A_x, b_x, A_l, b_l)

\[\begin{split}\begin{align*} x^*(\theta) &= A_x\theta + b_x\\ \lambda^*(\theta) &= A_l\theta + b_l\\ \end{align*}\end{split}\]

process_constraints() → None: Removes redundant constraints from the multiparametric programming problem.

sample_theta_space(num_samples: int = 100) → list | None

Samples the theta feasible space with a Diken walk algorithm. This is typically used to initiate the graph and geometric algorithm.

Returns:: list of found optimal active sets

scale_constraints() → None: Rescales the constraints of the multiparametric problem to ||[A|-F]||_i = 1, in the L2 sense.

solve_theta(theta_point: ndarray) → SolverOutput | None

Substitutes theta into the multiparametric problem and solves the following optimization problem

\[\min_{x} \tilde{c}^Tx\]

\[\begin{split}\begin{align} Ax &\leq \tilde{b}\\ A_{eq}x &= \tilde{b}_{eq}\\ x &\in R^n\\ \end{align}\end{split}\]

Parameters:: theta_point – An uncertainty realization
Returns:: The Solver output of the substituted problem, returns None if not solvable

solve_theta_variable() → SolverOutput | None

Leaves Theta as an optimization variable, solves the following problem

define y’ = [x^T theta^T]^T

min [c^T 0]^Ty’ s.t. [A -F]y’ <= b

Returns:: the Solver output of the substituted problem, returns None if not solvable

solver: Solver

warnings() → List[str]: Checks the dimensions of the matrices to ensure consistency.

ppopt.mplp_program.calc_weakly_redundant(A, b, equality_set: List[int] | None = None, deterministic_solver='gurobi')

ppopt.mpqp_program module

class ppopt.mpqp_program.MPQP_Program(A: ndarray, b: ndarray, c: ndarray, H: ndarray, Q: ndarray, A_t: ndarray, b_t: ndarray, F: ndarray, c_c: ndarray | None = None, c_t: ndarray | None = None, Q_t: ndarray | None = None, equality_indices=None, solver=None)

Bases: MPLP_Program

The standard class for quadratic multiparametric programming.

\[\begin{split}\begin{align} \min_x\quad \frac{1}{2}x^TQx& + \theta^TH^Tx + c^Tx\\ \text{s.t.}\quad Ax &\leq b + F\theta\\ A_{eq}x &= b_{eq}\\ A_\theta \theta &\leq b_\theta\\ x &\in R^n\\ \end{align}\end{split}\]

A: ndarray

A_t: ndarray

F: ndarray

H: ndarray

Q_t: ndarray

b: ndarray

b_t: ndarray

c: ndarray

c_c: ndarray

c_t: ndarray

check_optimality(active_set: list)

Tests if the active set is optimal for the provided mpqp program

\[\max_{x, \theta, \lambda, s, t} \quad t\]

\[\begin{split}\begin{align*} Qx + H \theta + (A_{A_i})^T \lambda_{A_i} + c &= 0\\ A_{A_i}x - b_ai-F_{a_i}\theta &= 0\\ A_{A_j}x - b_{A_j}-F_{A_j}\theta + s{j_k} &= 0\\ t*e_1 &\leq \lambda_{A_i}\\ t*e_2 &\leq s_{J_i}\\ t &\geq 0\\ \lambda_{A_i} &\geq 0\\ s_{J_i} &\geq 0\\ A_t\theta &\leq b_t \end{align*}\end{split}\]

Parameters:: active_set – active set being considered in the optimality test
Returns:: dictionary of parameters, or None if active set is not optimal

equality_indices: List[int] | ndarray

evaluate_objective(x, theta_point)

Evaluates the objective of the multiparametric program. for a given x and θ.

\[\frac{1}{2}x^TQx + \theta^TH^Tx+c^Tx\]

Parameters:

x – x input
theta_point – θ input

Returns:

Objective function evaluated at x, θ

latex() → List[str]: Creates a latex output for the multiparametric problem.

optimal_control_law(active_set: List[int]) → Tuple

This function calculates the optimal control law corresponding to an active set combination. This is effectivley just manipulating the stationarity conditions and active constraints for x, and λ

\[ \begin{align}\begin{aligned}Qx + c + H\theta + \hat{A}^T\hat{\lambda} = 0\\\hat{A}x = \hat{b} + \hat{F}\theta\end{aligned}\end{align} \]

\[\begin{split}\begin{align*} x^*(\theta) &= A_x\theta + b_x\\ \lambda^*(\theta) &= A_l\theta + b_l\\ \end{align*}\end{split}\]

Parameters:: active_set – an active set combination
Returns:: a tuple of the optimal x* and λ* functions in the following form(A_x, b_x, A_l, b_l)

solve_theta(theta_point: ndarray) → SolverOutput | None

Substitutes a particular realization of θ into the multiparametric problem and solves the resulting optimization problem.

\[\begin{split}\begin{align} \tilde{b} &= b + F\theta\\ \tilde{b}_eq &= b_{eq} + F_{eq}\theta\\ \tilde{c}^T &= c^T + \theta^T H^T \end{align}\end{split}\]

\[\begin{split}\begin{align} \min_{x}\quad &\frac{1}{2}x^TQx + \tilde{c}^Tx\\ \text{s.t.} \quad Ax &\leq \tilde{b}\\ A_{eq}x &= \tilde{b}_{eq}\\ x &\in \mathbb{R}^n \end{align}\end{split}\]

Parameters:: theta_point – An uncertainty realization
Returns:: The Solver output of the substituted problem, returns None if not solvable

solver: Solver

warnings() → List[str]: Checks the dimensions of the matrices to ensure consistency.

ppopt.plot module

ppopt.plot.gen_vertices(solution: Solution)

Generates the vertices associated with the critical regions in the solution.

Parameters:: solution – a multiparametric region
Returns:: a list of a collection of vertices sorted counterclockwise that correspond to the specific region

ppopt.plot.parametric_plot(solution: Solution, save_path: str | None = None, show=True, save_format: str = 'png', seed: int | None = None) → None

Makes a simple plot from a solution. This uses matplotlib to generate a plot, it is the general plotting backend.

Parameters:

solution – a multiparametric solution
save_path – if specified saves the plot in the directory
save_format – changes the saved image format to the specified
show – Keyword argument, if True displays the plot otherwise does not display
seed – If not set, will default to time in nanoseconds since the epoc

Returns:

no return, creates graph of solution

ppopt.plot.parametric_plot_1D(solution: Solution, save_path: str | None = None, show=True, save_format: str = 'png') → None

Makes a simple plot from a 1D parametric solution. This uses matplotlib to generate a plot, it is the general plotting backend.

Parameters:

solution – a multiparametric solution
save_path – if specified saves the plot in the directory
save_format – changes the saved image format to the specified
show – Keyword argument, if True displays the plot otherwise does not display

Returns:

no return, creates graph of solution

ppopt.plot.plotly_plot(solution: Solution, save_path: str | None = None, show=True, save_format: str = 'png') → None

Makes a plot via the plotly library, this is good for interactive figures that you can embed into webpages and handle interactively.

Parameters:

solution – a 2D parametric solution
save_path – Keyword argument, if a directory path is specified it will save a html copy and a png to that directory
save_format – changes the saved image format to the specified
show – Keyword argument, if True displays the plot otherwise does not display

Returns:

no return, creates a graph of the solution

ppopt.plot.sort_clockwise(vertices: List[ndarray]) → List[ndarray]

Sorts the vertices in clockwise order. This is important for rendering as if they were not sorted then you would see nonsense.

Parameters:: vertices – a list of 2D vertices
Returns:: List of vertices that have been sorted in a clockwise direction

ppopt.plot.vertex_enumeration_2d(A: ndarray, b: ndarray, solver: Solver) → List[ndarray]

Computes the vertices of a 2D polytope from the half space representation, uses a naive O(n^2) algorithm but is sufficient for plotting purposes.

Generates vertices for the 2D polytope of the following structure Ax <= b

Parameters:

solver – A solver object to solve the LPs
A – The left-hand side constraint matrix
b – The right-hand side constraint matrix

Returns:

List of vertices

ppopt.problem_generator module

ppopt.problem_generator.generate_mplp(x: int = 2, t: int = 2, m: int = 10) → MPLP_Program

Generates a random mpLP problem with of the following characteristics

Parameters:

x – number of parameters
t – number of uncertain variables
m – number of constraints

Returns:

A random mpLP of the specified type

ppopt.problem_generator.generate_mpqp(x: int = 2, t: int = 2, m: int = 10) → MPQP_Program

Generates a random mpQP problem with of the following characteristics

Parameters:

x – number of x dimensions
t – number of theta dimensions
m – number of constraints

Returns:

A random mpQP problem of the specified type

ppopt.solution module

class ppopt.solution.Solution(program: MPLP_Program | MPQP_Program, critical_regions: List[CriticalRegion], is_overlapping=False)

Bases: object

The Solution object is the output of multiparametric solvers, it contains all the critical regions as well as holds a copy of the original problem that was solved.

add_region(region: CriticalRegion) → None

Adds a region to the solution

Parameters:: region – region to add to the solution

critical_regions: List[CriticalRegion]

evaluate(theta_point: ndarray) → ndarray | None

returns the optimal x* from the solution, if it exists

Parameters:: theta_point – an uncertainty realization
Returns:: the calculated x* from theta

evaluate_objective(theta_point) → ndarray | None

Given a realization of an uncertainty parameter, calculate the objective value

Parameters:: theta_point – a theta realization
Returns:: the value of the objective or None (if theta_point is not inside any critical region)

get_region(theta_point: ndarray) → CriticalRegion | None

Find the critical region in the solution that corresponds to the theta provided

The method finds all critical regions that the solution is inside and returns the solutions, x*, with the lowest objective function of all of these regions.

In the case of no overlap we can make a shortcut

Parameters:: theta_point – an uncertainty realization
Returns:: the region that contains theta

get_region_no_overlap(theta_point: ndarray) → CriticalRegion | None

Find the critical region in the solution that corresponds to the provided theta, assumes that no critical regions overlap

Parameters:: theta_point – a theta realization
Returns:: the critical region that contains theta_point or None

get_region_overlap(theta_point: ndarray) → CriticalRegion | None

Find the critical region in the solution that corresponds to the provided theta

Parameters:: theta_point – realization of uncertainty
Returns:: the critical region that that theta is in with the lowest objective value or none

is_mixed_integer_sol()

program: MPLP_Program | MPQP_Program | MPMIQP_Program | MPMILP_Program

theta_dim() → int: Returns the number of theta/ parameter dimensions

verify_solution() → bool

This can be called to verify that all the critical regions agree with the optimization problem. With problems with numerically small critical regions the deterministic optimizer value could fail. This does NOT necessarily mean that the critical region is at fault but that perhaps more analysis should be done. This is especially apparent with critical regions with chebychev radii on the order of sqrt(machine epsilon).

In the case of overlapping critical regions this is not the proper analysis and a different method should be used.

Returns:: True if all is verified, else False

verify_theta(theta_point: ndarray) → bool

Checks that the result of the solution is consistent with theta substituted multiparametric problem

Parameters:: theta_point – an uncertainty realization
Returns:: True if they are the same, False if they are different

ppopt.solver module

class ppopt.solver.Solver(solvers: ~typing.Dict[str, str] = <factory>)

Bases: object

This is the primary user interface for deterministic solvers

The solvers can be changed by directly editing the solver dict to different solver names

check_supported_problem(problem_name: str) → None

static problem_not_supported(problem_name: str) → None: This is an internal method that throws an error and prompts the user when they use an unsupported Solver

solve_lp(c: ndarray | None, A: ndarray | None, b: ndarray | None, equality_constraints=None, verbose=False, get_duals=True) → SolverOutput | None

This is the breakout for solving linear programs

The Linear programming problem

\[\min_{xy} c^Tx\]

\[\begin{split}\begin{align} Ax &\leq b\\ A_{eq}x &= beq\\ x &\in R^n\\ \end{align}\end{split}\]

Parameters:

c – Column Vector, can be None
A – Constraint LHS matrix, can be None
b – Constraint RHS matrix, can be None
equality_constraints – List of Equality constraints
verbose – Flag for output of underlying Solver, default False
get_duals – Flag for returning dual variable of problem, default True (false for all mixed integer models)

Returns:

A SolverOutput object if optima found, otherwise None.

This is the breakout for solving mixed integer linear programs

The Mixed Integer Linear programming problem

\[\min_{x,y} c^T[x,y]\]

\[\begin{split}\begin{align} A[x,y] &\leq b\\ A_{eq}[x,y] &= beq\\ x &\in R^n\\ y &\in \{0, 1\}^m \end{align}\end{split}\]

Parameters:

c – Column Vector, can be None
A – Constraint LHS matrix, can be None
b – Constraint RHS matrix, can be None
equality_constraints – List of Equality constraints
bin_vars – List of binary variable indices
verbose – Flag for output of underlying Solver, default False
get_duals – Flag for returning dual variable of problem, default True (false for all mixed integer models)

Returns:

A dictionary of the Solver outputs, or none if infeasible or unbounded. output[‘sol’] = primal variables, output[‘dual’] = dual variables, output[‘obj’] = objective value, output[‘const’] = slacks, output[‘active’] = active constraints.

This is the breakout for solving mixed integer quadratic programs

The Mixed Integer Quadratic program programming problem

\[\min_{xy} \frac{1}{2} [xy]^TQ[xy] + c^T[xy]\]

\[\begin{split}\begin{align} A[xy] &\leq b\\ A_{eq}[xy] &= beq\\ x &\in R^n\\ y &\in \{0, 1\}^m \end{align}\end{split}\]

Parameters:

Q – Square matrix, can be None
c – Column Vector, can be None
A – Constraint LHS matrix, can be None
b – Constraint RHS matrix, can be None
equality_constraints – List of Equality constraints
bin_vars – List of binary variable indices
verbose – Flag for output of underlying Solver, default False
get_duals – Flag for returning dual variable of problem, default True (false for all mixed integer models)

Returns:

A SolverOutput object if optima found, otherwise None.

This is the breakout for solving quadratic programs

The Quadratic programming problem

\[\min_{x} \frac{1}{2}x^TQx + c^Tx\]

\[\begin{split}\begin{align} Ax &\leq b\\ A_{eq}x &= beq\\ x &\in R^n\\ \end{align}\end{split}\]

Parameters:

Q – Square matrix, can be None
c – Column Vector, can be None
A – Constraint LHS matrix, can be None
b – Constraint RHS matrix, can be None
equality_constraints – List of Equality constraints
verbose – Flag for output of underlying Solver, default False
get_duals – Flag for returning dual variable of problem, default True (false for all mixed integer models)

Returns:

A SolverOutput object if optima found, otherwise None.

static solver_not_supported(solver_name: str) → None: This is an internal method that throws an error and prompts the user when they use an unsupported Solver

solvers: Dict[str, str]

supported_problems = ['lp', 'qp', 'milp', 'miqp']

supported_solvers = ['gurobi', 'glpk', 'quadprog']

ppopt.solver.available_LP_solvers() → Iterable

Checks what LP solvers are available to use

Returns:: Installed and supported solvers for linear programs

ppopt.solver.available_QP_solvers()

Checks what QP solvers are avalable to use

Returns:: Installed and supported solvers for quadratic programs

ppopt.solver.check_modules(modules: Iterable) → Iterable: Given an iterable of module names, returns modules that are installed

ppopt.solver.check_solver_modules(module_map, packages) → Iterable: Maps optimization python package names to internal names and returns an iterable

ppopt.solver.default_solver_options()

Generates the default system solvers to use for optimization sub problems

Returns:: A dictionary of determanistic solvers to use

Module contents

PPOPT INIT FILE