# An Approximate Proximal Bundle Method to Minimize a Class of Maximum Eigenvalue Functions

Authors: Wei Wang; Lingling Zhang; Miao Chen; Sida Lin
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We present an approximate nonsmooth algorithm to solve a minimization problem, in which the objective function is the sum of a maximum eigenvalue function of matrices and a convex function. The essential idea to solve the optimization problem in this paper is similar to the thought of proximal bundle method, but the difference is that we choose approximate subgradient and function value to construct approximate cutting-plane model to solve the above mentioned problem. An important advantage of the approximate cutting-plane model for objective function is that it is more stable than cutting-plane model.
In addition, the approximate proximal bundle method algorithm can be given. Furthermore, the sequences generated by the algorithm converge to the optimal solution of the original problem.


---

## Body

## 1. Introduction

Bundle method is one of the efficient and promising methods for solving nonsmooth optimization problems. For example, a class of maximum eigenvalue function can be minimized by bundle method [1], bundle-filter method can be used to deal with nonsmooth convex constrained optimization problem [2], and penalized bundle method was proposed to solve nonsmooth optimization problem by Bonnans et al. [3]. Recently, a minimization problem for a class of constrained maximum eigenvalue function has been solved in [4] with the help of penalized bundle method. However, when constructing the cutting-plane model for the objective function, the formula ∂F(y)=β*∂λmax⁡(A(y))+∂g(y) shows that the subdifferential of λmax⁡(A(y)) is involved in [4]. Note that ∂λmax⁡(A(y)) is the face of Cn exposed by A(y), where Cn:={V∈Sn:V⪰0,tr⁡V=1}. So ∂λmax⁡(A(y)) changes drastically when the multiplicity of the λmax⁡(A(y)) is changed [5]. Thus ∂F(y) is unstable and it leads to the instability of cutting-plane model in [4]. In this paper, to avoid this drawback, we try to give a more stable approximate cutting-plane model for the objective function.In view of a class of nonsmooth optimization problem of the form(P)min⁡y∈Rnf(y)+g(y),
where f(y):=(λmax⁡∘A)(y) is the composite function of λmax⁡ and an affine mapping A, specifically
(1)Rn∋y⟼A(y)≔A0+βy
is affine, A0∈Sn and β is a linear operator from Rn to Sn; g(y) is a nonsmooth convex function. We modify the elements in bundle and give an approximate proximal bundle method algorithm for (P). Our algorithm is established on the basic assumption that at least one approximate function value and one approximate subgradient at each point are available. And suppose ri domf(y)∩ri domg(y)≠∅.The initial motivation for our present work lies in the following facts. The whole idea of so-called bundle methods can be concentrated on constructing a good approximation for the objective function. Reference [4] has solved this class of optimization problem with the help of cutting-plane model and penalized bundle method. However, the cutting-plane model in [4] is unstable. Our motivation is to construct a more stable approximate model for the objective function. We try to use the approximate subdifferential of the objective function F(y)≔f(y)+g(y)=(λmax⁡∘A)(y)+g(y). Note that in the equation ∂ɛF(y)=β*∂ɛλmax⁡(A(y))+∂ɛg(y), obviously, ∂ɛλmax⁡(A(y)) is involved. And ∂ɛλmax⁡(A(y)) is no longer a face of Cn; it is the intersection of Cn with the half-space {V∈Sn:V·A(y)≥λmax⁡(A(y))-ɛ}. In particular, almost all matrices in ∂ɛλmax⁡(A(y)) have rank n (for ɛ>0), whereas the rank of matrices in ∂λmax⁡(A(y)) is at most the multiplicity r, which is 1 for almost all A(y) (so ∂ɛλmax⁡(A(y)) is relative stable); this also gives an idea of the big gap existing between these two convex sets. Therefore we decide to introduce an enlarged subdifferential [6] of λmax⁡(A(y)) which can be regarded as an outer approximation of ∂λmax⁡(A(y)) and an inner approximation of ∂ɛλmax⁡(A(y)). Through the enlarged subdifferential of λmax⁡(A(y)), we can easily get an enlarged subdifferential of the objective function F(y). Using the approximate subgradient in the enlarged subdifferential to construct the approximate cutting-plane model for the objective function, there are two advantages: on one hand it can avoid the instability of the cutting-plane model which is constructed in [4], on the other hand it can avoid too much elements in ∂ɛλmax⁡(A(y)). After constructing a more stable approximate cutting-plane model, we propose our algorithm and prove the convergence of the algorithm.The rest of this paper is organized as follows. Section2 mainly contains the approximate cutting-plane model of the objective function. Here we firstly introduce an enlarged subdifferential which is an outer approximation of ∂F(y), simultaneously, it is an inner approximation of ∂ɛF(y). And then, using the approximate subgradient in the enlarged subdifferential to complete the constructing of an approximate cutting-plane model for the objective function. Section 3 gives the algorithm with respect to the approximate proximal bundle method and also provides a corresponding compression mechanism. Section 4 is devoted to convergence analysis of the algorithm mentioned in Section 3. Section 5 gives the conclusions.In the paper, the standard norm and inner product are all in Hilbert space and are denoted by∥·∥ and 〈·,·〉.


## 2. The Approximate Model of the Objective Function

In this section, we will mainly give the approximate model for the objective function. It is known that [4] has given a kind of approximate model for the objective function F(y):
(2)F~k(y)=max⁡i=1,2,…,k{F(xi)+〈β*Q(A(xi))ZQ(A(xi))T+si,1111111111111111111y-xi(A(xi))T〉},
where Q(A(xi))ZQ(A(xi))T∈∂λmax⁡(A(xi)) and si∈∂g(xi).It is known that∂λmax⁡(A(y)) is the face of Cn exposed by A(y), where Cn≔{V∈Sn:V⪰0,tr⁡V=1}. If the multiplicity of λmax⁡(A(y)) is changed, the subdifferential of λmax⁡(A(y)) changes drastically. So it leads that the subdifferential of function F(y) is unstable. Thus this causes the instability of F~k(y). In order to construct a stable approximate model, we take the approximate subdifferential of function F(y) into account. Firstly, we consider the approximate subdifferential of λmax⁡(A(y)).Definition 1.
For ally∈Rn, ɛ≥0 and A:Rn→Sn is an affine mapping. One defines the following:(1)
the set of indices ofɛ-largest eigenvalues:
(3)Iɛ(A(y))≔{i∈1,2,…,n:λi(A(y))>λmax⁡(A(y))-ɛ};(2)
theɛ-multiplicity of λmax⁡(A(y)):
(4)rɛ≔max⁡{i:i∈Iɛ(A(y))};(3)
theɛ-first eigenspace:
(5)Eɛ(A(y))≔⨁i∈Iɛ(A(y))⁡Ei(A(y)),where Ei(A(y)) is the eigenspace of A(y) associated with the its eigenspace λi(A(y)).For the composite maximum eigenvalue function, its approximate subdifferential is(6)∂ɛλmax⁡(A(y))={V∈Cn:V·A(y)≥λmax⁡(A(y))-ɛ},
where Cn={V∈Sn:V⪰0,tr⁡V=1}. From this one sees that ∂ɛλmax⁡(A(y)) is the intersection of Cn with the half-space {V∈Sn:V·A(y)≥λmax⁡(A(y))-ɛ}, instead of being a face of Cn. In particular, almost all matrices in ∂ɛλmax⁡(A(y)) have rank n (for ɛ>0), whereas the rank of matrices in ∂λmax⁡(A(y)) are at most the multiplicity r, which is 1 for almost all A(y); this gives ideas that ∂ɛλmax⁡(A(y)) is more stable than ∂λmax⁡(A(y)) and there is a big gap existing between these two convex sets.Introduce a compact convex set(7)σɛλmax⁡(A(y))={Qɛ(A(y))ZQɛ(A(y))T:Z∈Crɛ},
where Qɛ(A(y)) is a n×rɛ matrice whose columns form orthonormal basis of Eɛ(A(y)).Proposition 2.
LetA:Rn→Sn be an affine mapping, then for all y∈Rn and ɛ≥0 one has
(8)∂λmax⁡(A(y))⊂σɛλmax⁡(A(y))⊂∂ɛλmax⁡(A(y)).Proof.
The left inclusion can be derived from simple chain rules and (7). To see another inclusion, take P∈σɛλmax⁡(A(y)). Then
(9)P=Qɛ(A(y))ZQɛ(A(y))TwithZ∈Crɛ.
Since
(10)Qɛ(A(y))TTQɛ(A(y))=diag⁡(λmax⁡(A(y)),…,λrɛ(A(y)))⪰λrɛIrɛ
and tr⁡Z=1. Thus it follows that
(11)〈P,A(y)〉=〈Z,Qɛ(A(y))TTQɛ(A(y))〉≥λrɛ.
Together with (3), we have 〈P,A(y)〉≥λmax⁡(A(y))-ɛ; for P∈Cn this means that, according to (6), P∈∂ɛλmax⁡(A(y)). Accordingly, the proof of right inclusion is completed.Note that the compact convex setσɛλmax⁡(A(y)) can be regarded as an outer approximation of ∂λmax⁡(A(y)) and an inner approximation of ∂ɛλmax⁡(A(y)). This set will avoid both the weakness of ∂λmax⁡(A(y)) (unstable) and the drawback of ∂ɛλmax⁡(A(y)) (too much elements). Applying the linear mapping β* in (8). Then
(12)β*∂λmax⁡(A(y))⊂β*σɛλmax⁡(A(y))⊂β*∂ɛλmax⁡(A(y)).
Set σɛf(y)≔β*σɛλmax⁡(A(y)). Then we obtain
(13)∂λmax⁡∘A(y)⊂σɛλmax⁡∘A(y)⊂∂ɛλmax⁡∘A(y).
This formula is equivalent to
(14)∂f(y)⊂σɛf(y)⊂∂ɛf(y).
Add ∂g(y) simultaneously, since ri domf(y)∩ri domg(y)≠0, we have
(15)∂F(y)=∂f(y)+∂g(y)⊂σɛf(y)+∂g(y)⊂∂ɛf(y)+∂ɛg(y)=∂ɛF(y).
Set σɛF(y):=σɛf(y)+∂g(y). Thus ∂F(y)⊂σɛF(y)⊂∂ɛF(y). Finally, σɛF(y) is the enlarged subdifferential of the objective function F(y) and it can be regarded as an outer approximation of ∂F(y) and an inner approximation of ∂ɛF(y). The following work will base on the enlarged subdifferential σɛF(y).Chooseβ*Qɛ(A(xi))ZQɛ(A(xi))T∈σɛf(xi) and si∈∂g(xi), then
(16)β*Qɛ(A(xi))ZQɛ(A(xi))T+si∈σɛF(xi)⊂∂ɛF(xi).
Next at each point xi compute an approximate function value Fɛ(xi) satisfying
(17)F(xi)-ɛ≤Fɛ(xi)≤F(xi).
Thus, using these approximate information of F(y), the approximate model F~k(y) becomes
(18)F¯k(y)=max⁡i=1,…,k{(A(xi))TFɛ(xi)+〈β*Qɛ(A(xi))ZQɛ(A(xi))T11111111111111111111+si,y-xi(A(xi))T〉}.
Let the aggregate linearzation error at xk be denoted by ei:
(19)ei≔F(xk)-Fɛ(xi)-〈β*Qɛ(A(xi))ZQɛ(A(xi))T+si,xk-xi〉.
With the notation, we obtain the form of approximate model
(20)F¯k(y)=F(xk)11111111+max⁡i=1,…,k{(A(xi))T-ei+〈β*Qɛ(A(xi))ZQɛ(A(xi))T+si,1111111111111111111111y-xk(A(xi))T〉},
where Z∈Crɛ.Observe thatF¯k(y) is a more stable approximate model than F~k(y). In the following part, based on the approximate model F¯k(y), we will give the approximate proximal bundle method algorithm.


## 3. The Approximate Proximal Bundle Method Algorithm

Algorithm 3 (the approximate proximal bundle method).
Step
0. Let θ≥0, m∈(0,1) be given parameters. Choose x1, we can obtain an approximate function value Fɛ(x1) and approximate subgradient β*Qɛ(A(x1))ZQɛ(A(x1))T+s1∈σɛF(x1)⊂∂ɛF(x1). Then construct the approximate model and set k=1, δ1=∞.
Step
1. If δk≤θ, stop.
Step
2. Solve the quadratic program:
(P1)min⁡y∈RnF-k(y)+12ηk∥y-xk∥2.
Define δk+1 as the nominal decrease:
(21)δk+1:=F(xk)-F-k(yk+1)-12ηk∥yk+1-xk∥2.
Step
3. Call the black box again with y=yk+1, if
(22)F(xk)-F(yk+1)≥mδk+1.
Then set xk+1=yk+1, otherwise set xk+1=xk. Corresponding, the former one is said to be descent step and the latter one is called null step.
Step
4. Append yk+1 to the bundle model and construct F¯k+1. Change k to k+1 and go to Step 1.Remark 4.
For a parameterηk>0, then the candidate point yk+1 can be obtained through solving the dual problem of (P1).Theorem 5.
Ifyk+1 is the unique solution to (P1) and suppose that ηk>0, then yk+1=xk-(1/ηk)∑i=1npkα¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si) and α¯=(α¯1,…,α¯npk) is a solution to
(D1)min⁡12ηk∥∑i=1npk‍αi(β*Qɛ(A(xi))ZQɛ(A(xi))T111111111111111+si(A(xi))T)∑i=1npk‍∥+∑i=1npk‍αieis.t.α∈Δk={αi∈[0,1],∑i=1npk‍αi=1,i=1,…,npk}.
In addition, one can also have the following relations: (i)
∑i=1npkα¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si)∈∂ɛF-k(yk+1);(ii)
δk+1=ϵk+(1/2ηk)∥∑i=1npkα¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si∥2, where ϵk=∑i=1npkα-iei;(iii)
∑i=1npkα-i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si)∈∂ϵkF(xk).Proof.
Turn(P1) into a quadratic programming problem with an extra scalar variable r:
(P2)min⁡(y,r)∈Rn×Rrr+12ηk∥y-xk∥2s.t.F(xk)-ei111111+〈β*Qɛ(A(xi))ZQɛ(A(xi))T+si,y-xk〉11111≤r,i=1,2,…,npk.
The corresponding lagrangian is, for α∈R+npk,
(23)L(y,α,r)=r+12ηk∥y-xk∥2+∑i=1npk‍αi((A(xi))TF(xk)-ei1111111111+〈β*Qɛ(A(xi))ZQɛ(A(xi))T+si,11111111111111y-xk(A(xi))T〉-r(A(xi))T).
By strong convexity, the dual problem of (P1) is equivalent to problem (D1).
Andyk+1=xk-(1/ηk)∑i=1npkα¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si) is the solution to the quadratic programming problem (P1), then (i) holds.
To see (ii) and (iii), note that since there is no duality gap, the primal optimal value in(P1) equals the dual optimal value in (D1). Thus the term (ii) holds. The relation F(y)≥F-k(y)≥F-k(yk+1) implies that the term (iii) holds.From Theorem5 we can ensure the candidate point yk+1 which appears in Step 2 can be obtained.Remark 6.
As iterations conduct, the elements in the bundle become more and more. When the size of the bundle becomes too big, it is necessary to compress bundle. So, at Step 4, one should append the compression subalgorithm.When the current size of the bundle is bigger than the maximal size, that is,npk≥npmax⁡, Step 4 turns out to be as follows:Step  4′. Let nact:={i≤npk:α-i≥0} be the active indices.Ifnact≤npmax⁡-1, then keep active couples and delete all inactive couples from the bundle. Set nleft=nact and define npk+1=nleft+1. Then append new element
(24)(β*Qɛ(A(xnpk+1))ZQɛ(A(xnpk+1))T+snpk+1,enpk+1)
to the bundle and construct model F¯k+1. Let k=k+1, and go to Step 1. Note that enpk+1 is in new element: (i)
when it is a descent step,enpk+1=0,(ii)
when it is a null step,(25)enpk+1=F(xk)-Fɛ(yk+1)1111111111-〈(A(xnpk+1))Tβ*Qɛ(A(xnpk+1))11111111111111×ZQɛ(A(xnpk+1))T+snpk+1,xk-yk+1(A(xnpk+1))T〉.Ifnact>npmax⁡-1, then delete two or more couples of elements. In addition, nleft≤npmax⁡-2. Define npk+1=npleft+2 and then append new element
(26)(β*Qɛ(A(xnpk+1))ZQɛ(A(xnpk+1))T+snpk+1,enpk+1)
to the bundle and construct model F¯k+1. Let k=k+1, and go to Step 1. Note that enpk+1 is in new element: (i)
when it is a descent step,enpk+1=0,(ii)
when it is a null step,(27)enpk+1=F(xk)-Fɛ(yk+1)-〈yk+1β*Qɛ(A(xnpk+1))ZQɛ(A(xnpk+1))T+snpk+1,xk-yk+1(A(xnpk+1))T〉.Remark 7.
Under certain circumstance withnpk>npmax⁡, if the remaining couples are still too many after discarding all inactive couples from the bundle, one synthesizes indispensable information of active elements in bundle. Simultaneously the corresponding affine function is called aggregate linearization and is denoted by Fα(y)(28)Fα(y)≔F(xk)-ϵk+〈∑i=1npk‍α¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si),111111111y-xk∑i=1npk‍〉.
For the aggregate linearization Fα(y), it holds that
(29)Fα(y)=F-k(yk+1)+〈∑i=1npk‍α¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si),1111111y-yk+1∑i=1npk‍〉;F-k(y)≥Fα(y)-ɛ,∀y∈Rn.
When the maximum capacity is reached, for instance, if k=npmax⁡, then assume that one discards the elements x1,x2,…,xt(t<k) from the bundle and appends the aggregate couple. The resulting model will be
(30)F¯k+1(y)=max⁡{max⁡t+1≤i≤k+1{Fɛ(xi)+〈mi,y-xi〉},Fα(y)},
where mi=β*Qɛ(A(xi))ZQɛ(A(xi))T+si. Note that for all k and y∈Rn, in any case, one can have
(31)Fα(y)≤F¯k+1(y)≤F(y);F¯k+1(y)≥F(xk+1)11111111+〈β*Qɛ(A(xk+1))ZQɛ(A(xk+1))T+sk+1,1111111111111y-yk+1(A(xk+1))T〉.


## 4. Convergence Analysis

To show convergence of the algorithm, we have to refer the stoping toleranceθ. So we consider two situations, that is, θ>0 and θ=0.Firstly, when the parameterθ>0, use the notation Ks to denote the set of indices k in which a new descent step is done.Theorem 8.
Consider Algorithm3 and use the notation F* to denote lim⁡k∈Ks⁡F(xk). Assume that the algorithm never stops (k→∞) as well as F*>-∞. Then
(32)0≤∑k∈Ks‍δk≤F(x1)-F*m.Proof.
Sinceθ>0 and the algorithm never stops, the nominal decrease must satisfy δk>0 for all k∈Ks. Note that Ks is a descent index set, we have xk+1=yk+1 and F(xk)-F(xk+1)=F(xk)-F(yk+1). Let k′ be the index following k in Ks. Between k and k′ the algorithm makes null steps only without moving the stability center xk+1=yk+j for all j=2,…,k′-k. The descent test at k′ gives
(33)F(xk+1)-F(xk′+1)≥mδk′+1.
Thus for all k′′∈Ks, it holds that when we let k′′→∞,
(34)m∑k∈Ksk′′‍≤∑k∈Ksk′′‍F(xk)-F(xk+1)=F(x1)-F(xk′′+1)=F(x1)-F*.
Removing m to the right side of the inequation, we obtain the desired result.Whenθ is taken strictly positive, by Theorem 8, there is an index k~ for which δk~≤θ if (P) has minimizers. By Theorem 5(ii), both ϵk and
(35)1ηklast∥∑i=1npk‍α-i(β*Qɛ(A(xk~))ZQɛ(A(xk~))T+sk~)∥2
are all small. Therefore, xk~ is the minimizer.Secondly, when the stopping toleranceθ=0, the algorithm either stops by having found a solution to (P) or it never stops. In this case, there are two possibilities for the sequence of descent steps {xk}k∈Ks. One is that it has infinitely many elements. Another is that there is an iteration k~ where a last descent step is done, that is, xk=xk~ for all k≥k~. We proof these two cases separately.Case
1. There are infinitely many elements in Ks.Theorem 9.
Suppose that the algorithm generates infinitely many descent stepsxk for all k∈Ks. One has (i)
if(P) has an empty solution, then {f(xk)}↘0;(ii)
if(P) has minimizers and ∑k∈Ks(1/ηk)=+∞ with k∈Ks and k→∞, the sequence {xk} is minimizing for (P) and converges to a minimizer of (P).Proof.
(i) Note that the algorithm loops forever andθ=0 for all k∈Ks, thus δk+1 holds. Then the infinite sequence of objective values {f(xk)} is strictly decreasing. If (P) has no solution, the sequence {f(xk)} is close to -∞. Therefore the proof of (i) is completed.
(ii) To show that{xk} is a minimizing sequence. Suppose for contradiction purposes that there exists x~∈Rn and t>0 such that F(x~)≤F(xk)-t for all k∈Ks. By Theorem 5(iii), we have
(36)〈x-xk,∑i=1npk‍α¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si)〉≤F(x)-F(xk)+ϵk.
By xk+1=xk-(1/ηk)∑i=1npkα¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si) and Theorem 5(ii), hence
(37)∥xk+1-x∥2=∥xk-1ηk∑i=1npk‍α¯i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si)-x∥2≤∥xk-x∥2+2ηk(F(x)-F(xk)+ϵk)+2ηk(δk+1-ϵk)=∥xk-x∥2+2ηk(F(x)-F(xk)+δk+1).
Write the relation (37) for x=x~, we obtain
(38)0≤∥xk+1-x~∥2≤∥xk-x~∥2+2ηk(F(x~)-F(xk)+δk+1)≤∥xk-x~∥2+2ηk(-t+δk+1).
Since {δk}→0 with k→∞, there exists kt such that δk+1<t/2 for all k≥kt. Thus the relation (38) becomes
(39)0≤∥xk+1-x~∥2≤∥xk-x~∥2-tηk∀k∈Ks,k≥kt.
Summing the inequations over kt≤k∈Ks yields
(40)0≤∥xkt-x~∥2-t∑k≥kt,k∈Ks‍1ηk.
Letting k→∞, we obtain a contradiction for the divergence assumption ∑‍(1/ηk)=+∞. Therefore, the sequence {xk} is a minimizing sequence.
To see that{xk} converges to a minimizer of (P), take in (37) x=x¯, a solution to (P), and sum over k∈Ks. It holds that F(x¯)≤F(xk) for all k. We see that
(41)∥xk-x¯∥2≤∥x1-x¯∥2+2ηmin⁡∑k∈Ks‍δk≤∥x1-x¯∥2+2(F(x1)-F*)ηmin⁡m.
Then the sequence {xk} is bounded. Take a subsequence {xki}ki∈Ks converging to x¯ as i→∞. Given u>0, take i big enough such that
(42)∥xki-x¯∥2≤u2,∑k∈Ks,k≥ki‍δk+1≤12uηk.
Writing (37) with x=x¯ and summing it over k∈Ks from ki to an arbitrary k~>ki yield
(43)0≤∥xk~+1-x¯∥2≤∥xki-x¯∥2+1ηk∑k∈Ks,k≥ki‍δk+1≤u,
which implies that {xk} converges to a minimizer of (P).Case
2. There are finitely many descent steps. It means that the last descent step xk~ is followed by an infinite number of null step, that is, xk=xk~ for all k≥k~.Theorem 10.
Assume that Algorithm3 generates a last descent step xk~ followed by infinitely many null steps. Then sequence {xk} converges to xk~ and xk~ minimizes the function F.Proof.
Letyk+1 be the solution to (P1), we have
(44)F¯k(yk+1)+12ηk∥yk+1-xk~∥2≤F¯k(xk~)≤F(xk~).
Set
(45)Mk(y)≔F¯k(yk+1)+12ηk∥y-xk~∥2+12ηk∥yk+1-y∥2.
Then
(46)Mk(yk+1)≤F(xk~)∀k≤k~.
By (30), we have
(47)Mk+1(yk+2)≥Mk(yk+1)+12ηk∥yk+2-yk+1∥2;(48)Mk(yk+1)+12ηk∥yk+1-xk~∥2=F¯k(yk+1)+ηk∥yk+1-xk~∥2≤Fα(xk~)≤F(xk~).
Thus, the sequence {yk+1} is bounded. By the relation (47), we have
(49){yk+1-yk}⟶0ask⟶∞.
It is obvious from the convexity that
(50)F¯k(yk+1)-F(yk)≤F(yk+1)-Fyk≤L∥yk+1-yk∥2.
So, it holds that
(51)F¯k(yk+1)-F(yk)⟶0.
From the bounded sequence {yk} extract a subsequence {yki}→y¯ as i→∞, for {yk+1-yk}→0 and {yki+1-y¯}→0; thus
(52)F(yki+1)-F¯ki(yki+1)⟶0asi⟶∞.
Then
(53)F¯ki(yki+1)⟶F(y¯).
When k≥k~, the descent test is never satisfied, that is, F(yki+1)-F(xk~)>-mδki+1, adding δki+1 to the both sides of the inequation and using the definition of δki+1 in (21), we can obtain
(54)0≤(1-m)δki+1≤F(yki+1)-F¯ki(yki+1).
Let i→∞, then δki+1→0. In addition, as i→∞(55)ϵk⟶0,12ηk∥∑i=1npk‍α-i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si)∥2⟶0.
By Theorem 5(iii), it holds that
(56)F(y)≥F(xk~)+〈∑i=1npk‍α-i(β*Qɛ(A(xi))ZQɛ(A(xi))T+si),1111xxx11y-xk~∑i=1npk‍〉-ϵki.
Passing to the limit as i→∞ the inequation shows that {xk~} minimizes the function F.
This is to show thaty¯=xk~. Since
(57)F(y¯)≥F(xk~)≥F¯ki(xk~)≥F¯ki(yki+1)+12ηki+1∥yki+1-xk~∥2≥F¯ki(yki+1)+12ηk~∥yki+1-xk~∥2,
passing to the limit as i→∞, we obtain
(58)F(y)≥F¯(y)+12ηk~∥y¯-xk~∥2.
The inequality holds if and only if y¯=xk~. Thus xk~ is the minimizer.


## 5. Conclusions

In this paper, we have given an enlarged subdifferential and constructed a more stable approximate cutting-plane model for the objective function. Then we have proposed an approximate proximal bundle algorithm and shown how to use this algorithm to minimize a class of maximum eigenvalue functions. Finally, it may be possible to extend this method to an even larger class of constrained maximum eigenvalue function.



---

*Source: 893765-2014-07-17.xml*