Keywords

1 Introduction

The paper discusses Large-Scale optimization problems with the number of decision variables and the number of constraints. Such problems arise, for example, in finding optimal solutions in complex systems (production, economic and social). It is discussed in the papers [1,2,3].

There are two methodologies of Large-Scale problem solving: parallel computing based on mathematical programming algorithms and problem decomposition at the stage of defining of numerical algorithms. The last method is developed within the framework of block programming and is examined in this work.

Theoretical and applied methods of block programming is not limited only to development of efficient computing schemes and algorithms for Large-Scale optimization. These methods allow to study of information systems and the processes of coordination in complex systems [3]. In a general sense, algorithmic computation may be an example of public hierarchical system with distributed decision-making.

Lower elements play a leading role in making decisions in industrial practice. These elements are also known as “blocks” in mathematical researches [2].

Coordination Centre provides decisions on resources and production constraints. However, the main role of the Centre is to ensure the optimality of block solutions to serve the target function well.

The hierarchical system is driven by information flows between the elements. The volume of flows is substantially less than task dimensions.

To the present time has been widely used block methods of linear programming, in particular, the Dantzig-Wolfe Decomposition [1, 2, 4]. In [2, 4] it is shown that the linear programming problems to be solved by this method are a special case of the composite (block) tasks of nonlinear programming problem. This fact can be used to solve convex mathematical Large-Scale programming problems. In this paper, this method is used to build hierarchical algorithms for solving quadratic programming problems in which the objective function is convex and the constraints coincide with the linear programming problems.

2 Methods

The method of Dantzig-Wolfe Decomposition is obtained and justified as a specialized case of the simplex method for solving Large-Scale linear programming problems with a block structure system of constraints.

In this section, we will show that this method is applicable for convex mathematical programming problems, where the objective function has a composite (block) structure and constraints.

Let’s describe this class of Large-Scale problems [2].

Let \( Z_{i} \) be a set of function values \( z_{i}^{{}} (x_{i}^{{}} ) \).

We introduce the notation:

$$ \begin{aligned} & x = \{ x_{1} , \ldots ,x_{n} \} \in X = \times \prod\limits_{i = 1}^{n} {X_{i} } ;\quad z(x) = (z_{1} (x_{1} ), \ldots ,z_{n} (x_{n} )) \in Z = \times \prod\limits_{i = 1}^{n} {Z_{i} } ; \\ & \tilde{X} = \{ x \in X|g(z(x)) \in G\} ; \\ & \tilde{Z} = \{ z \in Z|g(z) \in G\} , \\ \end{aligned} $$

where \( \times \prod\limits_{i = 1}^{n} {X_{i} = } X_{1} \times \ldots \times X_{n} \) & \( \times \prod\limits_{i = 1}^{n} {Z_{i} } = Z_{1} \times \ldots \times Z_{n} \) are the Cartesian product of the sets \( X_{1} , \ldots ,X_{n} \) and \( Z_{1} , \ldots ,Z_{n} \), respectively.

Write n-block optimization problem:

$$ \hbox{max} \,\{ f(z(x))|x \in \tilde{X}\} $$
(1)

We introduce a system of tasks.

The task of the center:

$$ \hbox{max} \{ f(z)|z \in \tilde{Z}\} $$
(2)

The objective of the unit \( i,i = 1, \ldots ,n:: \)

$$ \delta_{i}^{{}} = \hbox{min} \,\{ \,||z_{i}^{*} - z_{i}^{{}} (x_{i}^{{}} )||\;|x_{i}^{{}} \in X_{i}^{{}} \,\} = 0 $$
(3)

where \( z_{{}}^{*} = (z_{1}^{*} , \ldots ,z_{n}^{*} ) \) is one of the solutions to problem (2).

Let’s show that problems (1) and (2)–(3) are equivalent.

The vector \( x^{*} = (x_{1}^{*} , \ldots ,x_{n}^{*} ) \) is obtained from solving all n problems (3). Let’s s call it the solution of the problem (2)–(3).

Thus, the vector z is considered to be an auxiliary vector.

Two extreme problems are equivalent if the set of solutions coincides. Suppose that there is the solution of problems.

For the problem (3) let \( z_{i}^{*} \in Z_{i}^{{}} \). Then for any \( z_{i}^{*} \in Z_{i}^{{}} \) we get \( \delta_{i} = 0 \), i.e. there is true equality

$$ z_{i}^{*} = z_{i}^{{}} (x_{i}^{*} ) $$
(4)

where \( x_{i}^{*} \) is the solution of the problem (3).

We will show that any solution of problem (1) is the solution of the system (2)–(3).

Let \( x_{{}}^{*} \) be a solution of problem (1), i.e. \( x_{{}}^{*} \in \tilde{X}; \) \( f(z(x_{{}}^{*} )) \ge f(z(x))\,\;\;\forall x \in \tilde{X} \). Examine the vector \( z_{{}}^{*} = z(x_{{}}^{*} ) \). For this vector, the fair inclusion \( z_{{}}^{*} \in Z \) and relationships \( f(z_{{}}^{*} ) = f(z(x_{{}}^{*} )) \ge f(z) = f(z(x))\quad \forall x \in \tilde{X} \).

The inequality is fulfilled when \( z \in \tilde{Z} \), i.e. \( z_{{}}^{*} \in \tilde{Z};\quad f(z_{{}}^{*} ) \ge f(z)\quad \forall z \in \tilde{Z} \). Therefore \( z_{{}}^{*} \) is the solution of the problem (2). Since (4) is satisfied, the vector \( x_{{}}^{*} = (x_{1}^{*} , \ldots ,x_{n}^{*} ) \) is the solution of the problem (3).

We will show that any solution of the system (2)–(3) is the solution of problem (1). Let \( z_{{}}^{*} = (z_{1}^{*} , \ldots ,z_{n}^{*} ); \) \( x_{{}}^{*} = (x_{1}^{*} , \ldots ,x_{n}^{*} ) \) be solutions of problems (2) and (3) respectively. The condition (4) is satisfied. We have \( g(z_{{}}^{*} ) = g(z(x_{{}}^{*} )) \in G; \) \( x_{i}^{*} \in X_{i}^{{}} ,\quad i = 1, \ldots ,n \); whence it follows that \( x_{{}}^{*} \in \tilde{X} \). Next, a vector \( z_{{}}^{*} \), by definition, satisfies the condition \( f(z_{{}}^{*} ) \ge f(z)\quad \forall z \in \tilde{Z} \). Given this expression and the definition \( \tilde{Z} \), we have \( f(z_{{}}^{*} ) = f(z(x_{{}}^{*} )) \ge f(z(x))\quad \forall x \in \tilde{X} \). Thus, \( x_{{}}^{*} \) is the solution of the problem (1).

It is easy to show that if the problem (1) has no solution, there is no solution in (2), and vice versa. In addition, the extreme values of the problem functions (1) and (2) coincide. So, we have proved the equivalence of problems (1) and (2)–(3). Therefore, it is proved that the system (n + 1) of extreme problems (2)–(3) is the block decomposition of extremal problem (1).

Problems (2), (3) can be solved with a set Z known in the task of center and, thus, all hierarchical algorithms have to find Z at the initial stage, or a subset \( \bar{Z}_{{}}^{*} \subset Z \) that contains the optimal solution or, finally, the point \( z_{{}}^{*} \). Here it is assumed that \( \bar{Z}_{{}}^{*} \cap Arg\,\hbox{max} \,\{ f(z)|z \in Z;\;g(z) \in G\} \ne \phi \).

Thus, the set of all algorithms may be classified in accordance with the following:

  1. (1)

    It restores a set Z as a whole.

  2. (2)

    It restores a significant part \( \bar{Z}_{{}}^{*} \) of the set Z.

  3. (3)

    It builds a maximizing sequence \( \{ z_{{}}^{k} \}_{k = 1}^{\infty } \), converging to \( z^{*} \).

Let’s consider below the 2nd way of building hierarchical algorithms in the case of inner approximation of the set Z. In the case of a convex set Z, it is similar to Dantzig-Wolfe Decomposition. In a specific example, we consider the example of the algorithm for solving the quadratic programming problem.

3 Results

Consider the second way of building hierarchical algorithms in the case of inner approximation of the set Z

Let’s write it in the following form:

Step 1. (starting the algorithm). Set \( Z_{i}^{1} \) with a defined condition \( Z_{i}^{1} \subseteq Z_{i}^{{}} ;\;\prod\limits_{i = 1}^{n} {Z_{i}^{1} } = Z_{{}}^{1} \cap \{ z|g(z) \in G\} \ne \phi \). Believe \( k = 1 \).

Step 2. Solve the problem of the Centre in the formulation (2). Find \( z_{{}}^{k} \) and the possible ways of checking the optimality of this solution for the set Z.

Step 3. Check the optimality condition of the point \( z_{{}}^{k} \) on the set Z. If the point \( z_{{}}^{k} \) is optimal on the set Z, go to step 5. Otherwise, find the point \( \tilde{z}_{{}}^{k} \), at which the optimality conditions on Z are violated.

Step 4. Go to set \( Z^{k + 1} \), apply \( k = k + 1 \) and go to step 2.

Step 5 (finding solutions). For \( z_{i}^{k} \) solve the problem (3) with \( \delta_{i}^{k} = 0, \) because \( z_{i}^{k} \in Z_{i} \).

For step 3 of the algorithm, consider a general nonlinear programming problem:

$$ \hbox{max} \,\{ \,f(z)|g_{j}^{{}} (z) \ge 0,\;j = \overline{{1,m_{1}^{{}} }} ;\;g_{j}^{{}} (z) = 0,\;j = \overline{{m_{1}^{{}} + 1,m}} ;\;z \in Z\,\} $$
(5)

where \( f,g_{j}^{{}} (z) \) is a continuously differentiable functions; \( Z \) - convex closed set containing interior points.

It is known the following property of problem (5), named as a generalized rule of Lagrange multipliers [5]. Let \( z_{{}}^{0} \) - the solution of problem (5). Suppose that the vectors \( g_{j}^{i} (z_{{}}^{0} ) \) \( j \in \{ \,m_{1}^{{}} + 1, \ldots ,m\,\} \cup \{ \,i = 1,2, \ldots ,m_{1}^{{}} |g_{i}^{{}} (z_{0}^{{}} ) = 0\,\} \) are linearly independent. Then there exist non-zero multipliers \( \lambda_{j}^{0} \,(j = 0,1, \ldots ,m) \), such that \( \lambda_{j}^{0} \ge 0,\; \) \( j = 0,1, \ldots ,m_{1} ; \) \( \lambda_{j}^{0} \cdot g_{j}^{{}} (z_{{}}^{0} ) = 0 \), \( j = 1, \ldots ,m \), and for all \( z \in Z \) is fulfilled \( (\lambda_{0}^{{}} f'(z_{{}}^{0} ) + \sum\limits_{j = 1}^{m} {\lambda_{j}^{0} g_{j}^{'} (z_{{}}^{0} ),\;z - z_{{}}^{0} ) \le 0} \).

Let discuss the use of this result for block quadratic programming. In step 4 of the algorithm, it is possible to apply the approach of method Dantzig-Wolfe Decomposition to construct a sequence of sets \( \bar{Z}_{{}}^{k} \) of convex linear combinations \( k \) of the known points from the set \( Z \).

Consider the mathematical model of production planning T industrial enterprises in the following form:

$$ \mathop {\hbox{max} }\limits_{x \in X} \left\{ {\sum\limits_{t = 1}^{T} { - (P_{t}^{H} - p_{t} x_{t} )^{2} |x_{t} \in X_{t} ,\;t = 1, \ldots ,T;\;\sum\limits_{t = 1}^{T} {\bar{A}x_{t} \le B} } } \right\} $$
(6)

where \( P_{t}^{H} \) - the profit potential, and \( X_{t}^{{}} \) – a valid set of unit plans \( t \): \( X_{t}^{{}} = \{ x_{t}^{{}} \in R_{{}}^{n} |A_{t}^{{}} x_{t}^{{}} \le B_{t}^{{}} ;\quad x_{t}^{{}} \ge 0 \).

The matrix in the above expressions have the following dimensions: \( p_{t}^{{}} - (1 \times n_{t}^{{}} );\;x_{t}^{{}} - (n_{t}^{{}} \times 1);\;\bar{A}_{t}^{{}} - (m \times n_{t}^{{}} ); \) \( B - (m \times 1); \) \( A_{t}^{{}} - (m_{t}^{{}} \times n_{t}^{{}} ); \) \( B_{t}^{{}} - (m_{t}^{{}} \times 1) \), where the first number indicates the number of rows, the second - the number of columns.

The economic meaning of the planning model is to optimize production plans of enterprises, where the potential possibilities for profit are maximally implemented.

Let’s introduce the units \( P_{t} = p_{t}^{{}} x_{t}^{{}} , \) \( S_{t} = \bar{A}_{t}^{{}} x_{t}^{{}} \) for problem (6) and the set \( Z_{t} \) of possible values for these units. Then problem (2) in this case has the form:

$$ \mathop {\hbox{max} }\limits_{(P,S)} \left\{ {\sum\limits_{t = 1}^{T} { - (P_{t}^{H} - P_{t} )^{2} |(P_{t} ,S_{t} ) \in Z_{t} ,\;t = 1, \ldots ,T;\;\sum\limits_{t = 1}^{T} {S_{t} \le B} } } \right\} $$
(7)

Let is found set \( Z_{t}^{k} \subseteq Z_{t} \) on iteration k of the algorithm. By solving the problem (7) for these sets, there is obtained points \( z_{t}^{k} \in Z_{t} \) and the dual variables \( u_{{}}^{k} \). According to (5) the point is optimal for the corresponding block problem (7), when for all \( z_{t}^{{}} \in Z_{t} \) fulfilled the inequality:

$$ 2(P_{t}^{H} - P_{t}^{k} )(P_{t} - P_{t}^{k} ) + u^{k} (S_{t} - S_{t}^{k} ) \le 0 $$
(8)

If inequality (8) is fulfilled for all \( t = 1, \ldots ,T \), then the solution of problem (7) is found.

Let denote \( \alpha_{t}^{k} = 2(P_{t}^{H} - P_{t}^{k} );\;\gamma_{t}^{k} = \alpha_{t}^{k} P_{t}^{k} ;\;\beta_{t}^{k} = u^{k} S_{t}^{k} \). Then, during the transition to the original variables, the inequality (8) for t-block is equivalent to the following inequality:

$$ \delta_{t}^{k} = \left[ {\mathop {\hbox{max} }\limits_{{x_{t} \in X_{t} }} (\alpha_{t}^{k} p_{t} + u^{k} \bar{A}_{t} )x_{t} - (\gamma_{t}^{k} + \beta_{t}^{k} )} \right] \le 0 $$
(9)

Thus, for the nonlinear problem (6) we found the indicator of optimality of the current solution (step 3 of the algorithm). It can be checked with a solution of separate task blocks. There is a finite speed of convergence of the solution to problem (7) for precise calculations.

Finite convergence of such block programming algorithms for accurately calculating is proved for example in [4]. According to (9) at each global iteration, the algorithm has to solve a linear programming problem on a polyhedral set with a limited number of corner points.

The study of nonlinear analog Dantzig-Wolfe method and its implementation in a hierarchical algorithm was conducted in Excel for an enterprise production planning system (6) with 5 companies (T = 5). All calculations of the lower level (the information of companies) was carried out in Excel. The numerical values provided with the matrix (6) were filled with uniformly-distributed pseudo-random numbers.

The marginal profit of the companies \( (P_{t}^{H} ) \) was defined as the maximum, without the resource constraints, by the decision of local linear programming problems. Exact solution of the problem (6) was obtained from a solver of Excel.

The formation of the initial coordinating task (7) performed by the classical scheme of the Danzig Wolfe method. For that, we selected the 2T columns corresponding to zero and to maximum plans. Additional columns of constraints were formed with using the expression (9). Each global iteration and the corresponding approximation of coordination tasks were performed in separate Excel worksheets.

The information exchange between the Centre and agents included current and optimal values of resource units, i.e. values of variables \( P_{t}^{k} ;\;S_{t}^{k} ;u^{k} \). We show the need to use performance structure of the optimal plan (Step 5 of the algorithm) because a price coordination (9) does not allow finding the solution of the problem (6). This effect is similar to the classical Dantzig Wolfe method, but in our case it has decentralized decisions, i.e. tasks (3) do not require of knowledge Centre for variables of lower levels. The proposed algorithm has obtained exact solutions for all considered numerical tasks (6). So the problem (6) with 12 variables and 24 constraints of 2 resources had error estimates for 4 initial iterations of functions 9,66%; 1,28%; 0,06%; 0,00% respectively.

4 Discussions

The main result of this paper is to prove the applicability of the Dantzig-Wolfe method for solving not only linear mathematical programming Large-Scale problems. It is proposed the modification of the Dantzig-Wolfe algorithm for solving convex mathematical programming problems with block (composite) structure in the function and constraints.

The algorithm for quadratic programming was implemented in MS Excel environment and its efficiency was studied. The rate of convergence in the number of global iterations was defined in tests, and it is shown that the proposed algorithm is not significantly different for this indicator from the Dantzig-Wolfe algorithm in linear block programming.