Simplex Embedding Method in Decomposition of Large Sparse Convex Nondi erentiable Optimization Problems ?

Abstract

We consider an adaptation of the simplex embedding method to the decomposition of large-scale convex problem with sparse blockwise constraint matrix. According to the Lagrangean relaxation technique such problem is reduced to the maximization of nondi erentiable concave function with subgradient that can be easily calculated at each feasible point. Simplex embedding method with modi cations gives us the appropriate performance to optimize nondi erentiable function that will be demonstrated on the numerical tests.

Keywords

• Decomposition
• Lagrangean relaxation ding method
• Nondi erentiable optimization
• Simplex embed-

-

Mathematical models are widely spread in di erent areas of our life and appear in economics, business, engineering and social sciences. To get proper vision of real object functioning and obtain reliable optimizing model parameters one can use the mathematical programming technique in which a system is represented by an objective function and several constraints. There are lots of mathematical programming problems that have huge number of variables and constraints due to the system they are related to. As the examples we can notice multidivisional problems with large number of subsystems, combinatorial problems containing large amount of model alternatives, dynamic problems with many replicating constraints or variables and stochastic problems with large amount of possibilities involved [ 10 ].

When we come across the large or too complicated mathematical programming problems it is sometimes necessary or more convenient to apply decomposition approaches. As a rule large-scale problems have a block-wise structure of ? The reported study was supported by RFBR, research project No. 18-07-01432.

Copyright c by the paper's authors. Copying permitted for private and academic purposes.

In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org matrix constraints and can be split into less dimension problems using di erent decomposition methods.

Dantzig-Wolfe decomposition [ 8 ] and Benders decomposition [ 5, 22 ] are the most representative methods of all decomposition techniques. A comprehensive survey up to 1979 year of developing these methods is given in [ 18 ]. Decomposition procedures in terms of algorithmic applications and questions about convergence of decomposition methods are discussed in [ 9 ].

Our interest within this article is concentrated on the Lagrangean relaxation technique for the decomposition problems. Such approach is used for reducing the initial large-scale problem to the maximizing of the nondi erentiable concave function with the subgradient that can be easily calculated at each feasible point. Detailed description of Lagrangean relaxation technique is given in [ 15, 6, 16 ]. In considering mixed integer nonlinear programming we refer to [ 17 ] where Lagrangean relaxation method is applied. Once we apply the Lagrangean relaxation technique the nondi erentiable optimization method must be chosen. In [ 6, 11 ] di erent methods of nondi erentiable optimization problems (subgradient methods [ 24 ], cutting plane methods [ 20 ], bundle methods [ 3 ]) are represented in terms of their applying to the decomposition problems.

One of the signi cant source of the large-scale optimization problems is a stochastic nature of the complex systems under study. In [ 23 ] it is represented the applying of decomposition methods to the convex stochastic programming problems.

Notice at last that decomposition is commonly used in practical applications as network design problems [ 4, 7 ], network utility problems [ 21 ] and producing problems [ 6 ].

The current work continues the series of articles [2, 12{14] devoted to the simplex embedding method modi cations and applications of the method to solving convex optimization problems. We present the adaptation of simplex embedding method to solving large sparse convex optimization problems by means of decomposition technique. This technique will be introduced in the section 3. We use the simplex embedding method modi cation with cutting plane shift that demonstrated quite good performance according to the numerical experiments implemented in [ 14 ]. The simplex embedding method with corresponding algorithm of implementation will be presented in the section 4. We will give the algorithm of combining the method modi cation with the decomposition procedure in the section 5. The results of numerical experiment will be demonstrated in the section 6. We conclude the paper with a short discussion of results in the section 7.

Problem Statement

We aim to solve the following convex optimization problem where matrix A is the m1 n-dimensional matrix, D is the m2 matrix that has block-wise structure with K blocks n-dimensional 2 D1 0

D2 . . . (2) x 2 Rn, b 2 Rm1 , d 2 Rm2 . Function f : Rn ! R is convex function that can be represented as a sum of separable items

f (x) = f1(x1) + f2(x2) + ::: + fK (xK ):

Vectors x, d can be split into subvectors that are corresponded to one of the k-th block, k = 1; :::; K: x = (x1; :::; xK ); d = (d1; :::; dK ); matrix A is split into submatrixes (A1; :::; AK ).

Let us introduce polytopes Xk, k = 1; :::; K for notation convenient: Xk = fxk j Dkxk dk; xk 0g ; k = 1; :::; K: Then the problem (1) can be represented in the following form: minimize subject to

PK

k=1 fk(xk), PK k=1 Akxk

b, xk 2 Xk; k = 1; :::; K.

The problem (2) corresponds to so called complicating constraints problem. It means that the structure of constraints is represented not only by the separable blocks Dkxk dk, k = 1; :::; K but also it is represented by constraints Ax b joining these blocks. We will consider only problems with this constraint structure. Figure 1 re ects schematically the structure of such problems.

D1 0 A1 Let us describe the Lagrangean relaxation technique for solving the problem (2).

We associate the Lagrangean multiplier i 0, i = 1; :::; m1 with each complicating constraint and form the Lagrangean function:

L(x; ) = f (x) +

T (Ax

K b) = X fk(xk) +

T Akxk

k=1 A dual function is de ned in the following way !( ) = xm2iXn fL(x; )g = K X

min k=1 xk2XK fk(xk) +

T Akxk

b: b; Notice that the calculation of the dual function value is split into solving the optimization subproblems

X = X1

X2 : : :

XK :

1 minimize subject to fk(xk) + Dkxk xk 0.

dk,

T Akxk,

Each of subproblem from (3) is the less dimensional convex problem in comparison with initial problem (2). Using performance of multiprocessor systems one can get an appropriate accelerate in calculations. To nd the optimal solution of the problem maximize subject to !( ), 0, we need to consider several important properties of the function ! [ 15, 16 ].

Let us rst give the de nition of a saddle point for the function L. (3) (4) De nition 1. A point (x0; 0) is said to be a constrained saddle point for L(x; ) if it satis es 1. Function ! is concave and nondi erentiable. 2. If the problem (2) has the solution x? with nite value then there exists a saddle point and for all 0 and for all solution x of the problem (2) we have the following expression !( ) !( ?) = f (x?) f (x); where ? is the optimal solution of the dual problem. 3. Let the vector x^k, k = 1; :::; K be the optimal solution of the problem (3), then the vector

K = X Akx^k k=1 b (5) de nes the subgradient of the function ! at the point .

A correspondence between the solution ? for the dual problem and the solution x? for the initial problem (2) is set by the following theorems [ 15 ]. Theorem 1. Let 0 L(x; ) if and only if 0. A point (x0; 0) is a constrained saddle point for x0 minimizes L(x; 0) over X, Dx0 d; 0 Ax0 b = 0: (6) Theorem 2. If (x0; 0) is a saddle point for L(x; ), then x0 solves the primal problem (2).

Since a Subgradient of the Dual Function ! at Each Point 0 Can Be Calculated It is Possible to Apply One of the Nondi erentiable Convex Optimization Method (concave in Our Case). In the Section Below We Introduce the Simplex Embedding Method Adapted for the Decomposition Technique. 4

Simplex Embedding Method

Simplex embedding method [ 1 ] is a centered cutting plane method that uses n-dimensional simplexes to localize the problem solution. The main idea of the method is similar to the well-known ellipsoid method [ 19 ]. To nd the optimization problem solution one need to embed the feasible set of the problem to initial simplex. Then it is drawn the cutting plane through a simplex center. This cutting plane divides simplex into two parts. The key step of the method is in embedding the truncated simplex containing the problem solution into a new minimal volume simplex. Then all the procedures repeat one more time for obtained minimal volume simplex. Implementation of such steps continues up to getting a simplex with a quite small volume. Then the algorithm is terminated.

To start the detailed method description we will give some important de nitions.

De nition 2. Let S be the subset of Rn. We call S the simplex if it has the following form

S = (

n x 2 Rn : x = x0 + X i xi

x0 ; i i=1

n 0; X i=1 i De nition 3. The center of the simplex S is the point xc 2 S de ned by the expression where X is the n n dimension matrix. The columns of this matrix are represented by the vectors x1; x2; :::; xn.

De nition 5. Each hyperplane of the form

L = x : gT (x xc) = 0 is called the cutting hyperplane passing through the center xc in the simplex S. De nition 6. The vertex xi of the simplex S is said not to be cut o cutting hyperplane L if i = gT xi xc < 0; by the (9) and this vertex is cut o if i

0, i = 0; :::; n.

The immersion procedure of truncated simplex into a new minimal volume simplex is the important principle of the method. It provides the convergence to the optimal problem solution. According to (7) let us de ne a new minimal volume simplex containing a truncated simplex SG in the following form: S( ) = x : x = x0 + 1 1 x1 x0 + ::: + n n xn x0 ; n X i 1; i 0; i = 1; :::; n:

) i=1 The theorem below contains the description of minimal volume simplex constructing [ 1 ]. Theorem 3. The minimal volume simplex S( ) containing a simplex SG is de ned by the parameters

? = 1 + it?; i = 1; :::; n; where t? is the solution of one-dimensional optimization problem 0 t

n min Y (1 + it) 1 ; 1= 0 i=1 0 = 0miinn i: The following theorem gives the estimation of the method convergence [ 1 ]. Theorem 4. Let S Rn be the n-dimensional simplex, xc is the center of the simplex, SG = x 2 S; gT (x xc) 0 is truncated simplex. Simplex SG can be immersed into a simplex S so that the following relation between the volumes V (S) and V (S ) of the simplexes S and S is ful lled:

V (S ) V (S) where k is the amount of saved vertices after drawing a cutting hyperplane through the simplex center, S is the minimal volume simplex constructed according to the theorem 3.

Convergence estimation obtained in (10) depends only on the amount of saved simplex vertices.The less vertices are saved the higher convergence rate of the method is obtained. As soon as only one simplex vertex is saved the analogue of dichotomy method can be obtain.

Let us introduce the general algorithm for the simplex embedding method implementation to solve the optimization problem minimize subject to f0(x) fi(x) 0, i = 1; :::m, where fi(x), i = 0; :::; m are convex functions, x 2 Rn.

Step 0. Choose an initial simplex S0 with matrix X0 so that S0 contains a feasible set of the problem (11). Set the accuracy parameter " and put 0 = 1. Iteration k, k = 0; 1; 2; :::; proceeds as follows.

Step 1. Find the simplex center xck using the formula (8).

Step 2. Compute maximal residual hk = max 1 i m

0; fi(xck) = fs(xck): Step 3. Find the cutting plane normal ak = where @fi(xck) is the subgradient of the convex function fi at the point xck. (10) (11) Step 4. Construct the truncated simplex

SGk = x : x 2 Sk; hak; x

k xc i 0 : Step 5. Find the parameters k using (9) and compute the stretch coe cients k following the directions of the theorem 3. De ne p = min0 i n i. Step 6. Find simplex Sk+1 with matrix Xk+1

Xikj+1 = ( Xpkj + ik(Xikj

Xpkj ); i 6= p; i = 0; 1; :::; n;

Xikj ; i = p; i = 0; 1; :::; n; Step 7. De ne the maximum edge of the simplex Sk+1: k+1 = mi;ajx jjvi k

k vj jj i 6= j; Swtheepre8.vIikf, ik=+10; ::":; tnheisnttheermcoinoardteintahtee aolfgothriethim-thwvitehrt"ex-opoftitmhaelssiomluptleioxnSxkck..

Otherwise increment k ! k + 1 and move to the Step 1.

According to the results of the theorem 4 several modi cations of the simplex embedding method were developed. The simultaneous introduction of several cutting planes into the simplex was considered in [ 2 ]. The technique of subdifferential description for a special class of convex nondi erentiable functions was represented in [ 12 ]. Such description was used to form a resulting cutting plane to cut o as much simplex vertices as possible. Constructing the minimal volume simplex around the certain set of points is considered in [ 13 ]. The inactive constraints identi cation by means of simplex embedding method and numerical comparison of the simplex embedding method modi cations with cutting plane shift were considered in [ 14 ]. These modi cations reduce the volume of truncated simplex containing the optimal solution and improves the method convergence.

To give an explanation of the cutting plane shift modi cation suppose we have a current simplex center xc and the set of linear constraints aix bi, where ai; x 2 Rn, i = 1; :::; m., b 2 Rm. The modi ed algorithm of simplex embedding method has the following form.

Step 1. Calculate the residuals at the point xc: i = aixc bi, i = 1; :::; m. Step 2. De ne the maximal residual and corresponding residual number: max = i=m1;a::x:;m i ; i = i i=1;:::;m i = max max : Step 3. De ne a new cutting plane

Lk = fx : ai x bi = 0g :

Numerical tests represented in [ 14 ] showed better performance of the modi ed algorithm for solving the set of nondi erentiable optimization problems. The way of obtaining a subgradient for the problem (4) includes an additional computational procedure that we will describe in the next section in details. Such procedure prevents us from direct comparison with the results from the work [ 14 ]. Nevertheless simplex embedding method modi cation with cutting plane shift is applicable for solving the decomposition problem.

Decomposition Algorithm

To solve the problem (2) we can implement a two-level decomposition technique with the rst level solving subproblems (3) and the second level adjusting the multipliers by means of simplex embedding method. The detailed algorithm of such technique is given below.

Step 0. Choose initial values 0 0. Iteration i, i = 0; 1; 2; :::; proceeds as follows.

Step 1. Solve the subproblems (3) with = i obtaining the solution x( i). Step 2. Calculate the subgradient of the function !( ): i =

K X Akxk( i) k=1 b: Step 3. Input the obtained subgradient i to the simplex embedding method to get a new point i?.

Step 4. If the simplex embedding method is terminated due to its inner stopping criterion then we terminate the decomposition algorithm with the solution i? of dual problem (4). Otherwise increment i ! i + 1, de ne i+1 = i? and move to the Step 1. 6

Preliminary Numerical Experiment

To test the two-level decomposition technique we used simplex embedding method modi cation with cutting plane shift [ 14 ]. Preliminary numerical testing was carried out on the decomposition problems that were generated automatically in the form (2) with random matrixes A and D and objective function Pin=1 xi2. Solution x? was set beforehand to obtain vectors b = Ax?, d = Dx?. The average results of numerical test series are represented in the table below where we give a comparison with the subgradient method. Each test series consisted of 5 problems of corresponding dimension. We accepted the following notation: SGM { subgradient method, SEM { simplex embedding method with cutting plane shift, n { number of variables, m { number of constraints, k { number of separable constraint blocks, iter { number of iterations, time is given in seconds. We took the accuracy parameter for both algorithms " = 10 3. All calculations were implemented in Matlab system on the computer tted with 8-core processor AMD FX-8350 that has 4 GHz clock speed per each core. RAM of the computer was 8 Gb.

m,n,k

SGM

SEM

Conclusions

We implemented a preliminary numerical testing of simplex embedding method with one of the possible modi cation that demonstrated better performance than subgradient method. Flexible and adaptive structure of the simplex embedding method makes it a perspective method for solving decomposition problems by means of Lagrangean relaxation technique.

References

1. Antsiferov , E.G. , Bulatov , V.P.: An algorithm of simplex imbeddings in convex programming . Zh. Vychisl. Mat. Mat. Fiz . 27 ( 3 ), 377 { 384 ( 1987 ), (in Russian)

2. Apekina , Y.V. , Khamisov , O.V. : A modi ed simplex immersions method with simultaneous introduction of several intersecting planes . Russian Mathematics (Iz . VUZ) 41 ( 12 ), 14 { 22 ( 1997 )

3. Bagirov , A. , Karmitsa , N. , Makela , M.M. : Introduction to Nonsmooth Optimization . Theory, Practice and Software . Springer International Publishing Switzerland ( 2014 )

4. Barmann , A. : Solving Network Design Problems via Decomposition, Aggregation and Approximation . Springer Fachmedien Wiesbaden ( 2016 )

5. Benders , J.F. : Partitioning procedures for solving mixed-variables programming problems . Numer. Math. 4 ( 3 ), 238 { 252 ( 1962 )

6. Conejo , A.J. , Castillo , E. , Minguez , R. , Garcia-Bertrand , R. : Decomposition Techniques in Mathematical Programming. Engineering and Science Applications . Springer-Verlag, Berlin Heidelberg ( 2006 )

7. Costa , A.M.: A survey on benders decomposition applied to xed-charge network design problems . Computers & Operations Research 32 , 1429 { 1450 ( 2005 )

8. Dantzig , G.B. , Wolfe , P. : Decomposition principle for linear programs . Oper. Res . 8 ( 1 ), 101 { 111 ( 1961 )

9. Flippo , O.E. , Rinnooy Kan , A.H.G. : Decomposition in general mathematical programming . Mathematical Programming 60 , 361 { 382 ( 1993 )

10. Geo rion , A.M.: Perspectves on Optimization. Addison-Wesley Publ. Co , Reading, Mass ( 1972 )

11. Kiwiel , K.C. : Approximations in Decomposition of Large-Scale Convex Programs via a Nondi erentiable Optimization Method . IFAC 11th Triennial World Congress , Tallinn, Estonia, USSR ( 1990 )

12. Kolosnitcyn , A.V. : Using of modi ed simplex imbeddings method for solving special class of convex non-di erentiable optimization problems . IIGU Ser. Matematika 11 , 54 - 68 ( 2015 )

13. Kolosnitcyn , A. : Modi ed simplex imbeddings method in convex non-di erentiable optimization . In: DOOR-2016 , CEUR-WS . vol. 1623 . pp. 218 { 255 ( 2016 )

14. Kolosnitsyn , A.V. : Computational e ciency of the simplex embedding method in convex nondi erentiable optimization . Computational Mathematics and Mathematical Physics 58 ( 2 ), 215 - 222 ( 2018 )

15. Lasdon , L.S. : Duality and decomposition in mathematical programming . IEEE Transactions on System Science and Cybernetics ssc- 4 ( 2 ), 86 { 100 ( 1968 )

16. Minoux , M. : Mathematical Programming: Theory and Algorithms . John Wiley & Sons Ltd ( 1986 )

17. Nowak , I. : Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming . ISNM vol. 152 , Birkhauser Verlag , Switzerland ( 2005 )

18. Molina , F.W.: A Survey of resource directive decomposition in mathematical programming . Computing Surveys 11 ( 2 ), 95 { 104 ( 1979 )

19. Nemirovsky , A. , Yudin , D. : Informational complexity and e cient methods for solution of convex extremal problems . J. Wiley & Sons, New York ( 1983 )

20. Nesterov , Yu .E.: Introductory Lectures on Convex Programming: A Basic Course . Springer Science + Business Media, New York ( 2004 )

21. Palomar , D.P. , Chiang , M.: A tutorial on decomposition methods for network utility maximization . IEEE Journal on Selected Areas in Communications 24(8) , 1439 { 1451 ( 2006 )

22. Rahmaniani , R. , Crainic , T.G. , Gendreau , M. , Rei , W.: The Benders decomposition algorithm: A literature review . European Journal of Operational Research 259 , 801 { 817 ( 2017 )

23. Ruszczynski , A.: Decomposition Methods . Handbooks in OR & MS, vol. 10 ( 2003 )

24. Shor , N.Z. : Minimization Methods for Non-di erentiable Functions . SpringerVerlag , Berlin ( 1985 )