ppopt.utils package

Submodules

ppopt.utils.chebyshev_ball module

ppopt.utils.chebyshev_ball.chebyshev_ball(A: ndarray, b: ndarray, equality_constraints: Iterable[int] | None = None, bin_vars: Iterable[int] | None = None, deterministic_solver='gurobi')

Chebyshev ball finds the largest ball inside a polytope defined by Ax <= b. This is solved by the following LP.

\[\min_{x,r} -r\]

\[\begin{split}\begin{align*} \text{s.t. } Ax + ||A_i||_2r &\leq b\\ A_{eq} x &= b_{eq}\\ r &\geq 0 \end{align*}\end{split}\]

Parameters:

A – LHS Constraint Matrix
b – RHS Constraint column vector
equality_constraints – indices of rows that have strict equality A[eq] @ x = b[eq]
bin_vars – indices of binary variables
deterministic_solver – The underlying Solver to use, e.g. gurobi, ect

Returns:

the SolverOutput object, None if infeasible

ppopt.utils.chebyshev_ball.chebyshev_ball_max(A: ndarray, b: ndarray, equality_constraints: Iterable[int] | None = None, bin_vars: Iterable[int] = (), deterministic_solver='glpk')

Chebyshev ball finds the smallest l-infinity ball the contains the polytope defined by Ax <= b. Where A has n hyper planes and d dimensions.

This is solved by the following Linear program

\[\min_{x_{c} ,r ,y_{j} ,u_{j}} \quad r\]

\[\begin{split}\begin{align*} A^Ty_{j} &= e_{j}, \forall j \in {1, .., d}\\ A^Tu_{j} &= -e_{j}, \forall j \in {1, .., d}\\ -x_{cj} + b^Ty_{j} &\leq r\\ x_{cj} + b^Tu_{j} &\leq r\\ r &\geq 0\\ y_{j} &\geq 0\\ u_{j} &\geq 0\\ r &\in R\\ y_{j} &\in R^n\\ u_{j} &\in R^n\\ x_c &\in R^d \end{align*}\end{split}\]

Source: Simon Foucart’s excellent book.

Parameters:

A – LHS Constraint Matrix
b – RHS Constraint column vector
equality_constraints – indices of rows that have strict equality A[eq] @ x = b[eq]
bin_vars – indices of binary variables
deterministic_solver – The underlying Solver to use, e.g. gurobi, ect

Returns:

the SolverOutput object, None if infeasible

ppopt.utils.constraint_utilities module

ppopt.utils.constraint_utilities.calculate_redundant_constraints(A, b)

Removes weakly redundant constraints, method is from the appendix of the Oberdieck paper url: https://www.sciencedirect.com/science/article/pii/S0005109816303971

Parameters:

A – LHS constraint matrix
b – RHS constraint column vector

Returns:

The processes’ constraint pair [A, b]

ppopt.utils.constraint_utilities.cheap_remove_redundant_constraints(A: ndarray, b: ndarray) → List[ndarray]

Removes zero rows, normalizes the constraint rows to ||A_i||_{L_2} = 1, and removes duplicate rows

Parameters:

A – LHS constraint matrix
b – RHS constraint column vector

Returns:

The processes’ constraint pair [A, b]

ppopt.utils.constraint_utilities.constraint_norm(A: ndarray) → ndarray

Finds the L2 norm of each row of a matrix

Parameters:: A – numpy matrix.
Returns:: A column vector of the row norms.

ppopt.utils.constraint_utilities.detect_implicit_equalities(A: ndarray, b: ndarray) → List[List[int]]

Detects inequality constraints that form implicit equality constraints. This is important because inequality constraint pairs that form equality constraints will actively mess with the true cardinality of the active set. Older solvers did not make check this and that led to some problematic results.

\[\begin{split}\begin{align*} -\langle a, x \rangle &\leq -b\\ \langle a, x \rangle &\leq b\\ \end{align*} \implies \langle a, x \rangle = b\end{split}\]

Parameters:

A – LHS of inequality set
b – RHS of inequality set

Returns:

List of all implicit inequality pairs

ppopt.utils.constraint_utilities.facet_ball_elimination(A: ndarray, b: ndarray) → List[ndarray]

Removes weakly redundant constraints, method is from the appendix of the Oberdieck paper url: https://www.sciencedirect.com/science/article/pii/S0005109816303971

Parameters:

A – LHS constraint matrix
b – RHS constraint column vector

Returns:

The processes’ constraint pair [A, b]

ppopt.utils.constraint_utilities.find_implicit_equalities(A: ndarray, b: ndarray, F: ndarray, equality_indices)

Find Implicit equalities in the main constraint block Ax <= b + F theta. E.g. L <= A_ix - F theta <= L. Which is equivalent to the direct constraint A_ix = b_i + F_i theta. Also detects when c^tx - d^t theta <= b and c^tx - d^T theta = b.

\[\begin{split}\begin{align} Ax &\leq b + F\theta\\ A_{eq}x &= b_{eq}\\ A_\theta \theta &\leq b_\theta\\ x &\in R^n, \theta \in R^m\\ \end{align}\end{split}\]

Parameters:

A – The LHS constraint matrix for main body constraints
b – the RHS constraint matrix for main body constraints
F – the RHS parametric uncertainty matrix in the main body constraints
equality_indices – Indices of equality constraints

Returns:

The filtered constraints matrix set A, b, F and the new equality set

ppopt.utils.constraint_utilities.find_redundant_constraints(A: ndarray, b: ndarray, equality_set: List[int] | None = None, solver='gurobi')

ppopt.utils.constraint_utilities.get_indices_of_zero_rows(A: array, epsilon: float = 1e-06) → [<class 'list'>, <class 'list'>]

ppopt.utils.constraint_utilities.is_full_rank(A: ndarray, indices: List[int] | None = None) → bool

Tests if the matrix A[indices] is full rank Empty matrices e.g. A[[]] will default to be full rank

Parameters:

A – Matrix
indices – indices to consider in rank

Returns:

if the matrix is full rank or not

ppopt.utils.constraint_utilities.process_program_constraints(A: ndarray, b: ndarray, F: ndarray, A_t: ndarray, b_t: ndarray, epsilon: float = 1e-06)

This is the main routine for removing redundant constraints and filtering constraints to the correct constraint set

\[\begin{split}\begin{align} Ax &\leq b + F\theta\\ A_{eq}x &= b_{eq}\\ A_\theta \theta &\leq b_\theta\\ x &\in R^n, \theta \in R^m\\ \end{align}\end{split}\]

Parameters:

A – The LHS constraint matrix for main body constraints
b – the RHS constraint matrix for main body constraints
F – the RHS parametric uncertainty matrix in the main body constraints
A_t – the LHS constraint matrix for parametric constraints
b_t – the RHS constraint vector for parametric constraints
epsilon – The numerical value to determine if something is a ‘zero’ row

Returns:

The filtered constraint matrix set A, b, F, A_t, b_t

ppopt.utils.constraint_utilities.process_region_constraints(A: ndarray, b: ndarray, deterministic_solver: str = 'gurobi') → List[ndarray]

Removes all strongly and weakly redundant constraints

Parameters:

A – LHS constraint matrix
b – RHS constraint column vector
deterministic_solver – the exact solver to be used

Returns:

The processes’ constraint pair [A, b]

ppopt.utils.constraint_utilities.remove_duplicate_rows(A: ndarray, b: ndarray) → List[ndarray]: Finds and removes duplicate rows in the constraints A @ x <= b.

ppopt.utils.constraint_utilities.remove_strongly_redundant_constraints(A: ndarray, b: ndarray, include_kept_indices=False, deterministic_solver: str = 'gurobi'): Removes strongly redundant constraints by testing the feasibility of each constraint if activated.

ppopt.utils.constraint_utilities.remove_zero_rows(A: ndarray, b: ndarray) → List[ndarray]

Finds rows equal to zero in A and then removes them from A and b

Parameters:

A – LHS Matrix constraint
b – RHS Column vector

Returns:

a list[A_cleaned, b_cleaned] of filtered constraints

ppopt.utils.constraint_utilities.row_equality(row_1: ndarray, row_2: ndarray, tol=1e-16) → bool

Tests if 2 row vectors are approximately equal

Parameters:

row_1 –
row_2 –
tol – tolerable L2 norm of the difference

Returns:

True if rows are equal

ppopt.utils.constraint_utilities.scale_constraint(A: ndarray, b: ndarray) → List[ndarray]

Normalizes constraints based on the L2 norm.

Parameters:

A – LHS Matrix constraint
b – RHS column vector constraint

Returns:

a list [A_scaled, b_scaled] of normalized constraints

ppopt.utils.constraint_utilities.shuffle_processed_constraints(A: ndarray, b: ndarray, F: ndarray, A_t: ndarray, b_t: ndarray, kept: list, remove: list)

Parameters:

A – The LHS constraint matrix for main body constraints
b – the RHS constraint matrix for main body constraints
F – the RHS parametric uncertainty matrix in the main body constraints
A_t – the LHS constraint matrix for parametric constraints
b_t – the RHS constraint vector for parametric constraints
kept –
remove –

:return:The filtered constraint matrix set A, b, F, A_t, b_t

ppopt.utils.general_utils module

ppopt.utils.general_utils.latex_matrix(A: List[str] | ndarray) → str

Creates a latex string for a given numpy array

Parameters:: A – A numpy array
Returns:: A latex string for the matrix A

ppopt.utils.general_utils.make_column(x: List | ndarray) → ndarray

Makes x into a column vector

Parameters:: x – a list or a numpy array
Returns:: a numpy array that is a column vector

ppopt.utils.general_utils.make_row(x: List | ndarray) → ndarray

Makes x into a row vector

Parameters:: x – a list or a numpy array
Returns:: a numpy array that is a row column

ppopt.utils.general_utils.num_cpu_cores()

Finds the number of allocated cores,with different behavior in windows and linux.

In Windows, returns number of physical cpu cores

In Linux, returns number of available cores for processing (this is for running on cluster or managed environment)

Returns:: number of cores

ppopt.utils.general_utils.ppopt_block(mat_list)

This is an internal utility function that was created for internal use only for performance reasons. This is a replacement of numpy.block for performance sensitive sections of the codebase. This is approximately 3x faster for the matrices that are typically used here.

Parameters:: mat_list – a list of matrices to concatenate in the same format as numpy.block
Returns:: the concatenated matrix

ppopt.utils.general_utils.remove_size_zero_matrices(list_matrices: List[ndarray]) → List[ndarray]

Removes size zero matrices from a list

Parameters:: list_matrices – A list of numpy arrays
Returns:: returns all matrices from the list that do not have a dimension of 0 in any index

ppopt.utils.general_utils.render_number(x, trade_off=0.0001) → str

ppopt.utils.general_utils.select_not_in_list(A: ndarray, list_: Iterable[int]) → ndarray

Filters a numpy array to select all rows that are not in a list

Parameters:

A – a numpy array
list – a list of indices that you want to remove

Returns:

return a numpy array of A[not in list_]

ppopt.utils.geometric module

ppopt.utils.mpqp_utils module

ppopt.utils.mpqp_utils.build_suboptimal_critical_region(program: MPQP_Program, active_set: List[int])

Builds the critical region without considering culling facets or any other operation. Primary uses for this is based on culling lower dimensional feasible sets.

Parameters:

program – the MQMP_Program to be solved
active_set – the active set combination to build this critical region from

Returns:

Returns the associated critical region if fully dimensional else returns None

ppopt.utils.mpqp_utils.gen_cr_from_active_set(program: MPQP_Program, active_set: List[int], check_full_dim=True) → CriticalRegion | None

Builds the critical region of the given mpqp from the active set.

Parameters:

program – the MQMP_Program to be solved
active_set – the active set combination to build this critical region from
check_full_dim – Keyword Arg, if true will return null if the region has lower dimensionality

Returns:

Returns the associated critical region if fully dimensional else returns None

ppopt.utils.mpqp_utils.get_boundary_types(region: ndarray, omega: ndarray, lagrange: ndarray, regular: ndarray) → List

Classifies the boundaries of a polytope into Omega constraints, Lagrange multiplier = 0 constraints, and Activated program constraints

Parameters:

region –
omega –
lagrange –
regular –

Returns:

ppopt.utils.mpqp_utils.is_full_dimensional(A, b, solver: Solver | None = None)

This checks the dimensionality of a polytope defined by P = {x: Ax≤b}. Current method is based on checking if the radii of the chebychev ball is nonzero. However, this is numerically not so stable, and will eventually be replaced by looking at the ratio of the 2 chebychev balls

Parameters:

A – LHS of polytope constraints
b – RHS of polytope constraints
solver – the solver interface to direct the deterministic solver

Returns:

True if polytope is fully dimensional else False

Module contents

PPOPT.UTILS INIT FILE - todo fill in.