|
Article Excerpt
This paper introduces a concept termed partial B-regularity for a feasible solution to a bivariate constraint system and shows that this condition leads to the equivalence between the B-stationarity of a pair of lifted and unlifted programs. In particular, for an optimization problem with a univariate pseudoconvex objective function constrained by such a nonconvex bivariate system, partial B-regularity provides a sufficient condition for a B-stationary point to be globally optimal. Applications of partial B-regularity to several classes of optimization and equilibrium problems are presented; these include a lexicographic optimization problem, a nonconvex mathematical program with equilibrium constraints (MPEC) that arises from a convex implicit value-function optimization problem, and a Nash equilibrium program with equilibrium constraints.
Key words: partial B-regularity; equilibrium constraints; stationary points; lexicographic optimization
1. Introduction. Nonconvex optimization problems are challenging in that the stationarity conditions are not sufficient for global optimality. The goal of this paper is to introduce a concept, which we term partial B-regularity, for a feasible solution to a bivariate constraint system and show that this condition enables the equivalence between the B-stationarity of a pair of lifted and unlifted programs. In particular, for an optimization problem with a univariate pseudoconvex objective function constrained by such a nonconvex bivariate system, partial B-regularity provides a sufficient condition for a B-stationary point to be globally optimal. This concept originates from the seminal work of Robinson [34] on a strongly regular solution to a generalized equation, whose impact on continuous optimization is enormous. An extension of strong regularity is regularity, whose fundamental role in the stability analysis of optimization problems and variational inequalities (VIs) is well documented in Facchinei and Pang [7, Chapter 5]. A further extension of regularity leads to the concept of partial B-regularity, which turns out to be fundamental for the global optimality of a stationary point to a nonconvex optimization problem of a certain kind.
A rich source of bivariate constraint systems is derived from univariate systems with implicitly defined functions, such as equilibrium constraints in the form of parametric VIs or complementarity problems (CPs), where the parameter, the model variables, and the multipliers all play different roles. In general, to expose the implicitly defined constraints or express the variational conditions to facilitate practical computations, auxiliary variables need to be introduced, thereby lifting the original constraints to a higher dimensional space that includes the added variables. Nevertheless, such lifting often destroys any convexity that the original system might possess, thereby endangering the global optimality of a numerical iterate in an optimization problem constrained by the lifted system. More generally, the relationship between the stationary points and local minima of the lifted formulation and those of the unlifted problem needs to be established. For a mathematical program with equilibrium constraints (MPEC), such an issue has been investigated in [section] 3.4 of the monograph (Luo et al. [22]). Our work extends the latter study in several directions. One, the primary problem of interest herein is an implicit program that is reformulated as an MPEC when the implicit functions are exposed; this is the step before the MPEC is reformulated as an optimization problem with complementarity constraints via the Karush-Kuhn-Tucker (KKT) conditions of the equilibrium constraints, the latter reformulation being the starting point of the study in Luo et al. [22]. Another topic that is not dealt with in the reference is the global optimality of a given stationary solution to the KKT formulation of the MPEC, with reference to the original implicit program in case the latter is convex. We are particularly interested in the latter issue because of the class of equilibrium programs with equilibrium constraints (EPECs), whose research has gained momentum in recent years because of its importance in modeling two-stage equilibrium problems.
The notion of partial B-regularity is another contribution of this work. In general, this notion can be defined with respect to any bivariate feasibility system in finite dimensions. When applied to a parametric VI, with the parameter and the variable of the VI considered as the pair of variables, a partially B-regular solution of the VI is not necessarily isolated (see Proposition 3.2); this is a significant departure from regularity (and thus from strong regularity) under which the solution on hand must be locally unique, among other things. As we will show, partial B-regularity is a rather mild restriction to be imposed on the solutions to an affine variational inequality (AVI). Because VIs, particularly complementarity, are the key nonconvex constraints in an MPEC (and/or a bilevel program) (Dempe [4, 5], Luo et al. [22], Outrata et al. [26]), it is natural to apply the partial B-regularity concept to the MPEC. In turn, because MPECs provide the basic component of an equilibrium program with equilibrium constraints (EPECs), partial B-regularity enables us to establish the sufficiency of the first-order necessary conditions that must be satisfied by a solution to an EPEC. The latter result provides a first nontrivial sufficient condition for an equilibrium solution to the EPEC in terms of some complementarity-like systems, thereby validating a natural nonlinear programming (NLP) approach for solving this class of highly nonconvex equilibrium problems (Leyffer and Munson [21]).
The EPEC is a novel mathematical paradigm for computing an equilibrium to a noncooperative game wherein the players make their decisions subject to a second-stage equilibrium (possibly optimization) that are dependent on the first-stage decisions. Two notable examples of an EPEC are the multileader-follower game (Pang and Fukushima [29]), which extends the well-known (single-leader) Stackelberg game, and a two-stage Nash-Cournot equilibrium problem that arises as a result of capacity expansion, financial contracts, and/or demand uncertainty. Within the short span of a few years since it was first informally introduced in an applied electricity market model (Hobbs et al. [15]), the EPEC has been the subject of several Ph.D. dissertations (Ehrenmann [6], Su [37], Yao [41]) and an increasing number of articles (Chen et al. [3], Hu and Ralph [17], Leyffer and Munson [21], Mordukhovich [23], Outrata [25], Pang and Fukushima [29], Su [38], Yao et al. [42]). In spite of the extensive research so far, constructive characterizations of a solution to an EPEC remain elusive to date. This is not without a reason; indeed, since the EPEC is the concatenation of several MPECs, each of which is a nonconvex optimization problem for which practical means are lacking for determining global optimality, it is not easy to determine when the first-order necessary conditions for an equilibrium solution to the EPEC are sufficient. Part of the contribution of this paper is to identify a class of EPECs, the partially B-regular ones, for which such a difficulty can be overcome.
The organization of the rest of this paper is as follows. The next section introduces the partial B-regularity concept and establishes a main result concerning the tangent vectors of an unlifted set and its lifted formulation. Section 3 identifies sufficient conditions for partial B-regularity in parametric variational constraint systems. Section 4 deals with MPEC stationarity and optimality conditions and establishes the equivalence of these conditions under regular B-regularity and convexity. The fifth and last [section] 5 discusses the applications of partial B-regularity to two classes of optimization problems and to a two-stage Nash game.
2. Partial B-regularity. Let Z be a closed set consisting of pairs of vectors (x, y) [member of] [R.sup.n+m]. To distinguish their respective roles, we call x the primary (or first-stage) variable and y the auxiliary (or second-stage) variable. We recall the tangent cone of Z at a pair [??] [equivalent to] ([??], [??] [member of] Z, denoted F(Z; [??]), which is a closed cone (not necessarily convex) whose elements are vectors dz [member of] [R.sup.n+m] for which a sequence {[z.sup.k]} [subset] Z of vectors converging to [??] and a sequence of positive scalars {[[tau].sub.k]} converging to zero exist such that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
Let X be...
|
