# AUV-Method for a Class of Constrained Minimized Problems of Maximum Eigenvalue Functions

Authors: Wei Wang; Ming Jin; Shanghua Li; Xinyu Cao
Journal: Journal of Function Spaces
 (2017)

---

## Abstract

In this paper, we apply theUV-algorithm to solve the constrained minimization problem of a maximum eigenvalue function which is the composite function of an affine matrix-valued mapping and its maximum eigenvalue. Here, we convert the constrained problem into its equivalent unconstrained problem by the exact penalty function. However, the equivalent problem involves the sum of two nonsmooth functions, which makes it difficult to apply UV-algorithm to get the solution of the problem. Hence, our strategy first applies the smooth convex approximation of maximum eigenvalue function to get the approximate problem of the equivalent problem. Then the approximate problem, the space decomposition, and the U-Lagrangian of the object function at a given point will be addressed particularly. Finally, the UV-algorithm will be presented to get the approximate solution of the primal problem by solving the approximate problem.


---

## Body

## 1. Introduction

The eigenvalue optimization problems have attracted wide attention to the nonsmooth optimization. Such problems arise from many applications such as signal recovery [1], shape optimization [2], and robotics [3]. Therefore, the research on methods for solving such problems plays an important role in enriching the blend of classical mathematical techniques and contemporary optimization theory. Various methods have been proposed to deal with such problems; for example, the bundle method was used by Helmberg and Oustry to solve a class of unconstrained maximum eigenvalue optimization problems [4]. Recently, Oustry applied U-Newton algorithm to solve the maximum eigenvalue optimization problem [5]. However, this method must satisfy the transversality condition. In this paper, we design a UV-algorithm which does not satisfy the strict condition above to solve the constrained maximum eigenvalue optimization problem approximately. Here, we focus our attention on the following mode problem particularly:Pmin⁡λ1Axs.t.fix≤0,i=1,2,…,m,where λ1(A(x)) is the maximum eigenvalue function and the mapping A(x)≔A0+A(x) is affine, A0∈Sn is given, A:Rn→Sn is a linear operator, and Sn is the space of n×n symmetric matrices. Consider an exact penalty function associated with P as follows: (1)Px≔λ1Ax+πmax⁡f0x,f1x,…,fmx,where f0(x)≡0, ∇f0(x)≡0, and π>0 is a penalty parameter. For π large enough, it is well known that the problem P is equivalent to the following form: P1minx∈Rn⁡Px.It is known that the UV-decomposition theory must be applied on the condition that the dimension of the V-space is not full dimensional. Since P(x) inherits the nondifferentiability of λ1(A(x)) and the function max⁡{fi}, it is difficult to apply UV-decomposition theory to P1 in that the V-space of P(x) at a given point is full dimensional. Hence, it is imperative to consider the smooth approximation function θε(x) [6] to the function λ1(A(x)). Then the approximate problem of P1 is given as follows: P2minx∈Rn⁡Pεx,where Pε(x)≔θε(x)+πmax⁡{f0(x),f1(x),…,fm(x)}. Thus the problem P2 can be solved by UV-algorithm and we can get the approximate solution of the problem P at the same time.The rest of the paper is organized as follows. Section2 introduces three equivalent UV-space decomposition definitions of Pε(x), associated with a given x¯∈Rn. The U-Lagrangian of Pε(x) and relevant property will be addressed more detailedly in Section 3. Section 4 is devoted to the UV-algorithm for solving the approximate problem and the convergence analysis of the method. Finally, Section 5 gives some conclusive comments.To be convenient for explanation, we give the set of the act indicators throughout the paper(2)Jx≔j∈0,1,…,m:θεx+πfjx=Pεxand set (3)φx≔πmax⁡f0x,f1x,…,fmx.The solution of the problemP depends on the study of the objective function of problem P2. The UV-space decomposition theory of Pε(x) will be shown firstly.


## 2.UV-Space Decomposition for Pε(x)

Firstly, we can easily obtain the description of the subdifferential aboutPε(x) as follows:(4)∂Pεx=∇θεx+∂φx=∇θεx+πconv⁡∇fjxj∈Jxand the relative interior of ∂Pε(x)(5)ri∂Pεx=∇θεx+ri∂φx.We start by defining a decomposition of spaceRn=U⊕V, associated with a given x-∈Rn. We give three definitions for the subspaces U and V as follows.Definition 1.
(i) DefineU1 as the subspace where Pε′(x¯,·) is linear and take V1≔U1⊥, and since Pε′(x¯,·) is sublinear, we have (6)U1≔d∈Rn:Pε′x¯,d=-Pε′x¯,-d.
(ii) DefineV2 as the subspace parallel to the affine hull of ∂Pε(x); in other words, (7)V2≔lin⁡∂Pεx¯-g¯,where g¯∈∂Pε(x¯) is arbitrary and take U2≔V2⊥.
(iii) DefineU3 and V3 as the normal and tangent cones to ∂Pε(x¯) at a given point g∘; that is, (8)U3≔N∂Pεx¯g∘,V3≔T∂Pεx¯g∘.In the meantime, U3 and V3 are subspaces.Theorem 2.
In Definition1, we have the following:
(i) The subspaceU3 is actually given by (9)U3=d∈Rn:g′+∇θεx¯-g∘,d=0,∀g′∈∂φx¯=N∂φx¯g∘-∇θεx¯and is independent of the particular g∘∈ri∂φ(x¯).
(ii) SubspaceV2 is parallel to the affine hull of ∂φ(x¯); that is,(10)V2=lin⁡∂φx¯-g′,∀g′∈∂φx¯.More specifically, V2=lin⁡⁡{∇fj(x¯)-∇f0(x¯)}j∈J(x¯).
(iii)U1=U2=U3≕U.Proof.
(i) On one hand, by Definition1 and a normal cone, we have(11)d∈N∂Pεx¯g∘⟺d,g′+∇θεx¯-g∘≤0⟺d,g′-g∘-∇θεx¯≤0⟺d∈N∂φx¯g∘-∇θεx¯,where g′+∇θε(x¯)∈∂Pε(x¯), g′∈∂φ(x¯), and g∘∈ri∂Pε(x¯).
On the other hand, let(12)N≔d∈Rn:d,g′+∇θεx¯-g∘=0,∀g′∈∂φx¯.By the definition of a normal cone, N⊆N∂φ(x¯)(g∘-∇θε(x¯)). Next, we only need to establish the converse case. Let d∈N∂φ(x¯)(g∘-∇θε(x¯)) and g′∈∂φ(x¯) and it suffices to prove 〈d,g′-(g∘-∇θε(x¯))〉≥0. Indeed, let (13)β=-g′-g∘-∇θεx¯g′-g∘-∇θεx¯∈V2.By the definition of relative interior, there exists a positive constant η such that g∘-∇θε(x¯)+ηβ∈∂φ(x¯) and d∈N∂φ(x¯)(g∘-∇θε(x¯)) implies that (14)d,g∘-∇θεx¯+ηβ-g∘+∇θεx¯=-ηg′-g∘-∇θεx¯d,g′-g∘-∇θεx¯≤0.Then the result (i) is proved.
(ii) Taking the affine hull of∂Pε(x¯)=∇θε(x¯)+∂φ(x¯), we obtain (15)aff∂Pεx¯=∇θεx¯+aff∂φx¯.Hence, the subspace which is parallel to the affine hull of ∂Pε(x¯) is also parallel to the affine hull of ∂φ(x¯); that is, V2=lin⁡∂φx¯-g′, where g′∈∂φ(x¯) is arbitrary. Moreover, by the definition of ∂φ(x¯), we have (16)∂φx¯=πconv⁡∇fjx¯j∈Jx¯=π∑j=0mαj∇fjx¯,where αj>0 and ∑j=0mαj=1. Let α0=1 and αj=0, j≠0, then π∇f0(x¯)∈∂φ(x¯), and we can obtain (17)V2=lin⁡π∑j=0mαj∇fjx¯-π∇f0x¯j∈Jx¯=lin⁡∇fjx¯-∇f0x¯j∈Jx¯.Then result (ii) is proved.
(iii) By the property ofPε′(x¯,·) and the definition of U1, we have φ′(x¯,d)=-φ′(x¯,-d). By the convexity of φ(x), we have(18)U1=d∈Rn:φ′x¯,d=-φ′x¯,-d=d∈Rn:maxg′∈∂φx¯⁡g′,d=ming′∈∂φx¯⁡g′,d.Let d∈U1, ∀g′∈∂φ(x¯), take g′′∈∂φ(x¯), and, by (18), we have 〈d,g′-g′′〉=〈d,g′〉-〈d,g′′〉=0. It implies that, ∀β′∈V2, d,β′=0; that is, d∈U2. Hence, U1⊆U2.
Letd∈U2, we have 〈d,g′〉=〈d,g′′〉 for all g′∈∂φ(x¯) and g′′∈∂φ(x¯). By the assumption g∘∈ri∂Pε(x¯), we have g∘-∇θε(x¯)∈ri∂φ(x¯)⊆∂φ(x¯). Then d,g′=d,g′′=〈d,g∘-∇θε(x¯)〉. By (i), we have d∈U3. Hence, U2⊆U3.
By (i) and (18), we obtain U3⊆U1. The proof of (iii) is completed.The solution of problemP is not only based on the UV-space decomposition of Pε(x) but also based on the study of the U-Lagrangian of Pε(x), which will be shown next.


## 3. TheU-Lagrangian of Pε(x)

Let∇θε(x¯)≔g~=g~U⊕g~V, let H2≔∇2θε(x¯) be a positive semidefinite matrix, and let U^ be a basis matrix for U. ∀g′∈∂φ(x¯), we define the U-Lagrange function of Pε(x¯) as follows:(19)LU,Pεu,g¯=inf⁡φx¯+u⊕v-gV′,vV+θεx¯+g~U,uU+12U^⊤H2U^u,uU.Associated with (19) we have the set of minimizers(20)Wu≔Argminv∈V⁡φx¯+u⊕v-gV′,vV.In the following paragraphs, a series of theorems and corollaries will be given to specify the property ofLU,Pε and the expansions of Pε(x).Theorem 3.
By the definition ofLU,Pε, we have the following conclusions:(i)
LU,Pε(u,g¯) is a proper convex function.(ii)
A minimum pointw∈W(u) in (20) is characterized by the existence of some g∈∂Pε(x¯) such that g¯V=gV′+g~V, where g′∈∂φx¯, and g′=gU′⊕gV′.(iii)
In particular,0∈W(0) and LU,Pε(0,g¯)=Pε(x¯).(iv)
Ifg′∈ri∂φ(x¯), then W(u) is nonempty for each u∈U and W(0)={0}.Theorem 4.
Letu satisfy W(u)≠∅. Then, ∀w∈W(u), the subdifferential of LU,Pε at this u has the expression (21)∂LU,Pεu,g¯=gU:gU⊕gV′+g~V∈∂Pεx¯+u⊕w.In particular, LU,Pε is differentiable at 0, with ∇LU,Pε(0,g¯)=gU′+g~U.Corollary 5.
Ifg′∈ri∂φ(x¯), then W(u)=o(uU).Theorem 6.
Letu satisfy W(u)≠∅, then, ∀w∈W(u), g′∈∂φ(x¯), g~=∇θε(x¯), and we have (22)Pεx¯+u⊕w=Pεx¯+g′+g~,u⊕wU+ouU.Theorem 7.
Assume the functionL¯U,Pε(u,g¯)=infv∈V⁡{φ(x¯+u⊕v)-〈gV′,v〉V} has a generalized Hessian H1 at u=0 and g′∈ri∂φ(x¯). For u∈U and x∈u⊕W(u), it holds that (23)Pεx¯+x=Pεx¯+g′+g~,x+12H1+U^⊤H2U^u,uU+ouU2.The proofs of the above theorems and corollary are similar to [7] and here we ignore the details of them.Based on the study ofUV-space decomposition theory and the U-Lagrangian of Pε(x), the UV-algorithm which can solve the problem P2 will be addressed in the next section.


## 4. TheUV-Method

Depending on theUV-theory mentioned above, the constrained minimization problem of maximum eigenvalue function has been converted into the convex minimization problem which can be solved by the UV-algorithm in [8]. Hence, we apply the UV-algorithm in [8] and do some appropriate modifications for solving the problem P2.In this section, some definitions and two quadratic programming problems will be denoted for easy understanding.Given a toleranceσ∈(0,1/2], a prox-parameter μ>0, and a prox-center x∈Rn, to find σ-approximation of Pμ(x), our bundle subroutine accumulates information from the candidates {yi}i∈B, where B≔{j:yj=x}.Definition 8.
Letx,yi∈Rn, i∈B, gi∈∂Pε(x), and the linearization error is defined by (24)ei≔ex,yi=Pεx-Pεyi-gi⊤x-yi.Definition 9.
Given a positive scalar parameterμ, the proximal point function depending on Pε(x) is defined by(25)pμx≔argminp∈RnPεp+12μp-x2forx∈Rn.The first quadratic programming subproblemχ-QP has the following form and properties; see [9]. The problem(26)χ-QPmin⁡r+12μp-x2:r,p∈R1+n,r≥Pεx-ei+gi⊤p-x,∀i∈B,μ>0has a dual problem(27)min⁡12μ∑i∈Bαigi2+∑i∈Bαiei:αi≥0,i∈B,∑i∈Bαi=1.Their respective solutions, denoted by (r~,p~) and α~=(α~1,…,α~B), satisfy(28)r~=ϕp~,p~=x-1μg~,g~≔∑i∈Bαi~gi,where ϕ(x)≔Pε(x)-∑i∈Bαi~ei-1/μ|g~|2 and αi~=0, for all i∈B, satisfies r~>Pε(x)-ei+gi⊤(p~-x). For convenience, in the sequel we denote the output of these calculations by (29)r~,p~=χ-QPμ,x,ei,gii∈B.The second quadratic programming subproblem is(30)γ-QPmin⁡r+12p-x2:r,p∈R1+n,r≥gi⊤p-x,∀i∈B~,where B~≔{i∈B:r~=Pε(x)-ei+gi⊤(p~-x)}∪{i+}, yi+=p~, and gi+∈∂Pε(p~). The above problem has a dual problem without linearization error terms: (31)min⁡12∑i∈B~αigi2:αi>0,i∈B~,∑i∈B~αi=1.Similar to (28), the respective solutions, denoted by (r¯,p¯) and α¯, satisfy(32)p¯-x=-s~,s~≔∑i∈B~α¯igi.Since the need of the algorithm, the solution of the problem (γ-QP) will be applied to get the matrix U~. Firstly, define an active index by B~act≔{i∈B~:r¯=g¯i(p¯-x)}. Then, from (32), r¯=-gi⊤s~ for all i∈B~act, so(33)gi-gl⊤s~=0for all such i and for a fixed l∈B~act. Define a full-column rank matrix V~ by choosing the largest number of indices i satisfying (33) such that the corresponding vectors gi-gl are linearly independent and by letting these vectors be the columns of V~. Then let U~ be a matrix where columns form an orthogonal basis for the null-space of V~⊤ with U~=I if V~ is vacuous.For convenience, in the sequel we denote the output from these calculations by(34)s~,U~=γ-QPgii∈B.The algorithm depending on the above quadratic programming problems is given as follows.Algorithm 10.
⁡
Step 0. Choose positive parameters ε, μ, and m with m<1. Let p0∈Rn and g0∈∂Pε(p0), respectively, be an initial point and subgradient. Also, let U0 be a matrix with orthogonal n-dimensional columns estimating an optimal U-basis. Set s0=g0 and k≔0.
Step 1. Stop if sk2≤ε.
Step 2. Choose an nk×nk positive definite matrix Hk, where nk is the number of columns of Uk and Uk approximating a basis for V(χ(u))⊤. For x¯ which is a minimizer of Pε(x), χ(u)=x¯+u⊕v(u), where v≔Rdim⁡U↦Rdim⁡V is a C2-function satisfying V¯v(u)∈W(u) for all g¯∈ri∂Pε(x¯). V¯ is a basis matrix of V and Hk is the approximation of ∇2LU,Pε(u,0).
Step 3. Compute an approximate U-Newton step by solving the linear system (35)HkΔu=-Uk⊤skforΔu=Δuk∈Rnkand set xk+1c≔pk+UkΔuk=pk-UkHk-1Uk⊤sk.
Step 4. Choose μk+1≥μ_, σk+1∈(0,1/2], initialize B, and run the following bundle subprocedure with x=xk+1c:Compute recursively(36)r~,p~=χ-QPμk+1,x,ei,gii∈Bε~=Pεp~-r~s~,U~=γ-QPgii∈B~until satisfying(37)ε~≤σk+1μk+1s~2.Then set (38)εk+1c,pk+1c,sk+1c,Uk+1c≔ε~,p~,s~,U~
Step 5. If (39)Pεpk+1c-Pεpk+1≤m2μk+1sk+1c2,and then declare a successful candidate and set (40)xk+1,εk+1,pk+1,sk+1,Uk+1≔xk+1c,εk+1c,pk+1c,sk+1c,Uk+1c.Otherwise, execute a line search on the line determined by pk and pk+1c to find xk+1 thereon satisfying Pε(xk+1)≤Pε(pk); reinitialize B and return the above bundle subroutine, but with x=xk+1, to find new values for (ε~,p~,s~,U~); then set (εk+1,pk+1,sk+1,Uk+1)≔(ε~,p~,s~,U~).
Step 6. Replace k by k+1 and go to stopping test.
Next, we will show the convergence of Algorithm10. From here on, we assume that ε=0 and that Algorithm 10 does not terminate. When the primal track at the initial point exists, firstly, it shows that if some execution of the bundle procedure in Algorithm 10 continues indefinitely, there is convergence to a minimizer of Pε.Theorem 11.
If the bundle procedure does not terminate, that is, if (37) never holds, then the sequence of p~-values converges to pμ(x) and pμ(x) minimizes Pε(x). If the procedure terminates with s~=0, the corresponding p~ equals pμ(x) and minimizes Pε(x). In both of these cases pμ(x)-x∈V(pμ(x)).Proof.
The recursion in the bundle subprocedure replacingB by B~ satisfies conditions (4.7) to (4.9) in [9]. By Proposition 4.3 in [9], if this procedure does not terminate it generates an infinite sequence of ε~-values converging to zero. Since (37) does not hold, the sequence of s~-values also converges to 0. Thus, by lemma 5 in [8] and continuity of Pε, we can get Pε(z)≥Pε(pμ(x)) for all z∈Rn. The termination case with ε~=0 follows in a similar manner, since (37) implies ε~=0 in this case. In either case, by the minimality of pμ(x), 0∈∂Pε(pμ(x)). From (3) in [8], 0-μ(x-pμ(x))∈V(pμ(x)), and the final result follows, since μ≠0.Next theorem shows minimizing convergence from any initial point without assuming the existence of a primal track. Here we assume that all executions of bundle procedure terminate.Theorem 12.
Suppose that the algorithm sequence{μk} is bounded above by μ¯. Then the following hold:(i)
The sequence{Pε(pk)} is decreasing and either {Pε(pk)}→-∞ or {sk} and {εk} both converge to 0.(ii)
IfPε is bounded from below, then any accumulation point of {pk} minimizes Pε.Proof.
(i) Sincesk≠0, whether or not pk+1c is successful candidate, the inequality(41)Pεpk+1-Pεpk≤m2μk+1sk+12holds. Equation (41) implies that {Pε(pk)} is decreasing. Suppose {Pε(pk)}↛-∞. Then summing (41) over k and using the fact that m/(2μk)≥m/(2μ¯) for all k imply that {sk}→0. From Lemma 5 in [8] and (37) with (μ,σ,ε~,p~,s~)=(μk,σk,εk,sk), we have(42)Pεpk+sk⊤z-pk-εk≤Pεz∀z∈Rn,(43)εk≤σkμksk2.Then (43) with σk≤1/2 and μk≥μ_>0 implies that εk→0 which establishes (i).
(ii) Now supposePε is bounded below and p¯ is any accumulation point of {Pk}. Then, because sk and {εk} converge to 0 by item (i), (42) together with the continuity of Pε implies that Pε(p¯)≤Pε(z) for all z∈Rn and (ii) is proved.In order to obtain convergence of the whole sequencepk, we need the concept of a strong minimizer.Definition 13.
We say thatx¯ is a strong minimizer of Pε if 0∈ri∂Pε(x¯) and the corresponding U-Lagrangian LU,Pε(u,0) has a Hessian at u=0 that is positive definite.Corollary 14.
Suppose thatx¯ is a strong minimizer of Pε, as in Definition 13, and that the algorithm sequence {μk} is bounded above by μ¯. Then {pk} converges to x¯. If, in addition, the sequence {Hk-1} is bounded, then {xk+1c} and {xk} converge to x¯ and {sk+1c} converges to 0∈Rn.Proof.
The proofs will be finished whenp~, s~, and Pε take the place of p^, s^, and f, respectively.


## 5. Conclusions

The principal result is that we present theUV-algorithm for solving the constrained minimization problem of maximum eigenvalue functions. The innovative point is converting the constrained problem into the approximate unconstrained problem. By using the smooth convex approximation of maximum eigenvalue function, the latter problem can be solved by UV-algorithm. Although this method is based on some assumptions, it enriches the ways to deal with the constrained minimization problem of maximum eigenvalue functions.



---

*Source: 5309698-2017-01-02.xml*