Character solution of nonlinear programming problems

Introduction

With the advent of the SymPy library for solving mathematical problems, additional possibilities have appeared that allow displaying the results in symbolic form.

A detailed description of the use of symbolic computations is given in the publication [1] entitled “Introduction to Scientific Python” in the section “Symbolic Computations”.

Expanding the field of application of symbolic computations to solve individual nonlinear programming problems will hopefully promote Python, including as an alternative to expensive mathematical packages.
')

Formulation of the problem

Give examples of symbolic calculations for the unconditional extremum of a differentiated nonlinear goal function with the definition of sufficient conditions for the existence of an extremum in the Hessian matrix. Also consider the problem of conditional nonlinear programming with linear constraints using Lagrange multipliers.

In order to decide on the terminology I will give the following definition [2]. The nonlinear programming problem (the NP problem) is the problem of finding the maximum (minimum) of a nonlinear function of many variables when there are (not) constraints on the variables such as equalities or inequalities.

Symbolic calculation of the unconditional extremum of a differentiable function of three variables

Despite the complexity of the tasks to be solved with a symbolic solution, everything becomes simple and visual. Consider the listing of the first example.

from sympy import * x,y,z=symbols(' xyz' ) #f=x**2+2*y**2+3*z**2-2*x*y-2*x*z f=-x**2-5*y**2-3*z**2+x*y-2*x*z+ 2*y*z+11 *x+2*y+18*z+10 print('  f   x,y,z -\nf= ', f ) print('  ') fx=f.diff(x) print('df/dx =',fx,'=0') fy=f.diff(y) print('df/dy =',fy,'=0') fz=f.diff(z) print('df/dz =',fz,'=0') try: sols=solve([fx,fy,fz],x,y,z) except: print('   ') raise SystemExit(1) print('  M(x,y,z) -',sols) print('    ') fxx=f.diff(x,x).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fxx=',fxx) fxy=f.diff(x,y).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fxy=',fxy) fxz=f.diff(x,z).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fxz=',fxz) fyy=f.diff(y,y).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fyy=',fyy) fzy=f.diff(z,y).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fyz=',fzy) fzz=f.diff(z,z).subs({x:sols[x],y:sols[y],z:sols[z]}) print('fzz=',fzz) fyx=fxy;fzx=fxz;fyz=fzy#       print('    \n («»    )') d1=fxx print(' 1- d1=',d1) M2=Matrix([[fxx,fxy],[fyx,fyy]]) print(' 2-',M2) d2=M2.det() print(' 2- d2=',d2) M3=Matrix([[fxx,fxy,fxz],[fyx,fyy,fyz],[fzx,fzy,fzz]]) print(' 3-',M3) d3=M3.det() print(' 3- d3=',d3) print ('  ') if d1>0 and d2>0 and d3>0: print(' d1=%s,>0, d2=%s>0, d3=%s>0,  f   (%s,%s,%s)'%(str(d1),str(d2),str(d3),str(sols[x]),str(sols[y]),str(sols[z]))) elif d1<0 and d2>0 and d3<0: print(' d1=%s,<0, d2=%s>0, d3=%s<0, f   (%s,%s,%s)'%(str(d1),str(d2),str(d3),str(sols[x]),str(sols[y]),str(sols[z]))) elif d3!=0: print('   (%s,%s,%s)'%(str(sols[x]),str(sols[y]),str(sols[z]))) else: print('    (%s,%s,%s)'%(str(sols[x]),str(sols[y]),str(sols[z]))) r=f.subs({x:sols[x],y:sols[y],z:sols[z]}) print(' %s    (%s,%s,%s)'%(str(r),str(sols[x]),str(sols[y]),str(sols[z]))) 

Result

The analyzed function f for the variables x, y, z - f = -x ** 2 + x * y - 2 * x * z + 11 * x - 5 * y ** 2 + 2 * y * z + 2 * y - 3 * z ** 2 + 18 * z + 10

Necessary conditions for extremum

df / dx = -2 * x + y - 2 * z + 11 = 0
df / dy = x - 10 * y + 2 * z + 2 = 0
df / dz = -2 * x + 2 * y - 6 * z + 18 = 0

Stationary points M (x, y, z) - {x: 4, y: 1, z: 2}

Second derivatives at point M

fxx = -2
fxy = 1
fxz = -2
fyy = -10
fyz = 2
fzz = -6

Calculation of the determinants of the Hesse matrix (“grow up” from the upper left corner)

The determinant of M1-d1 = -2
Matrix M2-Matrix ([[- 2, 1], [1, -10])
The determinant of M2 - d2 = 19
Matrix M3-Matrix ([[- 2, 1, -2], [1, -10, 2], [-2, 2, -6]])
The determinant of M3 - d3 = -74

Sufficient Extreme Conditions
When d1 = -2, <0, d2 = 19> 0, d3 = -74 <0, the maximum f at point M (4,1,2)
The value of 51 functions at the point M (4,1,2)

There are a lot of explanations in the program, but this is a positive thing for both learning and research. The number of variables in the goal function can both increase and decrease as suggested in [3].

The program determines the extremum of the minimum or maximum, as well as the "saddle". If the target function is not differentiated, the program displays a message and stops working. For example, by changing the goal function we get:

The analyzed function f for the variables x, y, z - f = x ** 2 - 2 * x * y - 2 * x * z + 2 * y ** 2 + 3 * z ** 2

Necessary conditions for extremum

df / dx = 2 * x - 2 * y - 2 * z = 0
df / dy = -2 * x + 4 * y = 0
df / dz = -2 * x + 6 * z = 0

Stationary points M (x, y, z) - {z: 0, y: 0, x: 0}

Second derivatives at point M

fxx = 2
fxy = -2
fxz = -2
fyy = 4
fyz = 0
fzz = 6

Calculation of the determinants of the Hesse matrix (“grow up” from the upper left corner)

The determinant of M1-d1 = 2
Matrix M2-Matrix ([[2, -2], [-2, 4]])
The determinant of M2 - d2 = 4
Matrix M3-Matrix ([[2, -2, -2], [-2, 4, 0], [-2, 0, 6]])
The determinant of M3 - d3 = 8

Sufficient Extreme Conditions
When d1 = 2,> 0, d2 = 4> 0, d3 = 8> 0, the minimum is f at point M (0.0.0)

Value 0 of function at point M (0,0,0)

Symbolic definition of the conditional extremum of a differentiable function using the Lagrange multipliers method

Let us demonstrate the Lagrange method by the example of a problem taken from the publication [4] by which we can compare the results:

There are two ways to produce some product. Production costs for each method depend on the x and y produced as follows: g (x) = 9 * x + x ** 2, g (y) = 6 * y + y ** 2. In a month, it is necessary to produce 3 × 50 units of production, distributing it between two methods so as to minimize total costs.

Consider the symbolic solution of the problem, which explains the method.

 from sympy import * x,y,w=symbols(' xyw' ) g=9*x+x**2+6*y+y**2 print('  f   x,y :\nf= ', g) q=x+y-150 print(': ', q,'=0') f=9*x+x**2+6*y+y**2+w*(x+y-150) print('   :\n ',f) fx=f.diff(x) print('df/dx =',fx,'=0') fy=f.diff(y) print('df/dy =',fy,'=0') fw=f.diff(w) print('df/dw =',fw,'=0') sols=solve([fx,fy,fw],x,y,w) print('  M(x,y) :\n',float(sols[x]),',',float(sols[y])) 

Result

The analyzed function f for variables x, y:

f = x ** 2 + 9 * x + y ** 2 + 6 * y

Restrictions: x + y - 150 = 0

Auxiliary Lagrange function:

w * (x + y - 150) + x ** 2 + 9 * x + y ** 2 + 6 * y
df / dx = w + 2 * x + 9 = 0
df / dy = w + 2 * y + 6 = 0
df / dw = x + y - 150 = 0

Stationary point M (x, y):
74.25, 75.75

Instead of conclusions

The result coincides with that given in [4], but the main thing, in my opinion, is different. On the example of symbolic calculations, it is easier to understand any method and use it. But for mathematical packages this idea is not new, and in Mathcad and in Matlab, symbolic calculations have long been widely used. But this is in Python!

Thanks to everyone who read the article.

Links

1. Introduction to Scientific Python.
2. Topic 6. Non-linear programming.
3. Extremes of functions of two and three variables.
4. Lagrange multipliers method. An example solution.