The problem of convex programming, Approximate solution of convex programming problems by the method of piecewise linear approximation - Investigation of operations in economics

The convex programming problem

Let there be given a system of inequalities of the form


and function


and all the functions φ; (Χ) are convex on some convex set A7, and the function Ζ is either convex on the set A /, or concave. The convex programming problem (VP) consists in finding a solution of the constraint system (10.6), for which the objective function Ζ reaches the minimum value or the concave function Ζ reaches its maximum value. The conditions of non-negativity of variables can be considered included in the system (10.6).

In view of property 3 (see Section 10.1), any linear programming problem is a special case of the VP problem. In the general case, the VP problems are problems of non-linear programming. The allocation of problems to a special class is explained by the extremal properties of convex functions: every local minimum of a convex function (the local maximum of a concave function) is simultaneously global; in addition, in view of property 2, a convex (concave) function defined on a closed bounded set attains a global maximum and a global minimum on this set. It follows that if the objective function Z is strictly convex (strictly concave) and if the domain of solutions of the constraint system is not empty and bounded, then the VP problem always has a unique solution. In this case, the minimum of a convex (maximum concave) function is achieved inside the solution domain if there is a stationary point there, or on the boundary of this region, if there is no stationary point inside it. In the general case, it can be stated only that the set of optimal solutions of any problem is a convex set.

10.4. Geometrically solve the following task VP: find the minimum of the function under constraints:

Solution. We build the domain of admissible solutions of this problem:

a) is a circle with the center at the origin of coordinates

nat and the radius R = 2 (Figure 10.3). The domain of solutions of the inequality consists of points lying inside this circle and on it itself;

b) - a straight line that can be constructed, for example, by points (0; 0) and (2; 1). The domain of solutions of the inequality

- the half-plane lying above this line, including the straight line itself;

c) x 2 = 2х {is a straight line, which is constructed, for example, by the points (0; 0) and (1; 2). The domain of solutions of the inequality

Fig. 10.3

x 2 2. Γ, is the half-plane lying under this line, including the straight line itself. Thus, taking into account the conditions of non-negativity of variables, the domain of admissible solutions of this problem is the closed sector OAB (see Figure 10.3).

Now we construct the level line of the function Z and define the direction of decrease of Z. All the level lines have the equation For C = 3 we get the level line is a circle

with center at the point O l (1; 1) and radius R = 1. It is clear that at any point of this level line, when moving from the center of the circle O, the function Z increases, and when it moves to the center it decreases. Thus, the minimum of Z is attained at the point (1; 1), (it is easy to see that the point (1; 1) is a stationary point of the function Z). ►

Approximate solution of convex programming problems by piecewise linear approximation

The function is called separable,

if it can be represented as a sum of functions, each of which depends only on one variable, ie. if


(it is possible that for some d).

Suppose that the goal function Z in the problem VP (10.6), (10.7) and the objective function Z, and all the constraints φ (are separable.) Then the problem looks like: find the minimum of the convex (maximum concave)

functions under the restrictions & quot;.


The idea of ​​the piecewise linear approximation method is that all f i and all & lt; p ~ are replaced by broken lines consisting of rectilinear segments. In this case, the initial task of the VP is replaced by a new, approximate problem, which is a linear programming problem. This problem is usually solved by a simplex method, and its solution is an approximate solution of the original problem of the EaP.

To construct an approximate problem, we consider a piecewise linear approximation of a function of one variable h (x), given on the interval [0, a]. We divide this segment into r parts by points so that (Figure 10.4). We calculate the values ​​of the function at these points. We connect in pairs the points and segments of lines. The broken line h (x) approximates the function h (x) on the interval [0, a] consisting of these segments. Without considering here an estimate of the accuracy of the approximation, we only note that the accuracy can be increased due to a smaller partition of the segment.

The equation of the polyline segment between the points (x k h k) and looks like: (equation

Fig. 10.4

a straight line on two points). If each of the relations in this equality is denoted by λ, then we get:



Note that for each there exists a unique value λ that satisfies the conditions (10.10) (see the equation of the interval (10.2)). By designating ,

, you can rewrite (10.10) in the form



Equations (10.11) are called the parametric equations of the interval. If h (x) = 0, then the second of these equations becomes 0 = 0, and the former takes the form (10.2) is the equation of the segment lying on the abscissa axis.

Thus, for any scrap equation

can be written in the form

( 10 . 12 )

where only two values ​​ are always different from zero (if X is an internal point of the k-ro of the segment of the partition) or one (if x coincides with the end of the segment).

Returning to the VP problem with separable functions, we note that, first of all (depending on the constraint system), it is necessary to determine the interval of variation of each variable . Then each interval is divided into parts by points and a piecewise linear approximation for functions is constructed using formulas (10.12), and . After this, we can write down the approximate problem for the initial problem (10.9):

find the maximum of the function

under the constraints (10.13)

Since the approximate problem (10.13) is a linear programming problem and we usually solve it by the simplex method, the conditions for the non-negativity of the variables are written separately from the remaining constraints. The difference between the obtained problem (10.13) and the usual linear programming problem is that for each X - there are no more than two neighboring nonzero and, therefore, take as the main variables two j and non-adjacent k. Note also that for the conditions of nonnegativity of the variables of the summands f- yxjj and (if any) a piecewise-linear an

it is of course not necessary to carry out the proximity.

10.5. Find the minimum of the constraint:

Solve this problem by piecewise-linear approximation.

Solution. First of all, we recommend that you make sure that the task is an EaP task (use the Sylvester criterion, see problem (10.2)). Further, under the condition of non-negativity of variables, the inequality shows that .g, can only change

from 0 to 2, and x 2 - from 0 to 4 (Figure 10.5).

The segment [0; 2] divided by points and the segment [0; 4] - points

. Comparing the condition of this problem with (10.9), we see that

Fig. 10.5

It is convenient to first compute the necessary values ​​of these functions (since we have only one restriction, that is, m = 1, we will write, and instead of φπ and φ12).

By the formulas (10.12) we have:

Thus, the approximate problem (10.13) for the given VP problem has the form: find the minimum of the function

under constraints:

We obtained a linear programming problem with 8 variables . To solve it by the simplex method, the first restriction-inequality must be transformed into an equation by introducing an additional nonnegative variable, which we denote by u:

Then the constraint system becomes a system of sin equations with 9 variables, i.e. 3 variables should be taken as the main ones (we take , since they enter only one equation each), and the remaining 6 are free. As usual, at each step of the solution, the main variables and the goal function are expressed in terms of free (non-basic) variables.

I step.

Since there are free variables with negative coefficients in the expression Z, the first basic solution is non-optimal (although it is feasible), and according to the simplex algorithm , it should be translated into the main variables. Find min , select the third equation and change the variable into free variables.

Step II. The main variables λ22, λ10, and.

Step III. The main variables λ , λ22, and.

The criterion of optimality of the simplex method is fulfilled, so, at 111 step the optimal basic solution is obtained:

Turning to the original variables we get:

Thus, the optimal solution of the approximate problem (1; 2) and

It would be possible to solve geometrically the initial problem of the VP and to verify that the optimal solution of the approximate problem exactly coincides with the optimal solution of the original problem. This coincidence is accidental. In the general case, the solution obtained is only a certain approximation of the optimal solution of the original problem. To improve the accuracy of the approximation, we can break up into smaller parts not the initial segments of the change of variables, but the smaller ones taken in the neighborhood of the first approximation obtained. The disadvantage of the method is a large increase in the dimensionality of the problem (that is, the number of variables) in the transition to an approximate linear model.

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.