NONLINEAR PROGRAMMING: METHODS AND EXERCISES - MATHS - 2025

The nonlinear programming is the process of optimizing a function that depends on several independent variables, which in turn are subjected to restrictions.

If one or more of the constraints, or if the function to be maximized or minimized (called the objective function), is not expressed as a linear combination of the variables, then you have a nonlinear programming problem.

Figure 1. Nonlinear programming problem (NLP). where G is the (non-linear) function to optimize in the green region, determined by the constraints. Source: F. Zapata.

And therefore the procedures and methods of linear programming cannot be used.

For example, the well-known Simplex method cannot be used, which only applies when the objective function and the constraints are all linear combinations of the variables in the problem.

Linear programming methods

For non-linear programming problems the main methods to be used are:

1.- Graphic methods.

2.- Lagrange multipliers to explore the boundary of the solution region.

3.- Calculation of the gradient to explore extremes of the objective function.

4.- The method of descending steps, to find the null gradient points.

5.- Modified method of the Lagrange multipliers (with the Karush-Kuhn-Tucker condition).

Example of solution with graphical method

An example of a solution with the graphical method is the one that can be seen in figure 2:

Figure 2. Example of a non-linear problem with non-linear restrictions and its graphical solution. Source: F. Zapata.

Exercises

- Exercise 1 (Graphic method)

The profit G of a certain company depends on the amount sold of product X and the amount sold of product Y, in addition, the profit is determined by the following formula:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Amounts X and Y are known to have the following restrictions:

X≥0; Y≥0 and X + Y ≤ 7

Determine the values ​​of X and Y that produce the maximum gain.

Figure 3. The profit of a company can be mathematically modeled to find the maximum profit using nonlinear programming. Source: Pixabay.

Solution

In this problem the objective function is nonlinear, while the inequalities that define the constraints are. This is a nonlinear programming problem.

For the solution of this problem, the graphical method will be chosen.

First, the solution region will be determined, which is given by the restrictions.

As X≥0; Y≥0, the solution must be found in the first quadrant of the XY plane, but since it must also be true that X + Y ≤ 7, the solution is in the lower half plane of the line X + Y = 7.

The solution region is the intersection of the first quadrant with the lower half plane of the line, which results in a triangular region where the solution is found. It is the same as indicated in figure 1.

On the other hand, the gain G can also be represented in the Cartesian plane, since its equation is that of an ellipse with center (2,3).

The ellipse is shown in Figure 1 for various values ​​of G. The higher the value of G, the greater the gain.

There are solutions that belong to the region, but do not give the maximum G value, while others, such as G = 92.4, are outside the green zone, that is, the solution zone.

Then, the maximum value of G, such that X and Y belong to the solution region corresponds to:

G = 77 (maximum gain), which is given for X = 7 and Y = 0.

Interestingly, the maximum profit occurs when the sales amount of product Y is zero, while the amount of product X reaches its highest possible value.

- Exercise 2 (Analytical method: Lagrange multipliers)

Find the solution (x, y) that makes the function f (x, y) = x ² + 2y ² maximum in the region g (x, y) = x ² + y ² - 1 = 0.

Solution

It is clearly a non-linear programming problem, since both the objective function f (x, y) and the restriction g (x, y) = 0, are not a linear combination of the variables x and y.

The Lagrange multipliers method will be used, which first requires defining the Lagrange function L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Where λ is a parameter called the Lagrange multiplier.

To determine the extreme values ​​of the objective function f, in the solution region given by the restriction g (x, y) = 0, follow these steps:

-Find the partial derivatives of the Lagrange function L, with respect to x, y, λ.

-Equalize each derivative to zero.

Here the sequence of these operations:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Possible system solutions

A possible solution of this system is λ = 1 so that the first equation is satisfied, in which case y = 0 so that the second is satisfied.

This solution implies that x = 1 or x = -1 for the third equation to be satisfied. In this way, two solutions S1 and S2 have been obtained:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

The other alternative is that λ = 2 so that the second equation is satisfied, regardless of the y value.

In this case, the only way for the first equation to be satisfied is for x = 0. Considering the third equation, there are only two possible solutions, which we will call S3 and S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

To find out which or which of these solutions maximize the objective function, we proceed to substitute in f (x, y):

S1: f (1, 0) = 1 ² + 2.0 ² = 1

S2: f (-1, 0) = (-1) ² + 2.0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

We conclude that the solutions that maximize f, when x and y belong to the circumference g (x, y) = 0 are S3 and S4.

The pairs of values ​​(x = 0, y = 1) and (x = 0, y = -1) maximize f (x, y) in the solution region g (x, y) = 0.

- Exercise 3 (Null gradient)

Find solutions (x, y) for the objective function:

f (x, y) = x ² + 2 y ²

Let be maximum in the region g (x, y) = x ² + y ² - 1 ≤ 0.

Solution

This exercise is similar to exercise 2, but the solution (or restriction) region extends to the interior region of the circumference g (x, y) = 0, that is to say to the circle g (x, y) ≤ 0. This includes to the circumference and its inner region.

The solution at the border was already determined in exercise 2, but the interior region remains to be explored.

To do this, the gradient of the function f (x, y) must be calculated and set equal to zero, to find extreme values ​​in the solution region. This is equivalent to calculating the partial derivatives of f with respect to x and y respectively and setting equal to zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

This system of equations has the only solution (x = 0, y = 0) that belongs to the circle g (x, y) ≤ 0.

Substituting this value in the function f results:

f (0, 0) = 0

In conclusion, the maximum value that the function takes in the solution region is 2 and occurs at the boundary of the solution region, for the values ​​(x = 0, y = 1) and (x = 0, y = -1).

References

1. Avriel, M. 2003. Nonlinear Programing. Dover Publishing.
2. Bazaraa. 1979. Nonlinear Programing. John Wiley & Sons.
3. Bertsekas, D. 1999. Nonlinear Programing: 2nd edition. Athena Scientific.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Nonlinear programming. Recovered from: es.wikipedia.com