A Minimization Algorithm with Approximation of an Epigraph of the Ob jective Function and a Constraint Set

Abstract

An algorithm is suggested for solving a convex programming problem 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 de ne 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

-

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 constrained 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 constraint 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 Let f (x), F (x) be convex functions de ned in an n-dimensional Euclidian space Rn, and the function f (x) reaches its minimal value on the set D = fx 2 Rn : F (x) 0g: We solve the problem

minff (x) : x 2 Dg:

Let f = minff (x) : x 2 Dg, X = fx 2 D : f (x) = f g, X (") = fx 2 D : f (x) f + "g, where " 0, epi(f; Rn) = f(x; ) 2 Rn+1 : x 2 Rn; f (x)g, @f (x), @F (x) be subdifferentails of functions f (x) and F (x) at point x 2 Rn respectively, K = f0; 1; : : :g, x = X . 3

The Cutting Algorithm and Discussion The proposed algorithm for solving problem ( 1 ) constructs an auxiliary sequence of approximations fyig, i 2 K, and a basic sequence fxkg, k 2 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 2 M0; epi(f; Rn)

G0: Generate numbers and "k > 0, k 2 K, according to conditions x 2 M0, "k ! 0, k ! 1. Assign i = 0, k = 0.

1. Find a point (yi; i), where yi 2 Rn, i 2 R1, as a solution of the problem f (x) for all minf : (x; ) 2 Gi; x 2 Mk; g: If yi 2 D and f (yi) = i, then yi 2 X , and minimization process is nished. If yi 2 D and at the same time the inequality is ful lled, then yi 2 X ("k), and the "k-solution of problem ( 1 ) is found. 2. Select an element bi 2 @f (yi). If f (yi) i

"k f (yi) i > "k; then assign

Gi+1 = Si ∩f(x; ) 2 Rn+1 : f (yi) + ⟨bi; x yi⟩ g; 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

4. Choose a convex closed set Si

Rn+1 in accordance with

xk 2 Mk; f (xk)

f (yik ): epi(f; Rn)

Si ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) and construct a set Gi+1 in the form of ( 6 ).

5. Construct a set Mk+1 by the following rule. If xk 2 D, then assign Mk+1 = Mk; else choose ak 2 @F (xk) and assign Mk+1 = Mk ∩fx 2 Rn : F (xk) + ⟨ak; x xk⟩ 0g: 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 2 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 2 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 ful lled for all k 2 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 2 K inequality ( 4 ) is de ned, and using Si = epi(f; Rn) in ( 8 ) we have equalities Gi = epi(f; Rn), i 2 K. Also note that it is possible to use G0 = Rn+1. In this case any point (y0; 0), where y0 2 M0 and 0 = , can be a solution of problem ( 3 ) for i = 0.

Note that one can assign Si = Gi for all i 2 K independently of conditions ( 4 ), ( 5 ). Then cutting planes formed approximating sets Gi+1 will be accumulated in nitely. 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 nite 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 2 K.

Lets observe some properties of the proposed algorithm.

Taking into account ( 2 ) it is easy to prove by induction that for all k 2 K and i 2 K inclusions x 2 Mk, (x ; f ) 2 Gi are ful lled.

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 2 K, i 2 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 2 D and condition ( 4 ) is determined, then from ( 9 ) it follows that f (yi) f + "k, and, consequently, the approximation yi is an "k-solution of the initial problem.

If the equation Si = Gi is de ned for all i 2 K in the algorithm, then taking into account ( 9 ) it is not difficult to prove the limit expression lim (f (yi) i) = 0. On i2K the base of this equality and in view of the methology [10] it is clear to observe the following Lemma 1. If the sequence f(yi; i)g is constructed by the suggested algorithm, then there exist a number i = ik 2 K for all k 2 K such that equality ( 4 ) is ful lled.

Theorem 1. The inclusion x 2 X is valid for any limit point x of the sequence fxkg 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 2 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 f"kg 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 En+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 dropping 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 nding discrete minimax with dropping 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].