# The Space Decomposition Theory for a Class of Semi-Infinite Maximum Eigenvalue Optimizations

Authors: Ming Huang; Li-Ping Pang; Xi-Jun Liang; Zun-Quan Xia
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We study optimization problems involving eigenvalues of symmetric
matrices. We present a nonsmooth optimization technique for a class of nonsmooth functions which
are semi-infinite maxima of eigenvalue functions. Our strategy uses generalized gradients and𝒰
𝒱
space decomposition techniques suited for the norm and other nonsmooth performance criteria. For
the class of max-functions, which possesses the so-called primal-dual gradient structure, we compute
smooth trajectories along which certain second-order expansions can be obtained. We also give the
first- and second-order derivatives of primal-dual function in the space of decision variables R
m under
some assumptions.


---

## Body

## 1. Introduction

H
∞ output feedback control is an important example of a design problem, where the feedback controller has to respond favorably to several performance specifications. Typically in H
∞ synthesis, the H
∞ channel is used to enhance the robustness of the design. Due to its prominence in practice, H
∞ control has been addressed in various ways over the years.In nominalH
∞ synthesis, feedback controllers are computed via semidefinite programming (SDP) [1] or algebraic Riccati equations [2]. When structural constraints on the controller are added, the H
∞ synthesis problem is no longer convex. Some of the problems above have even been recognized as NP-hard or as rationally undecidable. These mathematical concepts indicate the inherent difficulty of H
∞ synthesis under constraints on the controller. The H
∞ synthesis problem involves finding an output feedback control matrix K that minimizes the H
∞ norm of a certain transfer function, subject to the constraint that K is stabilizing. This is a challenging problem and even finding a stabilizing K can be difficult. Indeed, if the entries of K are restricted to lie in prescribed intervals, then finding a stabilizing K is an NP-hard problem [3].H
∞ feedback controller synthesis was one of the motivating application for the development of our work. We consider a linear time invariant dynamical system in the standard LFT form
(1)
[
x
˙
z
y
]
=
[
A
B
1
B
2
C
1
D
11
D
12
C
2
D
21
D
22
]
·
[
x
w
u
]
,
where x
∈
R
n
x is the state, y
∈
R
n
y is the output, u
∈
R
n
u is the command input, and w
∈
R
n
w, z
∈
R
n
z are the performance channel. To cancel direct transmission from input u to output y, the assumption D
22
=
0 is made. This is without loss of generality (see [4], chapter 17).LetK be a static feedback controller; then the closed-loop state space data and transfer function T
(
K
,
·
) read
(2)
x
˙
=
A
(
K
)
x
+
B
(
K
)
w
,
z
=
C
(
K
)
x
+
D
(
K
)
w
,
T
(
K
,
j
w
)
=
C
(
K
)
(
j
w
I
-
A
(
K
)
)
-
1
B
(
K
)
+
D
(
K
)
,
where
(3)
A
(
K
)
=
A
+
B
2
K
C
2
,
B
(
K
)
=
B
1
+
B
2
K
D
21
,
C
(
K
)
=
C
1
+
D
12
K
C
2
,
D
(
K
)
=
D
11
+
D
12
K
D
21
.
Dynamic controllers can be addressed in the same way by prior augmentation of the plant (3) (see, e.g., [5]).InH
∞ synthesis, we compute K to minimize the H
∞ norm of the transfer function T
(
K
,
·
); that is,
(4)
∥
T
(
K
,
·
)
∥
∞
:
=
sup
⁡
w
∈
[
0
,
∞
]
σ
1
(
T
(
K
,
j
w
)
)
;
(see, e.g., [4]). The standard approach to H
∞ synthesis in the literature uses the Kalman-Yakubovich-Popov Lemma and leads to a bilinear matrix inequality (BMI) [6]. Here we use a different and much more direct approach based on our 𝒰
𝒱-decomposition method. The advantage of this is that Lyapunov variables can be avoided, which is beneficial because they are a source of numerical trouble. Not only does their number grow quadratically with the system order, but they may also cause strong disparity between the optimization variables. The price to be paid for avoiding them is that a difficult semi-infinite and nonsmooth program has to be solved. To synthesize a dynamic controller K of order n
k
∈
N, n
k
≤
n
x, the objective f
:
R
(
n
k
+
n
u
)
×
(
n
k
+
n
y
)
→
R
+ is defined as follows:
(5)
f
(
K
)
:
=
max
⁡
w
∈
[
0
,
∞
]
λ
1
(
T
(
K
,
j
w
)
H
T
(
K
,
j
w
)
)
=
∥
T
(
K
,
·
)
∥
∞
2
,
which is nonsmooth and nonconvex with two sources of nonsmoothness, the infinite max-operator and the maximum eigenvalue function. In addition, Z
H stands for the conjugate transpose of the complex matrix Z.The application we have in mind is optimizing theH
∞-norm, which is structurally of the form
(6)
f
(
x
)
=
sup
⁡
ω
∈
[
0
,
∞
]
λ
1
(
A
(
x
,
ω
)
)
,
where A
:
R
m
×
[
0
,
∞
]
→
S
n is an operator with values in the space S
n of n
×
n symmetric or Hermitian matrices, equipped with the scalar product X
•
Y
=
Tr
⁡
(
X
Y
), and λ
1 denotes the maximum eigenvalue function on S
n.The above problem (5) can be recast as a case of (6). The program we wish to solve in this paper is
(7)
min
⁡
x
∈
R
m
f
(
x
)
,
where the function f has the form (6).f is nonsmooth with two possible sources of nonsmoothness: (a) the infinite max-operator and (b) the nonsmoothness of λ
1, which may lead to nonsmoothness of λ
1
(
A
(
x
,
ω
)
) for fixed ω.Optimization of theH
∞-norm is a prominent application in feedback synthesis, which has been pioneered by Polak and coworkers; see, for instance, [7, 8] and the references given there. Existing methods for the H
∞ synthesis problem are often based on first reformulating the problem into one involving linear matrix inequalities (LMIs) and an additional nonconvex rank constraint or nonconvex equality constraint. Solving methods for such reformulations of the problem include those based on linearization method [9], alternating projections method [10], augmented Lagrangian method [11], and sequential semidefinite programming method [12]. The H
∞ synthesis problem can also be reformulated into a problem involving bilinear matrix inequalities (BMIs). Dealing with such reformulations of the problem includes [12, 13] (see also the references therein). A disadvantage of these approaches is that they require the introduction of Lyapunov variables. As the number of Lyapunov variables grows quadratically with the number of state variables, the total number of variables can be quite large and even problems of moderate size can lead to numerical difficulties [14].In this paper, theH
∞ synthesis problem is posed as an unconstrained, nonsmooth, nonconvex minimization problem and requires special optimization techniques. Our approach avoids the use of Lyapunov variables; hence, it is well suited for optimizing our reformulation of the H
∞ synthesis problem. We develop the local nonsmooth optimization strategy, a superlinear space decomposition algorithm, which is suited for optimizing the H
∞-norm. Problem (7) implies the smoothness information; we can adopt variable space decomposition form. Meanwhile, since the problem (7) has the special structure called primal-dual gradient structure (PDG), which has been introduced in [15], it is possible to identify smooth tracks. So we can design a method which has fast convergent rate. The approach which is taken to solve this problem is based on using the recently developed local optimization algorithm presented in [15, 16]. In light of the 𝒰
𝒱-space decomposition, this method is introduced in [15] (see also [17, 18]). Moreover, it is applied to many applications such as nonlinear programming and second-order cone programming (see [19–22]). The idea is to decompose R
n into two orthogonal subspaces 𝒱 and 𝒰 at a point x
- that the nonsmoothness of f is concentrated essentially on 𝒱, and the smoothness of f appears on 𝒰-subspace. More precisely, for a given g
-
∈
∂
f
(
x
-
), where ∂
f
(
x
-
) denotes the Clarke subdifferential of f at x
-. Then R
n can be decomposed as direct sum of two orthogonal subspaces, that is, R
n
=
𝒰
⊕
𝒱, where 𝒱
=
lin
⁡
(
∂
f
(
x
-
)
-
g
-
), and 𝒰
=
𝒱
⊥. Then we define the primal-dual Lagrangian, an approximation of the original function, and show along certain manifolds it can be used to create as second-order expansion for a nondifferentiable function. As a result, we can design an algorithm frame that makes a step in the 𝒱-space, followed by a 𝒰-Newton step in order to obtain superlinear convergence, and show that it improves the situation considerably.The rest of the paper is organized as follows. In Section2, we recall some basic concepts about 𝒰
𝒱 decomposition theory. In Section 3, we reformulate these problems as unconstrained max-finite function optimization problems under the hypothesis of the multiplicity one of the largest eigenvalue. We also mention some of the issues involved in trying to solve such problems. Using primal-dual gradient structure (PDG), we give an important conclusion about second-order expansion of the function. Likewise, Section 4 outlines the optimization approach as in Section 3 and presents a different way to deal with the supposition of multiplying largest eigenvalues. The paper ends with some concluding remarks.


## 2. Preparation and Preliminary Results

We recall the𝒰
𝒱-theory developed in [15]. Let f
:
R
m
→
R be a finite-valued convex function. For a given x
∈
R
m, we start by defining a decomposition of the space R
m
=
𝒰
(
x
)
⊕
𝒱
(
x
). The subspaces 𝒰
(
x
) and 𝒱
(
x
) are equivalently defined as follows:
(8)
𝒰
(
x
)
:
=
{
d
∈
R
m
:
f
′
(
x
;
d
)
=
-
f
′
(
x
;
-
d
)
}
,
𝒱
(
x
)
:
=
𝒰
(
x
)
⊥
.
In other words, 𝒰 is the subspace where f
(
x
+
·
) appears to be differentiable at 0. Likewise, we can obtain the following result, which is stated in [15].Proposition 1.
Letf
:
R
m
→
R be a proper convex function for a given point x; one has the following.(1)
𝒱
(
x
)
is the subspace parallel to aff
∂
f
(
x
)
and
𝒰
(
x
)
=
𝒱
(
x
)
⊥
.
(2)
For any
g
∈
ri ∂
f
(
x
)
,  𝒰
(
x
)
and
𝒱
(
x
)
are, respectively, the normal and tangent cones to
∂
f
(
x
)
at  g
, where ri
C
stands for the relative interior respect to a given set
C
.We give the Clarke generalized gradient for local Lipschitz function.Definition 2 (see [23, 24]).
Letf be local Lipschitz on R
n; the generalized gradient of f at x, denoted by  ∂
f
(
x
), is defined by
(9)
∂
f
(
x
)
:
=
{
ξ
∈
R
n
:
f
∘
(
x
;
d
)
≥
〈
ξ
,
d
〉
,
∀
d
∈
R
n
}
,
where f
∘
(
x
;
d
)
=
limsup
⁡
y
→
x
,
t
→
0
+
(
f
(
y
+
t
d
)
-
f
(
y
)
)
/
t is the generalized directional derivative of f at x in the directive d.The following results come from [23]; we will use these properties in later sections; as for their proofs, we will omit them.Proposition 3.
Suppose{
f
i
} is a finite collection of functions (
i
=
1
,
…
,
n
), each of which is Lipschitz near x. The function f is defined by
(10)
f
(
x
)
=
max
⁡
i
=
1
,
…
,
n
f
i
(
x
)
.
Then one has
(11)
∂
f
(
x
)
⊂
conv
{
∂
f
i
(
x
)
:
i
∈
I
(
x
)
}
,
where I
(
x
)
:
=
{
i
:
f
i
(
x
)
=
f
(
x
)
}, and if f
i is regular at x for each i
∈
I
(
x
), then equality holds and f is regular at x.Notation.We introduce the basic notation in the remainder parts. S
n is the space of n
×
n symmetric matrices and S
n
+ stands for the cone of n
×
n positive semidefinite symmetric matrices. A
·
B
:
=
tr
⁡
A
B denotes Fröbenius scalar product of A
,
B
∈
S
n. Let p
≥
1 be the multiplicity of the largest eigenvalue λ
1
(
A
) of A; that is, A lies on the submanifold ℳ
p
:
=
{
A
∈
S
n
:
λ
1
(
A
)
=
⋯
=
λ
p
(
A
)
>
λ
p
+
1
(
A
)
}, where ℳ
p is a C
∞-submanifold of S
n. Let E
1
(
A
) be the eigenspace associated with λ
1, let Q
1
(
A
) be an orthonormal basis of E
1
(
A
), let P
1
(
A
) be an orthonormal basis associated with λ
1
,
…
,
λ
p, T
ℳ
(
A
), and let N
ℳ
(
A
) be, respectively, the tangent and normal spaces to the submanifold ℳ at A
∈
ℳ. 𝒜
*
:
S
n
→
R
m is the adjoint operator of the linear operator 𝒜
:
R
m
→
S
n. Much of the additional notation comes from [25, 26].


## 3.𝒰
𝒱-Space Decomposition for Single Eigenvalue

### 3.1.𝒰
𝒱
-Theory of the Single Eigenvalue Function

In this section we will analyse the case where the multiplicity ofλ
1
(
A
(
x
,
ω
)
) is one at all active frequencies ω. This is motivated by practical considerations because nonsmoothness (b) never occurred in our tests. The necessary changes required for the general case will be discussed in next section.Lemma 4.
For a closed-loop stabilizing controllerx, the set of active frequencies Ω
(
x
)
:
=
{
ω
∈
[
0
,
∞
]
:
f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
)
} is either finite or Ω
(
x
)
=
[
0
,
∞
]; that is, f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
) for all ω.A system whereΩ
(
x
)
=
[
0
,
∞
] is called all-pass. This is rarely encountered in practice. For the technical formulas we will concentrate on those  x’s, where the set of active frequencies or peaks Ω
(
x
)
=
{
ω
∈
[
0
,
∞
]
:
f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
)
} is finite.From what follows we will analyse the case where the multiplicity off
(
x
,
ω
)
:
=
λ
1
(
A
(
x
,
ω
)
) is one at all active frequencies ω. This is motivated by practical considerations because nonsmoothness about λ
1 never happened in our tests. The necessary changes required for the general case will be discussed in Section 4.In [27], three approaches to semi-infinite programming are discussed: exchange of constraints, discretization, and local reduction. We will use a local reduction method here. The main ideas are recalled below.Letx
- be a local solution of (7). Indexing the active frequencies Ω
(
x
)
:
=
{
ω
-
1
,
…
,
ω
-
p
} at x
-, we suppose that the following conditions are satisfied.Assumption 5.
Consider
(i)f
ω
′
(
x
-
,
ω
-
i
)
=
0,  i
=
1
,
…
,
p,
(ii)f
ω
ω
′′
(
x
-
,
ω
-
i
)
<
0,  i
=
1
,
…
,
p,
(iii)f
(
x
-
,
ω
)
<
f
(
x
-
),  for every ω
∉
Ω
(
x
-
)
=
{
ω
-
1
,
…
,
ω
-
p
}.These assumptions define the setting denoted as the standard case in semi-infinite programming [27]. The three conditions express the fact that the frequencies ω
-
i
∈
Ω
(
x
-
) are the strict global maximizers of f
(
x
-
,
·
). Notice that condition (iii) is the finiteness hypothesis already mentioned, justified by Lemma 4.Lemma 6.
Under conditions (i)–(iii), the neighborhoodU of x
- may be chosen such that max
⁡
ω
∈
[
0
,
∞
]
⁡
f
(
x
,
ω
)
=
max
⁡
i
=
1
,
…
,
p
⁡
f
(
x
,
ω
i
(
x
)
) for every x
∈
U. In particular, Ω
(
x
)
⊂
{
ω
1
(
x
)
,
…
,
ω
p
(
x
)
} for every x
∈
U.So we have that program (6) is locally equivalent to the standard following nonlinear program:
(12)
min
⁡
x
∈
R
n
sup
⁡
i
=
1
,
…
,
p
f
(
x
,
ω
i
(
x
)
)
,
where f
(
x
,
ω
i
(
x
)
)
=
λ
1
(
A
(
x
,
ω
i
(
x
)
)
); then we may solve (12) via the so-called 𝒰
𝒱-decomposition method.Assumption 7.
f
x
′
(
x
-
,
ω
-
1
)
,
…
,
f
x
′
(
x
-
,
ω
-
p
) are linearly independent.Under the hypothesis of Assumption7, local convergence of this approach will be assured because this guarantees that (12) satisfies the linear independence constraint qualification hypothesis.We denoteF
(
x
)
:
=
sup
⁡
i
=
1
,
…
,
p
λ
1
(
A
(
x
,
ω
i
(
x
)
)
), and q
1
i
(
x
),  i
=
1
,
…
,
p, stands for the eigenvector associated with the largest eigenvalue of A
(
x
,
ω
i
(
x
)
).Next a special kind of structure ofF
(
x
), called primal-dual structure (PDG), will be seen.Proposition 8.
There exists a ball aboutx
-, denoted by B
(
x
-
), p functions
(13)
f
i
(
x
)
:
=
f
(
x
,
ω
i
(
x
)
)
=
λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
,
f
o
r
i
=
1
,
…
,
p
;
the multiplicity of   λ
1
(
A
(
x
,
ω
i
(
x
)
)
) is single, so f
i
(
x
) are C
∞ on B
(
x
-
); in addition,(1)
x
-
∈
B
(
x
-
)  and
f
i
(
x
-
)
=
F
(
x
-
)  for  i
=
1
,
…
,
p
;
(2)
for each
x
∈
B
(
x
-
)
,
F
(
x
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
)
;
(3)
△
1
is the unit simplex in  R
p
given by
(14)
△
1
:
=
{
(
α
1
,
α
2
,
…
,
α
p
)
:
∑
i
=
1
p
‍
α
i
=
1
,
α
i
≥
0
,
i
=
1
,
…
,
p
}
;
(4)
on the basis of the property about the subdifferential of the maximum functions, for each
x
∈
B
(
x
-
)
,
g
∈
∂
F
(
x
)
if and only if
(15)
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
)
,
where  α
i
=
0  if  f
i
(
x
)
<
F
(
x
)
and  α
:
=
(
α
1
,
…
,
α
p
)
∈
△
1.We have the following result.Theorem 9.
Suppose the setΩ
(
x
) is finite. Then the Clarke subdifferential of F at x is the set as follows:(16)
∂
F
(
x
)
=
{
×
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
α
∈
Δ
|
I
(
x
)
|
G
∣
G
=
∑
i
∈
I
(
x
)
α
i
∇
f
(
x
,
ω
i
(
x
)
)
=
∑
i
∈
I
(
x
)
α
i
(
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
A
′
x
(
x
,
ω
i
(
x
)
)
mmmmmmmmmn
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
)
*
mmmmmmmmmmn
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
α
∈
Δ
|
I
(
x
)
|
}
,
where
(17)
I
(
x
)
=
{
i
∈
{
1
,
…
,
p
}
∣
F
(
x
)
=
f
(
x
,
ω
i
(
x
)
)
}
is the set of active indices at x and
(18)
Δ
s
=
{
α
∈
R
s
∣
α
i
≥
0
,
∑
i
=
1
s
‍
α
i
=
1
}
.Proof.
BecauseF
(
x
) is the finite maximum functions, we can directly make use of the Clarke subdifferential of it and derivative of the eigenvalue function with multiplicity one to get
(19)
∂
F
(
x
)
=
∑
i
∈
I
(
x
)
α
i
∇
x
(
λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
)
=
∑
i
∈
I
(
x
)
α
i
(
A
′
)
*
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
=
∑
i
∈
I
(
x
)
α
i
(
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
A
x
′
(
x
,
ω
i
(
x
)
)
mmmmmmim
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
i
′
(
x
)
)
*
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
and the proof is done.Theorem 10.
Suppose Assumptions5 and 7 hold. Then one has the following results at x
-.(1)
The Clarke subdifferential ofF
(
x
-
) has the following expression:
(20)
∂
F
(
x
-
)
=
{
g
∣
g
=
∑
i
=
1
p
‍
α
i
(
A
x
′
(
x
-
,
ω
-
i
)
)
*
(
q
1
i
(
x
-
)
(
q
1
i
(
x
-
)
)
T
)
,
α
∈
Δ
1
}
.
(2)
Let𝒱 denote the subspace generated by the subdifferential ∂
F
(
x
-
). Then
(21)
𝒱
=
lin
⁡
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
,
i
=
2
,
…
,
p
,
𝒰
=
{
d
∈
R
n
∣
〈
d
,
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
〉
=
0
,
i
=
2
,
…
,
p
}
,where lin
⁡
C stands for linear hull of a set C.Proof.
With Theorem9 and Assumption 5, we can get the conclusion (1).
Letα
1
=
1
,
α
i
=
0,  i
≠
1, and we have ∇
f
1
(
x
-
)
∈
∂
F
(
x
-
). Then it follows from the definition of space 𝒱 that
(22)
𝒱
=
lin
⁡
(
∂
F
(
x
-
)
-
∇
f
1
(
x
-
)
)
=
lin
⁡
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
,
and 𝒰
=
𝒱
⊥ means that the second formula holds. The proof is completed.Remark 11.
(i) Since the subspaces𝒰 and 𝒱 generate the whole space R
m, every vector can be decomposed along its 𝒱
𝒰-components at x
-. In particular, any x
∈
R
m can be expressed as follows:
(23)
R
n
∋
x
=
x
-
+
u
⊕
v
=
x
-
+
U
-
u
+
V
-
v
,
where V
-
=
[
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
,
i
=
2
,
…
,
p
] and U
-
=
V
-
⊥.
(ii) For anys
-
∈
∂
F
(
x
-
), we have
(24)
s
-
=
s
-
𝒰
⊕
s
-
𝒱
=
U
-
T
s
-
+
V
-
T
s
-
.
From the above Theorem 10, the 𝒰-component of a subgradient s
∈
∂
F
(
x
-
) is the same as that of any other subgradient at x
-; that is, s
-
𝒰
=
U
-
T
s
-.


### 3.2. Smooth Trajectory and Second-Order Properties

Given thatg
-
=
g
-
𝒰
⊕
g
-
𝒱
∈
∂
F
(
x
-
), the Lagrangian-like function of F can be formulated in
(25)
L
(
u
;
g
-
𝒱
)
=
inf
⁡
v
∈
𝒱
{
F
(
x
-
+
u
⊕
v
)
-
〈
g
-
𝒱
,
v
〉
𝒱
}
.Theorem 12.
Suppose Assumption7 holds. Then, for all u small enough, there exists the following.(i)
The solution of the nonlinear system with variables(
u
,
v
)
∈
𝒰
×
𝒱
(26)
f
i
(
x
-
+
u
⊕
v
)
-
f
1
(
x
-
+
u
⊕
v
)
=
0
,
1
≠
i
,
is unique andv
=
v
(
u
), where v
(
u
)
:
𝒰
→
𝒱 is a C
2 function.
(ii)
For theC
2 solution function v
(
u
) in (i) one has
(27)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
,
whereV
(
u
)
=
[
{
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
}
,
1
≠
i
].
The trajectory𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
) is C
2 and
(28)
J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
)
.
In particular,𝒳
(
0
)
=
x
-, J
v
(
0
)
=
0, and J
𝒳
(
0
)
=
U
-.
(iii)
F
(
𝒳
(
u
)
)
=
f
i
(
𝒳
(
u
)
)
=
f
(
𝒳
(
u
)
,
ω
i
(
𝒳
(
u
)
)
)
,
ω
i
∈
Ω
(
x
-
).Proof.
(i) Differentiating the left hand side of (26) with respect to v gives
(29)
[
∇
f
i
(
x
-
+
u
⊕
v
)
-
∇
f
1
(
x
-
+
u
⊕
v
)
]
T
V
-
,
1
≠
i
∈
{
2
,
…
,
p
}
.
This Jacobian at (
u
,
v
)
=
(
0,0
) is V
-
T
V
-, which is nonsingular because of Assumption 7. There is also a Jacobian with respect to u, so by the implicit function theorem, there is a C
1 function v
(
u
) defined on a neighborhood of u
=
0 such that v
(
0
)
=
0.
(ii) From (i), we have thatv
(
u
) is C
1. Thus, the Jacobian J
v
(
u
) and J
𝒳
(
u
) exist and are continuous. Differentiating the system f
i
(
𝒳
(
u
)
)
-
f
1
(
𝒳
(
u
)
) with respect to u, we obtain that
(30)
[
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
]
T
J
𝒳
(
u
)
=
0
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
ω
i
(
𝒳
(
u
)
)
∈
Ω
(
x
-
)
,
or, in matrix form, V
(
u
)
J
𝒳
(
u
)
=
0. Using the expression J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
), we have that
(31)
V
(
u
)
T
(
U
-
+
V
-
J
v
(
u
)
)
=
0
.
By virtue of the continuity of V
(
u
), V
(
u
)
T
V
- is nonsingular. Hence,
(32)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
.
Furthermore, V
(
u
) is C
1 because f
i
(
x
)
,
i
∈
{
1
,
…
,
p
}, is C
2; then J
v
(
u
) is C
1. Thus, 𝒳
(
u
) and v
(
u
) are C
2. From the definition of the 𝒰
𝒱 spaces, we have 𝒱
⊥
𝒰. Hence, V
-
T
U
-
=
0. So J
v
(
0
)
=
0 and J
𝒳
(
0
)
=
U
-.
(iii) The conclusion can be directly obtained in terms of (i) and the definition of𝒳
(
u
).So far we have developed a primal track𝒳
(
u
). Now we take our attention to an associated dual object, which is also a smooth function of u
∈
𝒰; we study a multiplier vector function α
(
u
), which depends on structure function gradients, 𝒳
(
u
), and an arbitrary subgradient at x
-.Lemma 13.
Given thatg
-
∈
∂
F
(
x
-
), the system with {
α
i
(
u
)
}
,
i
∈
{
1
,
…
,
p
},
(33)
V
-
T
[
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
-
g
-
]
=
0
,
∑
i
=
1
p
‍
α
i
(
u
)
=
1
,
has a unique solution α
=
α
(
u
), which is given by
(34)
{
α
i
(
u
)
}
i
≠
1
=
(
V
-
T
V
(
u
)
)
-
1
V
-
(
g
-
-
∇
f
1
(
𝒳
(
u
)
)
)
,
α
1
(
u
)
=
1
-
∑
i
≠
1
‍
α
i
(
u
)
,
in particular, for all i
∈
{
1
,
…
,
p
}
,
α
i
(
0
)
=
α
-
i.Theorem 14.
Given thatg
-
∈
∂
F
(
x
-
), at the trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
), one has
(35)
L
(
u
;
g
-
𝒱
)
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
,
i
∈
{
1
,
…
,
p
}
.Proof.
According to the definition ofL in (25) and the item (iii) from Theorem 12, we get
(36)
L
(
u
;
g
-
𝒱
)
=
F
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.Theorem 15.
Given thatg
-
∈
∂
F
(
x
-
) and supposing Assumption 7 holds; then for u small enough, the following assertions are true.(i)
L is a C
2 function of u and satisfies the Lagrangian-like result L
(
u
;
0
)
=
f
i
(
𝒳
(
u
)
), for i
=
1
,
…
,
p.
(ii)
The gradient ofL is given by ∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
), and, in particular, when u
=
0, one has
(37)
∇
L
(
0
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
)
=
U
-
T
g
-
.
(iii)
The Hessian ofL is given by
(38)
∇
2
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
(
𝒳
(
u
)
)
)
J
(
𝒳
(
u
)
)
.
In particular, whenu
=
0, one has
(39)
∇
2
L
(
0
;
g
-
𝒱
)
=
U
-
T
∑
i
=
1
p
‍
α
-
i
∇
2
f
i
(
x
-
)
U
-
.Proof.
(i) This conclusion follows fromC
2 of f
i.
(ii) Using the chain rule, the differential of the Lagrangian-like with respect tou can be written as follows:
(40)
∇
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∇
f
i
(
𝒳
(
u
)
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Multiplying each equation by the appropriate α
i
(
u
), summing the results, and using the fact that ∑
i
‍
α
i
(
u
)
=
1 yield
(41)
∇
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Using the transpose of the expression of J
(
𝒳
(
u
)
), we get
(42)
∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
+
J
v
(
u
)
T
V
-
T
(
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
-
g
-
)
,
which together with (6.11) in [28] yields the desired result.
Ifu
=
0, then  v
(
0
)
=
0, and 𝒳
(
0
)
=
x
-. By Remark 11(ii), we have
(43)
∇
L
𝒰
(
0
;
g
-
𝒱
)
=
U
-
T
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
=
U
-
T
g
-
.
(iii) Differentiating the following equation with respect tou;
(44)
∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
)
,
we obtain
(45)
∇
2
L
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
U
-
T
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
,
where M
(
u
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
), ω
i
(
𝒳
(
u
)
)
). It follows from the proof of Theorem 6.3 in [28] that
(46)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
=
-
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
.
Then
(47)
∇
2
L
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
-
U
-
T
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
J
v
(
u
)
T
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
[
U
-
T
+
J
v
(
u
)
T
V
-
T
]
M
(
u
)
J
(
𝒳
(
u
)
)
=
J
𝒳
(
u
)
T
M
(
u
)
J
(
𝒳
(
u
)
)
,
when u
=
0,
(48)
∇
2
L
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
)
U
-
=
U
-
T
∑
i
=
1
p
‍
α
-
i
(
∇
2
f
i
(
x
-
)
)
U
-
.
We finish the proof.Theorem 16.
Suppose Assumption7 holds and g
-
∈
∂
F
(
x
-
). Then for u small enough, there holds the second-order expansion of f along with the trajectory 𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
),
(49)
F
(
𝒳
(
u
)
)
=
F
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
L
2
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Proof .
From the definition ofL, we have
(50)
L
(
u
;
g
-
𝒱
)
=
F
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.
Since L
∈
C
2, we get
(51)
L
(
u
;
g
-
𝒱
)
=
L
(
0
;
g
-
𝒱
)
+
〈
∇
L
(
0
;
g
-
𝒱
)
,
u
〉
𝒰
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.
Therefore,
(52)
F
(
𝒳
(
u
)
)
=
F
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.


## 3.1.𝒰
𝒱
-Theory of the Single Eigenvalue Function

In this section we will analyse the case where the multiplicity ofλ
1
(
A
(
x
,
ω
)
) is one at all active frequencies ω. This is motivated by practical considerations because nonsmoothness (b) never occurred in our tests. The necessary changes required for the general case will be discussed in next section.Lemma 4.
For a closed-loop stabilizing controllerx, the set of active frequencies Ω
(
x
)
:
=
{
ω
∈
[
0
,
∞
]
:
f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
)
} is either finite or Ω
(
x
)
=
[
0
,
∞
]; that is, f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
) for all ω.A system whereΩ
(
x
)
=
[
0
,
∞
] is called all-pass. This is rarely encountered in practice. For the technical formulas we will concentrate on those  x’s, where the set of active frequencies or peaks Ω
(
x
)
=
{
ω
∈
[
0
,
∞
]
:
f
(
x
)
=
λ
1
(
A
(
x
,
ω
)
)
} is finite.From what follows we will analyse the case where the multiplicity off
(
x
,
ω
)
:
=
λ
1
(
A
(
x
,
ω
)
) is one at all active frequencies ω. This is motivated by practical considerations because nonsmoothness about λ
1 never happened in our tests. The necessary changes required for the general case will be discussed in Section 4.In [27], three approaches to semi-infinite programming are discussed: exchange of constraints, discretization, and local reduction. We will use a local reduction method here. The main ideas are recalled below.Letx
- be a local solution of (7). Indexing the active frequencies Ω
(
x
)
:
=
{
ω
-
1
,
…
,
ω
-
p
} at x
-, we suppose that the following conditions are satisfied.Assumption 5.
Consider
(i)f
ω
′
(
x
-
,
ω
-
i
)
=
0,  i
=
1
,
…
,
p,
(ii)f
ω
ω
′′
(
x
-
,
ω
-
i
)
<
0,  i
=
1
,
…
,
p,
(iii)f
(
x
-
,
ω
)
<
f
(
x
-
),  for every ω
∉
Ω
(
x
-
)
=
{
ω
-
1
,
…
,
ω
-
p
}.These assumptions define the setting denoted as the standard case in semi-infinite programming [27]. The three conditions express the fact that the frequencies ω
-
i
∈
Ω
(
x
-
) are the strict global maximizers of f
(
x
-
,
·
). Notice that condition (iii) is the finiteness hypothesis already mentioned, justified by Lemma 4.Lemma 6.
Under conditions (i)–(iii), the neighborhoodU of x
- may be chosen such that max
⁡
ω
∈
[
0
,
∞
]
⁡
f
(
x
,
ω
)
=
max
⁡
i
=
1
,
…
,
p
⁡
f
(
x
,
ω
i
(
x
)
) for every x
∈
U. In particular, Ω
(
x
)
⊂
{
ω
1
(
x
)
,
…
,
ω
p
(
x
)
} for every x
∈
U.So we have that program (6) is locally equivalent to the standard following nonlinear program:
(12)
min
⁡
x
∈
R
n
sup
⁡
i
=
1
,
…
,
p
f
(
x
,
ω
i
(
x
)
)
,
where f
(
x
,
ω
i
(
x
)
)
=
λ
1
(
A
(
x
,
ω
i
(
x
)
)
); then we may solve (12) via the so-called 𝒰
𝒱-decomposition method.Assumption 7.
f
x
′
(
x
-
,
ω
-
1
)
,
…
,
f
x
′
(
x
-
,
ω
-
p
) are linearly independent.Under the hypothesis of Assumption7, local convergence of this approach will be assured because this guarantees that (12) satisfies the linear independence constraint qualification hypothesis.We denoteF
(
x
)
:
=
sup
⁡
i
=
1
,
…
,
p
λ
1
(
A
(
x
,
ω
i
(
x
)
)
), and q
1
i
(
x
),  i
=
1
,
…
,
p, stands for the eigenvector associated with the largest eigenvalue of A
(
x
,
ω
i
(
x
)
).Next a special kind of structure ofF
(
x
), called primal-dual structure (PDG), will be seen.Proposition 8.
There exists a ball aboutx
-, denoted by B
(
x
-
), p functions
(13)
f
i
(
x
)
:
=
f
(
x
,
ω
i
(
x
)
)
=
λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
,
f
o
r
i
=
1
,
…
,
p
;
the multiplicity of   λ
1
(
A
(
x
,
ω
i
(
x
)
)
) is single, so f
i
(
x
) are C
∞ on B
(
x
-
); in addition,(1)
x
-
∈
B
(
x
-
)  and
f
i
(
x
-
)
=
F
(
x
-
)  for  i
=
1
,
…
,
p
;
(2)
for each
x
∈
B
(
x
-
)
,
F
(
x
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
)
;
(3)
△
1
is the unit simplex in  R
p
given by
(14)
△
1
:
=
{
(
α
1
,
α
2
,
…
,
α
p
)
:
∑
i
=
1
p
‍
α
i
=
1
,
α
i
≥
0
,
i
=
1
,
…
,
p
}
;
(4)
on the basis of the property about the subdifferential of the maximum functions, for each
x
∈
B
(
x
-
)
,
g
∈
∂
F
(
x
)
if and only if
(15)
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
)
,
where  α
i
=
0  if  f
i
(
x
)
<
F
(
x
)
and  α
:
=
(
α
1
,
…
,
α
p
)
∈
△
1.We have the following result.Theorem 9.
Suppose the setΩ
(
x
) is finite. Then the Clarke subdifferential of F at x is the set as follows:(16)
∂
F
(
x
)
=
{
×
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
α
∈
Δ
|
I
(
x
)
|
G
∣
G
=
∑
i
∈
I
(
x
)
α
i
∇
f
(
x
,
ω
i
(
x
)
)
=
∑
i
∈
I
(
x
)
α
i
(
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
A
′
x
(
x
,
ω
i
(
x
)
)
mmmmmmmmmn
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
)
*
mmmmmmmmmmn
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
α
∈
Δ
|
I
(
x
)
|
}
,
where
(17)
I
(
x
)
=
{
i
∈
{
1
,
…
,
p
}
∣
F
(
x
)
=
f
(
x
,
ω
i
(
x
)
)
}
is the set of active indices at x and
(18)
Δ
s
=
{
α
∈
R
s
∣
α
i
≥
0
,
∑
i
=
1
s
‍
α
i
=
1
}
.Proof.
BecauseF
(
x
) is the finite maximum functions, we can directly make use of the Clarke subdifferential of it and derivative of the eigenvalue function with multiplicity one to get
(19)
∂
F
(
x
)
=
∑
i
∈
I
(
x
)
α
i
∇
x
(
λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
)
=
∑
i
∈
I
(
x
)
α
i
(
A
′
)
*
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
=
∑
i
∈
I
(
x
)
α
i
(
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
′
i
(
x
)
A
x
′
(
x
,
ω
i
(
x
)
)
mmmmmmim
+
A
′
ω
(
x
,
ω
i
(
x
)
)
ω
i
′
(
x
)
)
*
(
q
1
i
(
x
)
(
q
1
i
(
x
)
)
T
)
,
and the proof is done.Theorem 10.
Suppose Assumptions5 and 7 hold. Then one has the following results at x
-.(1)
The Clarke subdifferential ofF
(
x
-
) has the following expression:
(20)
∂
F
(
x
-
)
=
{
g
∣
g
=
∑
i
=
1
p
‍
α
i
(
A
x
′
(
x
-
,
ω
-
i
)
)
*
(
q
1
i
(
x
-
)
(
q
1
i
(
x
-
)
)
T
)
,
α
∈
Δ
1
}
.
(2)
Let𝒱 denote the subspace generated by the subdifferential ∂
F
(
x
-
). Then
(21)
𝒱
=
lin
⁡
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
,
i
=
2
,
…
,
p
,
𝒰
=
{
d
∈
R
n
∣
〈
d
,
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
〉
=
0
,
i
=
2
,
…
,
p
}
,where lin
⁡
C stands for linear hull of a set C.Proof.
With Theorem9 and Assumption 5, we can get the conclusion (1).
Letα
1
=
1
,
α
i
=
0,  i
≠
1, and we have ∇
f
1
(
x
-
)
∈
∂
F
(
x
-
). Then it follows from the definition of space 𝒱 that
(22)
𝒱
=
lin
⁡
(
∂
F
(
x
-
)
-
∇
f
1
(
x
-
)
)
=
lin
⁡
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
,
and 𝒰
=
𝒱
⊥ means that the second formula holds. The proof is completed.Remark 11.
(i) Since the subspaces𝒰 and 𝒱 generate the whole space R
m, every vector can be decomposed along its 𝒱
𝒰-components at x
-. In particular, any x
∈
R
m can be expressed as follows:
(23)
R
n
∋
x
=
x
-
+
u
⊕
v
=
x
-
+
U
-
u
+
V
-
v
,
where V
-
=
[
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
,
i
=
2
,
…
,
p
] and U
-
=
V
-
⊥.
(ii) For anys
-
∈
∂
F
(
x
-
), we have
(24)
s
-
=
s
-
𝒰
⊕
s
-
𝒱
=
U
-
T
s
-
+
V
-
T
s
-
.
From the above Theorem 10, the 𝒰-component of a subgradient s
∈
∂
F
(
x
-
) is the same as that of any other subgradient at x
-; that is, s
-
𝒰
=
U
-
T
s
-.


## 3.2. Smooth Trajectory and Second-Order Properties

Given thatg
-
=
g
-
𝒰
⊕
g
-
𝒱
∈
∂
F
(
x
-
), the Lagrangian-like function of F can be formulated in
(25)
L
(
u
;
g
-
𝒱
)
=
inf
⁡
v
∈
𝒱
{
F
(
x
-
+
u
⊕
v
)
-
〈
g
-
𝒱
,
v
〉
𝒱
}
.Theorem 12.
Suppose Assumption7 holds. Then, for all u small enough, there exists the following.(i)
The solution of the nonlinear system with variables(
u
,
v
)
∈
𝒰
×
𝒱
(26)
f
i
(
x
-
+
u
⊕
v
)
-
f
1
(
x
-
+
u
⊕
v
)
=
0
,
1
≠
i
,
is unique andv
=
v
(
u
), where v
(
u
)
:
𝒰
→
𝒱 is a C
2 function.
(ii)
For theC
2 solution function v
(
u
) in (i) one has
(27)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
,
whereV
(
u
)
=
[
{
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
}
,
1
≠
i
].
The trajectory𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
) is C
2 and
(28)
J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
)
.
In particular,𝒳
(
0
)
=
x
-, J
v
(
0
)
=
0, and J
𝒳
(
0
)
=
U
-.
(iii)
F
(
𝒳
(
u
)
)
=
f
i
(
𝒳
(
u
)
)
=
f
(
𝒳
(
u
)
,
ω
i
(
𝒳
(
u
)
)
)
,
ω
i
∈
Ω
(
x
-
).Proof.
(i) Differentiating the left hand side of (26) with respect to v gives
(29)
[
∇
f
i
(
x
-
+
u
⊕
v
)
-
∇
f
1
(
x
-
+
u
⊕
v
)
]
T
V
-
,
1
≠
i
∈
{
2
,
…
,
p
}
.
This Jacobian at (
u
,
v
)
=
(
0,0
) is V
-
T
V
-, which is nonsingular because of Assumption 7. There is also a Jacobian with respect to u, so by the implicit function theorem, there is a C
1 function v
(
u
) defined on a neighborhood of u
=
0 such that v
(
0
)
=
0.
(ii) From (i), we have thatv
(
u
) is C
1. Thus, the Jacobian J
v
(
u
) and J
𝒳
(
u
) exist and are continuous. Differentiating the system f
i
(
𝒳
(
u
)
)
-
f
1
(
𝒳
(
u
)
) with respect to u, we obtain that
(30)
[
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
]
T
J
𝒳
(
u
)
=
0
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
ω
i
(
𝒳
(
u
)
)
∈
Ω
(
x
-
)
,
or, in matrix form, V
(
u
)
J
𝒳
(
u
)
=
0. Using the expression J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
), we have that
(31)
V
(
u
)
T
(
U
-
+
V
-
J
v
(
u
)
)
=
0
.
By virtue of the continuity of V
(
u
), V
(
u
)
T
V
- is nonsingular. Hence,
(32)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
.
Furthermore, V
(
u
) is C
1 because f
i
(
x
)
,
i
∈
{
1
,
…
,
p
}, is C
2; then J
v
(
u
) is C
1. Thus, 𝒳
(
u
) and v
(
u
) are C
2. From the definition of the 𝒰
𝒱 spaces, we have 𝒱
⊥
𝒰. Hence, V
-
T
U
-
=
0. So J
v
(
0
)
=
0 and J
𝒳
(
0
)
=
U
-.
(iii) The conclusion can be directly obtained in terms of (i) and the definition of𝒳
(
u
).So far we have developed a primal track𝒳
(
u
). Now we take our attention to an associated dual object, which is also a smooth function of u
∈
𝒰; we study a multiplier vector function α
(
u
), which depends on structure function gradients, 𝒳
(
u
), and an arbitrary subgradient at x
-.Lemma 13.
Given thatg
-
∈
∂
F
(
x
-
), the system with {
α
i
(
u
)
}
,
i
∈
{
1
,
…
,
p
},
(33)
V
-
T
[
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
-
g
-
]
=
0
,
∑
i
=
1
p
‍
α
i
(
u
)
=
1
,
has a unique solution α
=
α
(
u
), which is given by
(34)
{
α
i
(
u
)
}
i
≠
1
=
(
V
-
T
V
(
u
)
)
-
1
V
-
(
g
-
-
∇
f
1
(
𝒳
(
u
)
)
)
,
α
1
(
u
)
=
1
-
∑
i
≠
1
‍
α
i
(
u
)
,
in particular, for all i
∈
{
1
,
…
,
p
}
,
α
i
(
0
)
=
α
-
i.Theorem 14.
Given thatg
-
∈
∂
F
(
x
-
), at the trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
), one has
(35)
L
(
u
;
g
-
𝒱
)
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
,
i
∈
{
1
,
…
,
p
}
.Proof.
According to the definition ofL in (25) and the item (iii) from Theorem 12, we get
(36)
L
(
u
;
g
-
𝒱
)
=
F
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.Theorem 15.
Given thatg
-
∈
∂
F
(
x
-
) and supposing Assumption 7 holds; then for u small enough, the following assertions are true.(i)
L is a C
2 function of u and satisfies the Lagrangian-like result L
(
u
;
0
)
=
f
i
(
𝒳
(
u
)
), for i
=
1
,
…
,
p.
(ii)
The gradient ofL is given by ∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
), and, in particular, when u
=
0, one has
(37)
∇
L
(
0
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
)
=
U
-
T
g
-
.
(iii)
The Hessian ofL is given by
(38)
∇
2
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
(
𝒳
(
u
)
)
)
J
(
𝒳
(
u
)
)
.
In particular, whenu
=
0, one has
(39)
∇
2
L
(
0
;
g
-
𝒱
)
=
U
-
T
∑
i
=
1
p
‍
α
-
i
∇
2
f
i
(
x
-
)
U
-
.Proof.
(i) This conclusion follows fromC
2 of f
i.
(ii) Using the chain rule, the differential of the Lagrangian-like with respect tou can be written as follows:
(40)
∇
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∇
f
i
(
𝒳
(
u
)
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Multiplying each equation by the appropriate α
i
(
u
), summing the results, and using the fact that ∑
i
‍
α
i
(
u
)
=
1 yield
(41)
∇
L
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Using the transpose of the expression of J
(
𝒳
(
u
)
), we get
(42)
∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
+
J
v
(
u
)
T
V
-
T
(
∑
i
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
-
g
-
)
,
which together with (6.11) in [28] yields the desired result.
Ifu
=
0, then  v
(
0
)
=
0, and 𝒳
(
0
)
=
x
-. By Remark 11(ii), we have
(43)
∇
L
𝒰
(
0
;
g
-
𝒱
)
=
U
-
T
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
=
U
-
T
g
-
.
(iii) Differentiating the following equation with respect tou;
(44)
∇
L
(
u
;
g
-
𝒱
)
=
U
-
T
(
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
)
,
we obtain
(45)
∇
2
L
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
U
-
T
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
,
where M
(
u
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
), ω
i
(
𝒳
(
u
)
)
). It follows from the proof of Theorem 6.3 in [28] that
(46)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
=
-
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
.
Then
(47)
∇
2
L
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
-
U
-
T
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
J
v
(
u
)
T
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
[
U
-
T
+
J
v
(
u
)
T
V
-
T
]
M
(
u
)
J
(
𝒳
(
u
)
)
=
J
𝒳
(
u
)
T
M
(
u
)
J
(
𝒳
(
u
)
)
,
when u
=
0,
(48)
∇
2
L
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
)
U
-
=
U
-
T
∑
i
=
1
p
‍
α
-
i
(
∇
2
f
i
(
x
-
)
)
U
-
.
We finish the proof.Theorem 16.
Suppose Assumption7 holds and g
-
∈
∂
F
(
x
-
). Then for u small enough, there holds the second-order expansion of f along with the trajectory 𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
),
(49)
F
(
𝒳
(
u
)
)
=
F
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
L
2
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Proof .
From the definition ofL, we have
(50)
L
(
u
;
g
-
𝒱
)
=
F
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.
Since L
∈
C
2, we get
(51)
L
(
u
;
g
-
𝒱
)
=
L
(
0
;
g
-
𝒱
)
+
〈
∇
L
(
0
;
g
-
𝒱
)
,
u
〉
𝒰
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.
Therefore,
(52)
F
(
𝒳
(
u
)
)
=
F
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
L
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.


## 4.𝒰
𝒱-Decomposition for Multiple Eigenvalues

### 4.1.𝒰
𝒱-Theory of the Multiple Eigenvalue Function

The working hypothesis of the previous section was that leading eigenvaluesλ
1
(
A
(
x
,
ω
i
(
x
)
)
) had multiplicity 1 for all frequencies in the set {
ω
1
(
x
)
,
…
,
ω
p
(
x
)
} and for all x in a neighborhood of x
-. This hypothesis is motivated by our numerical experience, where we have never encountered multiple eigenvalues. This is clearly in contrast with experience in pure eigenvalue optimization problems. However, our approach is still functional if the hypothesis of single eigenvalues at active frequencies is abandoned. Based on the weaker assumption that the eigenvalue multiplicities r
-
i at the limit point x
- are known for all active frequencies ω
-
i
,
i
=
1
,
…
,
p, and on the information at the current iterate point, we have good technique to dependably guess r
-
i.This situation has been discussed by several authors (see, e.g., [27, 29–31]). Consider X
∈
S
n where λ
1
(
X
) has multiplicity r. We replace the maximum eigenvalue function λ
1 by the average of the first r eigenvalues
(53)
λ
^
r
(
X
)
=
1
r
∑
j
=
1
r
‍
λ
j
(
X
)
.
This function is smooth and convex in a neighborhood of the smooth manifold
(54)
ℳ
r
=
{
X
∈
S
n
:
λ
1
(
X
)
=
⋯
=
λ
r
(
X
)
>
λ
r
+
1
(
X
)
}
of the matrices X
∈
S
n with the largest eigenvalue multiplicity r, and λ
1
=
λ
^
r on ℳ
r. Then we may replace the nonsmooth information contained in λ
1 by the smooth information contained in the function λ
^
r by adding the constraint A
(
x
,
ω
i
(
x
)
)
∈
ℳ
r
-
i. The manifold has codimension d
:
=
(
(
r
(
r
+
1
)
)
/
2
)
-
1 in S
n and in a neighborhood of X
- may be described by d equations h
1
(
X
)
=
0
,
…
,
h
d
(
X
)
=
0, which has been presented independently in [16, 32]. The extension to the semi-infinite eigenvalue optimization is clear under the finiteness assumption (iii). We may then approach minimization of the H
∞-norm along the same lines and obtain the finite program
(55)
min
⁡
x
max
⁡
i
=
1
,
…
,
p
mmm
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
s
.
t
.
max
⁡
i
=
1
,
…
,
p
mnmm
A
(
x
,
ω
i
(
x
)
)
∈
ℳ
r
-
i
,
where r
-
i stands for the multiplicity of the largest eigenvalue  λ
1
(
A
(
x
-
,
ω
-
i
)
); we denote Q
r
-
i
Q
r
-
i
T by an orthonormal basis associated with the eigenvector of  λ
1
(
A
(
x
-
,
ω
-
i
)
). According to the foregoing analysis, we can transform the above constrained optimization problem into the following form:
(56)
min
⁡
x
max
⁡
i
=
1
,
…
,
p
mm
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
s
.
t
.
max
⁡
i
=
1
,
…
,
p
mnm
h
1
(
A
(
x
,
ω
1
(
x
)
)
)
=
0
⋮
h
d
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
=
0
h
d
-
1
+
1
(
A
(
x
,
ω
2
(
x
)
)
)
=
0
⋮
h
d
-
1
+
d
-
2
(
A
(
x
,
ω
2
(
x
)
)
)
=
0
⋮
h
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
A
(
x
,
ω
p
(
x
)
)
)
=
0
⋮
h
d
-
1
+
⋯
+
d
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
=
0
.
For convenience, we denote
(57)
f
1
(
x
)
=
λ
^
r
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
f
p
(
x
)
=
λ
^
r
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
,
ϕ
1
(
x
)
=
h
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
ϕ
d
-
1
(
x
)
=
h
d
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
ϕ
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
x
)
=
h
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
A
(
x
,
ω
p
(
x
)
)
)
,
⋮
ϕ
d
-
1
+
⋯
+
d
-
p
(
x
)
=
h
d
-
1
+
⋯
+
d
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
.SoF
^
(
x
)
=
max
⁡
i
=
1
,
…
,
p
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
) because λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
=
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
); we still label f
(
x
,
ω
i
(
x
)
) as λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
). In view of the property about the indicated functions, we can transform (56) into an unconstrained optimization. Thus, for the problem (56), we just need to deal with the following form equivalently:
(58)
min
⁡
x
F
^
(
x
)
:
=

max
⁡
i
=
1
,
…
,
p
f
i
(
x
)
+
I
{
0
}
(
ϕ
1
(
x
)
)
+
⋯
+
I
{
0
}
(
ϕ
N
p
(
x
)
)
,
where N
p
:
=
d
-
1
+
⋯
+
d
-
p, and I
C
(
y
) means the indicated function at y for the set C.Similarly as in Proposition8, we can obtain that the problem (58) possesses PDG.Proposition 17.
F
^
(
x
) in (58) is a primal-dual gradient structured (PDG) function.Proof.
First,f
i
(
x
)
=
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
=
(
1
/
r
-
i
)
∑
j
=
1
r
-
i
‍
λ
j
(
A
(
x
,
ω
i
(
x
)
)
); in [32] Shapiro and Fan had given the fact that the function ∑
j
=
1
r
-
i
‍
λ
j
(
A
(
x
,
ω
i
(
x
)
)
)
,
h
l
(
A
(
x
,
ω
i
(
x
)
)
)
∈
C
∞, for i
=
1
,
…
,
p and l
=
1
,
…
,
N
p, so f
i
(
x
)
∈
C
∞ too. In this way, there exists a ball about x
-, B
(
x
-
) and a dual multiplier set (1)
x
-
∈
𝒫
:
=
{
x
∈
B
(
x
-
)
:
ϕ
l
(
x
)
=
0
for
l
=
1
,
…
,
N
p
} and f
i
(
x
-
)
=
F
^
(
x
-
) for i
=
1
,
…
,
p;
(2)
for eachx
∈
𝒫,  F
^
(
x
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
);
(3)
△ is a closed convex set such that
(a)
ifγ
:
=
(
α
1
,
…
,
α
p
,
β
1
,
…
,
β
N
p
)
∈
△, then we know that F
^
(
x
)
=
∑
i
=
1
p
‍
α
i
f
i
(
x
); that is, (
α
1
,
…
,
α
p
)
∈
△
1, which is defined in (14);
(b)
for eachi
=
1
,
…
,
p
,
1
i
∈
△, where 1
j is the jth unit vector inR
p
+
N
p;
(c)
for eachl
=
1,2
,
…
,
N
p, there exists γ
l
∈
△ such that β
l
l
≠
0 and β
i
l
=
0 for i
∈
{
1
,
…
,
N
p
}
∖
{
l
};
(4)
for eachx
∈
B
(
x
-
),  g
∈
∂
F
^
(
x
) if and only if
(59)
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
)
+
∑
j
=
1
N
p
‍
β
j
∇
ϕ
j
(
x
)
,
whereα
i
=
0 if f
i
(
x
)
<
F
^
(
x
) and α
:
=
(
α
1
,
…
,
α
p
)
∈
△
1. Moreover, γ satisfies dual feasibility: γ
=
(
α
1
,
…
,
α
p
,
β
1
,
…
,
β
N
p
)
∈
△.Assumption 18.
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
x
-
)
}
j
=
1
N
p are linearly independent.Theorem 19.
Suppose Assumption18 holds. Then one has the following results at x
-. (1)
The Clarke subdifferential ofF
^
(
x
-
) has the following expression:
(60)
∂
F
^
(
x
-
)
=
{
g
∣
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
j
∇
ϕ
j
(
x
-
)
,
α
∈
Δ
1
}
,
whereN
p
:
=
d
-
1
+
⋯
+
d
-
p.
(2)
Let𝒱 denote the subspace generated by the subdifferential ∂
F
(
x
-
). Then
(61)
𝒱
=
lin
⁡
(
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
x
)
}
j
=
1
N
p
)
𝒰
=
{
d
∈
R
n
∣
〈
d
,
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
〉
=
0
,
i
=
2
,
…
,
p
}
,
where∇
f
i
(
x
-
)
=
(
1
/
r
-
i
)
(
A
x
′
(
x
-
,
ω
-
i
)
)
*
(
Q
r
-
i
Q
r
-
i
T
),
(62)
∇
f
i
(
x
-
)
∈
∂
F
^
(
x
-
)
for
i
=
1
,
…
,
p
;
∇
ϕ
j
(
x
-
)
∈
𝒱
for
j
=
1
,
…
,
N
p
.


### 4.2. Smooth Trajectory and Second-Order Properties

We give the smooth trajectory information about the functionF
^
(
x
) in the following theorem; with respect to its proofs, it is similar to Theorem 12.Theorem 20.
Suppose Assumption18 holds. Then for all u small enough, there exists the following. (i)
The nonlinear system with variables(
u
,
v
)
∈
𝒰
×
𝒱
(63)
f
i
(
x
-
+
u
⊕
v
)
-
f
1
(
x
-
+
u
⊕
v
)
=
0
,
i
=
2
,
…
,
p
,
ϕ
j
(
x
-
+
u
⊕
v
)
=
0
,
j
=
1
,
…
,
N
p
,
has a unique solutionv
=
v
(
u
), where v
:
𝒰
→
𝒱 is a C
2-function.
(ii)
ForC
2 function v
(
u
), one has
(64)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
,
whereV
(
u
)
=
[
{
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
𝒳
(
u
)
)
}
j
=
1
N
p
].
The trajectory𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
) is C
2, and
(65)
J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
)
.
In particular,𝒳
(
0
)
=
x
-
,
J
v
(
0
)
=
0, and J
𝒳
(
0
)
=
U
-.
(iii)
v
(
u
)
=
O
(
∥
u
∥
2
), and the smooth trajectory 𝒳
(
u
) is tangent to 𝒰 at 𝒳
(
0
)
=
x
-.
(iv)
F
^
(
𝒳
(
u
)
)
=
f
i
(
𝒳
(
u
)
)
,
i
=
1
,
…
,
p, and ϕ
j
(
𝒳
(
u
)
)
=
0
,
j
=
1
,
…
,
N
p.Now we pay our attention to an associated dual object, that is, also a smooth function ofu
∈
𝒰.Theorem 21.
We suppose Assumption18 is holding, with trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
) and to a subgradient g
-
∈
∂
F
^
(
x
-
) at x
-, for all u small enough; the linear system with variables α
i
,
i
=
1
,
…
,
p
;
β
j
,
j
=
1
,
…
,
N
p,
(66)
V
-
T
[
∑
i
=
1
p
‍
α
i
∇
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
∇
ϕ
j
(
𝒳
(
u
)
)
]
=
V
-
T
g
-
,
∑
i
=
1
p
‍
α
i
=
1
,
has a unique solution γ
(
u
)
=
(
α
(
u
)
,
β
(
u
)
), given by
(67)
{
α
i
(
u
)
}
i
=
2
p
,
{
β
j
(
u
)
}
j
=
1
N
p
=
(
V
-
T
V
(
u
)
)
-
1
V
-
(
g
-
-
∇
f
0
(
𝒳
(
u
)
)
)
,
α
1
(
u
)
=
1
-
∑
i
=
2
p
‍
α
i
(
u
)
,
where V
(
u
) is defined in Theorem 20.Next we consider the following primal-dual function(68)
ℒ
(
u
;
z
)
:
=
F
^
(
𝒳
(
u
)
)
-
z
T
v
(
u
)
.Theorem 22.
Giveng
-
∈
∂
F
^
(
x
-
), at the trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
), one has
(69)
ℒ
(
u
;
g
-
𝒱
)
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
,
i
∈
{
1
,
…
,
p
}
.Theorem 23.
Giveng
-
∈
∂
F
^
(
x
-
) and supposing that Assumption 18 holds, then for u small enough, the following assertions are true.(i)
ℒ is a C
2 function of u and
(70)
ℒ
(
u
;
0
)
=
[
∑
i
=
1
p
‍
α
i
(
u
)
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
ϕ
j
(
𝒳
(
u
)
)
]
.
(ii)
The gradient ofℒ is given by ∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
g
(
u
;
g
-
𝒱
), where
(71)
g
(
u
;
g
-
𝒱
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
,
and, in particular, whenu
=
0, one has
(72)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
[
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
x
-
)
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
mim
+
∑
j
=
1
N
p
‍
β
-
j
∇
ϕ
j
(
x
-
)
]
=
U
-
T
g
-
=
g
-
𝒰
.
(iii)
The Hessian ofℒ is given by
(73)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
M
(
u
,
g
-
𝒱
)
J
(
𝒳
(
u
)
)
,
whereM
(
u
,
g
-
𝒱
) is the n
×
n matrix function defined by
(74)
M
(
u
,
g
-
𝒱
)
≔
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
2
ϕ
j
(
𝒳
(
u
)
)
.In particular, when u
=
0, one has
(75)
∇
2
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
;
g
-
𝒱
)
U
-
.Proof.
(i) Becausef
i
(
𝒳
(
u
)
) is C
2, it follows from C
2 of ℒ in the above theorem. At the same time, Assumption 18 holds; using (68) with z
=
0 gives
(76)
ℒ
(
u
;
0
)
=
f
i
(
𝒳
(
u
)
)
,
i
=
1
,
…
,
p
.
In addition,
(77)
ϕ
j
(
𝒳
(
u
)
)
=
0
,
j
=
1
,
…
,
N
p
.
Multiplying α
i and β
j, respectively, for the above equations and summing, we get the Lagrangian-like expression in item (i).
(ii) Using the chain rule, the differential of the Lagrangian-like functions (69) and (77) with respect to u can be written as follows:
(78)
∇
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
(
∇
f
i
(
𝒳
(
u
)
)
)
-
J
v
(
u
)
T
V
-
T
g
-
,
J
(
𝒳
(
u
)
)
T
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
=
0
.
Multiplying each equation by the appropriate α
i
(
u
) and β
j
(
u
), summing the results, and using the fact that ∑
i
‍
α
i
(
u
)
=
1 yield
(79)
∇
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
[
+
∑
j
=
1
N
p
‍
β
j
(
u
)
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
∑
i
=
1
p
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
=
J
(
𝒳
(
u
)
)
mm
T
∑
j
=
1
N
p
‍
+
∑
j
=
1
N
p
‍
β
j
(
u
)
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
]
-
J
v
(
u
)
T
V
-
T
g
-
=
J
(
𝒳
(
u
)
)
T
g
(
u
;
g
-
𝒱
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Using the transpose of the expression of J
(
𝒳
(
u
)
), we get
(80)
∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
g
(
u
;
g
-
𝒱
)
+
J
v
(
u
)
T
V
-
T
(
g
(
u
;
g
-
𝒱
)
-
g
-
)
,
which together with (6.11) in [28] yields the desired result.
Ifu
=
0,  then v
(
0
)
=
0, and 𝒳
(
0
)
=
x
-, J
𝒳
(
0
)
=
U
-, ∑
i
=
1
p
‍
α
i
(
0
)
=
1, and by Theorem 19
(81)
either
∇
f
i
(
x
-
)
∈
∂
F
^
(
x
-
)
so
U
-
T
∇
f
i
(
x
-
)
=
g
-
𝒰
,
or
∇
ϕ
j
(
x
-
)
∈
𝒱
so
U
-
T
∇
ϕ
j
(
x
-
)
=
0
;
so we attain
(82)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
[
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
-
j
∇
ϕ
j
(
x
-
)
]
=
U
-
T
g
-
.
(iii) Differentiating the following equation with respect tou,
(83)
∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
(
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
=
U
-
T
n
∑
i
=
1
p
‍
α
i
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
)
,
we obtain
(84)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
U
-
T
[
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
m
+
U
-
T
mm
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
J
β
j
(
u
)
]
,
where M
(
u
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
2
ϕ
j
(
𝒳
(
u
)
). It follows from the proof of Theorem 6.3 in [28] that
(85)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
J
β
j
(
u
)
=
-
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
.
Then
(86)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
-
U
-
T
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
J
v
(
u
)
T
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
[
U
-
T
+
J
v
(
u
)
T
V
-
T
]
M
(
u
)
J
(
𝒳
(
u
)
)
=
J
(
𝒳
(
u
)
)
T
M
(
u
)
J
(
𝒳
(
u
)
)
,
when u
=
0,
(87)
∇
2
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
)
U
-
,
where M
(
0
;
g
-
𝒱
)
=
∑
i
=
1
p
‍
α
-
i
∇
2
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
-
j
∇
2
ϕ
j
(
x
-
).We call the corresponding Hessian matrix ofℒ at u
=
0 a basic 𝒰-Hessian for F
^ at x
- and denote it by H
-
:
=
∇
2
ℒ
(
0
;
0
). Using second-order 𝒰-derivatives we can specify second-order expansions for F
^ and give related necessary conditions for optimization problem.Theorem 24.
Suppose Assumption18 holds and g
-
∈
∂
F
^
(
x
-
). Then for u small enough, there holds the second-order expansion of f along the trajectory 𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
),
(88)
F
^
(
𝒳
(
u
)
)
=
F
^
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Proof.
From the definition ofℒ, we have
(89)
ℒ
(
u
;
g
-
𝒱
)
=
F
^
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.
Since ℒ
∈
C
2, we get
(90)
ℒ
(
u
;
g
-
𝒱
)
=
ℒ
(
0
;
g
-
𝒱
)
+
〈
∇
ℒ
(
0
;
g
-
𝒱
)
,
u
〉
𝒰
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
^
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.
Therefore,
(91)
F
^
(
𝒳
(
u
)
)
=
F
^
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
^
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Corollary 25.
Suppose Assumption18 holds and x
- is a local minimizer of (56). Then 0
∈
∂
F
^
(
x
-
) and the associated basic 𝒰-Hessian H
- is positive semidefinite.


## 4.1.𝒰
𝒱-Theory of the Multiple Eigenvalue Function

The working hypothesis of the previous section was that leading eigenvaluesλ
1
(
A
(
x
,
ω
i
(
x
)
)
) had multiplicity 1 for all frequencies in the set {
ω
1
(
x
)
,
…
,
ω
p
(
x
)
} and for all x in a neighborhood of x
-. This hypothesis is motivated by our numerical experience, where we have never encountered multiple eigenvalues. This is clearly in contrast with experience in pure eigenvalue optimization problems. However, our approach is still functional if the hypothesis of single eigenvalues at active frequencies is abandoned. Based on the weaker assumption that the eigenvalue multiplicities r
-
i at the limit point x
- are known for all active frequencies ω
-
i
,
i
=
1
,
…
,
p, and on the information at the current iterate point, we have good technique to dependably guess r
-
i.This situation has been discussed by several authors (see, e.g., [27, 29–31]). Consider X
∈
S
n where λ
1
(
X
) has multiplicity r. We replace the maximum eigenvalue function λ
1 by the average of the first r eigenvalues
(53)
λ
^
r
(
X
)
=
1
r
∑
j
=
1
r
‍
λ
j
(
X
)
.
This function is smooth and convex in a neighborhood of the smooth manifold
(54)
ℳ
r
=
{
X
∈
S
n
:
λ
1
(
X
)
=
⋯
=
λ
r
(
X
)
>
λ
r
+
1
(
X
)
}
of the matrices X
∈
S
n with the largest eigenvalue multiplicity r, and λ
1
=
λ
^
r on ℳ
r. Then we may replace the nonsmooth information contained in λ
1 by the smooth information contained in the function λ
^
r by adding the constraint A
(
x
,
ω
i
(
x
)
)
∈
ℳ
r
-
i. The manifold has codimension d
:
=
(
(
r
(
r
+
1
)
)
/
2
)
-
1 in S
n and in a neighborhood of X
- may be described by d equations h
1
(
X
)
=
0
,
…
,
h
d
(
X
)
=
0, which has been presented independently in [16, 32]. The extension to the semi-infinite eigenvalue optimization is clear under the finiteness assumption (iii). We may then approach minimization of the H
∞-norm along the same lines and obtain the finite program
(55)
min
⁡
x
max
⁡
i
=
1
,
…
,
p
mmm
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
s
.
t
.
max
⁡
i
=
1
,
…
,
p
mnmm
A
(
x
,
ω
i
(
x
)
)
∈
ℳ
r
-
i
,
where r
-
i stands for the multiplicity of the largest eigenvalue  λ
1
(
A
(
x
-
,
ω
-
i
)
); we denote Q
r
-
i
Q
r
-
i
T by an orthonormal basis associated with the eigenvector of  λ
1
(
A
(
x
-
,
ω
-
i
)
). According to the foregoing analysis, we can transform the above constrained optimization problem into the following form:
(56)
min
⁡
x
max
⁡
i
=
1
,
…
,
p
mm
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
s
.
t
.
max
⁡
i
=
1
,
…
,
p
mnm
h
1
(
A
(
x
,
ω
1
(
x
)
)
)
=
0
⋮
h
d
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
=
0
h
d
-
1
+
1
(
A
(
x
,
ω
2
(
x
)
)
)
=
0
⋮
h
d
-
1
+
d
-
2
(
A
(
x
,
ω
2
(
x
)
)
)
=
0
⋮
h
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
A
(
x
,
ω
p
(
x
)
)
)
=
0
⋮
h
d
-
1
+
⋯
+
d
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
=
0
.
For convenience, we denote
(57)
f
1
(
x
)
=
λ
^
r
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
f
p
(
x
)
=
λ
^
r
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
,
ϕ
1
(
x
)
=
h
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
ϕ
d
-
1
(
x
)
=
h
d
-
1
(
A
(
x
,
ω
1
(
x
)
)
)
,
⋮
ϕ
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
x
)
=
h
d
-
1
+
⋯
+
d
-
p
-
1
+
1
(
A
(
x
,
ω
p
(
x
)
)
)
,
⋮
ϕ
d
-
1
+
⋯
+
d
-
p
(
x
)
=
h
d
-
1
+
⋯
+
d
-
p
(
A
(
x
,
ω
p
(
x
)
)
)
.SoF
^
(
x
)
=
max
⁡
i
=
1
,
…
,
p
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
) because λ
1
(
A
(
x
,
ω
i
(
x
)
)
)
=
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
); we still label f
(
x
,
ω
i
(
x
)
) as λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
). In view of the property about the indicated functions, we can transform (56) into an unconstrained optimization. Thus, for the problem (56), we just need to deal with the following form equivalently:
(58)
min
⁡
x
F
^
(
x
)
:
=

max
⁡
i
=
1
,
…
,
p
f
i
(
x
)
+
I
{
0
}
(
ϕ
1
(
x
)
)
+
⋯
+
I
{
0
}
(
ϕ
N
p
(
x
)
)
,
where N
p
:
=
d
-
1
+
⋯
+
d
-
p, and I
C
(
y
) means the indicated function at y for the set C.Similarly as in Proposition8, we can obtain that the problem (58) possesses PDG.Proposition 17.
F
^
(
x
) in (58) is a primal-dual gradient structured (PDG) function.Proof.
First,f
i
(
x
)
=
λ
^
r
-
i
(
A
(
x
,
ω
i
(
x
)
)
)
=
(
1
/
r
-
i
)
∑
j
=
1
r
-
i
‍
λ
j
(
A
(
x
,
ω
i
(
x
)
)
); in [32] Shapiro and Fan had given the fact that the function ∑
j
=
1
r
-
i
‍
λ
j
(
A
(
x
,
ω
i
(
x
)
)
)
,
h
l
(
A
(
x
,
ω
i
(
x
)
)
)
∈
C
∞, for i
=
1
,
…
,
p and l
=
1
,
…
,
N
p, so f
i
(
x
)
∈
C
∞ too. In this way, there exists a ball about x
-, B
(
x
-
) and a dual multiplier set (1)
x
-
∈
𝒫
:
=
{
x
∈
B
(
x
-
)
:
ϕ
l
(
x
)
=
0
for
l
=
1
,
…
,
N
p
} and f
i
(
x
-
)
=
F
^
(
x
-
) for i
=
1
,
…
,
p;
(2)
for eachx
∈
𝒫,  F
^
(
x
)
=
max
⁡
i
=
1
,
…
,
p
f
i
(
x
);
(3)
△ is a closed convex set such that
(a)
ifγ
:
=
(
α
1
,
…
,
α
p
,
β
1
,
…
,
β
N
p
)
∈
△, then we know that F
^
(
x
)
=
∑
i
=
1
p
‍
α
i
f
i
(
x
); that is, (
α
1
,
…
,
α
p
)
∈
△
1, which is defined in (14);
(b)
for eachi
=
1
,
…
,
p
,
1
i
∈
△, where 1
j is the jth unit vector inR
p
+
N
p;
(c)
for eachl
=
1,2
,
…
,
N
p, there exists γ
l
∈
△ such that β
l
l
≠
0 and β
i
l
=
0 for i
∈
{
1
,
…
,
N
p
}
∖
{
l
};
(4)
for eachx
∈
B
(
x
-
),  g
∈
∂
F
^
(
x
) if and only if
(59)
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
)
+
∑
j
=
1
N
p
‍
β
j
∇
ϕ
j
(
x
)
,
whereα
i
=
0 if f
i
(
x
)
<
F
^
(
x
) and α
:
=
(
α
1
,
…
,
α
p
)
∈
△
1. Moreover, γ satisfies dual feasibility: γ
=
(
α
1
,
…
,
α
p
,
β
1
,
…
,
β
N
p
)
∈
△.Assumption 18.
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
x
-
)
}
j
=
1
N
p are linearly independent.Theorem 19.
Suppose Assumption18 holds. Then one has the following results at x
-. (1)
The Clarke subdifferential ofF
^
(
x
-
) has the following expression:
(60)
∂
F
^
(
x
-
)
=
{
g
∣
g
=
∑
i
=
1
p
‍
α
i
∇
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
j
∇
ϕ
j
(
x
-
)
,
α
∈
Δ
1
}
,
whereN
p
:
=
d
-
1
+
⋯
+
d
-
p.
(2)
Let𝒱 denote the subspace generated by the subdifferential ∂
F
(
x
-
). Then
(61)
𝒱
=
lin
⁡
(
{
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
x
)
}
j
=
1
N
p
)
𝒰
=
{
d
∈
R
n
∣
〈
d
,
∇
f
i
(
x
-
)
-
∇
f
1
(
x
-
)
〉
=
0
,
i
=
2
,
…
,
p
}
,
where∇
f
i
(
x
-
)
=
(
1
/
r
-
i
)
(
A
x
′
(
x
-
,
ω
-
i
)
)
*
(
Q
r
-
i
Q
r
-
i
T
),
(62)
∇
f
i
(
x
-
)
∈
∂
F
^
(
x
-
)
for
i
=
1
,
…
,
p
;
∇
ϕ
j
(
x
-
)
∈
𝒱
for
j
=
1
,
…
,
N
p
.


## 4.2. Smooth Trajectory and Second-Order Properties

We give the smooth trajectory information about the functionF
^
(
x
) in the following theorem; with respect to its proofs, it is similar to Theorem 12.Theorem 20.
Suppose Assumption18 holds. Then for all u small enough, there exists the following. (i)
The nonlinear system with variables(
u
,
v
)
∈
𝒰
×
𝒱
(63)
f
i
(
x
-
+
u
⊕
v
)
-
f
1
(
x
-
+
u
⊕
v
)
=
0
,
i
=
2
,
…
,
p
,
ϕ
j
(
x
-
+
u
⊕
v
)
=
0
,
j
=
1
,
…
,
N
p
,
has a unique solutionv
=
v
(
u
), where v
:
𝒰
→
𝒱 is a C
2-function.
(ii)
ForC
2 function v
(
u
), one has
(64)
J
v
(
u
)
=
-
(
V
(
u
)
T
V
-
)
-
1
V
(
u
)
T
U
-
,
whereV
(
u
)
=
[
{
∇
f
i
(
𝒳
(
u
)
)
-
∇
f
1
(
𝒳
(
u
)
)
}
i
=
2
p
⋃
‍
{
∇
ϕ
j
(
𝒳
(
u
)
)
}
j
=
1
N
p
].
The trajectory𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
) is C
2, and
(65)
J
𝒳
(
u
)
=
U
-
+
V
-
J
v
(
u
)
.
In particular,𝒳
(
0
)
=
x
-
,
J
v
(
0
)
=
0, and J
𝒳
(
0
)
=
U
-.
(iii)
v
(
u
)
=
O
(
∥
u
∥
2
), and the smooth trajectory 𝒳
(
u
) is tangent to 𝒰 at 𝒳
(
0
)
=
x
-.
(iv)
F
^
(
𝒳
(
u
)
)
=
f
i
(
𝒳
(
u
)
)
,
i
=
1
,
…
,
p, and ϕ
j
(
𝒳
(
u
)
)
=
0
,
j
=
1
,
…
,
N
p.Now we pay our attention to an associated dual object, that is, also a smooth function ofu
∈
𝒰.Theorem 21.
We suppose Assumption18 is holding, with trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
) and to a subgradient g
-
∈
∂
F
^
(
x
-
) at x
-, for all u small enough; the linear system with variables α
i
,
i
=
1
,
…
,
p
;
β
j
,
j
=
1
,
…
,
N
p,
(66)
V
-
T
[
∑
i
=
1
p
‍
α
i
∇
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
∇
ϕ
j
(
𝒳
(
u
)
)
]
=
V
-
T
g
-
,
∑
i
=
1
p
‍
α
i
=
1
,
has a unique solution γ
(
u
)
=
(
α
(
u
)
,
β
(
u
)
), given by
(67)
{
α
i
(
u
)
}
i
=
2
p
,
{
β
j
(
u
)
}
j
=
1
N
p
=
(
V
-
T
V
(
u
)
)
-
1
V
-
(
g
-
-
∇
f
0
(
𝒳
(
u
)
)
)
,
α
1
(
u
)
=
1
-
∑
i
=
2
p
‍
α
i
(
u
)
,
where V
(
u
) is defined in Theorem 20.Next we consider the following primal-dual function(68)
ℒ
(
u
;
z
)
:
=
F
^
(
𝒳
(
u
)
)
-
z
T
v
(
u
)
.Theorem 22.
Giveng
-
∈
∂
F
^
(
x
-
), at the trajectory 𝒳
(
u
)
=
x
-
+
U
-
u
+
V
-
v
(
u
), one has
(69)
ℒ
(
u
;
g
-
𝒱
)
=
f
i
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
,
i
∈
{
1
,
…
,
p
}
.Theorem 23.
Giveng
-
∈
∂
F
^
(
x
-
) and supposing that Assumption 18 holds, then for u small enough, the following assertions are true.(i)
ℒ is a C
2 function of u and
(70)
ℒ
(
u
;
0
)
=
[
∑
i
=
1
p
‍
α
i
(
u
)
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
ϕ
j
(
𝒳
(
u
)
)
]
.
(ii)
The gradient ofℒ is given by ∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
g
(
u
;
g
-
𝒱
), where
(71)
g
(
u
;
g
-
𝒱
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
,
and, in particular, whenu
=
0, one has
(72)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
[
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
x
-
)
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
mim
+
∑
j
=
1
N
p
‍
β
-
j
∇
ϕ
j
(
x
-
)
]
=
U
-
T
g
-
=
g
-
𝒰
.
(iii)
The Hessian ofℒ is given by
(73)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
M
(
u
,
g
-
𝒱
)
J
(
𝒳
(
u
)
)
,
whereM
(
u
,
g
-
𝒱
) is the n
×
n matrix function defined by
(74)
M
(
u
,
g
-
𝒱
)
≔
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
2
ϕ
j
(
𝒳
(
u
)
)
.In particular, when u
=
0, one has
(75)
∇
2
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
;
g
-
𝒱
)
U
-
.Proof.
(i) Becausef
i
(
𝒳
(
u
)
) is C
2, it follows from C
2 of ℒ in the above theorem. At the same time, Assumption 18 holds; using (68) with z
=
0 gives
(76)
ℒ
(
u
;
0
)
=
f
i
(
𝒳
(
u
)
)
,
i
=
1
,
…
,
p
.
In addition,
(77)
ϕ
j
(
𝒳
(
u
)
)
=
0
,
j
=
1
,
…
,
N
p
.
Multiplying α
i and β
j, respectively, for the above equations and summing, we get the Lagrangian-like expression in item (i).
(ii) Using the chain rule, the differential of the Lagrangian-like functions (69) and (77) with respect to u can be written as follows:
(78)
∇
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
(
∇
f
i
(
𝒳
(
u
)
)
)
-
J
v
(
u
)
T
V
-
T
g
-
,
J
(
𝒳
(
u
)
)
T
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
=
0
.
Multiplying each equation by the appropriate α
i
(
u
) and β
j
(
u
), summing the results, and using the fact that ∑
i
‍
α
i
(
u
)
=
1 yield
(79)
∇
ℒ
(
u
;
g
-
𝒱
)
=
J
(
𝒳
(
u
)
)
T
[
+
∑
j
=
1
N
p
‍
β
j
(
u
)
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
∑
i
=
1
p
‍
α
i
(
u
)
(
∇
f
i
(
𝒳
(
u
)
)
)
=
J
(
𝒳
(
u
)
)
mm
T
∑
j
=
1
N
p
‍
+
∑
j
=
1
N
p
‍
β
j
(
u
)
(
∇
ϕ
j
(
𝒳
(
u
)
)
)
]
-
J
v
(
u
)
T
V
-
T
g
-
=
J
(
𝒳
(
u
)
)
T
g
(
u
;
g
-
𝒱
)
-
J
v
(
u
)
T
V
-
T
g
-
.
Using the transpose of the expression of J
(
𝒳
(
u
)
), we get
(80)
∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
g
(
u
;
g
-
𝒱
)
+
J
v
(
u
)
T
V
-
T
(
g
(
u
;
g
-
𝒱
)
-
g
-
)
,
which together with (6.11) in [28] yields the desired result.
Ifu
=
0,  then v
(
0
)
=
0, and 𝒳
(
0
)
=
x
-, J
𝒳
(
0
)
=
U
-, ∑
i
=
1
p
‍
α
i
(
0
)
=
1, and by Theorem 19
(81)
either
∇
f
i
(
x
-
)
∈
∂
F
^
(
x
-
)
so
U
-
T
∇
f
i
(
x
-
)
=
g
-
𝒰
,
or
∇
ϕ
j
(
x
-
)
∈
𝒱
so
U
-
T
∇
ϕ
j
(
x
-
)
=
0
;
so we attain
(82)
∇
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
[
∑
i
=
1
p
‍
α
-
i
∇
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
-
j
∇
ϕ
j
(
x
-
)
]
=
U
-
T
g
-
.
(iii) Differentiating the following equation with respect tou,
(83)
∇
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
(
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
=
U
-
T
n
∑
i
=
1
p
‍
α
i
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
)
,
we obtain
(84)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
U
-
T
[
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
m
+
U
-
T
mm
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
J
β
j
(
u
)
]
,
where M
(
u
)
=
∑
i
=
1
p
‍
α
i
(
u
)
∇
2
f
i
(
𝒳
(
u
)
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
2
ϕ
j
(
𝒳
(
u
)
). It follows from the proof of Theorem 6.3 in [28] that
(85)
∑
i
=
1
p
‍
α
i
(
u
)
∇
f
i
(
𝒳
(
u
)
)
J
α
i
(
u
)
+
∑
j
=
1
N
p
‍
β
j
(
u
)
∇
ϕ
j
(
𝒳
(
u
)
)
J
β
j
(
u
)
=
-
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
.
Then
(86)
∇
2
ℒ
(
u
;
g
-
𝒱
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
-
U
-
T
V
(
u
)
(
V
-
V
(
u
)
)
-
1
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
U
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
+
J
v
(
u
)
T
V
-
T
M
(
u
)
J
(
𝒳
(
u
)
)
=
[
U
-
T
+
J
v
(
u
)
T
V
-
T
]
M
(
u
)
J
(
𝒳
(
u
)
)
=
J
(
𝒳
(
u
)
)
T
M
(
u
)
J
(
𝒳
(
u
)
)
,
when u
=
0,
(87)
∇
2
ℒ
(
0
;
g
-
𝒱
)
=
U
-
T
M
(
0
)
U
-
,
where M
(
0
;
g
-
𝒱
)
=
∑
i
=
1
p
‍
α
-
i
∇
2
f
i
(
x
-
)
+
∑
j
=
1
N
p
‍
β
-
j
∇
2
ϕ
j
(
x
-
).We call the corresponding Hessian matrix ofℒ at u
=
0 a basic 𝒰-Hessian for F
^ at x
- and denote it by H
-
:
=
∇
2
ℒ
(
0
;
0
). Using second-order 𝒰-derivatives we can specify second-order expansions for F
^ and give related necessary conditions for optimization problem.Theorem 24.
Suppose Assumption18 holds and g
-
∈
∂
F
^
(
x
-
). Then for u small enough, there holds the second-order expansion of f along the trajectory 𝒳
(
u
)
=
x
-
+
u
⊕
v
(
u
),
(88)
F
^
(
𝒳
(
u
)
)
=
F
^
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Proof.
From the definition ofℒ, we have
(89)
ℒ
(
u
;
g
-
𝒱
)
=
F
^
(
𝒳
(
u
)
)
-
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
.
Since ℒ
∈
C
2, we get
(90)
ℒ
(
u
;
g
-
𝒱
)
=
ℒ
(
0
;
g
-
𝒱
)
+
〈
∇
ℒ
(
0
;
g
-
𝒱
)
,
u
〉
𝒰
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
^
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.
Therefore,
(91)
F
^
(
𝒳
(
u
)
)
=
F
^
(
x
-
)
+
〈
g
-
𝒰
,
u
〉
𝒰
+
〈
g
-
𝒱
,
v
(
u
)
〉
𝒱
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
=
F
^
(
x
-
)
+
〈
g
-
,
u
⊕
v
(
u
)
〉
+
1
2
u
T
∇
2
ℒ
(
0
;
g
-
𝒱
)
u
+
o
(
∥
u
∥
𝒰
2
)
.Corollary 25.
Suppose Assumption18 holds and x
- is a local minimizer of (56). Then 0
∈
∂
F
^
(
x
-
) and the associated basic 𝒰-Hessian H
- is positive semidefinite.


## 5. Conclusions

In this paper, we mainly study the𝒰
𝒱-theory to optimize the H
∞-norm or other nonsmooth criteria which are semi-infinite maxima of maximum eigenvalue functions. We use a methodology from semi-infinite programming to obtain a local nonlinear programming model and apply the 𝒰
𝒱 decomposition method. With the so-called PDG that this problem possesses, Lagrangian-like theory is applied to the class of the functions. Under some hypothesis conditions, we can obtain the first- and second-order derivatives of the primal-dual Lagrangian function. This method can operate well in practice.For further work, the need can be anticipated: in this paper we only give the theory analysis to solve the special class of eigenvalue optimization, we will continue to study its executable algorithm, and we will extend the𝒰
𝒱 algorithm of convex eigenvalues to nonconvex cases, where its related theory will be researched in later papers.



---

*Source: 845017-2014-02-17.xml*