New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints

Abstract

In this paper, we consider a sufficiently broad class of non-linear mathematical programs with disjunctive constraints, which, e.g. include mathematical programs with complemetarity/vanishing constraints. We present an extension of the concept of -stationarity which can be easily combined with the well-known notion of M-stationarity to obtain the stronger property of so-called -stationarity. We show how the property of -stationarity (and thus also of M-stationarity) can be efficiently verified for the considered problem class by computing -stationary solutions of a certain quadratic program. We consider further the situation that the point which is to be tested for -stationarity, is not known exactly, but is approximated by some convergent sequence, as it is usually the case when applying some numerical method.

Keywords:

• Mathematical programs with disjunctive constraints
• B-stationarity
• M-stationarity
• -stationarity

1. Introduction

In this paper, we consider the following mathematical program with disjunctive constraints (MPDC)(1)

where the mappings and , are assumed to be continuously differentiable and , , are convex polyhedral sets.

Denoting ,(2)

we can rewrite the MPDC (1(1) ) in the form(3)

It is easy to see that D can also be written as the union of convex polyhedral sets by(4)

As an example for MPDC consider a mathematical program with complementarity constraints (MPCC) given by(5)

with , , , , , , . This problem fits into our setting (1(1) ) with ,

MPCC is known to be a difficult optimization problem, because, due to the complementarity constraints , , , many of the standard constraint qualifications of nonlinear programming are violated at any feasible point. Hence, it is likely that the usual Karush–Kuhn–Tucker conditions fail to hold at a local minimizer and various first-order optimality conditions such as Abadie (A-), Bouligand (B-), Clarke (C-), Mordukhovich (M-) and Strong (S-) stationarity conditions have been studied in the literature [1–9].

Another prominent example is the mathematical program with vanishing constraints (MPVC)(6)

with , , , , , , . Again, the problem MPVC can be written in the form (1(1) ) with , , as in the case of MPCC and

Similar as in the case of MPCC, many of the standard constraint qualifications of non-linear programming can be violated at a local solution of (6(6) ) and a lot of stationarity concepts have been introduced. For a comprehensive overview for MPVC we refer to [10] and the references therein.

However, when we do not formulate MPCC or MPVC as a non-linear program but as a disjunctive program MPDC, then first-order optimality conditions can be formulated which are valid under weak constraint qualifications. We know that a local minimizer is always B-stationary, which geometrically means that no feasible descent direction exists, or, in a dual formulation, that the negative gradient of the objective belongs to the regular normal cone of the feasible region, cf. [11, Theorem 6.12]. The difficult task is now to estimate this regular normal cone. For this regular normal cone always a lower inclusion is available, which yields so-called S-stationarity conditions. For an upper estimate, one can use the limiting normal cone which results in the so-called M-stationarity conditions. The notions of S-stationarity and M-stationarity have been introduced in [12] for general programs (3(3) ). S-stationarity always implies B-stationarity, but it requires some strong qualification condition on the constraints which is too restrictive. On the other hand, M-stationarity requires only some weak constraint qualification but it does not preclude the existence of feasible descent directions. Further, it is not known in general how to efficiently verify the M-stationarity conditions, since the description of the limiting normal cone involves some combinatorial structure which is not known to be resolved without enumeration techniques. These difficulties in verifying M-stationarity have also some impact for numerical solution procedures. E.g. for many algorithms for MPCC it cannot be guaranteed that a limit point is M-stationary, cf. [13].

In the recent paper [14], we derived another upper estimate for the regular normal cone yielding so-called -stationarity conditions. -stationarity has the advantage over S-stationarity that it does not require such unnecessarily strong constraint qualification conditions. -stationarity can be easily combined with M-stationarity to obtain so-called -stationarity which is stronger than M-stationarity. This is one of the advantages of -stationarity: there are several stationarity notions, in particular in the MPCC literature, like M-, C-, A- and weak stationarity, which are valid under weak constraint qualification conditions. M-stationarity is known to be the strongest stationarity concept and we even improve M-stationarity by -stationarity.

For the disjunctive formulations of the problems MPCC and MPVC the - and -stationarity conditions have been worked out in detail in [14]. In this paper, we extend this approach to the general problem MPDC. We show that under a qualification condition which ensures S-stationarity of local minimizers, -stationarity and S-stationarity are equivalent. Further, we prove that under some weak constraint qualification every local minimizer of MPDC is a -stationary solution and we provide an efficient algorithm for verifying -stationarity of some feasible point. More exactly, this algorithm either proves the existence of some feasible descent direction, i.e. the point is not B-stationary, or it computes multipliers fulfilling the -stationarity condition. To this end, we consider quadratic programs with disjunctive constraints (QPDC), i.e. the objective function f in MPDC is a convex quadratic function and the mappings , are linear. We propose a basic algorithm for QPDC, which either returns a -stationary point or proves that the problem is unbounded. Further, we show that M-stationarity for MPDC is related with -stationarity of some QPDC and the combination of the two parts yields the algorithm for verifying -stationarity. This algorithm does not rely on enumeration techniques and this is another big advantage of the concepts of - and -stationarity.

Our approach is well suited to the MPDC (1(1) ) when all the numbers , are small or of moderate size. Our disjunctive structure is not induced by integral variables like, e.g. in [15]. It is also not related to the approach of considering the convex hull of a family of convex sets like in [16,17].

The outline of the paper is as follows. In Section 2, we recall some basic definitions from variational analysis and discuss various stationarity concepts. In Section 3, we introduce the concepts of - and -stationarity for general optimization problems. These concepts are worked out in more detail for MPDC in Section 4. In Section 5, we consider quadratic programs with disjunctive linear constraints. We present a basic algorithm for solving such problems, which either return a -stationary solution or prove that the problem is not bounded below. In the next section, we demonstrate how this basic algorithm can be applied to a certain quadratic program with disjunctive linear constraints in order to verify M-stationarity or -staionarity of a point or to compute a descent direction. In the last Section 7, we present some results for numerical methods for solving MPDC which prevent convergence to non M-stationary and non--stationary points.

Our notation is fairly standard. In Euclidean space we denote by and the Euclidean norm and scalar product, respectively, whereas we denote by the maximum norm. The closed ball around some point x with radius r is denoted by . Given some cone , we denote by its polar cone. By we refer to the usual distance of some point x to a set A. We denote by the recession cone of a convex set C.

2. Preliminaries

For the reader’s convenience, we start with several notions from variational analysis. Given a set and a point , the cone

is called the (Bouligand/Severi) tangent/contingent cone to at . The (Fréchet) regular normal cone to at can be equivalently defined either by

where means that with , or as the dual/polar to the contingent cone, i.e. by

For convenience, we put for . Further, the (Mordukhovich) limiting/basic normal cone to at is given by

If is convex, then both the regular and the limiting normal cones coincide with the normal cone in the sense of convex analysis. Therefore, we will use in this case the notation .

Consider now the general mathematical program(7)

where , are continuously differentiable and is a closed set. Let(8)

denote the feasible region of the program (7(7) ). Then a necessary condition for a point being locally optimal is(9)

which is the same as(10)

cf. [11, Theorem 6.12]. The main task of applying this first-order optimality condition now is the computation of the regular normal cone which is very difficult for nonconvex D.

We always have the inclusion(11)

but equality will hold in (11(11) ) for nonconvex sets D only under comparatively strong conditions, e.g. when is surjective, see [11, Exercise 6.7]. The following weaker sufficient condition for equality in (11(11) ) uses the notion of metric subregularity.

Definition 1:

A multifunction is called metrically subregular at a point of its graph with modulus , if there is a neighborhood U of such that

Theorem 1:

[18, Theorem 4]]Let be given by (8(8) ) and . If the multifunction is metrically subregular at and if there exists a subspace such that(12)

and(13)

then

In order to state an upper estimate for the regular normal cone we need some constraint qualification.

Definition 2:

[12, Definition 6]] Let be given by (8(8) ) and let .

(1)	We say that the generalized Abadie constraint qualification (GACQ) holds at if (14) where denotes the linearized cone.
(2)	We say that the generalized Guignard constraint qualification (GGCQ) holds at if (15)

Obviously GGCQ is weaker than GACQ, but GACQ is easier to verify by using some advanced tools of variational analysis. E.g. if the mapping is metrically subregular at then GACQ is fulfilled at , cf. [19, Proposition 1]. Tools for verifying metric subregularity of constraint systems can be found e.g. in [20].

Proposition 1:

[14, Proposition 3]]Let be given by (8(8) ), let and assume that GGCQ is fulfilled, while the mapping is metrically subregular at (0, 0). Then(16)

Note that we always have , see [11, Proposition 6.27]. However, if D is the union of finitely many convex polyhedral sets, then equality(17)

holds. This is due to the fact that by the assumption on D there is some neighborhood V of 0 such that .

Let us mention that metric subregularity of the constraint mapping at does not only imply GACQ and consequently GGCQ, but also metric subregularity of the mapping at (0, 0) with the same modulus, see [21, Proposition 2.1].

The concept of metric subregularity has the drawback that, in general, it is not stable under small perturbations. It is well known that the stronger property of metric regularity is robust.

Definition 3:

A multifunction is called metrically regular near a point of its graph with modulus , if there are neighborhoods U of and V of such that

The infimum of the moduli for which the property of metric regularity holds is denoted by

In the following proposition, we gather some well-known properties of metric regularity:

Proposition 2:

Let where is continuously differentiable and D is the union of finitely many convex polyhedral sets and consider the multifunctions and . Then

Moreover for every there is a neighborhood W of such that for all the mapping is metrically regular near (0, 0) with modulus ,(18)

and

Proof The statement follows from [11, Exercise 9.44] together with the facts that by our assumption on D condition (17(17) ) holds and that is a cone.

We now recall some well known stationarity concepts based on the considerations above.

Definition 4:

Let be feasible for the program (7(7) ).

(i)	We say that is B-stationary, if (9(9) ) or, equivalently, (10(10) ) hold.
(ii)	We say that is S-stationary, if
(iii)	We say that is M-stationary, if

Every local minimizer of (7(7) ) is B-stationary and this stationarity concept is considered to be the most preferable one. S- and M-stationarity have been introduced in [12] as a generalization of these notions for MPCC. Using the inclusion (5(5) ) it immediately follows, that S-stationarity implies B-stationarity. However the reverse implication only holds true under some additional condition on the constraints, e.g. under the assumptions of Theorem 1. Note that there always hold the inclusions

In order that a B-stationary point is also S-stationarity, both inclusions must be fulfilled with equality, i.e. besides the GGCQ which allows to replace the tangent cone by the linearized tangent cone, we need another constraint qualification condition ensuring like the conditions (12(12) ) and (13(13) ). It is well known that this additional condition is much more restrictive than the usual constraint qualifications allowing the linearization of the problem like metric (sub)regularity of the constraint mapping . Thus in the general case one cannot expect that a local minimizer is also S-stationary. This is the reason why other stationarity concepts like M-stationarity have also to be considered.

A B-stationary point is M-stationary under the very weak assumptions of Proposition 1. However, the inclusion can be strict, implying that a M-stationary point needs not to be B-stationary. Hence, M-stationarity does eventually not preclude the existence of feasible descent directions, i.e. directions with .

3. On - and -stationarity

In this section, we consider an extension of the concept of -stationarity as introduced in the recent paper [14]. -stationarity is based on the following simple observation.

Consider the general program (7(7) ), assume that GGCQ holds at the point and assume that we are given K convex cones , . Then for each we obviously have implying

If we further assume that and by taking into account, that by [14, Lemma 1] we have

for arbitrary sets , we obtain

Here, we use the convention that for sets we set for . It is an easy consequence of (11(11) ), that equality holds in this inclusion, provided . Hence, we have shown the following theorem.

Theorem 2:

Assume that GGCQ holds at and assume that are convex cones contained in . If(19)

then(20)

Further, if(21)

then equality holds in (20(20) ) and .

Remark 1:

Condition (19(19) ) is e.g. fulfilled, if for each either there is a direction with or is a convex polyhedral set, cf. [14, Proposition 1].

The proper choice of is crucial in order that (20(20) ) provides a good estimate for the regular normal cone. It is obvious that we want to choose the cones , as large as possible in order that the inclusion (20(20) ) is tight. Further, it is reasonable that a good choice of fulfills(22)

because then equation (21(21) ) holds whenever has full rank. We now show that (21(21) ) holds not only under this full rank condition but also under some weaker assumption.

Theorem 3:

Assume that GGCQ holds at and assume that we are given convex cones fulfilling (19(19) ), (22(22) ) and(23)

Then

In particular, (23(23) ) holds if there is a subspace(24)

such that (13(13) ) holds.

Proof The statement follows from Theorem 2 if we can show that (21(21) ) holds. Consider . Then there are elements , and such that , and . We conclude , implying and thus

Hence, and (21(21) ) is verified. In order to show the last assertion note that from (24(24) ), we conclude and consequently . Thus , . Since

it follows that (23(23) ) holds.

Corollary 1:

Assume that GGCQ holds at and assume that we are given convex cones fulfilling (19(19) ) and (22(22) ). Further assume that there is some subspace L fulfilling (12(12) ) and (13(13) ). Then, the sets

are convex cones contained in ,(25)

and

Proof Firstly observe that by (12(12) ). Next, consider . By (13(13) ) there exists and such that . Because of we have and thus by [22, Theorem 6.1] implying (25(25) ) by taking into account Remark 1. Further, from it follows that

Finally, note that , and the assertion follows from Theorem 3.

The following definition is motivated by Theorem 2.

Definition 5:

Let be feasible for the program (7(7) ) and let be convex cones contained in fulfilling (19(19) ).

(i)	We say that is -stationary with respect to , if
(ii)	We say that is -stationary with respect to , if

Note that this definition is an extension of the definition of - and -stationarity in [14], where only the case was considered.

The following corollary is an immediate consequence of the definitions and Theorem 2.

Corollary 2:

Assume that GGCQ is fulfilled at the point feasible for (7(7) ). Further assume that we are given convex cones fulfilling (19(19) ). If is B-stationary, then is -stationary with respect to . Conversely, if is -stationary with respect to and (21(21) ) is fulfilled, then is S-stationary and consequently B-stationary.

We know that under the assumptions of Proposition 1 every B-stationary point for the problem (7(7) ) is both M-stationary and -stationary with respect to every collection of cones fulfilling (19(19) ), i.e.

Comparing this relation with the definition of -stationarity we see that -stationarity with respect to is stronger than the simultaneous fulfilment of M-stationarity and -stationarity with respect to . We refer to [14, Example 2] for an example which shows that -stationarity is strictly stronger than M-stationarity. This is one of the advantages of -stationarity:

However, to ensure -stationarity of a B-stationary point , some additional assumption has to be fulfilled.

Lemma 1:

Let be B-stationary for the program (7(7) ) and assume that the assumptions of Proposition 1 are fulfilled at . Further assume that for every there exists a convex cone containing and satisfying . Then there exists a convex cone fulfilling such that for every collection fulfilling (19(19) ) the point is -stationary with respect to .

Proof From the definition of B-stationarity and (16(16) ) we deduce the existence of fulfilling . By taking we obviously have implying . Now consider cones fulfilling (19(19) ). Similar to the derivation of Theorem 2 we obtain

and the lemma is proved.

Lemma 2:

Let be feasible for (7(7) ) and assume that is the union of finitely many closed convex cones . Then for every there is some satisfying .

Proof Consider . By the definition of the limiting normal cone there are sequences and with

By passing to a subsequence if necessary we can assume that there is an index such that for all k and we obtain . Since the polar cone is closed, we deduce .

If is the union of finitely many convex polyhedral cones , then the mapping is a polyhedral multifunction and thus metrically subregular at (0, 0) by Robinson’s result [23]. Further we know that for any convex polyhedral cone Q we have . Hence, we obtain the following corollary.

Corollary 3:

Assume that is B-stationary for the program (7(7) ), that GGCQ is fulfilled at and that is the union of finitely many convex polyhedral cones. Then there is a convex polyhedral cone such that for every collection of convex polyhedral cones contained in the point is -stationary with respect to .

Let us notice that in contrast to S-, M- and many other types of stationarity the properties of - and -stationarity cannot be characterized by some single multiplier. In fact, Q- and -stationarity with respect to implies the existence of K multipliers satisfying

In case of -stationarity the multiplier also fulfills the M-stationarity conditions.

Further, let us note that -stationarity, although it is stronger that M-stationarity, does not imply B-stationarity in general. Thus, in general -stationarity is not a sufficient condition for a local minimizer as well.

4. Application to MPDC

It is clear that -stationarity is not a very strong optimality condition for every choice of . As mentioned above the fulfillment of (22(22) ) is desirable. For the general problem (7(7) ), it can be impossible to choose the cones such that (22(22) ) holds. If is the union of finitely many convex cones then we obviously have

However, to consider -stationarity with respect to is in general not a feasible approach because p is often very large. We will now work out that the concepts of - and -stationarity are tailored for the MPDC (1(1) ). In what follows let D and F be given by (2(2) ).

Given a point , we denote by

the indices of sets which contain . Further we choose for each some index set such that(26)

Obviously the choice is feasible but for practical reasons it is better to choose smaller if possible. E.g. if holds for some indices , then we will not include in . Such a situation can occur e.g. in case of MPVC when with .

Now consider

Since for every the set is the union of finitely many convex polyhedral sets, for every tangent direction we have for all sufficiently small. Hence, we can apply [24, Proposition 1] to obtain

with given by (4(4) ), and(27)

We will apply this setting in particular to points with feasible for MPDC.

Lemma 3:

Let be feasible for the MPDC (1(1) ) and assume that we are given K elements such that(28)

Then for each the cone is a convex polyhedral cone contained in , , and

Proof Obviously, for every the cone is convex and polyhedral because it is the product of convex polyhedral cones. This implies and follows from (27(27) ). By taking into account (27(27) ) the last assertion follows from

Definition 6:

Let be feasible for the MPDC (1(1) ) and let index sets , fulfilling (26(26) ) be given. Further we denote by the collection of all elements with , such that (28(28) ) holds.

(1)	We say that is -stationary (-stationary) for (1(1) ) with respect to , if is -stationary (-stationary) with respect to in the sense of Definition 5 with , .
(2)	We say that is -stationary (-stationary) for (1(1) ) if is -stationary (-stationary) for (1(1) ) with respect to some .

Definition 6 is an extension of the definition of - and -stationarity made for MPCC and MPVC in [14]. Note that the number K appearing in the definition of is not fixed. Denoting the minimal number K such that , we obviously have(29)

We see from (27(27) ) that the tangent cone is the union of the convex polyhedral cones . Hence, the minimal number is much smaller than the number of components of the tangent cone, except when all or nearly all sets have cardinality 1. E.g. when holds for all as it is the case of the MPCC (5(5) ), then we have whereas the number of convex cones building the tangent cone grows exponentially with the number of biactive constraints, i.e. complementarity constraints satisfying . The concepts of - and -stationarity for MPDC take advantage of the fact that although the tangent cone is the union of a huge number of cones, its polar cone can be written as the intersection of a small number of polars. Further, it is clear that for every and every we can find such that .

We allow K to be greater than for numerical reasons primarily. Recall that for testing -stationarity with respect to , we have to check for all whether , or equivalently, that is a solution of the linear optimization program

with . Theoretically the treatment of degenerated linear constraints is not a big problem but the numerical practice tells us the contrary. In [25] we have implemented an algorithm for solving MPVC based on -stationarity and the degeneracy of the linear constraints was the reason when the algorithm crashed. The possibility of choosing gives us more flexibility to avoid linear programs with degenerated constraints.

The following theorem follows from Corollaries 2, 3, Theorem 3 and the considerations above.

Theorem 4:

Let be feasible for the MPDC (1(1) ) and assume that GGCQ is fulfilled at .

(i)	If is B-stationary then is -stationary with respect to every element and there exists some such that is -stationary with respect to every .
(ii)	Conversely, if is -stationary with respect to some and (30) where , , then is S-stationary and consequently B-stationary. In particular, (30(30) ) is fulfilled if (31)

5. On quadratic programs with disjunctive constraints

In this section, we consider the special case of quadratic programs with disjunctive constraints (QPDC)(32)

where B is a positive semidefinite matrix, , , are matrices and , , are convex polyhedral sets, i.e. QPDC is a special case of MPDC with and , . In what follows, we denote by A the matrix

where .

We start our analysis with the following preparatory lemma.

Lemma 4:

Assume that the convex quadratic program(33)

is feasible, where B is some symmetric positive semidefinite matrix, , A is a matrix and is a convex polyhedral set. Then either there exists a direction w satisfying(34)

or the program (33(33) ) has a global solution .

Proof Assume that for every w with , we have , i.e. 0 is a global solution of the program

Since C is a convex polyhedral set, its recession cone is a convex polyhedral cone and so is as well. Hence,

and from the first-order optimality condition we derive the existence of multipliers and such that

The convex polyhedral set C is the sum of the convex hull of its extreme points and its recession cone. Hence, for every x feasible for (33(33) ) there is some and some such that and, by taking into account , we obtain(35)

The set is compact and we conclude that the objective of (33(33) ) is bounded below on the feasible domain by . Thus

is finite and there remains to show that the infimum is attained. Consider some sequence with . We conclude from (35(35) ) that is bounded which in turn implies that the sequence is bounded. Hence, the sequence is bounded as well and we can conclude also the boundedness of . By passing to a subsequence we can assume that the sequence converges to some and it follows that . Since C is a convex polyhedral set, it follows by applying [22, Theorem 19.3] twice, that the sets and are convex and polyhedral. Since convex polyhedral sets are closed, it follows that . Thus there is some with and follows. This shows that is a global minimizer for (33(33) ).

In what follows, we assume that we have at hand an algorithm for solving (33(33) ), which either computes a global solution or a descent direction w fulfilling (34(34) ). Such an algorithm is, e.g. the active set method as described in [26], where we have to rewrite the constraints equivalently in the form , using the representation of C as the intersection of finitely many half-spaces, .

Consider now the following algorithm.

Algorithm 1 can be considered as a kind of active index set strategy. The set chosen in step (2) acts as a working set and is a subset of the active pieces of the disjunctive constraints. The number K will also depend on and for practical reasons it is desirable to keep K small to have small numerical effort in each iteration. Recall that we can always choose K equal to the number given by (29(29) ) which is bounded by . The working set is used for testing for unboundedness of the problem and -stationarity, respectively, by investigating the quadratic subproblems . If one of these subproblem’s problem appears unbounded, we stop the algorithm because of unboundedness of the whole program. If is a solution for every quadratic subproblem, we stop the algorithm because is -stationary. On the other hand, if is not a solution of one of these subproblems, then we take the point as the solution of this subproblem, yielding a smaller objective function value. Then, we repeat the whole procedure by generating a new working set and testing for termination.

In the next theorem, we show that Algorithm 1 is finite. However, we do not know any nontrivial bound on the number of iterations needed, as usual for active set strategies.

Theorem 5:

Algorithm 1(1) terminates after a finite number of iterations either with some feasible point and some descent direction w indicating that QPDC is unbounded below or with some -stationary solution.

Proof If Algorithm 1 terminates in step (2) the output is a feasible point together with some descent direction showing that QPDC is unbounded below. If the algorithm does not terminate in step (2), the computed sequence of function values is strictly decreasing. Moreover, denoting where l is the index chosen in step (4), we see that for each the point is global minimizer of the problem

This shows that all the vectors must be pairwise different and since there is only a finite number of possible choices for , the algorithm must stop in step (3). We will now show that the final iterate is -stationary with respect to . Since for each the point is a global minimizer of the subproblem , it also satisfies the first order optimality condition

This shows -stationarity of and the theorem is proved.

6. On verifying -stationarity for MPDC

The following theorem is crucial for the verification of M-stationarity.

Theorem 6:

(i)	Let be feasible for the general program (7(7) ). If there exists a B-stationary solution of the program (36) then is M-stationary.
(ii)	Let be B-stationary for the MPDC (1(1) ) and assume that GGCQ holds at . Then the program (36(36) ) has a global solution.

Proof

(i)

Let denote a B-stationary solution, i.e. , where . Since the matrix obviously has full rank, we have by [11, Exercise 6.7]. Thus there exists a multiplier such that and . Using [11, Proposition 6.27] we have establishing M-stationarity of .

(ii)

Consider for arbitrarily fixed the convex quadratic program (37) Assuming that this quadratic program does not have a solution, by Lemma 4 we could find a direction satisfying This implies , and and thus, together with GGCQ, contradicting our assumption that is B-stationary for (1(1) ). Hence, the quadratic program (37(37) ) must possess some global solution . By choosing such that it follows from (27(27) ) that is a global solution of (36(36) ).

We now want to apply Algorithm 1 to the problem (36(36) ). Note that the point (0, 0) is feasible for (36(36) ) and therefore we can start Algorithm 1 with .

Corollary 4:

Let be feasible for the MPDC (1(1) ) and apply Algorithm 1(1) to the QPDC (36(36) ). If the algorithm returns an iterate together with some descent direction indicating that (36(36) ) is unbounded below and if GGCQ is fulfilled at , then is not B-stationary. On the other hand, if the algorithm returns a -stationary solution, then is M-stationary.

Proof Observe that in case when Algorithm 1 returns a -stationary solution, by Theorem 4(ii) this solution is B-stationary because the Jocobian of the constraints obviously has full rank. Now the statement follows from Theorem 6.

We now want to analyse how the output of Algorithm 1 can be further utilized. Recalling that has the disjunctive structure

we define for the index sets

Further we choose for each some index set such that(38)

and set

Note that we always have

In order to verify -stationarity for the problem (36(36) ) at some feasible point (u, v), we have to consider the set consisting of all with , such that

At the k-th iterate we have to choose and then for each we must analyse the convex quadratic program

If for some this quadratic program is unbounded below then Algorithm 1 returns the index together with a descent direction fulfilling, as argued in the proof of Theorem 6(ii),

Therefore, constitutes a feasible descent direction, provided GACQ holds at , i.e. for every sufficiently small the projection of on the feasible set yields a point with a smaller objective function value than . If GACQ also holds for the constraint at , then we can also project the point on in order to reduce the objective function.

Now, assume that the final iterate of Algorithm 1 is -stationary for (36(36) ) and consequently is M-stationary for the MPDC (1(1) ). Setting , the first order optimality conditions for the quadratic programs result in

From this we conclude with where is the index vector returned from Algorithm 1. Now choosing such that we can simply check by testing , whether is stationary or is not B-stationary.

Further, we have the following corollary.

Corollary 5:

Let be B-stationary for the MPDC (1(1) ) and assume that GGCQ is fulfilled at . Let be the index vector returned by Algorithm 1(1) applied to (36(36) ). Then and for every with the point is -stationary with respect to .

7. Numerical aspects

In practice, the point which should be checked for M-stationarity and -stationarity, respectively, often is not known exactly. E.g. can be the limit point of a sequence generated by some numerical method for solving MPDC. Hence, let us assume that we are given some point close to and we want to state some rules when we can consider as approximately M-stationary or -stationary. Let us assume that the convex polyhedral sets have the representation

where without loss of generality we assume .

We use here the following approach.

In the first step of Algorithm 2, we want to estimate the tangent cone . In fact, to calculate we need not to know the point , we only need the index sets of constraints active at and these index sets are approximated by -active constraints. Note that whenever and , , this approach yields the exact tangent cones for all , . To be consistent with the notation of Section 4 we make the convention that in this case the index vector computed in step (2) belongs to and also, whenever we determine is step (4), we have . The regularization term in forces the objective to be strictly convex and therefore Algorithm 1 will always terminate with a -stationary solution. Further note that the verification of (39(39) ) requires the solution of linear optimization problems.

The following theorem justifies Algorithm 2. In the sequel, we denote by the set of all such that the mapping is metrically regular near (metrically subregular at ).

Theorem 7:

Let be feasible for the MPDC (1(1) ) and assume that and are Lipschitz near . Consider sequences , , and with

and let , and eventually and denote the output of Algorithm 2 with input data .

(i)

For all t sufficiently large and for all we have (39)

(ii)

Assume that the mapping is metrically regular near . (a) If is B-stationary then for all t sufficiently large the point is accepted as approximately M-stationary and approximately -stationary. (b) If for infinitely many t the point is accepted as approximately M-stationary then is M-stationary. (c) If for infinitely many t the point is accepted as approximately -stationary and then is -stationary. (d) For every t sufficiently large such that the point is not accepted as approximately M-stationary and we have . (e) For every t sufficiently large such that the point is not accepted as approximately -stationary and we have .

Proof (i) Let be chosen such that f, F and their derivatives are Lipschitz on with constant L. It is easy to see that we can choose such that for all we have and such that for every we have . Consider t with , and fix . For every we have

whereas for we have

showing . Now fix and let , i.e. . By taking into account we obtain

implying , whereas for we have

showing . Hence, . Because of our assumptions we have and for all t sufficiently large and this proves (40(40) ).

(ii) In view of Proposition 2, we can choose large enough such that the mappings , and , , are metrically regular near with modulus . By eventually shrinking R we can assume that for every the mappings , , are metrically regular near (0, 0) with modulus .

Without loss of generality we can assume that and (40(40) ) holds for all t implying that holds for all , . In fact, then the problem is the same as

The point is -stationary for this program and thus also S-stationary by Theorem 4(ii) and the full rank property of the matrix . Hence, there is a multiplier fulfilling , and we conclude(40)

from (18(18) ).

By -stationarity of we know that is the unique solution of the strictly convex quadratic program(41)

For every , the point is feasible for this quadratic program and thus is solution of

implying

Hence,(42)

and from (41(41) ) we obtain(43) (a) Assume on the contrary that is B-stationary but for infinitely many t the point is not accepted as approximately M-stationary and hence . This implies

and by the metric regularity of near (0, 0) we can find with

Our choice of the parameters , together with (43(43) ) ensures that for t sufficiently large we have

which contradicts B-stationarity of . Hence, for all t sufficiently large the point must be accepted as approximately M-stationary.

To prove the statement that is also accepted as approximately -stationary for all t sufficiently large we can proceed in a similar way. Assume on the contrary that is B-stationary but for infinitely many t the point is not accepted as approximately -stationary. For those t, let denote some element fulfilling , and Then, similar as before we can find such that

and for large t we obtain

contradicting B-stationarity of .

(b) By passing to a subsequence we can assume that for all t the point is accepted as approximately M-stationary and hence . By (44) we have that the sequence is uniformly bounded and by passing to a subsequence once more we can assume that it converges to some . By [11, Proposition 6.27] we have and together with

M-stationarity of is established.

(c) By passing to a subsequence we can assume that for all t the point is accepted as approximately -stationary and . Hence, for all t the point is also accepted as M-stationary and by passing to a subsequence and arguing as in (b) we can assume that converges to some fulfilling . Since the set is finite, by passing to a subsequence once more we can assume that there is a number K and elements such that , and , holds for all t. Since we assume that (40(40) ) holds we have and we will now show that is -stationary with respect to . Since also solves (42(42) ), it follows that and thus implying . There remains to show , . Assume on the contrary that for some index . Then there is some , such that and since , for each t there is some with

It follows that for all t sufficiently large we have and

contradicting our assumption that is accepted as approximately -stationary.

(d), (e) We assume that is chosen large enough such that the mappings , are metrically subregular at with modulus . Then by [21, Proposition 2.1] the mappings , are metrically subregular at (0, 0) with modulus as well. Taking into account that solves (42(42) ), we can copy the arguments from part (a) with replaced by to show the existence of with whenever is not accepted as approximately M-stationary and t is sufficiently large. In doing so, we also have to recognize that metric regularity of can be replaced by the weaker property of metric subregularity. Since , is a feasible descent direction and for sufficiently small the projection of on yields a point with a smaller objective function value than . This proves (d). In order to show (e), we can proceed in a similar way. Using the same arguments as in part (a), we can prove the existence of a feasible direction with , whenever t is sufficiently large and is not accepted as approximately -stationary. Together with the assertion follows.

Additional information

Funding

The research was supported by the Austrian Science Fund (FWF) [grant number P26132-N25], [grant number P29190-N32].

Notes

No potential conflict of interest was reported by the authors.