papyri
{ } Raw JSON

bundles / scipy 1.18.0 / scipy / optimize / _linprog_ip / _ip_hsd

function

scipy.optimize._linprog_ip:_ip_hsd

source: /scipy/optimize/_linprog_ip.py:569

Signature

def _ip_hsd(A, b, c, c0, alpha0, beta, maxiter, disp, tol, sparse, lstsq, sym_pos, cholesky, pc, ip, permc_spec, callback, postsolve_args)

Summary

Solve a linear programming problem in standard form:

Extended Summary

Minimize 

c @ x

Subject to 

A @ x == b
    x >= 0

using the interior point method of [4].

Parameters

A : 2-D array

2-D array such that A @ x, gives the values of the equality constraints at x.

b : 1-D array

1-D array of values representing the RHS of each equality constraint (row) in A (for standard form problem).

c : 1-D array

Coefficients of the linear objective function to be minimized (for standard form problem).

c0 : float

Constant term in objective function due to fixed (and eliminated) variables. (Purely for display.)

alpha0 : float

The maximal step size for Mehrota's predictor-corrector search direction; see :math:`beta_3`of [4] Table 8.1

beta : float

The desired reduction of the path parameter (see [6])

maxiter : int

The maximum number of iterations of the algorithm.

disp : bool

Set to True if indicators of optimization status are to be printed to the console each iteration.

tol : float

Termination tolerance; see [4] Section 4.5.

sparse : bool

Set to True if the problem is to be treated as sparse. However, the inputs A_eq and A_ub should nonetheless be provided as (dense) arrays rather than sparse matrices.

lstsq : bool

Set to True if the problem is expected to be very poorly conditioned. This should always be left as False unless severe numerical difficulties are frequently encountered, and a better option would be to improve the formulation of the problem.

sym_pos : bool

Leave True if the problem is expected to yield a well conditioned symmetric positive definite normal equation matrix (almost always).

cholesky : bool

Set to True if the normal equations are to be solved by explicit Cholesky decomposition followed by explicit forward/backward substitution. This is typically faster for moderate, dense problems that are numerically well-behaved.

pc : bool

Leave True if the predictor-corrector method of Mehrota is to be used. This is almost always (if not always) beneficial.

ip : bool

Set to True if the improved initial point suggestion due to [4] Section 4.3 is desired. It's unclear whether this is beneficial.

permc_spec : str (default = 'MMD_AT_PLUS_A')

(Has effect only with sparse = True, lstsq = False, sym_pos = True.) A matrix is factorized in each iteration of the algorithm. This option specifies how to permute the columns of the matrix for sparsity preservation. Acceptable values are:

  • NATURAL: natural ordering.

  • MMD_ATA: minimum degree ordering on the structure of A^T A.

  • MMD_AT_PLUS_A: minimum degree ordering on the structure of A^T+A.

  • COLAMD: approximate minimum degree column ordering.

This option can impact the convergence of the interior point algorithm; test different values to determine which performs best for your problem. For more information, refer to scipy.sparse.linalg.splu.

callback : callable, optional

If a callback function is provided, it will be called within each iteration of the algorithm. The callback function must accept a single scipy.optimize.OptimizeResult consisting of the following fields:

x

Current solution vector

fun

Current value of the objective function

success

True only when an algorithm has completed successfully, so this is always False as the callback function is called only while the algorithm is still iterating.

slack

The values of the slack variables. Each slack variable corresponds to an inequality constraint. If the slack is zero, the corresponding constraint is active.

con

The (nominally zero) residuals of the equality constraints, that is, b - A_eq @ x

phase

The phase of the algorithm being executed. This is always 1 for the interior-point method because it has only one phase.

status

For revised simplex, this is always 0 because if a different status is detected, the algorithm terminates.

nit

The number of iterations performed.

message

A string descriptor of the exit status of the optimization.

postsolve_args : tuple

Data needed by _postsolve to convert the solution to the standard-form problem into the solution to the original problem.

Returns

x_hat : float

Solution vector (for standard form problem).

status : int

An integer representing the exit status of the optimization 

0 : Optimization terminated successfully
1 : Iteration limit reached
2 : Problem appears to be infeasible
3 : Problem appears to be unbounded
4 : Serious numerical difficulties encountered
message : str

A string descriptor of the exit status of the optimization.

iteration : int

The number of iterations taken to solve the problem

Aliases

  • scipy.optimize._linprog_ip._ip_hsd