A method from a class of bundle methods is proposed to solve an unconstrained optimization problem. In this method an epigraph of the objective function is approximated by the set which is formed on the basis of the convex quadratic function. This method is characterized in that iteration points are constructed in terms of information obtained in the previous steps of the minimization process. Computational aspects of the proposed method are discussed, convergence of this one is proved, and convergence rate of the iteration process is obtained.
A class of bundle methods is quite wide (e.g. [2{6]). Such methods use multi-step approach of constructing iteration points to solve a convex programming problem. Namely, the next approximation is formed in term of prehistory of the solution process by minimizing an auxiliary convex quadratic function. Taking into account this feature the given methods pro tably differ from one-step methods by constructing anti gully trajectory of the iteration points and good convergence rate.
In this paper the method is proposed for solving a convex programming problem which belongs to the mentioned class. The suggested method also applies multi-step technique of constructing approximations. Moreover, note that unlike the famous bundle methods the solution of the auxiliary quadratic programming problem is obtained in the proposed method by the formula, and this fact is convinient to use in practical implementations of the method. The method is proposed for solving the following problem:
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes.
minff (x) : x 2 Rng; where f (x) is a continuously differentiable convex function de ned in an n-dimensional Euclidian space Rn, and the gradient of the function f (x) satis es Lipschitz continuous condition jf ′(x) f ′(y)j Ljjx yjj for all x, y 2 Rn with the parameter L > 0.
Let f = minff (x) : x 2 Rng, X = fx 2 Rn : f (x) = f g ̸= ∅, epi(f ) = f(x; ) 2 Rn+1 : f (x)g, K = f0; 1; : : :g. By jBj denote the cardinality of the set B Rn. 3
A sequence fxkg, k 2 K, is constructed by the proposed method as follows.
0. De ne numbers l > 0, > 0 and r 2 K such that r 1. Select any point v 2 Rn. Assign 0 = l, k = 0 and B0 = fvg.
1. Choose
xk = argminff (y) : y 2 Bkg; and nd a point zk as a solution of the problem where where φk(x) = f (xk) + ⟨f ′(xk); x xk⟩ + 2 jjx xkjj2: increment k by one, and go to Step 1.
Firstly, lets represent some properties of the suggested method.
(
2. Choose a number k(b) 2 (0; 1] for each b 2 Bk such that
(uk(b); k(b)) = (b; k(b)) + k(b)((zk; φk) (b; k(b))) 2 epi(f ); 4. If the inequality jBkj < r is de ned, then construct the next set Otherwise nd a point vk = argmaxff (a) : a 2 Bkg, and determine
k(b) = f (b) + k: wk = argminff (uk(b)) : b 2 Bkg:
Bk+1 = Bk ∪fwkg: Bk+1 = Bk n fvkg ∩fwkg:
l k+1 = (k + 1)2 ; Remark 1. The point v which is described at Step 0 in the algorithm is the initial iteration point. Unfortunately, there is no any general approach of constructing the initial iteration point in nonlinear programming methods. But in the process of solving practical optimization problems there are some informations to construct a region which approximate the set of solutions. Consequently, it is obviously to select the initial iteration point v as close as possible to the mentioned region.
Remark 2. Note that as well as the multi-step methods the proposed method uses
prehistory of the solution process. Namely, according to (
In the bundle methods each iteration point is obtained by minimizing the auxiliary quadratic function constructed on the basis of the model of the objective function. Since this model consists of several cutting planes, then it is nessesary to use various numerical methods for solving quadratic programming problems. In the proposed method the model of the objective function contains only one cutting plane. Thus, the solution of the auxiliary quadratic problem can be found by the formula. This result is represented in the following statement.
Lemma 1. Suppose that sequences fzkg, fφkg, k 2 K, are constructed by the proposed method. Then equalities
zk = xk φk = f (xk) f ′(xk) ; jjf ′(xk)jj2 2 are de ned for all k 2 K.
Proof. Note that the function φk(x) is differentiable and strongly convex. Consequently,
problem (
k(xk) k = f (xk)+ k(1 k(xk)) k(xk) jjf ′(xk)jj2. 2 (11) (12) Lemma 3. If
Before proving convergence of the proposed method lets construct the parameter k(xk), k 2 K, by the following rule. then k(xk) = 1. Otherwise k(xk) is selected so that the equation is de ned. Then there exists a constant c > 0 such that Proof. Lets x numbers " 2 (1; 2) and i
(φk; zk) 2 epi(f ); f (uk(xk)) = k(xk) k(xk)
L2 i c 8k 2 K: 0 such that 2 "; where L > 0 is Lipshitz constant of the gradient f ′(x).
Since f (x) is a continuously differentiable functions, and its gradient satis es Lipshitz condition, then in view of k(1 2 i) 0 for all k 2 K we give f (xk) f (xk 2 i f ′(xk)) + k(1 2 i) f (xk) f (xk 2 i f ′(xk)) ⟨f ′(xk); 2 i f ′(xk)⟩ L 2 i f ′(xk)jj2 = 2 i jjf ′(xk)jj2 L2 2 2i 1jjf ′(xk)jj2 = 2 i 1 jjf ′(xk)jj2" 2 jj for all k 2 K.
Hence, by putting 22 i jjf ′(xk)jj2 2 i uk = xk f ′(xk) = xk + 2 i(zk xk); k = f (xk) + k(1 2 i) 2 i 2 jjf ′(xk)jj2 = k(xk) + 2 i(φk k(xk)); we have f (uk) k, consequently,
(uk; k) 2 epi(f ):
Now lets prove that there exist a constant c > 0 such that inequality (16) is de ned.
Note that according to conditions of the lemma the parameter k(xk) is constructed
by 2 ways. Firstly, if inclusion (14) is determined for some k 2 K, then k(xk) = 1.
Secondly, let the parameter k(xk) is de ned in accordance with (15). In this case
according to (
(uk(xk); k(xk)) 2= intepi(f ): (uk; k) 2 [(zk; φk); (xk; k(xk))]: (14) (15) (16) (17) (18) (19) (20) (21) Now taking into account (20)-(22) lets suppose that
2 i > k(xk): Then there exists a number k > 0 such that
(uk; k) = (xk; k(xk)) + k((uk(xk); k(xk)) (xk; k(xk))):
Hence, in view of (18), (19), (23) and using equality (
Remark 3. If inclusion (14) is not satis ed for some k 2 K, then (uk(xk); k(xk)) should be found as a boundary point of the set epi(f ) by solving one-dimensional equation (15). Note that such equation is also solved in embedding methods [1] to construct cutting hyperplanes.
Theorem 1. Suppose that the sequence fxkg, k 2 K, is constructed by the proposed method in accordance with conditions of Lemma 3, the set M (x0) = fx 2 Rn : f (x) f (x0)+ g is bounded, where = ∑k1=0 k. Then the sequence fxkg, k 2 K, is bounded, and the following equality takes place lim f (xk) = f . Moreover, convergence rate k2K c0 k f (xk) f ; k 2 K; k 1; is determined, where c0 > 0.
Proof. In accordance with (13) and Lemma 3 the inequality (23) (24) (25) (26) (27) f jjf ′(xk)jjjjxk x jj djjf ′(xk)jj; k 2 K; (28) where d diamM (x0). Suppose ak = f (xk) f . Then from (26), (28) it follows that ak ak+1 = f (xk) f (xk+1) 2c jjf ′(xk)jj2 k 2cd a2k k. Then in view of (10) and by putting A = maxfl; 2Lc d g we have ak+1 ak aA2k + kA2 for all k 2 K. Hence, from Lemma 5 [7, p. 89] under conditions I0 = K and I1 = ∅ convergence rate (25) is proved.