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:
where and are continuously differentiable. The set is nonempty, closed, and convex, whereas is nonempty and closed, but not necessarily convex. We refer to as a geometric constraint, allowing 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. . 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 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 together with a convex set constraint 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 and , where 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 , the numerical realization in [9] is restricted to the case , 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 to separate the nonlinear coupling from the set constraint and rewrite (P) as
This standard reformulation preserves feasible points and local and global minimizers same as those of (P) in the sense that the map 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 is Mordukhovich stationary for (P) if and only if 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 . For the constraint dissolving problem to be solved, the constraints and are retained, whereas is dissolved into the objective function. Afterwards, the penalty parameter is kept if the feasibility error 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 with a constraint set 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 , we denote and as the corresponding projection mapping and the distance function, respectively. When is nonconvex, may fail to be a singleton, i.e., the projection onto does not need to be unique.
Given , the tangent cone to at is defined by
the normal cone to at is defined as
the limiting normal cone is defined as
We set and if . Note that the limiting normal cone is stable in the sense that
When is convex, the limiting normal cone coincides with the corresponding standard normal cone, i.e., for $z\in D,
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 .
Definition 2.1. A point is called an M (Mordukhovich)-stationary point for (P) if there exists such that
Definition 2.2. A point is called an AM (asymptotically Mordukhovich)-stationary point of (P) if there exist sequences , and , such that , , , and for all ,
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 of (P) is AM-regular if
where is the set-valued mapping defined by
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) and are continuously differentiable.
(ii) is nonempty, closed, and convex. 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 . For convenience, we denote , , and .
Definition 2.4. A mapping is called a constraint dissolving mapping for , if the following conditions hold.
(a) is continuously differentiable.
(b) holds for all .
(c) For all , .
Moreover, there exists a continuous mapping such that:
(d) for all ;
(e) for any , there exists such that
for all with .
Definition 2.4 generalizes the constraint dissolving mappings of [17, 18], which were developed for an equality constraint . In our setting, by contrast, the set can be an arbitrary nonempty, closed, and convex set. Moreover, whereas [18] additionally admits a constraint with a convex set , we incorporate the geometric constraint , where is allowed to be nonconvex. Therefore, the corresponding limiting normal cone is employed in (5).
Proposition 2.5. Let be any constraint dissolving mapping satisfying Definition 2.4. For every and , one has .
Proof. For any with , there exists a sequence and such that and
By differentiability of as in Definition 2.4 (a), one has
Definition 2.4(b) gives . Dividing it by , then (6) and (7) yield the assertion.
The following result shows that if satisfies AM-regularity, then the analogous regularity condition, formulated in terms of the set-valued mapping , holds at the pair .
Lemma 2.6. If is -regular for (P), then one has
where
Proof. Let us take any , then there exist sequences and satisfying and , such that . For any , by [13 Proposition 6.41], there exist , and such that and . Consequently,
By the continuity of , we have . Then the continuity of and AM-regularity at yield . Thus, there exists and such that . Let us set , then we have and , it follows from [13 Proposition 6.41] that . 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 and would read
where the role of is to ensure that and consequently . In this way, the auxiliary variable 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 is -regular, then one has
Meanwhile, we have the following results.
Proposition 2.9. Let Assumption 1 hold and satisfy Definition 2.4. For any , one has
(i) ,
(ii) ,
(iii) .
Moreover, for any , one has
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 satisfying , we have . Then (ii) yields
For every , Proposition 2.5 gives . It implies that
where the last inclusion is from Lemma 2.8. Then there exist some and such that . By (10), (i), and (ii), we have and thus .
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 satisfy Definition 2.4. For any and , one has
Relationships between stationarities
As illustrated above, the constraint dissolving mapping employed in this manuscript is jointly with the original variable and slack variable . For the convenience of analysis, we partition the constraint dissolving mapping with respect to the blocks and , namely,
where and . Then, by Definition 2.4, and satisfy, in particular, the following properties:
(i) and are continuously differentiable.
(ii) and for all .
Moreover, the Jacobian of admits
Based on the above notation, we consider the following constraint dissolving problem associated with (P)
where 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
The chain rule yields the two gradients
We denote their column concatenation by .
Definition 2.11. A pair is M-stationary for (Q) if
Theorem 2.12. Let Assumption 1 hold and be a constraint dissolving mapping satisfying Definition 2.3. For any and , one has
Proof. Since , we have , and thus . Hence, by Definition 2.11, is an M-stationary point of (Q) if and only if
By Theorem 2.10, this is equivalent to
On the other hand, is an M-stationary point of (P) if and only if there exists some such that
where the second block of (15) reads exactly . Since
(14) holds if and only if there exists such that (15) holds. Therefore, is an M-stationary point of (P) if and only if is an M-stationary point of (Q).
Algorithm
Leveraging the equivalence of M-stationarity between (P) and , this section develops a penalty-based constraint dissolving method for solving and establishes its corresponding convergence analysis. The overall algorithm is presented in Algorithm 1.
Algorithm 1: A constraint dissolving method with adaptive penalty
Require: , , , , and .
Set .
while does not satisfy a termination criterion do
Compute an approximate M-stationary point of the subproblem
i.e., there exist and such that
if or then
else
end if
Set .
end while
return
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 , 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 satisfy Definition 2.4, and be a sequence generated by Algorithm 1. Let be any accumulation point of . If one of the following conditions holds:
(i) is bounded, or
(ii) there exists some such that holds for all ,
then is feasible for and is feasible for .
Proof. Let us choose an infinite index set such that . By (18) and the closedness of and , we have .
(i) If is bounded, by the update rule of , we have . The continuity of implies that . It means that is feasible for . Furthermore, it implies that and , which means that is feasible for .
(ii) By the definition of in (Q), we have
Since , the continuity of and gives
Thus, taking the limit in (20) yields that . The continuity of further implies that . Therefore, by the same analysis as the case that is bounded, we conclude that is feasible for and is feasible for .
Proposition 3.2 provides the sufficient conditions for the feasibility of accumulation points. As illustrated in [8, 9], (ii) holds, for example, if is an (approximate) global minimizer of the subproblem (18). This, however, requires more restrictive assumption on model, for instance, is level bounded on [13 Example 1.11]. For the specific constraint dissolving mapping 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 , 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 satisfy Definition 2.4, and be a sequence generated by Algorithm 1. Let be any accumulation point of . If is bounded, then is M-stationary of
Proof. As in the proof of Proposition 3.2, we take is an infinite index set such that . Let us first consider the case is bounded, by Proposition 3.2, we have , which means that is a global minimizer of (21) and hence its M-stationary point. It remains to consider the situation . By (19), one has for all ,
By the boundedness of , continuity of , , and , and the fact that is robust, taking the limit implies that
It means that is an M-stationary point of (21).
Theorem 3.4. Let Assumption 1 hold, satisfy Definition 2.4, and be a sequence generated by Algorithm 1 with . Let be any accumulation point of feasible for . Then is an M-stationary point for .
Proof. As in the proof of Proposition 3.2, we take as an infinite index set such that . By the feasibility of , we have .
It implies that
In view of (13), Assumption 1, and Definition 2.4, Lemma 2.6 gives
Let us recall that , it follows from Theorem 2.12 that is an M-stationary point for .
Implementation of constraint dissolving mappings for nonconvex sets
This section focuses on the construction of constraint dissolving mappings 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
where and are continuously differentiable, and 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
where 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 . Then there exists some such that
In fact, the optimal depends on unknown normal vector and hence cannot be evaluated. To remove the dependence on , we assume that there exists a symmetric positive (semi)definite matrix such that (see Assumption 2 (b) for more general setting). Then we have . In this case, multiplying (24) by yields that
Under the condition that is invertible (a constraint qualification, like Assumption 3, seems to be necessary to ensure this assumption, see Lemma 4.2), one has
On the other hand, by employing the constraint dissolving method to solve (23), one has to solve
where 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 , then . Since is continuously differentiable, one has . By (25), it is reasonable to ask
Requiring this identity for every smooth objective , i.e., for arbitrary , leads to the candidate as follows
Motivated by the above analysis, we impose the following assumption.
Assumption 2. (a) is twice continuously differentiable.
(b) There exist continuously differentiable mappings and defined on some open set containing and , respectively, satisfying both and for all and are symmetric positive semidefinite such that
For several widely-used classes of , including disjunctive, sparsity, low-rank-, low-rank positive semidefinite constraints, suitable choices of has been summarized in [9 Table 1]. Moreover, is usually given by a box-constraint, the corresponding choice of can be found in [18 Table 2]. We refer interested readers to these references for more details.
For a fixed , let us define
Based on the above notation, for , we define
Note that is positive definite on under some constraint qualification (see Lemma 4.2); however, it may be nearly singular. The regularization term alleviates this issue. Indeed, for every ,
independent of . However, this term vanishes on regardless of the value of , so that 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 and on .
Example 4.1. Let , , , , , and . Then and . The point is AM-regular. Indeed, since , we have . By , we have , then holds trivially. On the other hand, to ensure Assumption 2 (b), we set and choose . By and , for every , we have
which is singular. Therefore, AM-regularity is not sufficient to ensure that is positive definite on .
Therefore, a stronger constraint qualification is needed to ensure and thus for every . 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 and are two polyhedral convex sets.
Assumption 3. At any , is the only vector satisfying
Lemma 4.2. Suppose that Assumption 2 and Assumption 3 hold, and thus at every . Moreover, every is AM-regular.
Proof. For any , as well as ,
Hence for all .
Now suppose . Then the positive semidefiniteness of and implies
By Assumption 2 (b) and Assumption 3, one has . Thus for all . Since by , for all .
For any , fix some . Then we find sequences , , and such that , , , and . In particular, there exist sequences and satisfying and such that
If is unbounded, without loss of generality, we assume . Then it is reasonable to set . Dividing (26) by , by the continuity of and the outer semicontinuity of the limiting normal cone, we have and . Then Assumption 3 implies , and thus , which contradicts . Thus, the sequence is bounded, and therefore, possesses a convergent subsequence with limit . By the continuity of , taking the limit in (26) along this subsequence yields that
Moreover, by the continuity of and , , , and the outer semicontinuity of the limiting normal cone, we have and . Thus, (27) implies that . This shows that is AM-regular.
Note that Lemma 4.2 ensures the well-definedness of in (25). We next verify that it satisfies Definition 2.4. For brevity, we denote
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 specifically given by (25), every accumulation point of the sequence generated by Algorithm 1 is feasible for , provided that the inexactness sequence is bounded.
Lemma 4.4. Suppose that Assumption 1, Assumption 2, and Assumption 3 hold, the constraint dissolving mapping is defined by (25). Let be generated by Algorithm 1 with being bounded, and be any accumulation point of . Then is feasible for and thus is feasible for .
Proof. By Proposition 3.2 (i), it suffices to consider the case where is unbounded. Let us also take as an infinite index set such that , and denote and for convenience. By the closedness of and , we have . Then by Lemma 4.2, we have . Let us set . In view of Assumption 2, , and thus defined in (24) are continuous, then there exists such that on . By
Assumption 1 and Assumption 2, (defined in (30)), , , , and are continuous. Then, the compactness of implies that the constants
are finite. Recall that . For all large enough , one has . By Assumption 2 and (30), one has
and thus
Moreover, by (26) and (30), we have
By (19), there exists some such that with for each . Consequently, we have
Let us write for brevity, then (31) implies
for all large enough . Moreover, we have for all large enough . By (33), we have
for all . Since is defined by (27), then we have
Then
for all large enough . On the other hand, by the notation of and in (26), one has
Then, in view of Lemma 4.2 and (33), we have
for all large enough . Since is bounded, we let be the constant satisfying for all sufficiently large . Then by (34), (35), and (36), one has
and consequently,
for all large enough . Since , then . This means that is feasible for , and thus is feasible for .
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, be defined in (27), and be the sequence generated by Algorithm 1 with . Let be any accumulation point of . Then is an -stationary point for .
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 and in Algorithm 1, the parameter of the constraint dissolving mapping, and the mappings and depend on the problem and will be specified below. PD replaces the constraint by and and penalizes the constraints and , so that its subproblems consist of minimizing with respect to and . Following [10 Algorithm 2], we solve these subproblems by alternating a gradient step in , whose step size is determined by an Armijo line search, and the update .
In outer iteration , the inner stopping criterion of CD and ALM is [8 (3.4)] with tolerance , while the alternating scheme of PD is terminated when . The outer stopping criteria are as follows: CD terminates when , ALM when [8 (4.5)] is satisfied, and PD when [10 Section 6]. The same tolerance is used for all three methods, with for the problems in Sections 5.1 and 5.3 and for the real-world portfolio problems in Section 5.2. In addition, we impose the upper bound on the penalty parameter and a budget of evaluations of the subproblem objective functions per run. Given a point , all three methods are initialized from the same projected point . CD additionally sets , and PD sets . 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:
which corresponds to , , and . Its global minimizer is with and local minimizer is with . For the constraint dissolving mapping, we choose and , and we test the values in order to illustrate the corresponding numerical influence.
All three methods are run from the same 1000 starting points , where is equally spaced in and are drawn independently from the uniform distribution on . In this problem, we set , , and for CD, and we use the same initial penalty parameter for the three methods.
The results are summarized in Table 1, which reports the average numbers of outer iterations () and of cumulative inner iterations (). and are the numbers of runs whose final iterate has a distance of at most to and , respectively, and the average running time per run in milliseconds (). For each runs, the final iterate is close to either or in the above sense. However, CD finds the global minimizer more often: for every value of , it terminates near 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 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 and , 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. | ||||||
| CD | 0.01 | 4.050 | 32.154 | 968 | 32 | 0.58 |
| CD | 0.1 | 2.963 | 22.569 | 934 | 66 | 0.51 |
| CD | 1 | 2.035 | 16.170 | 906 | 94 | 0.40 |
| CD | 10 | 1.458 | 16.681 | 831 | 169 | 0.39 |
| CD | 100 | 1.298 | 33.002 | 813 | 187 | 1.23 |
| ALM | – | 15.488 | 56.778 | 668 | 332 | 0.52 |
| PD | – | 104.795 | 3075.530 | 800 | 200 | 37.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 and as the covariance matrix and the vector of expected returns of assets and as the all-one vector. In both problems, we use and . For all three methods, we choose the starting point as , where is a solution of the respective problem without the cardinality constraint , 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
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 , under which the whole capital is invested, this yields a test problem in which is not a singleton. More precisely, we set , , and . The data and are taken from the test problem collection [5], from which we use the orl and pard instances of dimension , 30 (20 orl and 10 pard) instances for each dimension, together with , resulting in 270 test problems. For CD, we set , , , , and .
The results are summarized in Table 2, which reports, for each pair , the average numbers of outer iterations () and of cumulative inner iterations (), the average running time in milliseconds (, minimum over three repetitions), the average final objective function value (), and the numbers of instances on which CD attains the lower objective function value (), ALM attains the lower one (), and the two methods 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.
| \multicolumn{4}{c}{CD} | \multicolumn{4}{c}{ALM} | |||||||||||
| Outer | Inner | Time | Outer | Inner | Time | |||||||
| 200 | 3 | 6.07 | 138.8 | 3.7 | 122.943 | 27.30 | 335.0 | 6.1 | 128.637 | 23 | 5 | 2 |
| 200 | 5 | 7.53 | 124.3 | 3.3 | 71.241 | 19.27 | 259.5 | 4.5 | 75.488 | 26 | 1 | 3 |
| 200 | 7 | 7.67 | 125.4 | 3.7 | 51.399 | 26.63 | 376.0 | 6.8 | 54.770 | 28 | 2 | 0 |
| 300 | 3 | 5.93 | 129.0 | 3.6 | 176.978 | 32.33 | 395.9 | 8.9 | 191.376 | 26 | 1 | 3 |
| 300 | 5 | 7.27 | 151.1 | 4.6 | 107.272 | 25.57 | 354.2 | 7.6 | 114.332 | 25 | 4 | 1 |
| 300 | 7 | 8.17 | 167.7 | 5.5 | 81.081 | 20.17 | 278.8 | 6.2 | 81.603 | 21 | 8 | 1 |
| 400 | 3 | 6.80 | 154.5 | 5.3 | 231.621 | 28.20 | 403.6 | 10.7 | 250.707 | 28 | 1 | 1 |
| 400 | 5 | 7.90 | 157.3 | 5.6 | 141.453 | 30.80 | 378.3 | 10.3 | 148.225 | 26 | 2 | 2 |
| 400 | 7 | 8.67 | 173.3 | 6.6 | 105.463 | 24.40 | 341.7 | 9.3 | 107.701 | 23 | 6 | 1 |
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 , 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
where the variance of the portfolio is minimized subject to a lower bound on its expected return. In contrast to the previous problem, the set now combines an inequality and an equality constraint, since we set , , and . 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 set | Market conditions | Stocks | Total time period | Out-of-sample time period |
| NASDAQ100 | – | 95 | 01/02/2020–09/12/2023 | 08/03/2022–09/12/2023 |
| FTSE100 | – | 97 | 01/02/2020–09/12/2023 | 07/19/2022–09/12/2023 |
| S&P500-D | Declining market | 490 | 03/12/2020–10/12/2022 | 01/03/2022–10/12/2022 |
| S&P500-C | COVID-19 | 478 | 12/06/2017–12/31/2020 | 02/03/2020–12/31/2020 |
| S&P500-R | Rising market | 497 | 09/17/2021–09/30/2024 | 11/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 periods form the out-of-sample period in Table 3. For each , the estimation window is shifted by periods, and are taken as the sample covariance matrix and the sample mean of the returns in this window, and problem (39) is solved with and . The resulting portfolio is then evaluated on the return of the following period. For CD, we set , , , , and .
Following [14], the computed portfolios are assessed out of sample by the mean and the standard deviation of their realized returns, the Sharpe ratio , and the risk reduction with respect to the equally weighted portfolio, which is denoted by . The corresponding results are summarized in Table 4, which reports, for each data set, the averages of , , and (in milliseconds) over all windows, the number 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 set | Alg. | |||||||||
| NASDAQ100 | 279 | CD | 2.97 | 499.4 | 21.8 | 155 | 0.003 | 0.0092 | −0.0125 | 2.63 |
| ALM | 13.01 | 1329.7 | 28.2 | 54 | 0.002 | 0.0091 | −0.0139 | 2.59 | ||
| – | – | – | – | 0.069 | 0.0140 | 0.0394 | 1.00 | |||
| FTSE100 | 278 | CD | 3.28 | 764.0 | 27.0 | 88 | −0.008 | 0.0072 | −0.0315 | 2.16 |
| ALM | 9.73 | 440.5 | 8.0 | 63 | −0.008 | 0.0071 | −0.0312 | 2.15 | ||
| – | – | – | – | 0.022 | 0.0100 | 0.0076 | 1.00 | |||
| S&P500-D | 196 | CD | 2.98 | 464.1 | 35.8 | 134 | −0.073 | 0.0104 | −0.0846 | 2.32 |
| ALM | 15.82 | 1622.9 | 85.9 | 49 | −0.061 | 0.0101 | −0.0746 | 2.34 | ||
| – | – | – | – | −0.091 | 0.0147 | −0.0717 | 1.00 | |||
| S&P500-C | 232 | CD | 2.99 | 544.5 | 33.1 | 30 | 0.021 | 0.0171 | 0.0041 | 3.19 |
| ALM | 6.61 | 437.1 | 20.6 | 46 | 0.029 | 0.0173 | 0.0083 | 3.19 | ||
| – | – | – | – | 0.118 | 0.0249 | 0.0418 | 1.00 | |||
| S&P500-R | 229 | CD | 3.05 | 603.4 | 49.8 | 126 | 0.091 | 0.0057 | 0.1352 | 1.84 |
| ALM | 10.69 | 1125.6 | 61.7 | 74 | 0.099 | 0.0059 | 0.1441 | 1.79 | ||
| – | – | – | – | 0.143 | 0.0077 | 0.1679 | 1.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 ) 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 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 and denote as the weight of the edge between the vertices and . Since we allow zero weights, without loss of generality, we can assume that the graph is complete. Given a subset with complement , the cut defined by is the set of all edges with one end point in and the other one in , and its weight is . The MaxCut problem looks for a cut with maximum weight and is known to be NP-hard.
In the following, let us denote as the space of symmetric matrices, equipped with the Frobenius inner product. With and the Laplacian matrix , by [6, 8], the MaxCut problem can be reformulated as
since the feasible points of (40) are exactly the matrices with , and, for such a matrix, is the weight of the cut defined by . 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 , , and . A projection of onto is given by , where is a largest eigenvalue of and is a corresponding unit eigenvector, so that its computation does not require a full spectral decomposition. For the constraint dissolving mapping, we choose and .
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 vertices, edge densities between 0.1 and 0.99, and integer edge weights in and for which the optimal cut values are known. In order to obtain a good starting point, we take as a solution of the semidefinite relaxation of (40), which we compute by ALM with replaced by the cone of positive semidefinite matrices. For CD, we set , , , , and . From the final iterate of each method, we obtain a cut from the signs of the entries of an eigenvector of corresponding to its largest eigenvalue.
Figure 4 summarizes the cut quantity in a condensed way: for each instance, we take the quotient as quantity measurement of the cut, where is the final function value obtained by each of the three methods and is the optimal cut value. Figure 4 then reports, for , the number of instances on which each method attains at least of the optimal value. For , PD attains at least 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 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.
| Group | CD | ALM | PD | |||||||||
| Outer | Inner | Time | Cut | Outer | Inner | Time | Cut | Outer | Inner | Time | Cut | |
| g05_60 | 2.00 | 27.6 | 0.026 | 99.00 | 11.60 | 227.4 | 0.067 | 99.44 | 130.6 | 103228 | 30.7 | 98.93 |
| g05_80 | 2.00 | 34.9 | 0.026 | 99.07 | 16.50 | 259.7 | 0.102 | 98.87 | 136.5 | 149546 | 61.0 | 99.02 |
| g05_100 | 4.00 | 42.4 | 0.045 | 99.07 | 20.40 | 365.9 | 0.219 | 98.98 | 141.7 | 202753 | 122.8 | 98.99 |
| pm1s_80 | 1.40 | 25.3 | 0.027 | 93.37 | 10.60 | 220.7 | 0.095 | 95.63 | 123.9 | 112677 | 45.3 | 95.73 |
| pm1d_80 | 2.00 | 61.2 | 0.040 | 96.31 | 16.70 | 320.3 | 0.125 | 92.77 | 136.1 | 157439 | 63.8 | 96.81 |
| pm1s_100 | 3.00 | 61.0 | 0.069 | 95.90 | 12.10 | 288.6 | 0.175 | 94.41 | 128.0 | 150592 | 89.7 | 96.89 |
| pm1d_100 | 2.00 | 55.8 | 0.057 | 96.00 | 20.50 | 376.5 | 0.219 | 95.87 | 140.0 | 227674 | 135.8 | 97.03 |
| w01_100 | 2.00 | 77.1 | 0.080 | 96.29 | 19.70 | 382.0 | 0.224 | 97.65 | 147.6 | 289699 | 173.0 | 96.60 |
| pw01_100 | 4.00 | 55.4 | 0.058 | 97.91 | 14.10 | 396.9 | 0.233 | 98.97 | 151.9 | 264581 | 159.3 | 97.95 |
| w05_100 | 4.00 | 110.7 | 0.113 | 95.35 | 17.20 | 436.8 | 0.259 | 95.46 | 155.7 | 344831 | 205.9 | 95.68 |
| pw05_100 | 4.00 | 51.3 | 0.051 | 99.09 | 19.50 | 378.5 | 0.220 | 99.12 | 161.5 | 279766 | 170.8 | 98.93 |
| w09_100 | 4.00 | 124.7 | 0.128 | 95.87 | 17.80 | 408.5 | 0.239 | 94.31 | 158.7 | 403367 | 239.2 | 95.77 |
| pw09_100 | 6.00 | 63.1 | 0.063 | 99.32 | 23.20 | 427.1 | 0.248 | 99.27 | 164.8 | 291427 | 178.3 | 99.19 |
| All | 3.11 | 60.8 | 0.060 | 97.12 | 16.92 | 345.3 | 0.187 | 96.98 | 144.4 | 229045 | 128.9 | 97.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 and , 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 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, , , and are continuously differentiable, and thus defined in (27) is also continuously differentiable. Also, for all , we have , and thus .
In view of (27), we have
where denotes the Jacobian of at . In particular,
Moreover, for any , we have . Then (26) and (30) yield
Consequently, one has
which means Definition 2.4 (c) holds. It remains to verify Definition 2.4 (d) and (e).
Motivated by (41), we set . By Assumption 1 and Assumption 2, we know that is continuous. For any , we have and thus . It remains to verify (e).
For any , choose a constant arbitrarily. For any satisfying , by Assumption 2 (b), one has and thus
This completes the proof.
References
References
- [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]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]E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming 91 (2002), pp. 201–213.DOI
- [4]R. Fletcher, A class of methods for nonlinear programming with termination and convergence properties (1970).
- [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]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]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]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]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]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]P. Mehlitz, Asymptotic stationarity and regularity for nonsmooth optimization problems, Journal of Nonsmooth Analysis and Optimization 1 (2020), pp. 6575: 1–30.DOI
- [12]S.M. Robinson, Constraint nondegeneracy in variational analysis, Mathematics of Operations Research 28 (2003), pp. 201–232.DOI
- [13]R.T. Rockafellar and R.J. Wets, Variational analysis, Springer, 1998.DOI
- [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]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]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]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]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]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




