=Paper= {{Paper |id=Vol-2098/paper17 |storemode=property |title=Simplex Embedding Method in Decomposition of Large Sparse Convex Nondifferentiable Optimization Problems |pdfUrl=https://ceur-ws.org/Vol-2098/paper17.pdf |volume=Vol-2098 |authors=Anton Kolosnitsyn }} ==Simplex Embedding Method in Decomposition of Large Sparse Convex Nondifferentiable Optimization Problems== https://ceur-ws.org/Vol-2098/paper17.pdf

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

Anton Kolosnitsyn

Melentiev Energy Systems Institute SB RAS,
130 Lermontov Str., Irkutsk, Russia
ankolos25@mail.ru

Abstract. We consider an adaptation of the simplex embedding method
to the decomposition of large-scale convex problem with sparse block-
wise constraint matrix. According to the Lagrangean relaxation tech-
nique such problem is reduced to the maximization of nondifferentiable
concave function with subgradient that can be easily calculated at each
feasible point. Simplex embedding method with modifications gives us
the appropriate performance to optimize nondifferentiable function that
will be demonstrated on the numerical tests.

Keywords: Decomposition · Lagrangean relaxation · Simplex embed-
ding method · Nondifferentiable optimization

1 Introduction
Mathematical models are widely spread in different 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 mathemati-
cal programming problems that have huge number of variables and constraints
due to the system they are related to. As the examples we can notice multi-
divisional 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 program-
ming problems it is sometimes necessary or more convenient to apply decompo-
sition 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
190 A. Kolosnitsyn

matrix constraints and can be split into less dimension problems using different
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]. Decom-
position 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 nondifferentiable con-
cave 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 relax-
ation technique the nondifferentiable optimization method must be chosen. In
[6, 11] different methods of nondifferentiable 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 significant 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 sim-
plex embedding method modifications 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 de-
composition technique. This technique will be introduced in the section 3. We
use the simplex embedding method modification with cutting plane shift that
demonstrated quite good performance according to the numerical experiments
implemented in [14]. The simplex embedding method with corresponding algo-
rithm of implementation will be presented in the section 4. We will give the
algorithm of combining the method modification with the decomposition proce-
dure 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.
Simplex Embedding Method in Decomposition Problems 191

2 Problem Statement

We aim to solve the following convex optimization problem

minimize f (x)
subject to Ax ≤ b,
(1)
Dx ≤ d,
x ≥ 0,

where matrix A is the m1 × n-dimensional matrix, D is the m2 × n-dimensional
matrix that has block-wise structure with K blocks
 
D1 0
 D2 
D= ,
 
..
 . 
0 DK

x ∈ Rn , b ∈ Rm1 , d ∈ 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 = {xk | Dk xk ≤ dk ; xk ≥ 0} , k = 1, ..., K.

Then the problem (1) can be represented in the following form:
PK
minimize k=1 fk (xk ),
PK
subject to k=1 Ak xk ≤ b,
(2)
xk ∈ 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 sepa-
rable blocks Dk xk ≤ 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 reflects schematically the structure of such problems.
192 A. Kolosnitsyn

D1 0

D2 d

0 DK

A1 A2 AK b

Fig. 1. Block-wise structure of the otimization problem

3 Lagrangean Relaxation

Let us describe the Lagrangean relaxation technique for solving the problem (2).
We associate the Lagrangean multiplier λi ≥ 0, i = 1, ..., m1 with each com-
plicating constraint and form the Lagrangean function:
K
X
L(x, λ) = f (x) + λT (Ax − b) = fk (xk ) + λT Ak xk − λb.

k=1

A dual function is defined in the following way
K
X
fk (xk ) + λT Ak xk − λb,

ω(λ) = min {L(x, λ)} = min
x∈X xk ∈XK
k=1

X = X1 × X2 × . . . × XK .
1

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

minimize fk (xk ) + λT Ak xk ,
subject to Dk xk ≤ dk , (3)
xk ≥ 0.

Each of subproblem from (3) is the less dimensional convex problem in com-
parison with initial problem (2). Using performance of multiprocessor systems
one can get an appropriate accelerate in calculations. To find the optimal solution
of the problem
maximize ω(λ),
(4)
subject to λ ≥ 0,
we need to consider several important properties of the function ω [15, 16].
Let us first give the definition of a saddle point for the function L.
Simplex Embedding Method in Decomposition Problems 193

Definition 1. A point (x0 , λ0 ) is said to be a constrained saddle point for L(x, λ)
if it satisfies
L(x0 , λ0 ) ≤ L(x, λ0 ), for all x ∈ X,
L(x0 , λ0 ) ≥ L(x0 , λ), for all λ ≥ 0.
The main properties of the function ω is given below.

1. Function ω is concave and nondifferentiable.
2. If the problem (2) has the solution x? with finite 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
XK
γ= Ak x̂k − b (5)
k=1

defines 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 ≥ 0. A point (x0 , λ0 ) is a constrained saddle point for
L(x, λ) if and only if

x0 minimizes L(x, λ0 ) over X,
Dx0 ≤ d, (6)
λ0 Ax0 − b = 0.

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 Nondifferentiable Convex Opti-
mization 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 find the opti-
mization 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.
194 A. Kolosnitsyn

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 defini-
tions.
Definition 2. Let S be the subset of Rn . We call S the simplex if it has the
following form
( n n
)
X X
n 0 i 0

S= x∈R : x=x + σi x − x , σi ≥ 0, σi ≤ 1 (7)
i=1 i=1
0 1 0 n 0
where x is the simplex vertex, (x − x , ..., x − x ) are the simplex edges that
form basis in Rn .
Definition 3. The center of the simplex S is the point xc ∈ S defined by the
expression
1
x1 + ... + xn .

xc = (8)
n+1
Definition 4. The volume of the simplex S is defined by the next formula
1
V (S) = det X̄ ,
n!
where X̄ is the n × n dimension matrix. The columns of this matrix are repre-
sented by the vectors x1 , x2 , ..., xn .
Definition 5. Each hyperplane of the form
L = x : g T (x − xc ) = 0

is called the cutting hyperplane passing through the center xc in the simplex S.
Definition 6. The vertex xi of the simplex S is said not to be cut off by the
cutting hyperplane L if
αi = g T xi − xc < 0,

(9)
and this vertex is cut off 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 define 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 con-
structing [1].
Simplex Embedding Method in Decomposition Problems 195

Theorem 3. The minimal volume simplex S(τ ∗ ) containing a simplex SG is
defined by the parameters
τ ? = 1 + αi t? , i = 1, ..., n,
where t? is the solution of one-dimensional optimization problem
n
−1
Y
min (1 + αi t) , α0 = min αi .
0≤t≤−1/α0 0≤i≤n
i=1

The following theorem gives the estimation of the method convergence [1].
n
Theorem 4. Let S ⊂ R T be the n-dimensional simplex, xc is the center of the
c
simplex, SG = x ∈ S, g (x − x ) ≤ 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 fulfilled:
1
, k = 1,
V (S ∗ )  2
≤ k k−1 (10)
V (S)  k k
, 2 ≤ k ≤ n,
k+1 k−1

where k is the amount of saved vertices after drawing a cutting hyperplane
through the simplex center, S ∗ is the minimal volume simplex constructed ac-
cording 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 f0 (x)
(11)
subject to fi (x) ≤ 0, i = 1, ...m,
where fi (x), i = 0, ..., m are convex functions, x ∈ Rn .
Step 0. Choose an initial simplex S 0 with matrix X 0 so that S 0 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 xkc using the formula (8).
Step 2. Compute maximal residual
hk = max 0, fi (xkc ) = fs (xkc ).

1≤i≤m

Step 3. Find the cutting plane normal
∂f0 (xkc ), if hk = 0,

ak =
∂fi (xkc ), if hk > 0,

where ∂fi (xkc ) is the subgradient of the convex function fi at the point xkc .
196 A. Kolosnitsyn

Step 4. Construct the truncated simplex
k
= x : x ∈ Sk , hak , x − xkc i ≤ 0 .

SG
Step 5. Find the parameters αk using (9) and compute the stretch coefficients
τ k following the directions of the theorem 3. Define p = min0≤i≤n αi .
Step 6. Find simplex S k+1 with matrix X k+1
( k
Xpj + τik (Xij
k k
− Xpj ), i 6= p, i = 0, 1, ..., n,
k+1
Xij =
k
Xij , i = p, i = 0, 1, ..., n,
Step 7. Define the maximum edge of the simplex S k+1 :
ρk+1 = max ||vik − vjk || i 6= j,
i,j

where vik , i = 0, ..., n is the coordinate of the i-th vertex of the simplex S k .
Step 8. If ρk+1 ≤ ε then terminate the algorithm with ε-optimal solution xkc .
Otherwise increment k → k + 1 and move to the Step 1.
According to the results of the theorem 4 several modifications of the simplex
embedding method were developed. The simultaneous introduction of several
cutting planes into the simplex was considered in [2]. The technique of subdif-
ferential description for a special class of convex nondifferentiable functions was
represented in [12]. Such description was used to form a resulting cutting plane
to cut off as much simplex vertices as possible. Constructing the minimal vol-
ume simplex around the certain set of points is considered in [13]. The inactive
constraints identification by means of simplex embedding method and numerical
comparison of the simplex embedding method modifications with cutting plane
shift were considered in [14]. These modifications reduce the volume of truncated
simplex containing the optimal solution and improves the method convergence.
To give an explanation of the cutting plane shift modification suppose we
have a current simplex center xc and the set of linear constraints ai x ≤ bi ,
where ai , x ∈ Rn , i = 1, ..., m., b ∈ Rm . The modified algorithm of simplex
embedding method has the following form.
Step 1. Calculate the residuals at the point xc : δi = ai xc − bi , i = 1, ..., m.
Step 2. Define the maximal residual and corresponding residual number:

δmax = max δi , iδ = i max δi = δmax .
i=1,...,m i=1,...,m

Step 3. Define a new cutting plane
Lk = {x : aiδ x − biδ = 0} .
Numerical tests represented in [14] showed better performance of the mod-
ified algorithm for solving the set of nondifferentiable 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 modification with cutting
plane shift is applicable for solving the decomposition problem.
Simplex Embedding Method in Decomposition Problems 197

5 Decomposition Algorithm
To solve the problem (2) we can implement a two-level decomposition technique
with the first 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 ω(λ):
K
X
γi = Ak xk (λi ) − b.
k=1

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, define
λ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
modification with cutting plane shift [14]. Preliminary numerical testing was car-
ried out on the decomposition problems that were generated automatically Pn in
the form (2) with random matrixes A and D and objective function i=1 x2i .
Solution x? was set beforehand to obtain vectors b = Ax? , d = Dx? . The av-
erage 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 fitted 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
iter time iter time
10, 10, 5 > 2000 > 80 21 1
50, 50, 5 > 2000 > 250 108 15
100, 100, 10 > 2000 > 1000 355 195
150, 150, 15 > 2000 > 1000 771 978
198 A. Kolosnitsyn

7 Conclusions

We implemented a preliminary numerical testing of simplex embedding method
with one of the possible modification 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 modified simplex immersions method with si-
multaneous 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 Optimiza-
tion. 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 Tech-
niques in Mathematical Programming. Engineering and Science Applications.
Springer-Verlag, Berlin Heidelberg (2006)
7. Costa, A.M.: A survey on benders decomposition applied to fixed-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 pro-
gramming. Mathematical Programming 60, 361–382 (1993)
10. Geoffrion, A.M.: Perspectves on Optimization. Addison-Wesley Publ. Co, Reading,
Mass (1972)
11. Kiwiel, K.C.: Approximations in Decomposition of Large-Scale Convex Pro-
grams via a Nondifferentiable Optimization Method. IFAC 11th Triennial World
Congress, Tallinn, Estonia, USSR (1990)
12. Kolosnitcyn, A.V.: Using of modified simplex imbeddings method for solving spe-
cial class of convex non-differentiable optimization problems. IIGU Ser. Matem-
atika 11, 54-68 (2015)
13. Kolosnitcyn, A.: Modified simplex imbeddings method in convex non-differentiable
optimization. In: DOOR-2016, CEUR-WS. vol. 1623. pp. 218–255 (2016)
14. Kolosnitsyn, A.V.: Computational efficiency of the simplex embedding method in
convex nondifferentiable optimization. Computational Mathematics and Mathe-
matical 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)
Simplex Embedding Method in Decomposition Problems 199

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 pro-
gramming. Computing Surveys 11(2), 95–104 (1979)
19. Nemirovsky, A., Yudin, D.: Informational complexity and efficient 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 util-
ity 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-differentiable Functions. Springer-
Verlag, Berlin (1985)