Inexact Penalty Decomposition Methods for Optimization Problems with Geometric Constraints

2025-05-05 0 0 793.75KB 36 页 10玖币

侵权投诉

Inexact Penalty Decomposition

Methods for Optimization Problems

with Geometric Constraints

Christian Kanzow ∗Matteo Lapucci †

March 23, 2023

Abstract. This paper provides a theoretical and numerical investigation of a penalty

decomposition scheme for the solution of optimization problems with geometric constraints.

In particular, we consider some situations where parts of the constraints are nonconvex and

complicated, like cardinality constraints, disjunctive programs, or matrix problems involv-

ing rank constraints. By a variable duplication and decomposition strategy, the method

presented here explicitly handles these diﬃcult constraints, thus generating iterates which

are feasible with respect to them, while the remaining (standard and supposingly simple)

constraints are tackled by sequential penalization. Inexact optimization steps are proven

suﬃcient for the resulting algorithm to work, so that it is employable even with diﬃcult

objective functions. The current work is therefore a signiﬁcant generalization of existing

papers on penalty decomposition methods. On the other hand, it is related to some recent

publications which use an augmented Lagrangian idea to solve optimization problems with

geometric constraints. Compared to these methods, the decomposition idea is shown to be

numerically superior since it allows much more freedom in the choice of the subproblem

solver, and since the number of certain (possibly expensive) projection steps is signiﬁcantly

less. Extensive numerical results on several highly complicated classes of optimization prob-

lems in vector and matrix spaces indicate that the current method is indeed very eﬃcient

to solve these problems.

Keywords. Penalty Decomposition, Augmented Lagrangian, Mordukhovich-Stationarity,

Asymptotic Regularity, Asymptotic Stationarity, Cardinality Constraints, Low-Rank Opti-

mization, Disjunctive Programming

AMS subject classiﬁcations. 49J53,65K10,90C22,90C30,90C33

∗University of Würzburg, Institute of Mathematics, 97074 Würzburg, Germany,

kanzow@mathematik.uni-wuerzburg.de, ORCID: 0000-0003-2897-2509

†Department of Information Engineering, Università degli Studi di Firenze, Via di Santa Marta

3, 50139 Firenze, Italy, matteo.lapucci@unifi.it, ORCID: 0000-0002-2488-5486

arXiv:2210.05379v1 [math.OC] 11 Oct 2022

1 Introduction

We consider the program

min

xf(x)s.t. G(x)∈C, x ∈D, (1.1)

where f:X→Rand G:X→Yare continuously diﬀerentiable mappings, Xand

Yare Euclidean spaces, i.e., real and ﬁnite-dimensional Hilbert spaces, C⊆Yis

nonempty, closed, and convex, whereas D⊆Xis only assumed to be nonempty and

closed (not necessarily convex), representing a possibly complicated set.

This very general setting (analyzed for example in [25]) covers, for example, stan-

dard nonlinear programming problems with convex constraints, but also diﬃcult dis-

junctive programming problems [8,9,18,36], e.g., complementarity [42], vanishing [1],

switching [37] and cardinality constrained [30,31] problems. Matrix optimization

problems such as low-rank approximation [28,34] are also captured by our setting.

Problems with this structure, where the feasible set consists of the intersection of

a set of constraints expressed in analytical form and another complicated set, with-

out regularity guarantees but manageable for example by easy projections, have been

deeply studied in recent years. In particular, approaches based on decomposition and

sequential penalty or augmented Lagrangian methods have been proposed for the

convex case [19], the cardinality constrained case [31,33] and the low-rank approxi-

mation case [43]; the recurrent idea in all these works consists of the application of

the variable splitting technique [21,26], to then deﬁne a penalty function associated

with the diﬀerentiable constraints and the additional equality constraint linking the

two blocks of variables and ﬁnally solve the problem by a sequential penalty method.

The optimization of the penalty function is carried out by a two-block alternatimg

minimization scheme [20], which can be run in an exact [33,43] or inexact [19,31]

fashion.

The aim of this work is to extend the inexact Penalty Decomposition approach

to the general setting (1.1) in such a way that it can deal with arbitrary abstract

constraints D(at least theoretically, in practice Dneeds to be such that projections

onto this set are easy to compute) and that it allows additional (seemingly simple)

constraints given by G(x)∈C. This setting is related to some recent work on

(safeguarded) augmented Lagrangian methods, see, in particular, [25], where the

resulting subprobems are solved by a projected gradient-type method, which might

be ineﬃcient especially for ill-conditioned problems. The decomposition idea used

here allows a much wider choice of subproblem solvers, usually resulting in a more

eﬃcient solver of the given optimization problem (1.1).

The paper is organized as follows: Section 2summarizes some preliminary con-

cepts and results. In particular, we recall the deﬁnitions of an M-stationary point (the

counterpart of a KKT point for the general setting from (1.1)), of an AM-stationary

point (as a sequential version of M-stationarity) and of an AM-regular point (this

being a suitable and relatively weak constraint qualiﬁcation). Section 3then presents

the Penalty Decomposition method together with a global convergence theory, assum-

ing that the resulting subproblems can be solved inexactly up to a certain degree. In

Section 4, we then present a class of inexact alternating minimization methods which,

under certain assumptions, are guaranteed to ﬁnd the desired approximate solution

of the subproblems arising in the outer penalty scheme. The remaining part of the

paper is then devoted to the implementation of the overall method and corresponding

numerical results. To this end, Section 5ﬁrst discusses several instances of the general

setting (1.1) with diﬃcult constraints Dwhere our method can be applied to quite

eﬃciently since projections onto Dare simple and/or known analytically (though the

latter does not necessarily imply that these projections are easy to compute numer-

ically). In Section 6, we then present the results of an extensive numerical testing,

where we also compare our method, using diﬀerent realizations, with the augemented

Lagrangian method from [25]. We conclude with some ﬁnal remarks in Section 7.

2 Preliminaries

The Euclidean projection PC:Y→Yonto the nonempty, closed, and convex set C

is deﬁned by

PC(y) := argminz∈Ckz−yk.

The corresponding distance function dC:Y→Rcan then be written as

distC(y) := min

z∈Ckz−yk=kPC(y)−yk.

Note that the distance function is nonsmooth (in general), but the squared distance

function

sC(y) := 1

2dist2

C(y)

is continuously diﬀerentiable everywhere with derivative given by

∇sC(y) = y−PC(y),(2.1)

see [5, Cor. 12.30]. Moreover, projections onto the nonempty and closed set Dalso

exist, but are not necessarily unique. Therefore, we deﬁne the (usually set-valued)

projection operator ΠD:X⇒Xby

ΠD(x) := argmin

z∈D

kz−xk 6=∅.

The corresponding distance function distD(·)is, of course, single-valued again. Fur-

thermore, given a set-valued mapping S:X⇒Xon an arbitrary Euclidean space X,

we deﬁne the outer limit of Sat a point ¯xby

lim sup

x→¯x

S(x) := y∈X∃xk→¯x, ∃yk→ywith yk∈S(xk)∀k∈N.

This allows to deﬁne the limiting normal cone at a point x∈Dby

Nlim

D(x) := lim sup

v→xconev−ΠD(v),

see [38, Sect. 1.1] for further details. Writing

x→D¯x⇐⇒ x→¯x, x ∈D

for sequences converging to an element ¯x∈Dsuch that the whole sequence belongs

to D, the limiting normal cone has the important robustness property

lim sup

x→D¯x

Nlim

D(x) = Nlim

D(¯x)(2.2)

that will be exploited heavily in our subsequent analysis, see [38, Prop. 1.3].

Note that, for Dbeing convex, this limiting normal cone reduces to the standard

normal cone from convex analysis, i.e., we have

Nlim

D(¯x) = ND(¯x) := {λ∈X| hλ, x −¯xi ≤ 0∀x∈D}

for any given ¯x∈D. For points ¯x6∈ D, we set Nlim

D(¯x) := ND(¯x) := ∅. For the

convex set C, the standard normal cone and the projection operator are related by

p=PC(y)⇐⇒ y−p∈ NC(p),(2.3)

see [5, Prop. 6.46].

We next introduce a stationarity condition which generalizes the concept of a

KKT point to constrained optimization problems with possibly diﬃcult constraints

as given by the set Din our setting (1.1).

Deﬁnition 2.1. A feasible point ¯x∈Xof the optimization problem (1.1) is called

an M-stationary point (Mordukhovich-stationary point) of (1.1) if there exists a mul-

tiplier λ∈Ysuch that

0∈ ∇f(¯x) + G0(¯x)∗λ+Nlim

D(¯x), λ ∈ NCG(¯x).

Note that this deﬁnition coincides with the one of a KKT point if Dis convex. The

following is a sequential version of M-stationarity.

Deﬁnition 2.2. A feasible point ¯x∈Xof the optimization problem (1.1) is called

an AM-stationary point (asymptotically M-stationary point) of (1.1) if there exist

sequences {xk},{εk} ⊆ Xand {λk},{zk} ⊆ Ysuch that xk→¯x,εk→0,zk→0, as

well as

εk∈ ∇f(xk) + G0(xk)∗λk+Nlim

D(xk), λk∈ NCG(xk)−zk

for all k∈N.

Note that the previous deﬁnition generalizes the related concept of AKKT points

introduced for standard nonlinear programs in [2] to our setting with the more diﬃcult

constraints. In a similar way, the subsequent regularity conditions are also motivated

by related ones from [3] , where they were presented for standard nonlinear programs.

Every M-stationary point is obviously also AM-stationary, whereas the opposite

implication will be guaranteed to hold by a regularity condition that will now be

introduced. To this end, let us write

M(x, z) := G0(x)∗NCG(x)−z+Nlim

D(x).

Recall that Nlim

D(x)is nonempty if and only if x∈D, which is therefore an implicit

requirement for the set M(x, z)to be nonempty. Moreover, we consider the set

lim sup

x→¯x,z→0

M(x, z) = v∃xk→D¯x, ∃zk→0 : vk→vand vk∈ M(xk, zk)∀k∈N.

Note that the auxiliary sequence {zk}needs to be introduced since the elements G(xk)

do not necessarily belong to C, whereas xkis supposed to be an element of D.

Deﬁnition 2.3. Let ¯xbe feasible for (1.1). Then ¯xis called AM-regular for (1.1) if

lim supx→¯x,z→0M(x, z)⊆ M(¯x, 0).

Using this terminology, the following statements hold, cf. [35] for further details.

Theorem 2.4. The following statements hold:

(a) Every local minimum of (1.1)is an AM-stationary point.

(b) If ¯xis an AM-stationary point satisfying AM-regularity, then ¯xis an M-stationary

point of (1.1).

¯xis an AM-stationary point =⇒¯xis an M-stationary point

holds for the corresponding optimization problem (1.1), then ¯xis AM-regular.

Statement (a) shows that every local minimum of (1.1) is an AM-stationary point even

in the absense of any constraint qualiﬁcation (CQ for short). Hence AM-stationary

is a (sequential) ﬁrst-order optimality condition. In order to guarantee that an AM-

stationary point is already an M-stationary point (hence a KKT point in the standard

setting of a nonlinear program, say), we require a CQ, namely the AM-regularity

condition, cf. Theorem 2.4 (b). The ﬁnal statement (c) of that result shows that, in a

certain sense, AM-regularity is the weakest CQ which implies AM-stationary points

to be M-stationary. In fact, this AM-regularity condition turns out to be a fairly weak

condition. For example, for standard nonlinear programs, AM-regularity is stronger

than the Abadie CQ, but weaker than most of the other well-known CQs like MFCQ

(Mangasarian-Fromovitz CQ), CRCQ (constant rank CQ), CPLD (constant positive

linear dependence), and RCPLD (relaxed CPLD), to mention at least some of the

more prominent ones. We refer the interested reader to [4,35] and references therein

for further details.

The algorithm, to be described in the following section, is based on the reformu-

lation

min

x,y f(x)s.t. x−y= 0, G(x)∈C, y ∈D, (2.4)

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

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

10 玖币 0人已下载

立即下载

摘要：

InexactPenaltyDecompositionMethodsforOptimizationProblemswithGeometricConstraintsChristianKanzow*MatteoLapucciMarch23,2023Abstract.Thispaperprovidesatheoreticalandnumericalinvestigationofapenaltydecompositionschemeforthesolutionofoptimizationproblemswithgeometricconstraints.Inparticular,weconsiders...

展开>> 收起<<

Inexact Penalty Decomposition Methods for Optimization Problems with Geometric Constraints.pdf

共36页,预览5页

还剩页未读，继续阅读

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

Inexact Penalty Decomposition Methods for Optimization Problems with Geometric Constraints

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: