|
Article Excerpt
In this paper, optimization problems P with complementarity constraints are considered. Characterizations for local minimizers [bar.x] of P of Orders 1 and 2 are presented. We analyze a parametric smoothing approach for solving these programs in which P is replaced by a perturbed problem [P.sub.[tau]] depending on a (small) parameter [tau]. We are interested in the convergence behavior of the feasible set [F.sub.[tau]], and the convergence of the solutions [[bar.x].sub.[tau]] of [P.sub.[tau]] for [tau] [right arrow] 0. In particular, it is shown that, under generic assumptions, the solutions [[bar.x].sub.[tau]] are unique and converge to a solution [bar.x] of P with a rate O([square root of [tau]]). Moreover, the convergence for the Hausdorff distance d([F.sub.[tau]], F) between the feasible sets of [P.sub.[tau]] and P is of order O([square root of [tau]]).
Key words: mathematical programs with complementarity constraints; smoothing method; rate of convergence; genericity
1. Introduction. This paper deals with optimization problems of the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. (1)
As usual, such a program will be called a mathematical program with complementarity constraints or a mathematical program with equilibrium constraints (MPEC). All functions f, [g.sub.j], [r.sub.i], [s.sub.i]: [R.sup.n] [right arrow] are assumed to be [C.sup.2] functions. The constraints [r.sub.i](x)[s.sub.i](x) = 0, [r.sub.i](x), [s.sub.i](x) [greater than or equal to] are called complementarity constraints.
This class of MPEC problems is a topic of intensive recent research. (See, e.g., Fukushima and Lin [4], Fukushima and Pang [5], Hu and Ralph [8], Leyffer [9], Lin and Fukushima [10], Luo et al. [11], Ralph and Wright [13], Scheel and Scholtes [14], Scholtes and Stohr [16], and the references in these contributions.) Complementarity constraints arise in problems with equilibrium conditions (cf. Outrata et al. [12]) or as special cases in the so-called Karush-Kuhn-Tucker (KKT) approach for solving problems with a bilevel structure (see, e.g., Stein and Still [17]).
We say that at a local solution [bar.x] of P the strict complementary (SC) slackness is fulfilled if the relation
(SC): [r.sub.i]([bar.x]) + [s.sub.i]([bar.x]) > 0, [for all] i [member of] I (2)
is satisfied. The problem in MPEC is that typically the condition SC is not satisfied at a solution [bar.x] of P. It is also well known that the Mangasarian-Fromovitz constraint qualification (MFCQ) of standard finite programming (and thus the stronger Linear Independency constraint qualification [LICQ]) fails to hold at any feasible point of P (see, e.g., Chen and Florian [2]). So, to solve these complementarity constrained programs numerically, we cannot use standard software of nonlinear programming, since the standard algorithms always rely on LICQ.
To circumvent this problem the following parametric smoothing approach can be applied. Instead of P, we consider the perturbed problem
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], (3)
where [tau] > is a small perturbation parameter. In this paper, we intend to analyze the convergence behavior of this approach.
In the following, let [phi], [[phi].sub.[tau]] denote the marginal values, F, [F.sub.[tau]], the feasible sets, and [L.sub.[tau]], L the sets of minimizers of P = [P.sub.0], [P.sub.[tau]], respectively. We expect, by letting [tau] [right arrow] 0, that a solution [[bar.x].sub.[tau]] of [P.sub.[tau]] converges to a solution [bar.x] of P.
It will be shown that under natural (generic) assumptions the convergence rate for
[F.sub.[tau]] [right arrow] F and for [[bar.x].sub.[tau]] [right arrow] [bar.x] is of order O([square root of [tau]]).
The assumptions MPEC-LICQ, MPEC-SC, and MPEC-SOC (cf. (6), (15), (16)) will play a crucial role in the convergence analysis.
The paper is organized as follows: Section 2 illustrates the convergence behavior on some motivating examples and discusses natural regularity conditions. Section 3 reviews the genericity results in Scholtes and Stohr [16] and presents necessary and sufficient optimality conditions for a minimizer [bar.x] of P of Orders 1 and 2 under natural assumptions. In [section] 4, the convergence behavior of the perturbed feasible set [F.sub.[tau]] is analyzed from local and global viewpoints. Finally, in the last section we prove the existence of local minimizers [[bar.x].sub.[tau]] of [P.sub.[tau]] near a local minimizer [bar.x] of P and their unicity. We show that generically the rate [parallel][[bar.x].sub.[tau]] - [bar.x][parallel] = P([square root of [tau]]) takes place.
We introduce some notation. The distance between a point x and a set F is defined by d(x, F) = min{[parallel]x - x[parallel]| x [member of] F}. We also use the notation [B.sub.[epsilon]]([bar.x]) = {x | [parallel]x - [bar.x][parallel] < [epsilon]} and denote its closure by [[bar.B].sub.[epsilon]]([bar.x]). The norm [parallel]x[parallel] will always be the Euclidean norm.
In the rest of this introduction, we will discuss earlier results related to our investigations. The parametric approach (3) was used for the first time by Luo et al. [11] in connection with equilibrium constrained problems. Here, constraints [y.sub.i][w.sub.i] = had been perturbed to [y.sub.i][w.sub.i] = [sigma][mu] (cf. Luo et al. [11, p. 280]). For problems of the type (1), this smoothing method has been applied by Facchinei et al. [3], Fukushima and Pang [5], and Hu [7] (using NCP-functions). In these papers, the convergence to a B-stationary point has been established (under appropriate regularity assumptions). In Stein and Still [17], such a convergence is obtained for a similar (interior point) approach for solving semi-infinite programming problems. A referee drew our attention to the (preprint) of Ralph and Wright [13]. Here, a convergence [parallel][[bar.x].suib.[tau]] - [bar.x][parallel] [less than or equal to] O([[tau].sup.1/4]) has been shown (see also Corollary 5.2).
Under an additional MPEC-SC condition, we will prove the convergence [parallel][[bar.x].sub.[tau]] - [bar.x][parallel] = O([[tau].sup.1/2]) (cf. Theorem 5.1). With respect to this result, the present contribution is complementary to the paper (Ralph and Wright [13]).
Other regularizations of MPEC problems have been considered in the literature such as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].
Scholtes [15] answered the question under which assumptions a stationary point x([tau]) of [P.sup.[less than or equal to].sub.[tau]], [tau] [down arrow] 0, converges to a B-stationary point of P. In Ralph and Wright [13], it is shown that (under natural conditions) the solution x([tau]) of [P.sup.[less than or equal to].sub.[tau]] converges to a (nearby) solution [bar.x] of MPEC with order O([tau]). Similar results are stated for the problem [P.sup.[less than or equal to].sub.[tau]].
We emphasize that these regularizations [P.sup.[less than or equal to].sub.[tau]], [P.sup.[less than or equal to].sub.[tau]] are structurally completely different from the smoothing approach [P.sub.[tau]]. For [P.sup.[less than or equal to].sub.[tau]], e.g., the following is shown in Scholtes [15, Theorem 3.1, Corollary 3.2]: if [bar.x] is a solution of P where MPEC-LICQ and MPEC-SC holds, then for the (nearby) minimizers [x.sub.[tau]] of [P.sup.[less than or equal to].sub.[tau]] (for [tau] small enough), the complementarity constraints [r.sub.i](x)[s.sub.i](x) [less than or equal to] [tau], i [member of] [I.sub.rs] ([bar.x]), are not active (cf. [section] 2 for a definition of [I.sub.rs]([bar.x])). More precisely,
[r.sub.i]([x.sub.[tau]]) = [s.sub.i]([x.sub.[tau]]) = 0, [for all] I [member of] [I.sub.rs]([bar.x]) is true. This fact can also be deduced from Corollary 3.1 (cf. [section] 3). In particular, in the case I = I[r.sub.s]([bar.x]) (for all small [tau] > 0), the solution [[??].sub.[tau]] of [P.sup.[less than or equal to].sub.[tau]] coincides with the solution [bar.x] of P. In Hu and Ralph [8], the following parametric version of P has been studied:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],
under the assumption f, [g.sub.j], [r.sub.i], [s.sub.i] [member] [C.sup.2] (with respect to [wrt] all variables). Let [bar.x] be a local minimizer of P(0) (i.e., [tau] = 0). In contrast to our perturbation [P.sub.[tau]] in (3), under natural assumptions the parametric program P([tau]) can be analyzed using the (smooth) Implicit Function Theorem so that, roughly speaking, the perturbation P([tau]) behaves more smoothly than the perturbation [P.sub.[tau]] (In fact, by using the result of Corollary 3.1, the problem P([tau]) can be analyzed as the parametric version of the relaxed problem [P.sub.R]([bar.x]) [see Corollary 3.1], i.e., it can be treated as a standard parametric optimization problem.) In particular, under the assumption that MPEC-LICQ and MPEC-SOC hold at [bar.x], the value function [phi]([tau]) of P([tau]) is differentiable at [tau] = implying
[absolute value of [phi]([tau]) - [phi]] = O([tau])
and a similar behavior for the minimizers. This contrasts with the nonsmooth behavior [absolute value of [phi]([tau]) - [phi]] = O([square root of [tau]]) for the perturbation [P.sub.[tau]] (see Example 2.1 and Corollary 5.1).
REMARK 1.1. For numerical purposes, it is convenient to model the constraints [r.sub.i](x)[s.sub.i](x) = [tau] and [r.sub.i](x), [s.sub.i](x) [greater than or equal to] equivalently by a unique constraint [[phi].sub.[tau]]([r.sub.i](x), [s.sub.i](x)) = where [[phi].sub.[tau]] is a so-called parameterized NCP-function (see, e.g., Chen and Mangasarian [1] and Fukushima and Pang [5]).
REMARK 1.2. We emphasize that all results in this paper remain valid for problems P containing additional equality constraints [c.sub.l](x) = if we assume additional linear independence of the gradients [nabla][c.sub.l](x). To keep the presentation as clear as possible, we omit these equality constraints.
The smoothing approach [P.sub.[tau]] is directly connected with the interior point method for solving finite optimization problems (FP). To solve a program
FP: min f(x) s.t. [g.sub.j](x) [greater than or equal to] 0, j [member of] J,
one tries to solve the perturbed KKT system
[E.sub.[tau]]: [nabla]f(x) - [[nabla].sup.T] g(x)[mu] = 0, [g.sub.j](x)[[mu].sub.j] = [tau], [for all] j [member of] J,
and [[mu].sub.j], [g.sub.j](x) [greater than or equal to] 0. This is a special case of a feasible set of a problem [P.sub.[tau]] (including equality constraints). In Wright and Orban [19] the convergence behavior of solutions [x.sub.[tau]], [[mu].sub.[tau]] of [E.sub.[tau]] has been analyzed (via properties of the log barrier function) also for the case that the SC condition is not satisfied at the solution [bar.x], [bar.[mu]] of [E.sub.0]. Here also, a convergence rate O([square root of [tau]]) has been established (under the weaker MFCQ assumption). So the results of [section]5 can be seen as a generalization of (some of the) results in Wright and Orban [19].
2. Motivating examples and regularity conditions. We begin with some illustrative examples and formulate regularity conditions to avoid some negative convergence behavior.
EXAMPLE 2.1.
min [x.sub.1] + [x.sub.2]
s.t. [x.sub.1] x [x.sub.2] = 0,
[x.sub.1], [x.sub.2] [greater than or equal to] 0.
Here, the set [F.sub.[tau]] converges to the set F and the solutions [[bar.x].sub.[tau]] = ([square root of [tau]], [square root of [tau]]) of [P.sub.[tau]] converge to the solution [bar.x] = of P with a rate [parallel][[bar.x].sub.[tau]] - [bar.x][parallel] = [square root of 2] x [square root of [tau]] and [absolute value of [[phi].sub.[tau]] - [phi]] = [square...
|
