betaFeedback

WorksMathematics

A constraint dissolving method for generally constrained optimization over a nonconvex set

Abstract

This manuscript studies a constraint dissolving method for solving optimization problems with general constraints, comprising an abstract constraint G(x) \in C and a potentially nonconvex geometric constraint x \in D, which, to the best of our knowledge, is the first constraint dissolving type method applicable to this general setting. More specifically, we introduce an auxiliary variable s to decouple G(x) \in C into G(x) = s and s \in C, and construct the constraint dissolving mapping acting jointly on both variables. We then propose a penalty-based constraint dissolving method, in which the penalty parameter is updated adaptively according to the feasibility error. Under mild conditions, every accumulation point is Mordukhovich-stationary. By a specific choice of the constraint dissolving mapping, every accumulation point is guaranteed to be feasible, which stands in contrast to standard penalty-type methods in nonconvex settings. Numerical experiments on Rosenbrock, portfolio, and MAXCUT problems demonstrate the effectiveness of the proposed method against the augmented Lagrangian and the penalty decomposition methods.

Introduction

In this paper, we consider the following optimization problem with a geometric constraint:

min⁡xf(x)s.t.G(x)∈C, x∈D,(1)\begin{aligned} \min_{x}\quad&f(x)\\ \text{s.t.}\quad&G(x) \in C,\ x \in D, \tag*{(1)} \end{aligned}

where f:Rn→Rf : \mathbb{R}^{n} \to\mathbb{R} and G:Rn→RmG : \mathbb{R}^{n} \to\mathbb{R}^{m} are continuously differentiable. The set C⊂RmC \subset\mathbb{R}^{m} is nonempty, closed, and convex, whereas D⊂RnD \subset\mathbb{R}^{n} is nonempty and closed, but not necessarily convex. We refer to x∈Dx \in D as a geometric constraint, allowing DD to represent potentially nonconvex structures, such as cardinality, complementarity, either-or, and low-rank constraints.

To the best of our knowledge, penalty-based methods are potentially efficient for solving such types of problems. Specifically, Jia et al. [8] develop an augmented Lagrangian method that handles the geometric constraint in a unified framework, while Kanzow and Lapucci [10] propose an inexact penalty decomposition method where an auxiliary variable is employed to separate the geometric constraint1. x∈Dx \in D. More recently, the constraint dissolving technique, originally introduced for optimization over the Stiefel manifold [16], has shown great potential for solving (P). This type of method is first developed for problems with equality constraints G(x)=0G(x) = 0 in [17], and a practical scheme based on Monte Carlo sampling for determining the penalty parameter is provided in [15]. It is subsequently generalized to handle equality constraints G(x)=0G(x) = 0 together with a convex set constraint x∈Dx \in D in [18]. Beyond these settings, Hu et al. [7] transform nonconvex-strongly-convex bilevel optimization problems into unconstrained constraint dissolving problems and develop a unified framework for subgradient-based methods, and the technique has also been applied to feasibility problems over nonconvex sets [19]. Building on the works mentioned above, Jia et al. [9] consider this type of method for solving (P), i.e., with the more general constraints G(x)∈CG(x) \in C and x∈Dx \in D, where DD is possibly nonconvex, and establish theoretical foundations for the constraint dissolving mapping and the corresponding algorithm. However, due to the nonsmoothness of the projection onto CC, the numerical realization in [9] is restricted to the case C:={0}C := \{0\}, leaving the general convex case, including standard inequality constraints, unaddressed. This manuscript aims to resolve this gap, as a substantial extension of [9].

To this end, we introduce a slack variable s∈Rms \in\mathbb{R}^{m} to separate the nonlinear coupling from the set constraint G(x)∈CG(x) \in C and rewrite (P) as

min⁡x,sf(x)s.t.G(x)−s=0,x∈D,s∈C.\begin{aligned} \min_{x,s}\quad& f(x)\\ \text{s.t.}\quad& G(x)-s=0,\quad x\in D,\quad s\in C. \end{aligned}

This standard reformulation preserves feasible points and local and global minimizers same as those of (P) in the sense that the map x↦(x,G(x))x \mapsto(x, G(x)) is bijection; see, e.g., [2 Section 3]. Based on this reformulation, the main contributions of this manuscript are threefold.

  • Theoretically, we introduce a constraint dissolving mapping that acts jointly on the original and slack variables. Extending the analysis of [9] to this reformulation, we prove under a mild constraint qualification that, for every positive penalty parameter, a feasible point xx is Mordukhovich stationary for (P) if and only if (x,G(x))(x, G(x)) is Mordukhovich stationary for the resulting constraint dissolving problem. On this basis, we show that every feasible accumulation point of the proposed method is a Mordukhovich stationary point of (P). Moreover, for a specific constraint dissolving mapping, we prove that every accumulation point is feasible for (P), which stands in contrast to classical penalty-type methods in the nonconvex setting, whose accumulation points are not necessarily feasible in general.

  • Algorithmically, we propose a penalty-based constraint dissolving method, which computes, by a projected gradient method, an approximate Mordukhovich stationary point of the penalty function obtained from constraint dissolving over (x,s)∈D×C(x,s) \in D \times C. For the constraint dissolving problem to be solved, the constraints x∈Dx \in D and s∈Cs \in C are retained, whereas G(x)=sG(x) = s is dissolved into the objective function. Afterwards, the penalty parameter β\beta is kept if the feasibility error ∥G(x)−s∥\lVert G(x)-s\rVert has decreased by a prescribed factor and is increased otherwise. This explicit adaptive rule stands in contrast to the fixed penalty parameter in [18] and the nondecreasing update without an explicit rule in [9].

  • Numerically, we implement the proposed method with the explicit constraint dissolving mapping constructed in this manuscript and test it on complementarity-constrained Rosenbrock, sparse portfolio, and MAXCUT problems. In accordance with the general setting considered here, these problems include instances that combine a nonconvex set DD with a constraint set CC that is not a singleton. In the presented experiments, it requires, in most cases, fewer outer iterations than the safeguarded augmented Lagrangian method [8] and the inexact penalty decomposition method [10], while attaining solutions of comparable or better quality.

The rest of the paper is organized as follows. In § 2, we recall necessary definitions and properties of variational analysis, establish properties of the constraint dissolving mapping, and characterize the relationships between stationary points of (P) and those of the reformulated problem via the constraint dissolving mapping. In § 3, we propose a penalty-based constraint dissolving method for solving (P) and establish its convergence analysis. In § 4, we construct a specific constraint dissolving mapping and prove that every accumulation point generated by the proposed algorithm is feasible for (P). In § 5, we conduct numerical experiments on several benchmark problems, including Rosenbrock, portfolio optimization, and MAXCUT problems, to demonstrate the effectiveness of the proposed algorithm. Finally, § 6 concludes the manuscript.

Preliminaries

In this section, we first recall the tools from variational analysis [13] used throughout the paper in § 2.1. § 2.2 derives key properties of the constraint dissolving mapping. § 2.3 investigates relationships between stationary points of (P) and those of the corresponding penalty problem based on the constraint dissolving mapping.

Materials for variational analysis

For any nonempty, closed, but not necessarily convex set D⊆RnD \subseteq\mathbb{R}^{n}, we denote PD(x):=arg⁡min⁡z∈D∥z−x∥P_{D}(x):=\arg\min_{z\in D}\|z-x\| and dist⁡D(x):=inf⁡z∈D∥z−x∥\operatorname{dist}_{D}(x):=\inf_{z\in D}\|z-x\| as the corresponding projection mapping and the distance function, respectively. When DD is nonconvex, PD(x)P_{D}(x) may fail to be a singleton, i.e., the projection onto DD does not need to be unique.

Given z∈Dz\in D, the tangent cone to DD at zz is defined by

TD(z):={w∈Rn | zk−zτk→w for some zk→Dz, τk↓0}.\mathcal{T}_{D}(z):=\left\{w\in\mathbb{R}^{n}\ \middle|\ \frac{z^{k}-z}{\tau^{k}}\to w\text{ for some }z^{k}\xrightarrow[D]{}z,\ \tau^{k}\downarrow0\right\}.

the normal cone to DD at zz is defined as

ND(z):={v∈Rn | ⟨v,x−z⟩≤o(∥x−z∥) for x∈D}.\mathcal{N}_{D}(z):=\left\{v\in\mathbb{R}^{n}\ \middle|\ \langle v,x-z\rangle\le o(\|x-z\|)\text{ for }x\in D\right\}.

the limiting normal cone is defined as

NDlim⁡(z):={v∈Rn | there exist sequences zk→Dz and vk→v with vk∈ND(zk)}.\mathcal{N}_{D}^{\lim}(z):=\left\{v\in\mathbb{R}^{n}\ \middle|\ \text{there exist sequences }z^{k}\xrightarrow[D]{}z\text{ and }v^{k}\to v\text{ with }v^{k}\in\mathcal{N}_{D}(z^{k})\right\}.

We set ND(z)=∅\mathcal{N}_{D}(z)=\varnothing and NDlim⁡(z)=∅\mathcal{N}_{D}^{\lim}(z)=\varnothing if z∉Dz\notin D. Note that the limiting normal cone is stable in the sense that

lim sup⁡z→zˉNDlim⁡(z)=NDlim⁡(zˉ),∀ zˉ∈D.(2)\limsup_{z\to\bar{z}}\mathcal{N}_{D}^{\lim}(z)=\mathcal{N}_{D}^{\lim}(\bar{z}),\quad\forall\ \bar{z}\in D. \tag*{(2)}

When DD is convex, the limiting normal cone coincides with the corresponding standard normal cone, i.e., for $z\in D,

NDlim⁡(z)=ND(z):={v∈Rn | ⟨v,x−z⟩≤0, ∀ x∈D}.\mathcal{N}_{D}^{\lim}(z)=\mathcal{N}_{D}(z):=\left\{v\in\mathbb{R}^{n}\ \middle|\ \langle v,x-z\rangle\le0,\ \forall\ x\in D\right\}.

Let us first specify the stationarity concepts for the original problem. These provide the reference conditions for the reformulations and the convergence analysis. In this manuscript, we denote the feasible set of (P) by F:={x∈D:G(x)∈C}\mathcal{F}:=\{x\in D:G(x)\in C\}.

Definition 2.1. A point xˉ∈F\bar{x}\in\mathcal{F} is called an M (Mordukhovich)-stationary point for (P) if there exists λ∈Rm\lambda\in\mathbb{R}^{m} such that

0∈∇f(xˉ)+∇G(xˉ)Tλ+NDlim⁡(xˉ),λ∈NC(G(xˉ)).(3)0\in\nabla f(\bar{x})+\nabla G(\bar{x})^{\mathsf{T}}\lambda+\mathcal{N}_{D}^{\lim}(\bar{x}),\quad\lambda\in\mathcal{N}_{C}(G(\bar{x})). \tag*{(3)}

Definition 2.2. A point xˉ∈F\bar{x}\in\mathcal{F} is called an AM (asymptotically Mordukhovich)-stationary point of (P) if there exist sequences {xk}\{x^{k}\}, {ϵk}⊂Rn\{\epsilon^{k}\}\subset\mathbb{R}^{n} and {λk}\{\lambda^{k}\}, {zk}⊂Rm\{z^{k}\}\subset\mathbb{R}^{m} such that xk→xˉx^{k}\to\bar{x}, ϵk→0\epsilon^{k}\to0, zk→0z^{k}\to0, and for all k∈Nk\in\mathbb{N},

ϵk∈∇f(xk)+∇G(xk)Tλk+NDlim⁡(xk),λk∈NC(G(xk)−zk).(4)\epsilon^{k}\in\nabla f(x^{k})+\nabla G(x^{k})^{\mathsf{T}}\lambda^{k}+\mathcal{N}_{D}^{\lim}(x^{k}),\quad\lambda^{k}\in\mathcal{N}_{C}(G(x^{k})-z^{k}). \tag*{(4)}

Note that M-stationarity obviously implies AM-stationarity. The converse is ensured by the following constraint qualification; see [8 Section 2.2].

Definition 2.3. A point xˉ∈F\bar{x} \in\mathcal{F} of (P) is AM-regular if

lim sup⁡x→xˉz→0M(x,z)⊆M(xˉ,0),(5)\limsup_{\substack{x \to\bar{x}\\ z \to0}} \mathcal{M}(x,z) \subseteq\mathcal{M}(\bar{x},0), \tag*{(5)}

where M:Rn×Rm⇉Rn\mathcal{M} : \mathbb{R}^{n} \times\mathbb{R}^{m} \rightrightarrows\mathbb{R}^{n} is the set-valued mapping defined by

M(x,z):=∇G(x)TNC(G(x)−z)+NDlim⁡(x).\mathcal{M}(x,z) := \nabla G(x)^{\mathsf{T}}N_{C}(G(x)-z)+N_{D}^{\lim}(x).

As illustrated in [9, 16, 17, 18], a constraint qualification is typically required for the analysis of constraint dissolving methods. As shown in [9 Lemma 2.15], AM-regularity is weaker than the constraint qualification employed in [16, 17, 18]. We now state some assumptions required for our analysis.

Assumption 1 (Properties of the optimization problem (P)).

(i) f:Rn→Rf : \mathbb{R}^{n} \to\mathbb{R} and G:Rn→RmG : \mathbb{R}^{n} \to\mathbb{R}^{m} are continuously differentiable.

(ii) C⊆RmC \subseteq\mathbb{R}^{m} is nonempty, closed, and convex. D⊆RnD \subseteq\mathbb{R}^{n} is nonempty, closed, but not necessarily convex.

(iii) AM-regularity, as defined in Definition 2.3, holds at every feasible point.

Properties of constraint dissolving mappings

This subsection focuses on the definition and properties of the constraint dissolving mapping tailored for (Ps)(P_s). For convenience, we denote H(x,s):=G(x)−sH(x,s) := G(x)-s, K:=D×CK := D \times C, and Fs:={(x,s)∈K∣G(x)=s}\mathcal{F}_s := \{(x,s) \in K \mid G(x)=s\}.

Definition 2.4. A mapping A:K→Rn+m\mathcal{A} : K \to\mathbb{R}^{n+m} is called a constraint dissolving mapping for H(x,s)=0H(x,s)=0, if the following conditions hold.

(a) A\mathcal{A} is continuously differentiable.

(b) A(x,s)=(x,s)\mathcal{A}(x,s)=(x,s) holds for all (x,s)∈Fs(x,s) \in\mathcal{F}_s.

(c) For all (x,s)∈Fs(x,s) \in\mathcal{F}_s, ∇A(x,s)T∇H(x,s)T=0\nabla\mathcal{A}(x,s)^{\mathsf{T}}\nabla H(x,s)^{\mathsf{T}}=0.

Moreover, there exists a continuous mapping RA:K→R(n+m)×(n+m)\mathcal{R}_{\mathcal{A}} : K \to\mathbb{R}^{(n+m)\times(n+m)} such that:

(d) RA(x,s)=0\mathcal{R}_{\mathcal{A}}(x,s)=0 for all (x,s)∈Fs(x,s) \in\mathcal{F}_s;

(e) for any (x,s)∈Fs(x,s) \in\mathcal{F}_s, there exists ωx,s>0\omega_{x,s}>0 such that

(∇A(y,t)−In+m−RA(y,t))TNKlim⁡(y,t)={0}(6)\left(\nabla\mathcal{A}(y,t)-I_{n+m}-\mathcal{R}_{\mathcal{A}}(y,t)\right)^{\mathsf{T}}N_{K}^{\lim}(y,t)=\{0\} \tag*{(6)}

for all (y,t)∈K(y,t) \in K with ∥(y,t)−(x,s)∥≤ωx,s\lVert(y,t)-(x,s)\rVert\leq\omega_{x,s}.

Definition 2.4 generalizes the constraint dissolving mappings of [17, 18], which were developed for an equality constraint G(x)=0G(x)=0. In our setting, by contrast, the set CC can be an arbitrary nonempty, closed, and convex set. Moreover, whereas [18] additionally admits a constraint x∈Xx \in X with a convex set XX, we incorporate the geometric constraint x∈Dx \in D, where DD is allowed to be nonconvex. Therefore, the corresponding limiting normal cone is employed in (5).

Proposition 2.5. Let A\mathcal{A} be any constraint dissolving mapping satisfying Definition 2.4. For every (x,s)∈Fs(x,s) \in\mathcal{F}_s and (dx,ds)∈TFs(x,s)(d_x,d_s) \in T_{\mathcal{F}_s}(x,s), one has ∇A(x,s)(dx,ds)=(dx,ds)\nabla\mathcal{A}(x,s)(d_x,d_s)=(d_x,d_s).

Proof. For any (dx,ds)∈TFs(x,s)(d_x,d_s) \in T_{\mathcal{F}_s}(x,s) with (x,s)∈Fs(x,s) \in\mathcal{F}_s, there exists a sequence (xj,sj)∈Fs(x^j,s^j) \in\mathcal{F}_s and tj↓0t_j \downarrow0 such that (xj,sj)→(x,s)(x^j,s^j) \to(x,s) and

(xj,sj)−(x,s)tj→(dx,ds).(7)\frac{(x^j,s^j)-(x,s)}{t_j} \to(d_x,d_s). \tag*{(7)}

By differentiability of A\mathcal{A} as in Definition 2.4 (a), one has

A(xj,sj)−A(x,s)=∇A(x,s)((xj,sj)−(x,s))+o(∥(xj,sj)−(x,s)∥).(8)\mathcal{A}(x^j,s^j)-\mathcal{A}(x,s)=\nabla\mathcal{A}(x,s)\left((x^j,s^j)-(x,s)\right)+o\left(\left\|(x^j,s^j)-(x,s)\right\|\right). \tag*{(8)}

Definition 2.4(b) gives A(xj,sj)−A(x,s)=(xj,sj)−(x,s)\mathcal{A}(x^j,s^j)-\mathcal{A}(x,s)=(x^j,s^j)-(x,s). Dividing it by tjt_j, then (6) and (7) yield the assertion.

The following result shows that if xˉ\bar{x} satisfies AM-regularity, then the analogous regularity condition, formulated in terms of the set-valued mapping (x,s)↦Range⁡(∇H(x,s)T)+NKlim⁡(x,s)(x,s)\mapsto\operatorname{Range}(\nabla H(x,s)^\mathsf{T})+\mathcal{N}^{\lim}_K(x,s), holds at the pair (xˉ,G(xˉ))(\bar{x},G(\bar{x})).

Lemma 2.6. If xˉ∈F\bar{x}\in\mathcal{F} is AMAM-regular for (P), then one has

lim sup⁡(x,s)→(xˉ,G(xˉ))M^(x,s)⊆M^(xˉ,G(xˉ)),\limsup_{(x,s)\to(\bar{x},G(\bar{x}))}\widehat{\mathcal{M}}(x,s)\subseteq\widehat{\mathcal{M}}(\bar{x},G(\bar{x})),

where

M^(x,s):=Range⁡(∇H(x,s)T)+NKlim⁡(x,s).(9)\widehat{\mathcal{M}}(x,s):=\operatorname{Range}(\nabla H(x,s)^\mathsf{T})+\mathcal{N}^{\lim}_K(x,s). \tag*{(9)}

Proof. Let us take any (a,b)∈lim sup⁡(x,s)→(xˉ,G(xˉ))M^(x,s)(a,b)\in\limsup_{(x,s)\to(\bar{x},G(\bar{x}))}\widehat{\mathcal{M}}(x,s), then there exist sequences {(xk,sk)}⊂K\{(x^k,s^k)\}\subset K and {(ak,bk)}\{(a^k,b^k)\} satisfying (xk,sk)→(xˉ,G(xˉ))(x^k,s^k)\to(\bar{x},G(\bar{x})) and (ak,bk)→(a,b)(a^k,b^k)\to(a,b), such that (ak,bk)∈M^(xk,sk)(a^k,b^k)\in\widehat{\mathcal{M}}(x^k,s^k). For any k∈Nk\in\mathbb{N}, by [13 Proposition 6.41], there exist λk∈Rm\lambda^k\in\mathbb{R}^m, uk∈NDlim⁡(xk)u^k\in\mathcal{N}^{\lim}_D(x^k) and vk∈NC(sk)v^k\in\mathcal{N}_C(s^k) such that ak=∇G(xk)Tλk+uka^k=\nabla G(x^k)^\mathsf{T}\lambda^k+u^k and bk=−λk+vkb^k=-\lambda^k+v^k. Consequently,

ak+∇G(xk)Tbk=∇G(xk)Tvk+uk∈M(xk,zk) with zk:=G(xk)−sk.a^k+\nabla G(x^k)^\mathsf{T}b^k=\nabla G(x^k)^\mathsf{T}v^k+u^k\in\mathcal{M}(x^k,z^k)\text{ with }z^k:=G(x^k)-s^k.

By the continuity of GG, we have zk→0z^k\to0. Then the continuity of ∇G\nabla G and AM-regularity at xˉ\bar{x} yield a+∇G(xˉ)Tb∈M(xˉ,0)=∇G(xˉ)TNC(G(xˉ))+NDlim⁡(xˉ)a+\nabla G(\bar{x})^\mathsf{T}b\in\mathcal{M}(\bar{x},0)=\nabla G(\bar{x})^\mathsf{T}\mathcal{N}_C(G(\bar{x}))+\mathcal{N}^{\lim}_D(\bar{x}). Thus, there exists v∈NC(G(xˉ))v\in\mathcal{N}_C(G(\bar{x})) and u∈NDlim⁡(xˉ)u\in\mathcal{N}^{\lim}_D(\bar{x}) such that a+∇G(xˉ)Tb=∇G(xˉ)Tv+ua+\nabla G(\bar{x})^\mathsf{T}b=\nabla G(\bar{x})^\mathsf{T}v+u. Let us set ξ:=v−b∈Rm\xi:=v-b\in\mathbb{R}^m, then we have a=∇G(xˉ)Tξ+ua=\nabla G(\bar{x})^\mathsf{T}\xi+u and b=−ξ+vb=-\xi+v, it follows from [13 Proposition 6.41] that (a,b)∈M^(xˉ,G(xˉ))(a,b)\in\widehat{\mathcal{M}}(\bar{x},G(\bar{x})). Therefore, the assertion holds.

Remark 2.7. To be consistent with the form of Definition 2.3, the set-valued mapping associated with the constraints H(x,s)=0H(x,s)=0 and (x,s)∈K(x,s)\in K would read

M^((x,s),z):=∇H(x,s)TN{0}(H(x,s)−z)+NKlim⁡(x,s),\widehat{\mathcal{M}}((x,s),z):=\nabla H(x,s)^\mathsf{T}\mathcal{N}_{\{0\}}(H(x,s)-z)+\mathcal{N}^{\lim}_K(x,s),

where the role of zz is to ensure that H(x,s)−z=0H(x,s)-z=0 and consequently N{0}(H(x,s)−z)=Rm\mathcal{N}_{\{0\}}(H(x,s)-z)=\mathbb{R}^m. In this way, the auxiliary variable zz can be eliminated, thus, for convenience, we adopt the simplified form (8).

By [11 Theorem 3.16], we directly have the following result.

Lemma 2.8. If x∈Fx\in\mathcal{F} is AMAM-regular, then one has

NFslim⁡(x,G(x))⊆Range⁡(∇H(x,G(x))T)+NKlim⁡(x,G(x)).(10)\mathcal{N}^{\lim}_{\mathcal{F}_s}(x,G(x))\subseteq\operatorname{Range}(\nabla H(x,G(x))^\mathsf{T})+\mathcal{N}^{\lim}_K(x,G(x)). \tag*{(10)}

Meanwhile, we have the following results.

Proposition 2.9. Let Assumption 1 hold and A\mathcal{A} satisfy Definition 2.4. For any (x,s)∈Fs(x,s)\in\mathcal{F}_s, one has

(i) ∇A(x,s)TRange⁡(∇H(x,s)T)={0}\nabla\mathcal{A}(x,s)^\mathsf{T}\operatorname{Range}(\nabla H(x,s)^\mathsf{T})=\{0\},

(ii) (∇A(x,s)−In+m)TNKlim⁡(x,s)={0}(\nabla\mathcal{A}(x,s)-I_{n+m})^\mathsf{T}\mathcal{N}^{\lim}_K(x,s)=\{0\},

(iii) ∇A(x,s)T(Range⁡(∇H(x,s)T)+NKlim⁡(x,s))=NKlim⁡(x,s)\nabla\mathcal{A}(x,s)^\mathsf{T}\left(\operatorname{Range}(\nabla H(x,s)^\mathsf{T})+\mathcal{N}^{\lim}_K(x,s)\right)=\mathcal{N}^{\lim}_K(x,s).

Moreover, for any w∈Rn+mw \in\mathbb{R}^{n+m}, one has

0∈∇A(x,s)⊤w+NKlim⁡(x,s)⟹∇A(x,s)⊤w−w∈Range⁡(∇H(x,s)⊤).0 \in\nabla A(x,s)^{\top}w + N_{K}^{\lim}(x,s) \Longrightarrow\nabla A(x,s)^{\top}w-w \in\operatorname{Range}(\nabla H(x,s)^{\top}).

Proof. The identities (i) and (ii) follow from Definition 2.4 (c)-(e). The identity (iii) is the direct consequence of (i) and (ii). For any w∈Rn+mw \in\mathbb{R}^{n+m} satisfying 0∈∇A(x,s)⊤w+NKlim⁡(x,s)0 \in\nabla A(x,s)^{\top}w + N_{K}^{\lim}(x,s), we have −∇A(x,s)⊤w∈NKlim⁡(x,s)-\nabla A(x,s)^{\top}w \in N_{K}^{\lim}(x,s). Then (ii) yields

(∇A(x,s)⊤)2w=∇A(x,s)⊤w.(11)\left(\nabla A(x,s)^{\top}\right)^2w=\nabla A(x,s)^{\top}w. \tag*{(11)}

For every d∈TFs(x,s)d \in T_{\mathcal{F}_s}(x,s), Proposition 2.5 gives ⟨d,∇A(x,s)⊤w−w⟩=⟨(∇A(x,s)−In+m)d,w⟩=0\langle d,\nabla A(x,s)^{\top}w-w\rangle=\langle(\nabla A(x,s)-I_{n+m})d,w\rangle=0. It implies that

∇A(x,s)⊤w−w∈(TFs(x,s))∘⊆NFslim⁡(x,s)⊆Range⁡(∇H(x,s)⊤)+NKlim⁡(x,s).\nabla A(x,s)^{\top}w-w\in\left(T_{\mathcal{F}_s}(x,s)\right)^\circ\subseteq N_{\mathcal{F}_s}^{\lim}(x,s)\subseteq\operatorname{Range}(\nabla H(x,s)^{\top})+N_{K}^{\lim}(x,s).

where the last inclusion is from Lemma 2.8. Then there exist some λ∈Rm\lambda\in\mathbb{R}^{m} and q∈NKlim⁡(x,s)q \in N_{K}^{\lim}(x,s) such that ∇A(x,s)⊤w−w=∇H(x,s)⊤λ+q\nabla A(x,s)^{\top}w-w=\nabla H(x,s)^{\top}\lambda+q. By (10), (i), and (ii), we have q=0q=0 and thus ∇A(x,s)⊤w−w=∇H(x,s)⊤λ∈Range⁡(∇H(x,s)⊤)\nabla A(x,s)^{\top}w-w=\nabla H(x,s)^{\top}\lambda\in\operatorname{Range}(\nabla H(x,s)^{\top}).

Based on Proposition 2.9, taking the same argument as the proof in [9 Theorem 2.8] directly implies the following result.

Theorem 2.10. Let Assumption 1 hold and A\mathcal{A} satisfy Definition 2.4. For any (x,s)∈Fs(x,s)\in\mathcal{F}_s and w∈Rn+mw\in\mathbb{R}^{n+m}, one has

0∈∇A(x,s)⊤w+NKlim⁡(x,s)⟺0∈w+Range⁡(∇H(x,s)⊤)+NKlim⁡(x,s).0\in\nabla A(x,s)^{\top}w+N_{K}^{\lim}(x,s)\Longleftrightarrow0\in w+\operatorname{Range}(\nabla H(x,s)^{\top})+N_{K}^{\lim}(x,s).

Relationships between stationarities

As illustrated above, the constraint dissolving mapping employed in this manuscript is jointly with the original variable xx and slack variable ss. For the convenience of analysis, we partition the constraint dissolving mapping A(x,s)\mathcal{A}(x,s) with respect to the blocks xx and ss, namely,

A(x,s)=(Ax(x,s),As(x,s)),\mathcal{A}(x,s)=(\mathcal{A}_x(x,s),\mathcal{A}_s(x,s)),

where Ax(x,s)∈Rn\mathcal{A}_x(x,s)\in\mathbb{R}^{n} and As(x,s)∈Rm\mathcal{A}_s(x,s)\in\mathbb{R}^{m}. Then, by Definition 2.4, Ax\mathcal{A}_x and As\mathcal{A}_s satisfy, in particular, the following properties:

  • (i) Ax\mathcal{A}_x and As\mathcal{A}_s are continuously differentiable.

  • (ii) Ax(x,s)=x\mathcal{A}_x(x,s)=x and As(x,s)=s\mathcal{A}_s(x,s)=s for all (x,s)∈Fs(x,s)\in\mathcal{F}_s.

Moreover, the Jacobian of A(x,s)\mathcal{A}(x,s) admits

∇A(x,s)=[∇xAx(x,s)∇sAx(x,s)∇xAs(x,s)∇sAs(x,s)].\nabla A(x,s)= \begin{bmatrix} \nabla_x\mathcal{A}_x(x,s) & \nabla_s\mathcal{A}_x(x,s)\\ \nabla_x\mathcal{A}_s(x,s) & \nabla_s\mathcal{A}_s(x,s) \end{bmatrix}.

Based on the above notation, we consider the following constraint dissolving problem associated with (P)

min⁡x∈D,  s∈C hβ(x,s):=f(Ax(x,s))+β2∥G(x)−s∥2,(12)\min_{x\in D,\;s\in C}\ h_\beta(x,s):=f(\mathcal{A}_x(x,s))+\frac{\beta}{2}\lVert G(x)-s\rVert^2, \tag*{(12)}

where β>0\beta>0 is a penalty parameter.

In order to solve (P) via (Q), it seems to be necessary to derive the equivalence of (M-)stationary points between (P) and (Q). To this end, we first introduce the some notation for convenience and then present the notion of stationarity for (Q). Let us define

gx(x,s):=∇xAx(x,s)⊤∇f(Ax(x,s)),g_x(x,s) := \nabla_x\mathcal{A}_x(x,s)^\top\nabla f(\mathcal{A}_x(x,s)),
gs(x,s):=∇sAx(x,s)⊤∇f(Ax(x,s)),g_s(x,s) := \nabla_s\mathcal{A}_x(x,s)^\top\nabla f(\mathcal{A}_x(x,s)),
g(x,s):=(gx(x,s)gs(x,s))=∇A(x,s)⊤(∇f(Ax(x,s))0m×1).(13)g(x,s) := \begin{pmatrix} g_x(x,s) \\ g_s(x,s) \end{pmatrix} = \nabla\mathcal{A}(x,s)^\top \begin{pmatrix} \nabla f(\mathcal{A}_x(x,s)) \\ 0_{m\times1} \end{pmatrix}. \tag*{(13)}

The chain rule yields the two gradients

∇xhβ(x,s)=gx(x,s)+β∇G(x)⊤(G(x)−s),\nabla_x h_\beta(x,s) = g_x(x,s) + \beta\nabla G(x)^\top(G(x)-s),
∇shβ(x,s)=gs(x,s)−β(G(x)−s).(14)\nabla_s h_\beta(x,s) = g_s(x,s) - \beta(G(x)-s). \tag*{(14)}

We denote their column concatenation by ∇hβ(x,s)\nabla h_\beta(x,s).

Definition 2.11. A pair (xˉ,sˉ)∈K(\bar{x},\bar{s}) \in K is M-stationary for (Q) if

0∈∇xhβ(xˉ,sˉ)+NDlim⁡(xˉ)and0∈∇shβ(xˉ,sˉ)+NC(sˉ).(15)0 \in\nabla_x h_\beta(\bar{x},\bar{s})+\mathcal{N}^{\lim}_D(\bar{x}) \quad\text{and}\quad0 \in\nabla_s h_\beta(\bar{x},\bar{s})+\mathcal{N}_C(\bar{s}). \tag*{(15)}

Theorem 2.12. Let Assumption 1 hold and A\mathcal{A} be a constraint dissolving mapping satisfying Definition 2.3. For any β>0\beta>0 and xˉ∈F\bar{x}\in F, one has

xˉ is M-stationary for (P)⟺(xˉ,G(xˉ)) is M-stationary for (Q).\bar{x}\text{ is M-stationary for (P)} \Longleftrightarrow(\bar{x},G(\bar{x}))\text{ is M-stationary for (Q)}.

Proof. Since xˉ∈F\bar{x}\in F, we have (xˉ,G(xˉ))∈Fs(\bar{x},G(\bar{x}))\in F_s, and thus Ax(xˉ,G(xˉ))=xˉ\mathcal{A}_x(\bar{x},G(\bar{x}))=\bar{x}. Hence, by Definition 2.11, (xˉ,G(xˉ))(\bar{x},G(\bar{x})) is an M-stationary point of (Q) if and only if

0∈∇A(xˉ,G(xˉ))⊤(∇f(xˉ)0m)+NKlim⁡(xˉ,G(xˉ)).0 \in\nabla\mathcal{A}(\bar{x},G(\bar{x}))^\top \begin{pmatrix} \nabla f(\bar{x}) \\ 0_m \end{pmatrix} +\mathcal{N}^{\lim}_K(\bar{x},G(\bar{x})).

By Theorem 2.10, this is equivalent to

0∈(∇f(xˉ)0m)+Range⁡(∇G(xˉ)⊤−Im)+(NDlim⁡(xˉ)NC(G(xˉ))).(16)0 \in \begin{pmatrix} \nabla f(\bar{x}) \\ 0_m \end{pmatrix} +\operatorname{Range} \begin{pmatrix} \nabla G(\bar{x})^\top\\ -I_m \end{pmatrix} +\begin{pmatrix} \mathcal{N}^{\lim}_D(\bar{x}) \\ \mathcal{N}_C(G(\bar{x})) \end{pmatrix}. \tag*{(16)}

On the other hand, xˉ\bar{x} is an M-stationary point of (P) if and only if there exists some λ∈Rm\lambda\in\mathbb{R}^m such that

0∈(∇f(xˉ)0m)+(∇G(xˉ)⊤−Im)λ+(NDlim⁡(xˉ)NC(G(xˉ))),(17)0 \in \begin{pmatrix} \nabla f(\bar{x}) \\ 0_m \end{pmatrix} +\begin{pmatrix} \nabla G(\bar{x})^\top\\ -I_m \end{pmatrix}\lambda +\begin{pmatrix} \mathcal{N}^{\lim}_D(\bar{x}) \\ \mathcal{N}_C(G(\bar{x})) \end{pmatrix}, \tag*{(17)}

where the second block of (15) reads exactly λ∈NC(G(xˉ))\lambda\in\mathcal{N}_C(G(\bar{x})). Since

Range⁡(∇G(xˉ)⊤−Im)={(∇G(xˉ)⊤−Im)ξ: ξ∈Rm},\operatorname{Range}\begin{pmatrix} \nabla G(\bar{x})^\top\\ -I_m \end{pmatrix} = \left\{ \begin{pmatrix} \nabla G(\bar{x})^\top\\ -I_m \end{pmatrix}\xi:\ \xi\in\mathbb{R}^m \right\},

(14) holds if and only if there exists λ∈Rm\lambda\in\mathbb{R}^m such that (15) holds. Therefore, xˉ\bar{x} is an M-stationary point of (P) if and only if (xˉ,G(xˉ))(\bar{x},G(\bar{x})) is an M-stationary point of (Q). □\square

Algorithm

Leveraging the equivalence of M-stationarity between (P) and (Ps)(P_s), this section develops a penalty-based constraint dissolving method for solving (Ps)(P_s) and establishes its corresponding convergence analysis. The overall algorithm is presented in Algorithm 1.

Algorithm 1: A constraint dissolving method with adaptive penalty

Require: β0>0\beta_0 > 0, η∈(0,1)\eta\in(0,1), τ>1\tau> 1, x0∈Dx^0 \in D, and s0=G(x0)s^0 = G(x^0).

  1. Set k:=0k := 0.

  2. while xkx^k does not satisfy a termination criterion do

  3. Compute an approximate M-stationary point (xk+1,sk+1)(x^{k+1},s^{k+1}) of the subproblem

min⁡x,s hβk(x,s)\min_{x,s}\ h_{\beta_k}(x,s)
s.t. s∈C,x∈D,(18)\text{s.t. } s \in C, x \in D, \tag*{(18)}

i.e., there exist εxk+1∈Rn\varepsilon_x^{k+1} \in\mathbb{R}^n and εsk+1∈Rm\varepsilon_s^{k+1} \in\mathbb{R}^m such that

εxk+1∈∇xhβk(xk+1,sk+1)+NDlim⁡(xk+1),\varepsilon_x^{k+1} \in\nabla_x h_{\beta_k}(x^{k+1},s^{k+1}) + N_D^{\lim}(x^{k+1}),
εsk+1∈∇shβk(xk+1,sk+1)+NC(sk+1).(19)\varepsilon_s^{k+1} \in\nabla_s h_{\beta_k}(x^{k+1},s^{k+1}) + N_C(s^{k+1}). \tag*{(19)}
  1. if k=0k = 0 or ∥G(xk+1)−sk+1∥≤η∥G(xk)−sk∥\lVert G(x^{k+1}) - s^{k+1}\rVert\leq\eta\lVert G(x^k) - s^k\rVert then

  2. βk+1:=βk\beta_{k+1} := \beta_k

  3. else

  4. βk+1:=τβk\beta_{k+1} := \tau\beta_k

  5. end if

  6. Set k:=k+1k := k + 1.

  7. end while

  8. return xkx^k

Remark 3.1. (i) Step 3 requires the subproblem (16) to be solved inexactly, for which we employ projected gradient descent method proposed in [8 Algorithm 3.1] whose either last iterate or any accumulation point is M-stationary.

(ii) Regarding the penalty parameter βk\beta_k, it is updated in a nondecreasing manner according to the infeasibility measurement with respect to (Q). This is in contrast to [18], where a fixed (large enough) penalty parameter is adopted, and [9], where the penalty parameter is allowed to vary dynamically but without any update rule.

We first present the feasibility analysis of the accumulation points generated by Algorithm 1.

Proposition 3.2. Let Assumption 1 hold, the mapping AA satisfy Definition 2.4, and {(xk,sk)}\{(x^k,s^k)\} be a sequence generated by Algorithm 1. Let (xˉ,sˉ)(\bar{x},\bar{s}) be any accumulation point of {(xk,sk)}\{(x^k,s^k)\}. If one of the following conditions holds:

(i) {βk}\{\beta_k\} is bounded, or

(ii) there exists some B∈RB \in\mathbb{R} such that hβk(xk+1,sk+1)≤Bh_{\beta_k}(x^{k+1},s^{k+1}) \leq B holds for all kk,

then (xˉ,sˉ)(\bar{x},\bar{s}) is feasible for (Ps)(P_s) and xˉ\bar{x} is feasible for (P)(P).

Proof. Let us choose an infinite index set K\mathcal{K} such that (xk,sk)→K(xˉ,sˉ)(x^k,s^k) \to_{\mathcal{K}} (\bar{x},\bar{s}). By (18) and the closedness of CC and DD, we have (xˉ,sˉ)∈D×C(\bar{x},\bar{s}) \in D \times C.

(i) If {βk}\{\beta_k\} is bounded, by the update rule of {βk}\{\beta_k\}, we have ∥G(xk)−sk∥→0\lVert G(x^k) - s^k\rVert\to0. The continuity of GG implies that G(xˉ)=sˉG(\bar{x}) = \bar{s}. It means that (xˉ,sˉ)(\bar{x},\bar{s}) is feasible for (Ps)(P_s). Furthermore, it implies that xˉ∈D\bar{x} \in D and G(xˉ)=sˉ∈CG(\bar{x}) = \bar{s} \in C, which means that xˉ\bar{x} is feasible for (P)(P).

(ii) By the definition of hβkh_{\beta_k} in (Q), we have

0≤∥G(xk)−sk∥2=2(hβk−1(xk,sk)−f(Ax(xk,sk)))βk−1≤2(B−f(Ax(xk,sk)))βk−1,∀k≥1.(20)0 \leq\lVert G(x^k) - s^k\rVert^2 = \frac{2\left(h_{\beta_{k-1}}(x^k,s^k) - f(A_x(x^k,s^k))\right)}{\beta_{k-1}} \leq\frac{2\left(B - f(A_x(x^k,s^k))\right)}{\beta_{k-1}}, \quad\forall k \geq1. \tag*{(20)}

Since (xk,sk)→K(xˉ,sˉ)∈D×C(x^k,s^k) \xrightarrow{\mathcal K} (\bar{x},\bar{s}) \in D \times C, the continuity of ff and AxA_x gives

f(Ax(xk,sk))→Kf(Ax(xˉ,sˉ))=f(xˉ).f(A_x(x^k,s^k)) \xrightarrow{\mathcal K} f(A_x(\bar{x},\bar{s})) = f(\bar{x}).

Thus, taking the limit k→K∞k \xrightarrow{\mathcal K} \infty in (20) yields that ∥G(xk)−sk∥→K0\lVert G(x^k)-s^k\rVert\xrightarrow{\mathcal K} 0. The continuity of GG further implies that G(xˉ)=sˉG(\bar{x})=\bar{s}. Therefore, by the same analysis as the case that {βk}\{\beta_k\} is bounded, we conclude that (xˉ,sˉ)(\bar{x},\bar{s}) is feasible for (Ps)(P_s) and xˉ\bar{x} is feasible for (P)(P).

Proposition 3.2 provides the sufficient conditions for the feasibility of accumulation points. As illustrated in [8, 9], (ii) holds, for example, if (xk+1,sk+1)(x^{k+1},s^{k+1}) is an (approximate) global minimizer of the subproblem (18). This, however, requires more restrictive assumption on model, for instance, hβ(x,s)h_{\beta}(x,s) is level bounded on KK [13 Example 1.11]. For the specific constraint dissolving mapping A(x,s)A(x,s) given by (27), every accumulation point is verified to be feasible under some mild conditions, see Lemma 4.4, without requiring (ii). However, under a general constraint dissolving mapping A(x,s)A(x,s), we can only obtain that every accumulation point is an M-stationary point of the constraint violation problem.

Proposition 3.3. Let Assumption 1 hold, the mapping AA satisfy Definition 2.4, and {(xk,sk)}\{(x^k,s^k)\} be a sequence generated by Algorithm 1. Let (xˉ,sˉ)(\bar{x},\bar{s}) be any accumulation point of {(xk,sk)}\{(x^k,s^k)\}. If {(εxk,εsk)}\{(\varepsilon_x^k,\varepsilon_s^k)\} is bounded, then (xˉ,sˉ)(\bar{x},\bar{s}) is M-stationary of

min⁡x∈D, s∈C 12∥G(x)−s∥2.(21)\min_{x\in D,\ s\in C}\ \frac{1}{2}\lVert G(x)-s\rVert^2 . \tag*{(21)}

Proof. As in the proof of Proposition 3.2, we take K\mathcal K is an infinite index set such that (xk,sk)→K(xˉ,sˉ)(x^k,s^k) \xrightarrow{\mathcal K} (\bar{x},\bar{s}). Let us first consider the case {βk}\{\beta_k\} is bounded, by Proposition 3.2, we have G(xˉ)=sˉG(\bar{x})=\bar{s}, which means that (xˉ,sˉ)(\bar{x},\bar{s}) is a global minimizer of (21) and hence its M-stationary point. It remains to consider the situation βk→∞\beta_k\to\infty. By (19), one has for all k≥1k\ge1,

εxk−gx(xk,sk)βk−1∈∇G(xk)T(G(xk)−sk)+NDlim⁡(xk),\frac{\varepsilon_x^k-g_x(x^k,s^k)}{\beta_{k-1}} \in\nabla G(x^k)^{\mathsf T}(G(x^k)-s^k)+N_D^{\lim}(x^k),
εsk−gs(xk,sk)βk−1∈−(G(xk)−sk)+NC(sk).\frac{\varepsilon_s^k-g_s(x^k,s^k)}{\beta_{k-1}} \in-(G(x^k)-s^k)+N_C(s^k).

By the boundedness of {(εxk,εsk)}\{(\varepsilon_x^k,\varepsilon_s^k)\}, continuity of ∇G\nabla G, GG, ∇A\nabla A and ∇f\nabla f, and the fact that NDlim⁡(⋅)N_D^{\lim}(\cdot) is robust, taking the limit k→K∞k \xrightarrow{\mathcal K} \infty implies that

0∈∇G(xˉ)T(G(xˉ)−sˉ)+NDlim⁡(xˉ),and0∈−(G(xˉ)−sˉ)+NC(sˉ).0 \in\nabla G(\bar{x})^{\mathsf T}(G(\bar{x})-\bar{s})+N_D^{\lim}(\bar{x}), \quad\text{and}\quad0 \in-(G(\bar{x})-\bar{s})+N_C(\bar{s}).

It means that (xˉ,sˉ)(\bar{x},\bar{s}) is an M-stationary point of (21).

Theorem 3.4. Let Assumption 1 hold, AA satisfy Definition 2.4, and {(xk,sk)}\{(x^k,s^k)\} be a sequence generated by Algorithm 1 with (εxk+1,εsk+1)→(0,0)(\varepsilon_x^{k+1},\varepsilon_s^{k+1})\to(0,0). Let (xˉ,sˉ)(\bar{x},\bar{s}) be any accumulation point of {(xk,sk)}\{(x^k,s^k)\} feasible for (Ps)(P_s). Then xˉ\bar{x} is an M-stationary point for (P)(P).

Proof. As in the proof of Proposition 3.2, we take K\mathcal K as an infinite index set such that (xk,sk)→K(xˉ,sˉ)(x^k,s^k) \xrightarrow{\mathcal K} (\bar{x},\bar{s}). By the feasibility of (xˉ,sˉ)(\bar{x},\bar{s}), we have sˉ=G(xˉ)\bar{s}=G(\bar{x}).

By employing (14), (19) reads

εxk∈gx(xk,sk)+βk−1∇G(xk)TH(xk,sk)+NDlim⁡(xk),\varepsilon_x^k \in g_x(x^k,s^k)+\beta_{k-1}\nabla G(x^k)^{\mathsf T}H(x^k,s^k)+N_D^{\lim}(x^k),
εsk∈gs(xk,sk)−βk−1H(xk,sk)+NC(sk),∀k≥1.\varepsilon_s^k \in g_s(x^k,s^k)-\beta_{k-1}H(x^k,s^k)+N_C(s^k), \quad\forall k\ge1.

It implies that

(εxkεsk)−g(xk,sk)∈Range⁡(∇G(xk)T−Im)+NKlim⁡(xk,sk),∀k≥1.\begin{pmatrix} \varepsilon_x^k\\ \varepsilon_s^k \end{pmatrix} -g(x^k,s^k) \in \operatorname{Range} \begin{pmatrix} \nabla G(x^k)^{\mathsf T}\\ -I_m \end{pmatrix} +N_{\mathcal K}^{\lim}(x^k,s^k), \quad\forall k\ge1.

In view of (13), Assumption 1, and Definition 2.4, Lemma 2.6 gives

0∈∇A(xˉ,sˉ)T(∇f(xˉ)0m)+Range⁡(∇G(xˉ)T−Im)+NKlim⁡(xˉ,sˉ).(22)0 \in\nabla A(\bar{x},\bar{s})^{\mathsf T} \begin{pmatrix} \nabla f(\bar{x})\\ 0_m \end{pmatrix} +\operatorname{Range} \begin{pmatrix} \nabla G(\bar{x})^{\mathsf T}\\ -I_m \end{pmatrix} +N_{\mathcal K}^{\lim}(\bar{x},\bar{s}). \tag*{(22)}

Let us recall that sˉ=G(xˉ)\bar{s}=G(\bar{x}), it follows from Theorem 2.12 that xˉ\bar{x} is an M-stationary point for (P)(P).

Implementation of constraint dissolving mappings for nonconvex sets

This section focuses on the construction of constraint dissolving mappings A(x,s)\mathcal{A}(x,s) satisfying Definition 2.4. To this end, we first present the motivation based on the idea from Fletcher [4].

Let us consider the following optimization problem

min⁡f(w)s.t.c(w)=0,w∈K,(23)\begin{aligned} \min\quad& f(w)\\ \text{s.t.}\quad& c(w)=0,\quad w\in K, \tag*{(23)} \end{aligned}

where ff and cc are continuously differentiable, and KK is nonempty, closed, and possibly nonconvex. For brevity, we do not specify the dimensions explicitly. All vectors, matrices and mappings are assumed to have compatible dimensions.

In order to solve (23), we alternatively solve

min⁡f(w)−c(w)Tλw+β2∥c(w)∥2s.t.w∈K,\begin{aligned} \min\quad& f(w)-c(w)^{\mathsf{T}}\lambda_w+\frac{\beta}{2}\lVert c(w)\rVert^2\\ \text{s.t.}\quad& w\in K, \end{aligned}

where λw\lambda_w is a Lagrangian multiplier. The objective function takes the form of Fletcher’s penalty function [4].

Moreover, under some constraint qualification, the optimality condition of (23) reads 0∈∇f(w)−∇c(w)Tλw+NKlim⁡(w)0\in\nabla f(w)-\nabla c(w)^{\mathsf{T}}\lambda_w+N_K^{\lim}(w). Then there exists some νw∈NKlim⁡(w)\nu_w\in N_K^{\lim}(w) such that

0=∇f(w)−∇c(w)Tλw+νw.(24)0=\nabla f(w)-\nabla c(w)^{\mathsf{T}}\lambda_w+\nu_w. \tag*{(24)}

In fact, the optimal λw\lambda_w depends on unknown normal vector νw\nu_w and hence cannot be evaluated. To remove the dependence on νw\nu_w, we assume that there exists a symmetric positive (semi)definite matrix QwQ_w such that Null⁡(Qw)=Span⁡(NKlim⁡(w))\operatorname{Null}(Q_w)=\operatorname{Span}(N_K^{\lim}(w)) (see Assumption 2 (b) for more general setting). Then we have Qwνw=0Q_w\nu_w=0. In this case, multiplying (24) by ∇c(w)Qw\nabla c(w)Q_w yields that

0=∇c(w)Qw∇f(w)−∇c(w)Qw∇c(w)Tλw.0=\nabla c(w)Q_w\nabla f(w)-\nabla c(w)Q_w\nabla c(w)^{\mathsf{T}}\lambda_w.

Under the condition that ∇c(w)Qw∇c(w)T\nabla c(w)Q_w\nabla c(w)^{\mathsf{T}} is invertible (a constraint qualification, like Assumption 3, seems to be necessary to ensure this assumption, see Lemma 4.2), one has

λw=(∇c(w)Qw∇c(w)T)−1∇c(w)Qw∇f(w).(25)\lambda_w=\left(\nabla c(w)Q_w\nabla c(w)^{\mathsf{T}}\right)^{-1}\nabla c(w)Q_w\nabla f(w). \tag*{(25)}

On the other hand, by employing the constraint dissolving method to solve (23), one has to solve

min⁡f(A(w))+β2∥c(w)∥2s.t.w∈K,\begin{aligned} \min\quad& f(\mathcal{A}(w))+\frac{\beta}{2}\lVert c(w)\rVert^2\\ \text{s.t.}\quad& w\in K, \end{aligned}

where A\mathcal{A} is a constraint dissolving mapping. From the perspective that constraint dissolving method incorporates the multiplier correlation term from Fletcher’s penalty function in [4] implicitly through the constraint dissolving mapping A\mathcal{A}, then f(A(w))≈f(w)−c(w)Tλwf(\mathcal{A}(w))\approx f(w)-c(w)^{\mathsf{T}}\lambda_w. Since ff is continuously differentiable, one has f(A(w))≈f(w)+⟨∇f(w),A(w)−w⟩f(\mathcal{A}(w))\approx f(w)+\langle\nabla f(w),\mathcal{A}(w)-w\rangle. By (25), it is reasonable to ask

⟨∇f(w),A(w)−w⟩=−c(w)T(∇c(w)Qw∇c(w)T)−1∇c(w)Qw∇f(w).\langle\nabla f(w),\mathcal{A}(w)-w\rangle=-c(w)^{\mathsf{T}}\left(\nabla c(w)Q_w\nabla c(w)^{\mathsf{T}}\right)^{-1}\nabla c(w)Q_w\nabla f(w).

Requiring this identity for every smooth objective ff, i.e., for arbitrary ∇f(w)\nabla f(w), leads to the candidate A(w)\mathcal{A}(w) as follows

A(w):=w−Qw∇c(w)T(∇c(w)Qw∇c(w)T)−1c(w).\mathcal{A}(w):=w-Q_w\nabla c(w)^{\mathsf{T}}\left(\nabla c(w)Q_w\nabla c(w)^{\mathsf{T}}\right)^{-1}c(w).

Motivated by the above analysis, we impose the following assumption.

Assumption 2. (a) GG is twice continuously differentiable.

(b) There exist continuously differentiable mappings QD\mathcal{Q}_D and QC\mathcal{Q}_C defined on some open set containing DD and CC, respectively, satisfying both QD(x)\mathcal{Q}_D(x) and QC(s)\mathcal{Q}_C(s) for all x∈Dx \in D and s∈Cs \in C are symmetric positive semidefinite such that

Null⁡(QD(x))=Span⁡(NDlim⁡(x)),x∈D,\operatorname{Null}(\mathcal{Q}_D(x)) = \operatorname{Span}\left(\mathcal{N}^{\lim}_D(x)\right), \quad x \in D,
Null⁡(QC(s))=Span⁡(NC(s)),s∈C.\operatorname{Null}(\mathcal{Q}_C(s)) = \operatorname{Span}\left(\mathcal{N}_C(s)\right), \quad s \in C.

For several widely-used classes of DD, including disjunctive, sparsity, low-rank-, low-rank positive semidefinite constraints, suitable choices of QD\mathcal{Q}_D has been summarized in [9 Table 1]. Moreover, CC is usually given by a box-constraint, the corresponding choice of QC\mathcal{Q}_C can be found in [18 Table 2]. We refer interested readers to these references for more details.

For a fixed α>0\alpha> 0, let us define

Q(x,s):=(QD(x)00QC(s)),\mathcal{Q}(x,s) := \begin{pmatrix} \mathcal{Q}_D(x) & 0 \\ 0 & \mathcal{Q}_C(s) \end{pmatrix},
M0(x,s):=∇H(x,s)Q(x,s)∇H(x,s)T=∇G(x)QD(x)∇G(x)T+QC(s),(26)M_0(x,s) := \nabla H(x,s)\mathcal{Q}(x,s)\nabla H(x,s)^{\mathsf{T}} = \nabla G(x)\mathcal{Q}_D(x)\nabla G(x)^{\mathsf{T}} + \mathcal{Q}_C(s), \tag*{(26)}
M(x,s):=M0(x,s)+α∥H(x,s)∥2Im.M(x,s) := M_0(x,s) + \alpha\lVert H(x,s)\rVert^2 I_m.

Based on the above notation, for (x,s)∈K(x,s) \in K, we define

A(x,s):=(x,s)−Q(x,s)∇H(x,s)TM(x,s)−1H(x,s),(27)\mathcal{A}(x,s) := (x,s) - \mathcal{Q}(x,s)\nabla H(x,s)^{\mathsf{T}}M(x,s)^{-1}H(x,s), \tag*{(27)}

Note that M0(x,s)M_0(x,s) is positive definite on KK under some constraint qualification (see Lemma 4.2); however, it may be nearly singular. The regularization term α∥H(x,s)∥2Im\alpha\lVert H(x,s)\rVert^2 I_m alleviates this issue. Indeed, for every (x,s)∈K∖Fs(x,s) \in K \setminus\mathcal{F}_s,

∥M(x,s)−1H(x,s)∥≤∥H(x,s)∥λmin⁡(M0(x,s))+α∥H(x,s)∥2≤1α∥H(x,s)∥,\lVert M(x,s)^{-1}H(x,s)\rVert\leq\frac{\lVert H(x,s)\rVert}{\lambda_{\min}(M_0(x,s))+\alpha\lVert H(x,s)\rVert^2} \leq\frac{1}{\alpha\lVert H(x,s)\rVert},

independent of λmin⁡(M0(x,s))\lambda_{\min}(M_0(x,s)). However, this term vanishes on Fs\mathcal{F}_s regardless of the value of α\alpha, so that M(x,s)=M0(x,s)M(x,s)=M_0(x,s) there.

We next present a counterexample showing that the AM-regularity, introduced in Definition 2.3 and used in the preceding sections, is not sufficient to guarantee the positive definiteness of M0(x,s)M_0(x,s) and M(x,s)M(x,s) on KK.

Example 4.1. Let n=1n=1, m=2m=2, f≡0f\equiv0, D=RD=\mathbb{R}, C=R−2C=\mathbb{R}^2_-, and G(x)=(x,−x)TG(x)=(x,-x)^{\mathsf{T}}. Then F={0}\mathcal{F}=\{0\} and Fs={(0,(0,0))}\mathcal{F}_s=\{(0,(0,0))\}. The point xˉ=0\bar{x}=0 is AM-regular. Indeed, since NDlim⁡(x)≡{0}\mathcal{N}^{\lim}_D(x)\equiv\{0\}, we have M(x,z)={λ1−λ2:λ∈NC(G(x)−z)}\mathcal{M}(x,z)=\{\lambda_1-\lambda_2:\lambda\in\mathcal{N}_C(G(x)-z)\}. By NC((0,0))=R+2\mathcal{N}_C((0,0))=\mathbb{R}^2_+, we have M(0,0)=R\mathcal{M}(0,0)=\mathbb{R}, then lim sup⁡x→0, z→0M(x,z)⊆M(0,0)\limsup_{x\to0,\ z\to0}\mathcal{M}(x,z)\subseteq\mathcal{M}(0,0) holds trivially. On the other hand, to ensure Assumption 2 (b), we set QC(0)=0\mathcal{Q}_C(0)=0 and choose QD(0)=1\mathcal{Q}_D(0)=1. By ∇G(x)≡(1,−1)T\nabla G(x)\equiv(1,-1)^{\mathsf{T}} and H(0,(0,0))=0H(0,(0,0))=0, for every α≥0\alpha\geq0, we have

M(0,(0,0))=M0(0,(0,0))=∇G(0)∇G(0)T=(1−1−11),M(0,(0,0))=M_0(0,(0,0))=\nabla G(0)\nabla G(0)^{\mathsf{T}}=\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix},

which is singular. Therefore, AM-regularity is not sufficient to ensure that M(x,s)M(x,s) is positive definite on Fs\mathcal{F}_s.

Therefore, a stronger constraint qualification is needed to ensure M0(x,s)≻0M_0(x,s)\succ0 and thus M(x,s)≻0M(x,s)\succ0 for every (x,s)∈K(x,s)\in K. To this end, we impose the following condition, which generalizes the Robinson nondegeneracy condition [12 Definition 2.1, (2.3)]. In particular, the two conditions coincide when CC and DD are two polyhedral convex sets.

Assumption 3. At any (x,s)∈K(x,s)\in K, d=0d=0 is the only vector d∈Rmd\in\mathbb{R}^m satisfying

∇G(x)Td∈Span⁡(NDlim⁡(x))andd∈Span⁡(NC(s)).\nabla G(x)^{\mathsf{T}}d\in\operatorname{Span}\left(\mathcal{N}^{\lim}_D(x)\right)\quad\text{and}\quad d\in\operatorname{Span}\left(\mathcal{N}_C(s)\right).

Lemma 4.2. Suppose that Assumption 2 and Assumption 3 hold, M0(x,s)≻0M_0(x,s) \succ0 and thus M(x,s)≻0M(x,s) \succ0 at every (x,s)∈K(x,s) \in K. Moreover, every xˉ∈F\bar{x} \in F is AM-regular.

Proof. For any (x,s)∈K(x,s) \in K, as well as d∈Rmd \in\mathbb{R}^{m},

dTM0(x,s)d=(∇G(x)Td)TQD(x)(∇G(x)Td)+dTQC(s)d≥0.d^{\mathsf{T}}M_0(x,s)d = \left(\nabla G(x)^{\mathsf{T}}d\right)^{\mathsf{T}}Q_D(x)\left(\nabla G(x)^{\mathsf{T}}d\right) + d^{\mathsf{T}}Q_C(s)d \ge0.

Hence M0(x,s)⪰0M_0(x,s) \succeq0 for all (x,s)∈K(x,s) \in K.

Now suppose dTM0(x,s)d=0d^{\mathsf{T}}M_0(x,s)d = 0. Then the positive semidefiniteness of QD(x)Q_D(x) and QC(s)Q_C(s) implies

∇G(x)Td∈Null⁡(QD(x)),d∈Null⁡(QC(s)).\nabla G(x)^{\mathsf{T}}d \in\operatorname{Null}(Q_D(x)), \quad d \in\operatorname{Null}(Q_C(s)).

By Assumption 2 (b) and Assumption 3, one has d=0d = 0. Thus M0(x,s)≻0M_0(x,s) \succ0 for all (x,s)∈K(x,s) \in K. Since α∥H(x,s)∥2Im⪰0\alpha\lVert H(x,s)\rVert^2 I_m \succeq0 by α>0\alpha> 0, M(x,s)≻0M(x,s) \succ0 for all (x,s)∈K(x,s) \in K.

For any xˉ∈F\bar{x} \in F, fix some ξ∈lim sup⁡x→xˉ,z→0M(x,z)\xi\in\limsup_{x \to\bar{x},z \to0} M(x,z). Then we find sequences {xk}⊂Rn\{x^k\} \subset\mathbb{R}^n, {ξk}⊂Rn\{\xi^k\} \subset\mathbb{R}^n, and {zk}⊂Rm\{z^k\} \subset\mathbb{R}^m such that xk→Dxˉx^k \to_D \bar{x}, ξk→ξ\xi^k \to\xi, zk→0z^k \to0, and ξk∈M(xk,zk)\xi^k \in M(x^k,z^k). In particular, there exist sequences {λk}⊂Rm\{\lambda^k\} \subset\mathbb{R}^m and {uk}⊂Rn\{u^k\} \subset\mathbb{R}^n satisfying λk∈NC(G(xk)−zk)\lambda^k \in N_C(G(x^k)-z^k) and uk∈NDlim⁡(xk)u^k \in N_D^{\lim}(x^k) such that

ξk=∇G(xk)Tλk+uk,∀k∈N.(28)\xi^k = \nabla G(x^k)^{\mathsf{T}}\lambda^k + u^k, \quad\forall k \in\mathbb{N}. \tag*{(28)}

If {(λk,uk)}\{(\lambda^k,u^k)\} is unbounded, without loss of generality, we assume ∥(λk,uk)∥→∞\lVert(\lambda^k,u^k)\rVert\to\infty. Then it is reasonable to set (λk,uk)/∥(λk,uk)∥→(λ,u)≠(0,0)(\lambda^k,u^k)/\lVert(\lambda^k,u^k)\rVert\to(\lambda,u) \ne(0,0). Dividing (26) by ∥(λk,uk)∥\lVert(\lambda^k,u^k)\rVert, by the continuity of GG and the outer semicontinuity of the limiting normal cone, we have λ∈NC(G(xˉ))\lambda\in N_C(G(\bar{x})) and −∇G(xˉ)Tλ=u∈NDlim⁡(xˉ)-\nabla G(\bar{x})^{\mathsf{T}}\lambda= u \in N_D^{\lim}(\bar{x}). Then Assumption 3 implies λ=0\lambda= 0, and thus u=−∇G(xˉ)Tλ=0u = -\nabla G(\bar{x})^{\mathsf{T}}\lambda= 0, which contradicts (λ,u)≠(0,0)(\lambda,u) \ne(0,0). Thus, the sequence {(λk,uk)}\{(\lambda^k,u^k)\} is bounded, and therefore, possesses a convergent subsequence with limit (λ^,u^)(\hat{\lambda},\hat{u}). By the continuity of ∇G\nabla G, taking the limit in (26) along this subsequence yields that

ξ=∇G(xˉ)Tλ^+u^.(29)\xi= \nabla G(\bar{x})^{\mathsf{T}}\hat{\lambda} + \hat{u}. \tag*{(29)}

Moreover, by the continuity of GG and ∇G\nabla G, zk→0z^k \to0, xk→Dxˉx^k \to_D \bar{x}, and the outer semicontinuity of the limiting normal cone, we have λ^∈NC(G(xˉ))\hat{\lambda} \in N_C(G(\bar{x})) and u^∈NDlim⁡(xˉ)\hat{u} \in N_D^{\lim}(\bar{x}). Thus, (27) implies that ξ∈∇G(xˉ)TNC(G(xˉ))+NDlim⁡(xˉ)=M(xˉ,0)\xi\in\nabla G(\bar{x})^{\mathsf{T}}N_C(G(\bar{x})) + N_D^{\lim}(\bar{x}) = M(\bar{x},0). This shows that xˉ\bar{x} is AM-regular.

Note that Lemma 4.2 ensures the well-definedness of A\mathcal{A} in (25). We next verify that it satisfies Definition 2.4. For brevity, we denote

J(x,s):=Q(x,s)∇H(x,s)TM(x,s)−1.(30)J(x,s) := Q(x,s)\nabla H(x,s)^{\mathsf{T}}M(x,s)^{-1}. \tag*{(30)}

Proposition 4.3. Suppose that Assumption 1, Assumption 2, and Assumption 3 hold, the mapping (25) is a constraint dissolving mapping, i.e., it satisfies Definition 2.4.

Proof. Since the proof is similar to that in [9 Proposition 4.3], we present it in Appendix A.

We next show that, with A\mathcal{A} specifically given by (25), every accumulation point of the sequence generated by Algorithm 1 is feasible for (Ps)(P_s), provided that the inexactness sequence {(ϵxk,ϵsk)}\{(\epsilon_x^k,\epsilon_s^k)\} is bounded.

Lemma 4.4. Suppose that Assumption 1, Assumption 2, and Assumption 3 hold, the constraint dissolving mapping A(x,s)\mathcal{A}(x,s) is defined by (25). Let {(xk,sk)}\{(x^k,s^k)\} be generated by Algorithm 1 with {(ϵxk,ϵsk)}\{(\epsilon_x^k,\epsilon_s^k)\} being bounded, and (xˉ,sˉ)(\bar{x},\bar{s}) be any accumulation point of {(xk,sk)}\{(x^k,s^k)\}. Then (xˉ,sˉ)(\bar{x},\bar{s}) is feasible for (Ps)(P_s) and thus xˉ\bar{x} is feasible for (P)(P).

Proof. By Proposition 3.2 (i), it suffices to consider the case where {βk}\{\beta_k\} is unbounded. Let us also take K\mathcal{K} as an infinite index set such that (xk,sk)→K(xˉ,sˉ)(x^k,s^k) \to_{\mathcal{K}} (\bar{x},\bar{s}), and denote w:=(x,s)w := (x,s) and wˉ:=(xˉ,sˉ)\bar{w} := (\bar{x},\bar{s}) for convenience. By the closedness of CC and DD, we have wˉ∈K\bar{w} \in K. Then by Lemma 4.2, we have M0(wˉ)≻0M_0(\bar{w}) \succ0. Let us set μ:=λmin⁡(M0(wˉ))>0\mu:= \lambda_{\min}(M_0(\bar{w})) > 0. In view of Assumption 2, M0(⋅)M_0(\cdot), and thus M(⋅)M(\cdot) defined in (24) are continuous, then there exists ρ1>0\rho_1 > 0 such that M(w)⪰M0(w)⪰μ2ImM(w) \succeq M_0(w) \succeq\frac{\mu}{2}I_m on B1:=Bρ1(wˉ)B_1 := B_{\rho_1}(\bar{w}). By

Assumption 1 and Assumption 2, JJ (defined in (30)), DJDJ, A\mathcal{A}, HH, and ∇f\nabla f are continuous. Then, the compactness of B1B_1 implies that the constants

LJ:=max⁡w∈B1∥J(w)∥,LDJ:=max⁡w∈B1∥DJ(w)∥,L_J := \max_{w\in B_1} \|J(w)\|,\qquad L_{DJ} := \max_{w\in B_1} \|DJ(w)\|,
LH:=max⁡w∈B1∥H(w)∥,Lf:=max⁡w∈B1∥∇f(Ax(w))∥L_H := \max_{w\in B_1} \|H(w)\|,\qquad L_f := \max_{w\in B_1} \|\nabla f(\mathcal{A}_x(w))\|

are finite. Recall that wk:=(xk,sk)→K(xˉ,sˉ):=wˉw^k := (x^k,s^k) \to_{\mathcal{K}} (\bar{x},\bar{s}) := \bar{w}. For all large enough k∈Kk\in\mathcal{K}, one has wk∈Bρ(wˉ)w^k\in B_\rho(\bar{w}). By Assumption 2 and (30), one has

J(wk)⊤νk=M(wk)−1∇H(wk)Q(wk)νk=0,∀ νk∈NKlim⁡(wk),(31)J(w^k)^\top\nu^k = M(w^k)^{-1}\nabla H(w^k)Q(w^k)\nu^k = 0,\quad\forall\ \nu^k\in N_{\mathcal{K}}^{\lim}(w^k), \tag*{(31)}

and thus

⟨νk,J(wk)H(wk)⟩=⟨J(wk)⊤νk,H(wk)⟩=0.(32)\langle\nu^k,J(w^k)H(w^k)\rangle= \langle J(w^k)^\top\nu^k,H(w^k)\rangle= 0. \tag*{(32)}

Moreover, by (26) and (30), we have

∇H(wk)J(wk)=∇H(wk)Q(wk)∇H(wk)⊤M(wk)−1=M0(wk)M(wk)−1=Im−α∥H(wk)∥2M(wk)−1.(33)\begin{aligned} \nabla H(w^k)J(w^k) = \nabla H(w^k)Q(w^k)\nabla H(w^k)^\top M(w^k)^{-1} = M_0(w^k)M(w^k)^{-1} \\ &= I_m-\alpha\|H(w^k)\|^2M(w^k)^{-1}. \tag*{(33)} \end{aligned}

By (19), there exists some νk∈NKlim⁡(wk)\nu^k\in N_{\mathcal{K}}^{\lim}(w^k) such that εk=∇hβk−1(wk)+νk\varepsilon^k=\nabla h_{\beta_{k-1}}(w^k)+\nu^k with εk:=(εxk,εsk)\varepsilon^k:=(\varepsilon_x^k,\varepsilon_s^k) for each k≥1k\ge1. Consequently, we have

0=⟨∇hβk−1(wk)+νk−εk,J(wk)H(wk)⟩,∀ k≥1.0=\langle\nabla h_{\beta_{k-1}}(w^k)+\nu^k-\varepsilon^k,J(w^k)H(w^k)\rangle,\quad\forall\ k\ge1.

Let us write ξk:=J(wk)H(wk)\xi^k:=J(w^k)H(w^k) for brevity, then (31) implies

0=⟨∇Ax(wk)⊤∇f(Ax(wk)),ξk⟩+βk−1⟨∇H(wk)⊤H(wk),ξk⟩−⟨εk,ξk⟩(34)0=\langle\nabla\mathcal{A}_x(w^k)^\top\nabla f(\mathcal{A}_x(w^k)),\xi^k\rangle+\beta_{k-1}\langle\nabla H(w^k)^\top H(w^k),\xi^k\rangle-\langle\varepsilon^k,\xi^k\rangle \tag*{(34)}

for all large enough k∈Kk\in\mathcal{K}. Moreover, we have ∥ξk∥≤LJ∥H(wk)∥\|\xi^k\|\le L_J\|H(w^k)\| for all large enough k∈Kk\in\mathcal{K}. By (33), we have

J(wk)∇H(wk)⊤ξk=J(wk)∇H(wk)⊤J(wk)H(wk)=J(wk)H(wk)−α∥H(wk)∥2J(wk)M(wk)−1H(wk)\begin{aligned} J(w^k)\nabla H(w^k)^\top\xi^k=J(w^k)\nabla H(w^k)^\top J(w^k)H(w^k) \\ &=J(w^k)H(w^k)-\alpha\|H(w^k)\|^2J(w^k)M(w^k)^{-1}H(w^k) \end{aligned}

for all k≥1k\ge1. Since A\mathcal{A} is defined by (27), then we have

∥∇A(wk)⊤ξk∥=∥ξk−(DJ(wk)[ξk])H(wk)−J(wk)∇H(wk)⊤ξk∥=∥(DJ(wk)[ξk])H(wk)−α∥H(wk)∥2J(wk)M(wk)−1H(wk)∥≤LDJLJ∥H(wk)∥2+2αLJμ∥H(wk)∥3≤(LDJLJ+2αLJLHμ)∥H(wk)∥2,∀ large enough k∈K.\begin{aligned} \|\nabla\mathcal{A}(w^k)^\top\xi^k\|=\|\xi^k-(DJ(w^k)[\xi^k])H(w^k)-J(w^k)\nabla H(w^k)^\top\xi^k\| \\ &=\|(DJ(w^k)[\xi^k])H(w^k)-\alpha\|H(w^k)\|^2J(w^k)M(w^k)^{-1}H(w^k)\| \\ &\le L_{DJ}L_J\|H(w^k)\|^2+\frac{2\alpha L_J}{\mu}\|H(w^k)\|^3 \\ &\le\left(L_{DJ}L_J+\frac{2\alpha L_JL_H}{\mu}\right)\|H(w^k)\|^2,\quad\forall\ \text{large enough }k\in\mathcal{K}. \end{aligned}

Then

⟨∇Ax(wk)⊤∇f(Ax(wk)),ξk⟩≤Lf(LDJLJ+2αLJLHμ)∥H(wk)∥2(35)\langle\nabla\mathcal{A}_x(w^k)^\top\nabla f(\mathcal{A}_x(w^k)),\xi^k\rangle\le L_f\left(L_{DJ}L_J+\frac{2\alpha L_JL_H}{\mu}\right)\|H(w^k)\|^2 \tag*{(35)}

for all large enough k∈Kk\in\mathcal{K}. On the other hand, by the notation of M0M_0 and MM in (26), one has

λmin⁡(M0(wk)M(wk)−1)≥μμ+2αLH2.\lambda_{\min}\left(M_0(w^k)M(w^k)^{-1}\right)\ge\frac{\mu}{\mu+2\alpha L_H^2}.

Then, in view of Lemma 4.2 and (33), we have

⟨∇H(wk)⊤H(wk),ξk⟩=⟨H(wk),∇H(wk)J(wk)H(wk)⟩=H(wk)⊤M0(wk)M(wk)−1H(wk)≥μμ+2αLH2∥H(wk)∥2.(36)\begin{aligned} \langle\nabla H(w^k)^\top H(w^k),\xi^k\rangle=\langle H(w^k),\nabla H(w^k)J(w^k)H(w^k)\rangle\\ &=H(w^k)^\top M_0(w^k)M(w^k)^{-1}H(w^k) \\ &\ge\frac{\mu}{\mu+2\alpha L_H^2}\|H(w^k)\|^2. \tag*{(36)} \end{aligned}

for all large enough k∈Kk \in\mathcal{K}. Since {εk}\{\varepsilon^k\} is bounded, we let E>0E > 0 be the constant satisfying ∥εk∥≤E\|\varepsilon^k\| \le E for all sufficiently large k∈Kk \in\mathcal{K}. Then by (34), (35), and (36), one has

βk−1μμ+2αLH2∥H(wk)∥2≤Lf(LDJLJ+2αLJLHμ)∥H(wk)∥2+ELJLH\beta_{k-1}\frac{\mu}{\mu+2\alpha L_H^2}\|H(w^k)\|^2 \le L_f\left(L_DJ L_J+\frac{2\alpha L_JL_H}{\mu}\right)\|H(w^k)\|^2+EL_JL_H

and consequently,

(βk−1μμ+2αLH2−LfLDJLJ−Lf2αLJLHμ)∥H(wk)∥2≤ELJLH\left(\beta_{k-1}\frac{\mu}{\mu+2\alpha L_H^2}-L_fL_DJ L_J-L_f\frac{2\alpha L_JL_H}{\mu}\right)\|H(w^k)\|^2 \le EL_JL_H

for all large enough k∈Kk \in\mathcal{K}. Since βk−1=βk/τ→∞\beta_{k-1}=\beta_k/\tau\to\infty, then H(wk)→H(wˉ)=0H(w^k)\to H(\bar{w})=0. This means that (xˉ,sˉ)(\bar{x},\bar{s}) is feasible for (Ps)(P_s), and thus xˉ\bar{x} is feasible for (P)(P).

By Lemma 4.4 and Theorem 3.4, we directly have the following result.

Theorem 4.5. Let Assumption 1, Assumption 2, and Assumption 3 hold, A\mathcal{A} be defined in (27), and {(xk,sk)}\{(x^k,s^k)\} be the sequence generated by Algorithm 1 with (εxk+1,εsk+1)→(0,0)(\varepsilon_x^{k+1},\varepsilon_s^{k+1})\to(0,0). Let (xˉ,sˉ)(\bar{x},\bar{s}) be any accumulation point of {(xk,sk)}\{(x^k,s^k)\}. Then xˉ\bar{x} is an MM-stationary point for (P)(P).

Numerical Experiments

In this section, we report numerical results for Algorithm 1, referred to as CD for short, in comparison with the safeguarded augmented Lagrangian method (ALM) [8] and the inexact penalty decomposition (PD) method [10]. All experiments were carried out in MATLAB (R2025b) on a MacBook Air with an Apple M4 chip and 16 GB of memory.

CD and ALM solve their subproblems by the projected gradient method [8 Algorithm 3.1], where the parameters are the same as those in [8 Section 6]. For CD, in turn, the parameters η\eta and τ\tau in Algorithm 1, the parameter α\alpha of the constraint dissolving mapping, and the mappings QDQ_D and QCQ_C depend on the problem and will be specified below. PD replaces the constraint x∈Dx \in D by x−y=0x-y=0 and y∈Dy \in D and penalizes the constraints x−y=0x-y=0 and G(x)∈CG(x) \in C, so that its subproblems consist of minimizing qβ(x,y):=f(x)+β2∥x−y∥2+dist⁡C(G(x))2q_\beta(x,y):=f(x)+\frac{\beta}{2}\|x-y\|^2+\operatorname{dist}_C(G(x))^2 with respect to x∈Rnx \in\mathbb{R}^n and y∈Dy \in D. Following [10 Algorithm 2], we solve these subproblems by alternating a gradient step in xx, whose step size is determined by an Armijo line search, and the update y=PD(x)y=P_D(x).

In outer iteration k≥0k\geq0, the inner stopping criterion of CD and ALM is [8 (3.4)] with tolerance εinner,k=10−4/k+1\varepsilon_{\mathrm{inner},k}=10^{-4}/\sqrt{k+1}, while the alternating scheme of PD is terminated when qβk(xk,yk)−qβk(xk+1,yk+1)≤10−5q_{\beta_k}(x^k,y^k)-q_{\beta_k}(x^{k+1},y^{k+1})\leq10^{-5}. The outer stopping criteria are as follows: CD terminates when ∥G(xk+1)−sk+1∥∞≤εout\|G(x^{k+1})-s^{k+1}\|_\infty\leq\varepsilon_{\mathrm{out}}, ALM when [8 (4.5)] is satisfied, and PD when ∥xk+1−yk+1∥∞+∥G(xk+1)−PC(G(xk+1))∥∞≤εout\|x^{k+1}-y^{k+1}\|_\infty+\|G(x^{k+1})-P_C(G(x^{k+1}))\|_\infty\leq\varepsilon_{\mathrm{out}} [10 Section 6]. The same tolerance εout\varepsilon_{\mathrm{out}} is used for all three methods, with εout=10−4\varepsilon_{\mathrm{out}}=10^{-4} for the problems in Sections 5.1 and 5.3 and εout=10−5\varepsilon_{\mathrm{out}}=10^{-5} for the real-world portfolio problems in Section 5.2. In addition, we impose the upper bound 10810^8 on the penalty parameter and a budget of 10710^7 evaluations of the subproblem objective functions per run. Given a point x~0\tilde{x}^0, all three methods are initialized from the same projected point x0∈PD(x~0)x^0\in P_D(\tilde{x}^0). CD additionally sets s0=PC(G(x0))s^0=P_C(G(x^0)), and PD sets y0=x0y^0=x^0. Following [8 Section 6], ALM and PD use the same initial penalty parameter as therein, while the initial penalty parameter of CD is specified individually in the following subsections.

A complementarity-constrained Rosenbrock problem

We first consider the following Rosenbrock problem with interval and complementarity constraints:

min⁡x∈R2f(x):=(1−x1)2+100(x2−x12)2,s.t.12≤x1+x2≤32,x1≥0,x2≥0,x1x2=0.(37)\begin{aligned} \min_{x\in\mathbb{R}^2}\quad&f(x):=(1-x_1)^2+100(x_2-x_1^2)^2,\\ \text{s.t.}\quad&\frac{1}{2}\leq x_1+x_2\leq\frac{3}{2},\quad x_1\geq0,\quad x_2\geq0,\quad x_1x_2=0. \tag*{(37)} \end{aligned}

which corresponds to G(x)=x1+x2G(x)=x_1+x_2, C=[12321212]C=\begin{bmatrix}\frac{1}{2} & \frac{3}{2} \\ \frac{1}{2} & \frac{1}{2}\end{bmatrix}, and D={x∈R+2:x1x2=0}D=\{x\in\mathbb{R}_+^2:x_1x_2=0\}. Its global minimizer is x⋆=(1/2,0)⊤x^\star=(1/2,0)^\top with f(x⋆)=6.5f(x^\star)=6.5 and local minimizer is x~=(0,1/2)⊤\tilde{x}=(0,1/2)^\top with f(x~)=26f(\tilde{x})=26. For the constraint dissolving mapping, we choose QD(x)=cdiag⁡(x12,x22)Q_D(x)=c\operatorname{diag}(x_1^2,x_2^2) and QC(s)=(s−12)(32−s)Q_C(s)=(s-\frac{1}{2})(\frac{3}{2}-s), and we test the values c∈{0.01,0.1,1,10,100}c\in\{0.01,0.1,1,10,100\} in order to illustrate the corresponding numerical influence.

All three methods are run from the same 1000 starting points x~i=(ai,ai2+0.1ξi)⊤\tilde{x}^i=(a_i,a_i^2+0.1\xi_i)^\top, where aia_i is equally spaced in [−1,1][-1,1] and ξi\xi_i are drawn independently from the uniform distribution on [0,1][0,1]. In this problem, we set τ=10\tau=10, η=0.5\eta=0.5, and α=10\alpha=10 for CD, and we use the same initial penalty parameter β0\beta_0 for the three methods.

The results are summarized in Table 1, which reports the average numbers of outer iterations (OuterOuter) and of cumulative inner iterations (InnerInner). NglobalN_{\mathrm{global}} and NlocalN_{\mathrm{local}} are the numbers of runs whose final iterate has a distance of at most 10−310^{-3} to x⋆x^\star and x~\tilde{x}, respectively, and the average running time per run in milliseconds (TimeTime). For each runs, the final iterate is close to either x⋆x^\star or x~\tilde{x} in the above sense. However, CD finds the global minimizer more often: for every value of cc, it terminates near x⋆x^\star in 813 to 968 of the 1000 runs, whereas ALM and PD do so in 668 and 800 runs, respectively. Moreover, CD requires fewer iterations. Its average number of outer iterations decreases from 4.050 to 1.298 as cc increases from 0.01 to 100, compared with 15.488 for ALM and 104.795 for PD, and its average number of inner iterations lies between 16.170 and 33.002, compared with 56.778 for ALM and 3075.530 for PD. The number of inner iterations and the running time of CD are smallest for the intermediate values c=1c=1 and c=10c=10, for which CD requires 0.40 and 0.39 ms on average, respectively, compared with 0.52 ms for ALM and 37.86 ms for PD.

Alg.ccOuterOuterInnerInnerNglobalN_{\mathrm{global}}NlocalN_{\mathrm{local}}TimeTime
CD0.014.05032.154968320.58
CD0.12.96322.569934660.51
CD12.03516.170906940.40
CD101.45816.6818311690.39
CD1001.29833.0028131871.23
ALM–15.48856.7786683320.52
PD–104.7953075.53080020037.86

Table 1. Averaged results of CD, ALM, and PD for solving (35).

Sparse portfolio optimization

This subsection considers two types of portfolio problems with cardinality constraints, i.e., the interval-budget model in Section 5.2.1 and the mean-variance model in Section 5.2.2, as the variants of the classical portfolio problem [1]. We denote Σ\Sigma and μ\mu as the covariance matrix and the vector of expected returns of nn assets and ee as the all-one vector. In both problems, we use D={x∈R+n:∥x∥0≤κ}D=\{x\in\mathbb{R}_+^n:\lVert x\rVert_0\leq\kappa\} and QD(x)=cdiag⁡(x12,…,xn2)Q_D(x)=c\operatorname{diag}(x_1^2,\ldots,x_n^2). For all three methods, we choose the starting point as x0=PD(x~0)x^0=P_D(\tilde{x}^0), where x~0\tilde{x}^0 is a solution of the respective problem without the cardinality constraint ∥x∥0≤κ\lVert x\rVert_0\leq\kappa, which is a convex quadratic program. For both problems, PD fails to satisfy the outer stopping criterion, and its results are therefore not reported.

Interval-budget model on benchmark instances

We first consider the sparse portfolio problem with an interval budget constraint

min⁡x∈Rnf(x):=12x⊤Σx−μ⊤xs.t.0.8≤e⊤x≤1,x≥0,∥x∥0≤κ,(38)\begin{aligned} \min_{x\in\mathbb{R}^n}\quad& f(x):=\frac{1}{2}x^\top\Sigma x-\mu^\top x\\ \text{s.t.}\quad& 0.8\leq e^\top x\leq1,\quad x\geq0,\quad\lVert x\rVert_0\leq\kappa, \tag*{(38)} \end{aligned}

in which at least 80% of the capital has to be invested and the remainder may be held in cash. In contrast to the usual budget constraint e⊤x=1e^{\top}x = 1, under which the whole capital is invested, this yields a test problem in which CC is not a singleton. More precisely, we set G(x)=e⊤x−1G(x) = e^{\top}x - 1, C=[−0.2,0]C = [-0.2, 0], and QC(s)=(s+0.2)(−s)Q_C(s) = (s + 0.2)(-s). The data Σ\Sigma and μ\mu are taken from the test problem collection [5], from which we use the orl and pard instances of dimension n∈{200,300,400}n \in\{200, 300, 400\}, 30 (20 orl and 10 pard) instances for each dimension, together with κ∈{3,5,7}\kappa\in\{3, 5, 7\}, resulting in 270 test problems. For CD, we set τ=2\tau= 2, η=0.5\eta= 0.5, c=0.01c = 0.01, α=0.001\alpha= 0.001, and β0=300\beta_0 = 300.

The results are summarized in Table 2, which reports, for each pair (n,κ)(n, \kappa), the average numbers of outer iterations (OuterOuter) and of cumulative inner iterations (InnerInner), the average running time in milliseconds (TimeTime, minimum over three repetitions), the average final objective function value (fˉ\bar{f}), and the numbers of instances on which CD attains the lower objective function value (NCDN_{\mathrm{CD}}), ALM attains the lower one (NALMN_{\mathrm{ALM}}), and the two methods tie (NtieN_{\mathrm{tie}}). In addition, Figure 1 shows the final objective function values for every instance. Regarding the objective function values, CD attains the lower value on 226 of the 270 instances and ALM on 30, while the two methods tie on the remaining 14. In each of the nine settings, CD attains the lower value on at least 21 of the 30 instances and its average objective function value is lower than that of ALM. Regarding the numerical effort, CD requires fewer outer iterations, fewer inner iterations, and less running time than ALM in all nine settings. More precisely, its average number of inner iterations is between 33% and 60% of that of ALM. Over all settings, the average running times range from 3.3 to 6.6 ms for CD and from 4.5 to 10.7 ms for ALM.

nnκ\kappa\multicolumn{4}{c}{CD}\multicolumn{4}{c}{ALM}NCDN_{\mathrm{CD}}NALMN_{\mathrm{ALM}}NtieN_{\mathrm{tie}}
OuterInnerTimefˉ\bar{f}OuterInnerTimefˉ\bar{f}
20036.07138.83.7122.94327.30335.06.1128.6372352
20057.53124.33.371.24119.27259.54.575.4882613
20077.67125.43.751.39926.63376.06.854.7702820
30035.93129.03.6176.97832.33395.98.9191.3762613
30057.27151.14.6107.27225.57354.27.6114.3322541
30078.17167.75.581.08120.17278.86.281.6032181
40036.80154.55.3231.62128.20403.610.7250.7072811
40057.90157.35.6141.45330.80378.310.3148.2252622
40078.67173.36.6105.46324.40341.79.3107.7012361

Table 2. Averaged results of CD and ALM for solving (38).

Figure 1. Final objective values of ALM and CD for solving (38). Each panel shows, for one pair (n,κ)(n,\kappa), the 20 orl instances (left part, left axis) and the 10 pard instances (right part, right axis) of [5]. Note that the gray vertical line separates the two families of orl instances.

Mean–variance model on market data

We consider the cardinality-constrained mean–variance model

min⁡x∈Rn12x⊤Σxs.t.μ⊤x≥ρ,e⊤x=1,x≥0,∥x∥0≤κ,(39)\begin{aligned} \min_{x \in\mathbb{R}^n} \quad& \frac{1}{2}x^{\top}\Sigma x \\ \text{s.t.} \quad& \mu^{\top}x \ge\rho,\quad e^{\top}x = 1,\quad x \ge0,\quad\lVert x \rVert_0 \le\kappa, \tag*{(39)} \end{aligned}

where the variance of the portfolio is minimized subject to a lower bound ρ\rho on its expected return. In contrast to the previous problem, the set CC now combines an inequality and an equality constraint, since we set G(x)=(μ⊤x−ρ,e⊤x−1)⊤G(x) = (\mu^{\top}x - \rho, e^{\top}x - 1)^{\top}, C=R+×{0}C = \mathbb{R}_+ \times\{0\}, and QC(s)=diag⁡(s12,0)Q_C(s) = \operatorname{diag}(s_1^2, 0). We test five real stock data sets with daily return rates, which are listed in Table 3 and include NASDAQ100, FTSE100, and three S&P500 data sets covering different market conditions.

Data setMarket conditionsStocksTotal time periodOut-of-sample time period
NASDAQ100–9501/02/2020–09/12/202308/03/2022–09/12/2023
FTSE100–9701/02/2020–09/12/202307/19/2022–09/12/2023
S&P500-DDeclining market49003/12/2020–10/12/202201/03/2022–10/12/2022
S&P500-CCOVID-1947812/06/2017–12/31/202002/03/2020–12/31/2020
S&P500-RRising market49709/17/2021–09/30/202411/01/2023–09/30/2024

Table 3. The tested stock data sets.

The test problems are generated by a rolling-window procedure, in which the first 70% of the periods of each data set form the initial estimation window, whereas the remaining ToutT_{\mathrm{out}} periods form the out-of-sample period in Table 3. For each t=1,…,Toutt = 1, \ldots, T_{\mathrm{out}}, the estimation window is shifted by t−1t - 1 periods, Σ\Sigma and μ\mu are taken as the sample covariance matrix and the sample mean of the returns in this window, and problem (39) is solved with κ=10\kappa= 10 and ρ=(e⊤μ−max⁡iμi)/n\rho= (e^{\top}\mu- \max_i \mu_i)/n. The resulting portfolio is then evaluated on the return of the following period. For CD, we set τ=10\tau= 10, η=0.5\eta= 0.5, c=10c = 10, α=0.01\alpha= 0.01, and β0=10\beta_0 = 10.

Following [14], the computed portfolios are assessed out of sample by the mean MeanpMean_p and the standard deviation StdpStd_p of their realized returns, the Sharpe ratio SRpSR_p, and the risk reduction RRpRR_p with respect to the equally weighted portfolio, which is denoted by 1/N1/N. The corresponding results are summarized in Table 4, which reports, for each data set, the averages of OuterOuter, InnerInner, and TimeTime (in milliseconds) over all windows, the number NlowN_{\mathrm{low}} of windows on which the respective method attains the lower objective function value, and these criteria. In addition, Figure 2 and Figure 3 show the cumulative wealth over the out-of-sample periods.

Data setToutT_{\mathrm{out}}Alg.OuterOuterInnerInnerTimeTimeNlowN_{\mathrm{low}}MeanpMean_pStdpStd_pSRpSR_pRRpRR_p
NASDAQ100279CD2.97499.421.81550.0030.0092−0.01252.63
ALM13.011329.728.2540.0020.0091−0.01392.59
1/N1/N––––0.0690.01400.03941.00
FTSE100278CD3.28764.027.088−0.0080.0072−0.03152.16
ALM9.73440.58.063−0.0080.0071−0.03122.15
1/N1/N––––0.0220.01000.00761.00
S&P500-D196CD2.98464.135.8134−0.0730.0104−0.08462.32
ALM15.821622.985.949−0.0610.0101−0.07462.34
1/N1/N––––−0.0910.0147−0.07171.00
S&P500-C232CD2.99544.533.1300.0210.01710.00413.19
ALM6.61437.120.6460.0290.01730.00833.19
1/N1/N––––0.1180.02490.04181.00
S&P500-R229CD3.05603.449.81260.0910.00570.13521.84
ALM10.691125.661.7740.0990.00590.14411.79
1/N1/N––––0.1430.00770.16791.00

Table 4. Out-of-sample results of the rolling-window procedure for solving (39).

Figure 2. Cumulative wealth over the out-of-sample periods of NASDAQ100 and FTSE100 for the portfolios computed by CD and ALM.

Figure 3. Cumulative wealth over the out-of-sample periods of the S&P500 data sets for the portfolios computed by CD and ALM.

Regarding the objective function values, CD attains the lower value on 533 of the 1214 windows and ALM on 286, while the two methods tie on the remaining 395 windows, 156 of which belong to S&P500-C. In particular, CD attains the lower value more often on four of the five data sets. Regarding the numerical effort, CD requires about 3 outer iterations on average on every data set, compared with between 6.61 and 15.82 for ALM, and, on NASDAQ100, S&P500-D, and S&P500-R, also fewer inner iterations and less running time, the difference being most pronounced on S&P500-D, where the average running time is 35.8 ms for CD and 85.9 ms for ALM. These are the data sets on which the return constraint is active in most windows. In fact, on the 776 windows on which this constraint is active (up to 10−410^{-4}) at the point computed by CD, CD requires 447.8 inner iterations on average, compared with 1309.8 for ALM, whereas ALM requires fewer inner iterations on the remaining 438 windows.

Finally, since both methods address the same model, they yield similar out-of-sample criteria. On the windows without a tie, the in-sample variances of the portfolios computed by the two methods differ on average by at most 1.2%, and the cumulative wealth curves in Figure 2 and Figure 3 remain close to each other, with final wealth differing by at most 0.024. Hence, the savings in computational effort reported above are achieved without a deterioration of the out-of-sample performance beyond these small differences. The sparse portfolios have a smaller standard deviation than the equally weighted portfolio, with RRpRR_p between 1.8 and 3.2, and, in the declining market of S&P500-D, they also lose less, with a final wealth of 0.86 for CDiP and 0.88 for ALM, compared with 0.82.

MAXCUT problems

We consider an undirected graph with vertex set V={1,…,N}V = \{1,\ldots,N\} and denote aij=ajia_{ij}=a_{ji} as the weight of the edge between the vertices ii and jj. Since we allow zero weights, without loss of generality, we can assume that the graph is complete. Given a subset S⊆VS \subseteq V with complement ScS^c, the cut defined by SS is the set of all edges with one end point in SS and the other one in ScS^c, and its weight is ∑i∈S,j∈Scaij\sum_{i\in S,j\in S^c}a_{ij}. The MaxCut problem looks for a cut with maximum weight and is known to be NP-hard.

In the following, let us denote SN\mathbb{S}^N as the space of symmetric N×NN \times N matrices, equipped with the Frobenius inner product. With A:=(aij)∈SNA := (a_{ij}) \in\mathbb{S}^N and the Laplacian matrix L:=Diag⁡(Ae)−AL := \operatorname{Diag}(Ae)-A, by [6, 8], the MaxCut problem can be reformulated as

min⁡W∈SNf(W):=−14tr⁡(LW),s.t.diag⁡(W)=e,W⪰0,rank⁡(W)≤1,(40)\begin{aligned} \min_{W\in\mathbb{S}^N}\quad&f(W):=-\frac{1}{4}\operatorname{tr}(LW),\\ \text{s.t.}\quad&\operatorname{diag}(W)=e,\quad W\succeq0,\quad\operatorname{rank}(W)\leq1, \tag*{(40)} \end{aligned}

since the feasible points of (40) are exactly the matrices W=wwTW=ww^{\mathsf{T}} with w∈{−1,1}Nw\in\{-1,1\}^N, and, for such a matrix, −f(W)=14wTLw-f(W)=\frac{1}{4}w^{\mathsf{T}}Lw is the weight of the cut defined by S={i∈V:wi=1}S=\{i\in V:w_i=1\}. Omitting the rank constraint yields the semidefinite relaxation of (40). We take the set of positive semidefinite matrices of rank at most one as the complicated set, that is, we set G(W)=diag⁡(W)−eG(W)=\operatorname{diag}(W)-e, C={0}C=\{0\}, and D={W∈SN:W⪰0,rank⁡(W)≤1}D=\{W\in\mathbb{S}^N:W\succeq0,\operatorname{rank}(W)\leq1\}. A projection of W∈SNW\in\mathbb{S}^N onto DD is given by max⁡{λ,0}vvT\max\{\lambda,0\}vv^{\mathsf{T}}, where λ\lambda is a largest eigenvalue of WW and vv is a corresponding unit eigenvector, so that its computation does not require a full spectral decomposition. For the constraint dissolving mapping, we choose QC≡0Q_C\equiv0 and QD(W)[Y]=c(WY+YW)Q_D(W)[Y]=c(WY+YW).

We use the rudy collection of the Biq Mac library http://biqmac.aau.at/biqmaclib.html as the test database, which consists of 130 randomly generated graphs with N∈{60,80,100}N\in\{60,80,100\} vertices, edge densities between 0.1 and 0.99, and integer edge weights in [−10,10][-10,10] and for which the optimal cut values are known. In order to obtain a good starting point, we take as W~0\widetilde{W}^{0} a solution of the semidefinite relaxation of (40), which we compute by ALM with DD replaced by the cone of positive semidefinite matrices. For CD, we set τ=10\tau=10, η=0.5\eta=0.5, c=1c=1, α=0.3\alpha=0.3, and β0=5\beta_0=5. From the final iterate WW of each method, we obtain a cut from the signs of the entries of an eigenvector of WW corresponding to its largest eigenvalue.

Figure 4 summarizes the cut quantity in a condensed way: for each instance, we take the quotient ffinal/fopt∈[0,1]f_{\mathrm{final}/f_{\mathrm{opt}} \in[0,1]} as quantity measurement of the cut, where ffinalf_{\mathrm{final}} is the final function value obtained by each of the three methods and foptf_{\mathrm{opt}} is the optimal cut value. Figure 4 then reports, for p=87,…,100p=87,\ldots,100, the number of instances on which each method attains at least p%p\% of the optimal value. For p=88,…,98p=88,\ldots,98, PD attains at least p%p\% of the optimal value on more instances than CD and ALM, and its cuts attain on average 97.50% of the optimal values, compared with 97.12% for CD and 96.98% for ALM.

Figure 4. Number of the 130 rudy instances on which CD, ALM, and PD attain a cut of at least p%p\% of the optimal value.

However, PD requires more outer and inner iterations and longer running times compared with CD and ALM. This is reflected in Table 5, which reports the average numbers of outer iterations (Outer) and of cumulative inner iterations (Inner), the average running time in seconds (Time), and the average weight of the computed cuts in percent of the optimal values (Cut). In fact, PD requires on average 128.9 s running time per instance, which is about 690 times that of ALM and about 2100 times that of CD. On every instance, its running time exceeds those of CD and ALM by more than two orders of magnitude.

GroupCDALMPD
OuterInnerTimeCutOuterInnerTimeCutOuterInnerTimeCut
g05_602.0027.60.02699.0011.60227.40.06799.44130.610322830.798.93
g05_802.0034.90.02699.0716.50259.70.10298.87136.514954661.099.02
g05_1004.0042.40.04599.0720.40365.90.21998.98141.7202753122.898.99
pm1s_801.4025.30.02793.3710.60220.70.09595.63123.911267745.395.73
pm1d_802.0061.20.04096.3116.70320.30.12592.77136.115743963.896.81
pm1s_1003.0061.00.06995.9012.10288.60.17594.41128.015059289.796.89
pm1d_1002.0055.80.05796.0020.50376.50.21995.87140.0227674135.897.03
w01_1002.0077.10.08096.2919.70382.00.22497.65147.6289699173.096.60
pw01_1004.0055.40.05897.9114.10396.90.23398.97151.9264581159.397.95
w05_1004.00110.70.11395.3517.20436.80.25995.46155.7344831205.995.68
pw05_1004.0051.30.05199.0919.50378.50.22099.12161.5279766170.898.93
w09_1004.00124.70.12895.8717.80408.50.23994.31158.7403367239.295.77
pw09_1006.0063.10.06399.3223.20427.10.24899.27164.8291427178.399.19
All3.1160.80.06097.1216.92345.30.18796.98144.4229045128.997.50

Table 5. Results of CD, ALM, and PD for solving (40) with the rudy instances. Each row except the last summarizes the 10 instances of one group of the rudy collection. The last row reports the average results over all instances listed above.

Therefore, we merely compare the numerical performance of CD and ALM in the form of [3]. Specifically, Figure 5 shows the number of successfully-solved instances within a given running time, number of outer iterations, and number of cumulative inner iterations. Overall, CD consistently outperforms ALM: it solves more instances faster and with fewer iterations.

Conclusion

In this manuscript, we developed a constraint dissolving method for solving optimization problems with constraints G(x)∈CG(x) \in C and x∈Dx \in D, which, to the best of our knowledge, is the first constraint dissolving type method applicable to this general setting. More specifically, we introduced an auxiliary variable to decouple the constraint G(x)∈CG(x) \in C into an equality constraint and a set constraint, and constructed a constraint dissolving mapping acting jointly on the original and auxiliary variables. Under mild conditions, every accumulation point generated by the proposed algorithm is guaranteed to be an M-stationary point. Moreover, by a specific choice of the constraint dissolving mapping, every accumulation point is

Figure 5. Number of the 130 rudy instances that CD and ALM solve within a given running time (a), number of outer iterations (b), and number of cumulative inner iterations (c).

feasible. Numerical experiments on Rosenbrock, portfolio, and MAXCUT problems demonstrated the effectiveness of the proposed method in comparison with the augmented Lagrangian method and the penalty decomposition method, which, to the best of our knowledge, are the state-of-the-art algorithms for solving optimization problems with general constraints.

Data Availability. The five real-world stock datasets used in § 5.2.2, including NASDAQ100, FTSE100, and three S&P500 datasets, are available from Haonan Shen ([email protected]) upon reasonable request.

Proof of Proposition 4.3

Proof. By Assumption 1 and Assumption 2, GG, ∇G\nabla G, QDQ_D and QCQ_C are continuously differentiable, and thus A(x,s)A(x,s) defined in (27) is also continuously differentiable. Also, for all (x,s)∈Fs(x,s) \in F_s, we have H(x,s)=0H(x,s)=0, and thus A(x,s)=(x,s)A(x,s)=(x,s).

In view of (27), we have

∇A(x,s)=In+m−DJ(x,s)H(x,s)−J(x,s)∇H(x,s),∀ (x,s)∈K,(41)\nabla A(x,s)=I_{n+m}-D J(x,s)H(x,s)-J(x,s)\nabla H(x,s),\quad\forall\ (x,s)\in K, \tag*{(41)}

where DJ(x,s)D J(x,s) denotes the Jacobian of JJ at (x,s)(x,s). In particular,

∇A(x,s)=In+m−J(x,s)∇H(x,s),∀ (x,s)∈Fs.\nabla A(x,s)=I_{n+m}-J(x,s)\nabla H(x,s),\quad\forall\ (x,s)\in F_s.

Moreover, for any (x,s)∈Fs(x,s)\in F_s, we have M(x,s)=M0(x,s)M(x,s)=M_0(x,s). Then (26) and (30) yield

∇H(x,s)J(x,s)=∇H(x,s)Q(x,s)∇H(x,s)T(∇H(x,s)Q(x,s)∇H(x,s)T)−1=Im.\nabla H(x,s)J(x,s)=\nabla H(x,s)Q(x,s)\nabla H(x,s)^{\mathsf T}\left(\nabla H(x,s)Q(x,s)\nabla H(x,s)^{\mathsf T}\right)^{-1}=I_m.

Consequently, one has

∇A(x,s)T∇H(x,s)T=∇H(x,s)T−∇H(x,s)TJ(x,s)T∇H(x,s)T=0,\nabla A(x,s)^{\mathsf T}\nabla H(x,s)^{\mathsf T}=\nabla H(x,s)^{\mathsf T}-\nabla H(x,s)^{\mathsf T}J(x,s)^{\mathsf T}\nabla H(x,s)^{\mathsf T}=0,

which means Definition 2.4 (c) holds. It remains to verify Definition 2.4 (d) and (e).

Motivated by (41), we set RA(x,s):=−DJ(x,s)H(x,s)R_A(x,s):=-D J(x,s)H(x,s). By Assumption 1 and Assumption 2, we know that RAR_A is continuous. For any (x,s)∈Fs(x,s)\in F_s, we have H(x,s)=0H(x,s)=0 and thus RA(x,s)=0R_A(x,s)=0. It remains to verify (e).

For any (x,s)∈Fs(x,s)\in F_s, choose a constant ωx,s>0\omega_{x,s}>0 arbitrarily. For any (y,t)∈K(y,t)\in K satisfying ∥(y,t)−(x,s)∥≤ωx,s\lVert(y,t)-(x,s)\rVert\le\omega_{x,s}, by Assumption 2 (b), one has Q(y,t)NKlim⁡(y,t)={0}Q(y,t)N_K^{\lim}(y,t)=\{0\} and thus

(∇A(y,t)−In+m−RA(y,t))TNKlim⁡(y,t)=(−J(y,t)∇H(y,t))TNKlim⁡(y,t)=−∇H(y,t)TM(y,t)−1∇H(y,t)Q(y,t)NKlim⁡(y,t)={0}.\begin{aligned} \left(\nabla A(y,t)-I_{n+m}-R_A(y,t)\right)^{\mathsf T}N_K^{\lim}(y,t)=\left(-J(y,t)\nabla H(y,t)\right)^{\mathsf T}N_K^{\lim}(y,t) \\ &=-\nabla H(y,t)^{\mathsf T}M(y,t)^{-1}\nabla H(y,t)Q(y,t)N_K^{\lim}(y,t)=\{0\}. \end{aligned}

This completes the proof.

References

References

  1. [1]D. Bertsimas and R. Cory-Wright, A scalable algorithm for sparse portfolio selection, INFORMS Journal on Computing 34 (2022), pp. 1489–1511.DOI
  2. [2]A. De Marchi, X. Jia, C. Kanzow, and P. Mehlitz, Constrained composite optimization and augmented Lagrangian methods, Mathematical Programming 201 (2023), pp. 863–896.DOI
  3. [3]E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming 91 (2002), pp. 201–213.DOI
  4. [4]R. Fletcher, A class of methods for nonlinear programming with termination and convergence properties (1970).
  5. [5]A. Frangioni and C. Gentile, SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters 35 (2007), pp. 181–185.DOI
  6. [6]M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM) 42 (1995), pp. 1115–1145.DOI
  7. [7]X. Hu, N. Xiao, X. Liu, and K.C. Toh, An improved unconstrained approach for bilevel optimization, SIAM Journal on Optimization 33 (2023), pp. 2801–2829.arxiv.org/abs/2208.00732
  8. [8]X. Jia, C. Kanzow, P. Mehlitz, and G. Wachsmuth, An augmented Lagrangian method for optimization problems with structured geometric constraints, Mathematical Programming 199 (2023), pp. 1365–1415.arxiv.org/abs/2105.08317
  9. [9]X. Jia, L. Lerch, S. Streif, and M. Schaller, A constraint dissolving inexact penalty method for optimization problems with geometric constraints, arXiv preprint arXiv:2608.24542 (2026).arxiv.org/abs/2608.24542
  10. [10]C. Kanzow and M. Lapucci, Inexact penalty decomposition methods for optimization problems with geometric constraints, Computational Optimization and Applications 85 (2023), pp. 937–971.DOI
  11. [11]P. Mehlitz, Asymptotic stationarity and regularity for nonsmooth optimization problems, Journal of Nonsmooth Analysis and Optimization 1 (2020), pp. 6575: 1–30.DOI
  12. [12]S.M. Robinson, Constraint nondegeneracy in variational analysis, Mathematics of Operations Research 28 (2003), pp. 201–232.DOI
  13. [13]R.T. Rockafellar and R.J. Wets, Variational analysis, Springer, 1998.DOI
  14. [14]Z. Wu, K. Sun, Z. Ge, Z. Allen-Zhao, and T. Zeng, Sparse portfolio optimization via ℓ_1 over ℓ_2 regularization, European Journal of Operational Research 319 (2024), pp. 820–833.
  15. [15]N. Xiao, X. Hu, X. Liu, and K.C. Toh, CDOpt: a Python package for a class of Riemannian optimization, Mathematical Programming Computation 17 (2025), pp. 173–230.arxiv.org/abs/2212.02698
  16. [16]N. Xiao and X. Liu, Solving optimization problems over the Stiefel manifold by smooth exact penalty functions, Journal of Computational Mathematics 42 (2024), pp. 1246–1276.DOI
  17. [17]N. Xiao, X. Liu, and K.C. Toh, Dissolving constraints for Riemannian optimization, Mathematics of Operations Research 49 (2024), pp. 366–397.arxiv.org/abs/2203.10319
  18. [18]N. Xiao, T. Tang, S. Wang, and K.C. Toh, An exact penalty approach for equality constrained optimization over a convex set, Mathematical Programming (2026).arxiv.org/abs/2505.02495
  19. [19]N. Xiao, S. Wang, T. Tang, and K.C. Toh, A quadratically convergent alternating projection method for nonconvex sets, arXiv preprint arXiv:2511.22916 (2025).arxiv.org/abs/2511.22916

Paper details

vlnc:W_223z4cs2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents