=Paper=
{{Paper
|id=Vol-1623/papermp18
|storemode=property
|title=A Minimization Algorithm with Approximation of an Epigraph of the Objective Function and a Constraint Set
|pdfUrl=https://ceur-ws.org/Vol-1623/papermp18.pdf
|volume=Vol-1623
|authors=Igor Zabotin, Oksana Shulgina, Rashid Yarullin
|dblpUrl=https://dblp.org/rec/conf/door/ZabotinSY16
}}
==A Minimization Algorithm with Approximation of an Epigraph of the Objective Function and a Constraint Set==
https://ceur-ws.org/Vol-1623/papermp18.pdf
A Minimization Algorithm with Approximation
of an Epigraph of the Objective Function
and a Constraint Set
Igor Zabotin, Oksana Shulgina, and Rashid Yarullin
Kazan (Volga Region) Federal University, Institute of Computational Mathematics
and Information Technologies, Kremlyovskaya str. 35, 420008 Kazan, Russian
{iyazabotin,onshul}@mail.ru, yarullinrs@gmail.com
http://www.kpfu.ru
Abstract. An algorithm is suggested for solving a convex programming prob-
lem which belongs to a class of cutting methods. In the algorithm an epigraph of
the objective function and a feasible solutions set of the problem are embedded
into some auxiliary sets to construct iteration points. Since these embedded
sets are constructed as polyhedral sets in the algorithm, then each iteration
point is found by solving a linear programming problem independently of the
type of functions which define the initial problem. The suggested algorithm is
characterized by the following fact. Sets which approximate the epigraph of the
objective function can be updated periodically on the base of discarding cutting
planes.
Keywords: cutting-plane methods, minimization methods, approximation sets,
an epigraph, a constraint set
1 Introduction
Cutting methods (e. g. [1–8]) are quite often applied to solve both application tasks
and auxiliary problems of constructing iteration points in the famous methods of con-
strained optimization. It can be explained, in particular, by the fact that there are
usually some possibilities to estimate proximity of the current value of the objective
function to its optimal value.
Among this class of methods there are ones which use approximation both an
epigraph of the objective function and a feasible set of the initial problem to construct
iteration points (e. g. [6,9]). These methods are convenient from the practical viewpoint,
because in these ones iteration points can be obtained on the base of solving auxiliary
linear programming problems.
The cutting algorithm proposed in this paper for solving a convex programming
problem also uses embedding procedures of both mentioned sets. Note that the con-
straint set can be embedded partially, and, moreover, in the algorithm there are some
opportunities of periodically dropping cutting planes which form sets for approximating
the epigraph.
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
322 A Minimization Algorithm
2 Problem Setting
Let f (x), F (x) be convex functions defined in an n-dimensional Euclidian space Rn ,
and the function f (x) reaches its minimal value on the set D = {x ∈ Rn : F (x) ≤ 0}.
We solve the problem
min{f (x) : x ∈ D}. (1)
Let f ∗ = min{f (x) : x ∈ D}, X ∗ = {x ∈ D : f (x) = f ∗ }, X ∗ (ε) = {x ∈ D :
f (x) ≤ f ∗ + ε}, where ε ≥ 0, epi(f, Rn ) = {(x, γ) ∈ Rn+1 : x ∈ Rn , γ ≥ f (x)}, ∂f (x),
∂F (x) be subdifferentails of functions f (x) and F (x) at point x ∈ Rn respectively,
K = {0, 1, . . .}, x∗ = X ∗ .
3 The Cutting Algorithm and Discussion
The proposed algorithm for solving problem (1) constructs an auxiliary sequence of
approximations {yi }, i ∈ K, and a basic sequence {xk }, k ∈ K, by the following rule.
A convex bounded closed set M0 ⊂ Rn and a convex closed set G0 ⊂ Rn+1 are formed
such that
x∗ ∈ M0 , epi(f, Rn ) ⊂ G0 . (2)
Generate numbers γ̄ and εk > 0, k ∈ K, according to conditions γ̄ ≤ f (x) for all
x ∈ M0 , εk → 0, k → ∞. Assign i = 0, k = 0.
1. Find a point (yi , γi ), where yi ∈ Rn , γi ∈ R1 , as a solution of the problem
min{γ : (x, γ) ∈ Gi , x ∈ Mk , γ ≥ γ̄}. (3)
If yi ∈ D and f (yi ) = γi , then yi ∈ X ∗ , and minimization process is finished. If yi ∈ D
and at the same time the inequality
f (yi ) − γi ≤ εk (4)
is fulfilled, then yi ∈ X ∗ (εk ), and the εk -solution of problem (1) is found.
2. Select an element bi ∈ ∂f (yi ). If
f (yi ) − γi > εk , (5)
then assign ∩
Gi+1 = Si {(x, γ) ∈ Rn+1 : f (yi ) + ⟨bi , x − yi ⟩ ≤ γ}, (6)
where Si = Gi , and go to Step 1, increase the value of i by one. Otherwise go to Step
3.
3. Assign ik = i, and choose a point xk such that
xk ∈ Mk , f (xk ) ≤ f (yik ). (7)
4. Choose a convex closed set Si ⊂ Rn+1 in accordance with
epi(f, Rn ) ⊂ Si (8)
A Minimization Algorithm 323
and construct a set Gi+1 in the form of (6).
5. Construct a set Mk+1 by the following rule. ∩ If xk ∈ D, then assign Mk+1 = Mk ,
else choose ak ∈ ∂F (xk ) and assign Mk+1 = Mk {x ∈ Rn : F (xk ) + ⟨ak , x − xk ⟩ ≤ 0}.
6. Increment values of i and k by one, and go to Step 1.
Lets represent some remarks for the algorithm.
It is advisable to choose the initial approximating sets M0 , G0 as polyhedral sets,
because in this case on each iteration i ∈ K problem (3) of constructing the auxiliary
point yi is a linear programming problem.
If the set D is bounded and polyhedral, then it is not necessary to approximate D
by the sets Mk , k ∈ K. In accordance with (2) it is clear to assign M0 = D in the
algorithm, and in view of Steps 3, 5 equalities Mk+1 = Mk = D will be fulfilled for all
k ∈ K.
Condition (2) allows to assign G0 = epi(f, Rn ), and this way is suitable in case of
determining the function f (x) as maximum of linear functions. At the same time for
each i ∈ K inequality (4) is defined, and using Si = epi(f, Rn ) in (8) we have equalities
Gi = epi(f, Rn ), i ∈ K. Also note that it is possible to use G0 = Rn+1 . In this case any
point (y0 , γ0 ), where y0 ∈ M0 and γ0 = γ̄, can be a solution of problem (3) for i = 0.
Note that one can assign Si = Gi for all i ∈ K independently of conditions (4),
(5). Then cutting planes formed approximating sets Gi+1 will be accumulated infinitely.
Notice that condition (8) of constructing sets Si allows to update sets that approximate
the epigraph in the process of forming Gik +1 on iterations with numbers i = ik . Namely,
there is rejection of a finite number of cutting planes f (yi ) + ⟨bi , x − yi ⟩ = γ by
construction Sik , for example, on the base of any sets G0 , . . . , Gik −1 according to (8).
In particular, if we assign Sik = G0 , then we discard all planes which are constructed
to the step i = ik .
Note that condition (7) of selection of the point xk allows to assign, in particular,
xk = yik for all k ∈ K.
Lets observe some properties of the proposed algorithm.
Taking into account (2) it is easy to prove by induction that for all k ∈ K and
i ∈ K inclusions x∗ ∈ Mk , (x∗ , f ∗ ) ∈ Gi are fulfilled.
On the base of these inclusions, the construction condition of the number γ̄ and the
type of constraints in problem (3) it is not difficult to observe that the inequality
γi ≤ f ∗ (9)
is determined for the solution (yi , γi ) of problem (3) under any k ∈ K, i ∈ K.
Obviously the stopping criterion represented in Step 1 of the algorithm is proved
according to condition (9). If the point (yi , γi ) is constructed such that yi ∈ D and
condition (4) is determined, then from (9) it follows that f (yi ) ≤ f ∗ + εk , and, conse-
quently, the approximation yi is an εk -solution of the initial problem.
If the equation Si = Gi is defined for all i ∈ K in the algorithm, then taking into
account (9) it is not difficult to prove the limit expression lim (f (yi ) − γi ) = 0. On
i∈K
the base of this equality and in view of the methology [10] it is clear to observe the
following
Lemma 1. If the sequence {(yi , γi )} is constructed by the suggested algorithm, then
there exist a number i = ik ∈ K for all k ∈ K such that equality (4) is fulfilled.
324 A Minimization Algorithm
According to Lemma 1 the sequence {xk }, k ∈ K, will be formed with the sequence
{yi }, i ∈ K, by the algorithm.
Theorem 1. The inclusion x̄ ∈ X ∗ is valid for any limit point x̄ of the sequence {xk }
constructed by the algorithm.
Proof. This theorem is proved by the following schema. Firstly, taking into account
the approach of constructing sets Mk the inclusion x̄ ∈ D is proved, consequently, the
inequality
f (x̄) ≥ f ∗ (10)
is observed too. Further, from (4), (7), (9) and according to the technique of establishing
{εk } it is easy to get contradiction with inequality (10).
References
1. Bulatov, V.P.: Embedding Methods in Optimization Problems. Nauka, Novosibirsk (1977)
[in Russian].
2. Bulatov, V.P., Khamisov, O.V.: Cutting methods in E n+1 for global optimization of a
class of functions. Zhurn. Vychisl. Matem. i Matem. Fiz. 47(11), 1830–1842 (2007) [in
Russian].
3. Zabotin, I.Ya., Yarullin, R.S.: One approach to constructing cutting algorithms with drop-
ping of cutting planes. Russian Math. (Iz. VUZ). 58 (3), 60–64 (2013).
4. Zabotin, I.Ya., Yarullin, R.S.: Cutting plane method based on epigraph approximation
with discarding the cutting planes. Automation and Remote Control. 76 (11), 1578–1587
(2015).
5. Kolokolov, A.A.: Regular partitions and cuts in integer programming. Sib. zhurn. issled.
oper. 1 (2), 18–39 (1994) [in Russian].
6. Nesterov, Yu.E.: Introduction to Convex Optimization. Moscow, MCCME (2010).
7. Nurminski, E.A.: Cutting method for solving non-smooth convex optimization problem
with limited memory. Vychisl. Met. i Program. 7, 133–137 (2006) [in Russian].
8. Zabotin, I.Ya., Yarullin, R.S.: A cutting method for finding discrete minimax with drop-
ping of cutting planes. Lobach. Journal of Math., 35 (2), 157–163 (2014).
9. Demyanov, V.F., Vasiliev, L.V.: Nondifferentiable optimization. Mir, Moscow (1972) [in
Russian].
10. Zabotin, I.Ya., Yarullin, R.S.: A cutting plane algorithm with an approximation of an
epigraph. Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauki. 155 (4), 48–54 (2013) [in
Russian].