Linear constrained optimization

2. Linear constrained optimization#

In this chapter, we’ll cover how to apply scipy.optimize.linprog to linear constrained optimization problems. As a reminder, linear constrained optimization considers:

(2.1)#minxf(x)such thatgj(x)0j=1,mhk(x)=0k=1,pxilxixiui=1,n

with:

  • f(x), the linear objective function

  • x, the n design variables

  • gj(x), the m linear inequality constraints

  • hk(x), the p linear inequality constraints

  • xkl and xku, the n low er and upper bounds of the design variable

Because all functions are linear, this problem can be rewritten as:

(2.2)#minxcTxsuch thatAubxbubAeqx=beqxilxixiui=1,n

with:

  • x, the n design variables

  • c, the n coefficients of the linear objective function

  • Aub, the inequality constraint matrix of m inequality constraints

  • bub, the inequality constraint vector of m inequality constraints

  • Aeq, the equality constraint matrix of p equality constraints

  • beq, the equality constraint vector of p equality constraints

  • xil and xiu, the n lower and upper bounds of the design variable

Method#

For linear programs, we can use the function scipy.optimize.linprog. In contrast to scipy.optimize.minimize, this function is limited to linear functions. The documentation of this function is available here: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html [The SciPy community, 2024]. In this course we’ll cover only the relevant parts.

Again, we won’t use all options, but a minimum requirement for our problem is the command scipy.optimize.linprog(c, A_ub, b_ub, A_eq, b_eq, bounds, ...) with:

  • c, a onedimensional numpy array with the n coefficients of the linear objective function c.

  • A_ub, a twodimensional numpy array with the n coefficient of the m linear inequality constraints matrix Aub.

  • b_ub, a onedimensional numpy array with the upper bound of the m linear inequality constraint vector bub.

  • A_eq, a twodimensional numpy array with the n coefficient of the p linear equality constraints matrix Aeq.

  • b_eq, a onedimensional numpy array with value of the p linear equality constraint vector beq.

  • Bounds: A sequence of i (min, max) pairs for each element in x, defining the minimum xil and maximum values xiu of that decision variable. Use None to indicate that there is no bound.

The function scipy.optimize.linprog outputs an object scipy.optimize.OptimizeResult similar as scipy.optimize.minimize explained for unconstrained optimization.

Test Yourself

Questions, discussions and comments#