Strong Variational Sufficiency for Nonlinear Semidefinite Programming and its Implications

2025-05-02 0 0 815.35KB 23 页 10玖币

侵权投诉

STRONG VARIATIONAL SUFFICIENCY FOR NONLINEAR

SEMIDEFINITE PROGRAMMING AND ITS IMPLICATIONS∗

SHIWEI WANG†, CHAO DING‡, YANGJING ZHANG§,AND XINYUAN ZHAO¶

Abstract. Strong variational suﬃciency is a newly proposed property, which turns out to

be of great use in the convergence analysis of multiplier methods. However, what this property

implies for non-polyhedral problems remains a puzzle. In this paper, we prove the equivalence

between the strong variational suﬃciency and the strong second order suﬃcient condition (SOSC)

for nonlinear semideﬁnite programming (NLSDP), without requiring the uniqueness of multiplier or

any other constraint qualiﬁcations. Based on this characterization, the local convergence property

of the augmented Lagrangian method (ALM) for NLSDP can be established under strong SOSC

in the absence of constraint qualiﬁcations. Moreover, under the strong SOSC, we can apply the

semi-smooth Newton method to solve the ALM subproblems of NLSDP as the positive deﬁniteness

of the generalized Hessian of augmented Lagrangian function is satisﬁed.

Key words. strong variational suﬃciency, nonlinear semideﬁnite programming, strong second

order suﬃcient condition, augmented Lagrangian method

MSC codes. 49J52, 90C22, 90C46

1. Introduction. The local optimality of the general optimization problem is a

crucial topic for its theoretical importance and wide application. Traditionally, it is

studied through the growth condition, e.g., the well-known ﬁrst or second order op-

timality condition (cf. e.g., [6]). Recently, Rockafellar [34] proposed a new property

named strong variational suﬃciency to deal with this topic geometrically. The key idea

of this abstract deﬁnition originates from a so-called (strong) variational convexity,

which indicates that the values and subgradients of a function are locally indistin-

guishable from those of a convex function. These two approaches seem to originate

from diﬀerent angles to understand the local optimality, but whether they possess

deep connections is an essential issue as it provides not only a better comprehension

of optimization theory, but also a solid theoretical foundation in algorithm design.

Thus an explicit characterization of strong variational suﬃciency is demanding.

The deﬁnition of (strong) variational suﬃcient condition (Deﬁnition 2.3) is oﬃ-

cially given in [37] for the following general composite optimization problem

(1.1) min

x∈Xf(x) + θ(G(x)),

where Xand Yare two given Euclidean spaces, f:X→Rand G:X→Yare twice

∗This version: May 4, 2023

†School of Mathematical Sciences, University of Chinese Academy of Science, Beijing, P.R. China.

Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy

of Sciences, Beijing, P.R. China. (wangshiwei182@mails.ucas.ac.cn).

‡Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Acad-

emy of Sciences, Beijing, P.R. China. School of Mathematical Sciences, University of Chinese Acad-

emy of Science, Beijing, P.R. China. (dingchao@amss.ac.cn). The work of this author was supported

in part by the Beijing Natural Science Foundation (Z190002), National Natural Science Foundation

of China under project No. 12071464 and CAS Project for Young Scientists in Basic Research No.

YSBR-034.

§Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Acad-

emy of Sciences, Beijing, P.R. China. (yangjing.zhang@amss.ac.cn).The work of this author was

supported by the National Natural Science Foundation of China under project No. 12201617.

¶Department of Mathematics, Beijing University of Technology, Beijing, P.R. China.

(xyzhao@bjut.edu.cn). The work of this author was supported in part by the National Natural

Science Foundation of China under project No. 12271015 and No. 11871002.

arXiv:2210.04448v4 [math.OC] 9 Jul 2023

2SHIWEI WANG, CHAO DING, YANGJING ZHANG AND XINYUAN ZHAO

continuously diﬀerentiable, and θ:Y→(−∞,∞] is a closed proper convex function.

The strong variational suﬃcient condition is ﬁrstly introduced to deal with the local

convexity of primal augmented Lagrangian function and the augmented tilt stability.

It has gained more and more attention for its mathematical elegance and wide appli-

cations in the convergence analysis of multiplier methods. Several characterizations

of this abstract property are also given in [37]. For instance, it is equivalent to the

positive deﬁniteness of the Hessian bundle of the augmented Lagrangian function [37,

Theorem 3] or the criterion [37, Theorem 5] involving quadratic bundle (Deﬁnition

2.6).

In terms of the connection with traditional optimality conditions, Rockafellar [37,

Theorem 4] shows that the strong variational suﬃciency is equivalent to the well-

known strong second order suﬃcient condition (SOSC), which is expressed entirely

via the program data, when the function θin (1.1) is polyhedral convex (i.e., the

epigraph epi θof θis a polyhedral convex set). For non-polyhedral problems, the

equivalence is still valid if θin (1.1) is the indicator function of the second order

cone with G(¯x)̸= 0, where ¯xis a local optimal solution (see [37, Example 3] for

details). However, an explicit and veriﬁable characterization of strong variational

suﬃcient condition for general non-polyhedral problems remains unknown. In this

paper, without loss of generality, we mainly focus on the characterization of strong

variational suﬃciency for the following nonlinear semideﬁnite programming (NLSDP):

(1.2) min

x∈Xf(x)

s.t. G(x)∈Sn

where Snis the linear space of all n×nreal symmetric matrices equipped with the

usual Frobenius inner product and its induced norm, Sn

+(Sn

−) is the closed convex cone

of all n×npositive (negative) semideﬁnite matrices in Sn. One of our contributions

lies in uncovering the equivalence between strong variational suﬃcient condition and

strong SOSC (see Deﬁnition 2.2 for details) for NLSDP problems without requiring

any other constraint qualiﬁcations.

An important application of the strong variational suﬃciency of NLSDP is the

local convergence analysis of the augmented Lagrangian method (ALM). The ALM,

which was ﬁrstly proposed by Hestenes and Powell in 1969, and it has attained fruitful

achievements during the past ﬁfty years. Especially, [33] uncovers the equivalence be-

tween the proximal point algorithm (PPA) and ALM for convex problems. This work

is of great importance in establishing the Q-linear convergence rate of the dual se-

quence for ALM. The conditions for the local linear convergence are further weakened

(see e.g., [24,13]). For nonconvex case, the properties built up under the convexity

assumption have become inadequate. Many eﬀorts have been made to explore the

convergence properties of ALM for nonconvex problems. See [4,9,10,20,17,18]

for more details. It is worth noting that in [4], the author revealed a kind of lo-

cal duality based on suﬃcient conditions for local optimality, which turns out to be

the key to understanding the convergence of ALM for nonconvex nonlinear program-

ming. It follows that there may be a local reduction from nonconvex optimization

to convex optimization. This gives a hint on extending this local duality approach

to broader nonconvex problems. Recently, the newly published work [38] opens new

doors for the convergence rate analysis of ALM for nonconvex problems by using the

aforementioned characterization of strong variational suﬃcient condition without any

constraint qualiﬁcations.

For NLSDP (1.2), the Lagrangian function is deﬁned by

(1.3) L(x, Y ) := f(x) + ⟨Y, G(x)⟩,(x, Y )∈X×Sn.

For any Y∈Sn, denote the ﬁrst-order and second-order derivatives of L(·, Y ) at x∈X

by L′

x(x, Y ) and L′′

xx(x, Y ), respectively. Given ρ > 0, the augmented Lagrangian

function of (1.2) takes the following form (cf. [39, Section 11.K] and [40])

(1.4) Lρ(x, Y ) := f(x) + ρ

2dist2(G(x) + Y

ρ,Sn

+)−∥Y∥2

2ρ,

where dist(z, Sn

+) is the distance from point zto Sn

+. For a given initial point (x0, Y 0)∈

X×Snand a constant ρ0>0, the (k+ 1)-th iteration of (extended) augmented

Lagrangian method (ALM) for NLSDP (1.2) proposed by [38] takes the following

form

(1.5) (xk+1 ≈arg min{Lρk(x, Y k)},

Yk+1 =Yk+eρkG(xk+1)−ΠSn

+(G(xk+1) + Yk

ρk),

where ρk,eρk>0 and ΠSn

+(·) is the metric projection onto Sn

+. The (extended) ALM

(1.5) reduces to the traditional ALM when eρk=ρk. To see how ALM (1.5) works for

nonconvex problems without constraint qualiﬁcations, consider the following simple

example:

(1.6)

min 1

2x3

s.t.−x2



000

001



∈S3

The optimal solution of (1.6) is ¯x= 0 with the corresponding multiplier set M(¯x) :=

{Y|Y∈S3

−}. Due to the unboundedness of M(¯x), we know from [50, Theorem 4.1]

that the Robinson constraint qualiﬁcation [30] does not hold at ¯x. Pick a particular

multiplier

Y=



0 0 0

0−1 0

0 0 −2

∈ M(¯x).

It is clear that L′′

xx(¯x, Y )=4>0, which implies strong SOSC (Deﬁnition 2.2) holds

at (¯x, Y ). We directly apply the ALM (Algorithm 4.1) to problem (1.6), and we ﬁnd

that the corresponding ALM subproblem in (1.5) can be solved exactly. Then, it

can be observed from Figure 1that for ﬁxed ρkand eρk, dist(Yk,M(¯x)), the distance

between the k-th iteration Ykand M(¯x), converges to zero linearly.

In this paper, combing [37] with our equivalence result, we obtain the Q-linear

convergence of dual variables and the R-linear convergence of primal ones of ALM for

NLSDP under merely strong SOSC, without requiring the uniqueness of multiplier or

any other constraint qualiﬁcations. It is worth noting that [44] and [21] obtained the

ALM local convergence result under (strong) SOSC and nondegeneracy [41, Deﬁnition

3.2] or strict Robinson constraint qualiﬁcation (SRCQ) (see e.g., [15, (11)] for its def-

inition) respectively, both of which imply the uniqueness of multiplier. Although [48,

Theorem 2] relaxed the uniqueness assumption of multiplier, additional assumptions

[48, Assumption 1] with respect to multipliers are still needed.

4SHIWEI WANG, CHAO DING, YANGJING ZHANG AND XINYUAN ZHAO

Fig. 1.ALM for solving (1.6)with diﬀerent penalty parameters ρk=ρ.

Another important and practical issue in applying ALM is how to solve the ALM

subproblem (1.5). For convex problems, the successes of SDPNAL [49], SDPNAL+

[45,47] and QSDPNAL [23] have proved the eﬃciency of the semi-smooth Newton-CG

method. Its eﬃciency relies critically on the positive deﬁniteness of certain generalized

Hessian of the augmented Lagrangian function. And we are able to show the positive

deﬁniteness of the generalized Hessian under strong SOSC, as a direct application of

[37, Theorem 3] and our equivalence result.

The remaining parts of this paper are organized as follows. In the next section,

we introduce some preliminary knowledge in semideﬁnite cone and strong variational

suﬃciency. In Section 3, we propose our main equivalence result for both nonlinear

second order cone programming (NLSOC) and NLSDP. Section 4, as a direct appli-

cation, copes with the convergence properties of ALM for NLSDP. Moreover, how to

solve the subproblems and the corresponding convergence analysis are discussed. In

Section 5, the numerical experiment of an example is given to show the validity of

the aforementioned results. We conclude our paper and make some comments in the

ﬁnal section.

2. Preliminaries. For a given Euclidean space X, let Cbe any subset in X,

aﬀ Cis the aﬃne hull of C[32, page 6]. The Bouligand tangent/contingent cone of

Cat xis a closed cone deﬁned by

TC(x) := d∈X| ∃tk↓0 and dk→dwith x+tkdk∈Cfor all k.

When Cis convex, the normal cone in the sense of convex analysis [32] is deﬁned as

NC(x) = {d∈X| ⟨d, x′−x⟩ ≤ 0∀x′∈C}.

For any x∈C, the critical cone associated with y∈ NC(x) of Cis deﬁned in [16,

Page 98], i.e., CC(x, y) = TC(x)∩(y)⊥.

For a set-valued mapping F:X⇒X, its lim sup means

lim sup

x→¯xF(x) := {d∈X| ∃ xk→¯x, yk→dsuch that yk∈ F(xk)∀k}.

The following deﬁnitions of proximal and (general/Mordukhovich limiting) subdiﬀer-

entials of functions are adopted from [39, Deﬁnition 8.45 and 8.3].

Definition 2.1. Consider a function f:X→(−∞,+∞]and a point ¯xwith

f(¯x)ﬁnite. The proximal subdiﬀerential of fat ¯xis deﬁned as

∂πf(¯x) := {d| ∃ l > 0, r > 0 such that f(x)≥f(¯x)+⟨d, x−¯x⟩−l∥x−¯x∥2∀x∈ Br(¯x)},

where Br(¯x)is the ball centered at ¯xwith radius r. The (general/Mordukhovich limit-

ing) subdiﬀerential of fat ¯xis ∂f(¯x) := lim sup

→¯x

∂πf(x), where xf

→¯xsigniﬁes x→¯x

with f(x)→f(¯x).

Note that in an Euclidean space, the (general) subdiﬀerential also can be constructed

via the regular/Fr´echet subdiﬀerentials of functions b

∂f [39, Deﬁnition 8.3]. It is well-

known that these two deﬁnitions are equivalent (see e.g., [39, page 345] or [26, Theorem

1.89] for details). In particular, when fis convex and ﬁnite at the corresponding

point, the proximal and (general) subdiﬀerentials coincide with the subdiﬀerential in

the sense of convex analysis [32].

2.1. Variational analysis of NLSDP. Let A∈Snbe given. We use λ1(A)≥

λ2(A)≥. . . ≥λn(A) to denote the eigenvalues of A(all real and counting multi-

plicity) arranging in nonincreasing order and use λ(A) to denote the vector of the

ordered eigenvalues of A. Let Λ(A) := Diag(λ(A)). Also, we use v1(A)>··· > vd(A)

to denote the diﬀerent eigenvalues and ζl:= {i|λi(A) = vl(A)}. Consider the eigen-

value decomposition of A, i.e., A=PΛ(A)PT, where P∈ On(A) is a corresponding

orthogonal matrix of the orthonormal eigenvectors. By considering the index sets of

positive, zero, and negative eigenvalues of A, we are able to write Ain the following

form

(2.1) A=PαPβPγ





Λ(A)αα 0 0

0 0 0

0 0 Λ(A)γγ















,

where α:= {i:λi(A)>0},β:= {i:λi(A) = 0}and γ:= {i:λi(A)<0}.

The critical cone of Sn

+at Y∈ NSn

+(X) with A=X+Yis given by (cf. [8,

equations (11) and (12)])

(2.2) CSn

+(X, Y ) = {H∈Sn|PT

βHPβ∈S|β|

+, P T

βHPγ= 0, P T

γHPγ= 0}

and the aﬃne hull of CSn

+(X, Y ) is

(2.3) aﬀ CSn

+(X, Y ) = {H∈Sn|PT

βHPγ= 0, P T

γHPγ= 0}.

The NLSDP (1.2) can be written in the following form

min f(x) + δSn

+(G(x)),(2.4)

where δSn

+:Sn→(−∞,∞] is the indicator function of positive semideﬁnite cone

+. Denote SKKT (a, b) the solution set of the KKT optimality condition for problem

(2.4), i.e.,

(2.5) SKKT (a, b) = ((x, Y )∈X×Sn

L′

x(x, Y )−a= 0,

+∋(G(x)−b)⊥Y∈Sn

−.).

For any KKT pair (¯x, Y ) that satisﬁes the KKT condition with (a, b) = (0,0), we call

¯xa stationary point. Suppose ¯xis a stationary point. Deﬁne M(¯x) as the set of all

multipliers Y∈Snsatisfying the KKT condition (2.5), i.e.,

(2.6) M(¯x) = {Y∈Sn|(¯x, Y )∈SKKT (0,0)}.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

STRONGVARIATIONALSUFFICIENCYFORNONLINEARSEMIDEFINITEPROGRAMMINGANDITSIMPLICATIONS∗SHIWEIWANG†,CHAODING‡,YANGJINGZHANG§,ANDXINYUANZHAO¶Abstract.Strongvariationalsufficiencyisanewlyproposedproperty,whichturnsouttobeofgreatuseintheconvergenceanalysisofmultipliermethods.However,whatthispropertyimpliesfo...

收起<<

Strong Variational Sufficiency for Nonlinear Semidefinite Programming and its Implications.pdf

共23页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Strong Variational Sufficiency for Nonlinear Semidefinite Programming and its Implications

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: