Nonlinear Optimization and Applications 2, pp. 1-000 G. Di Pillo and F. Giannessi, Editors \begin{matrix}c \\ ◯ \end{matrix}1998 Kluwer Academic Publishers B.V.

A new merit function and an SQP method for non-strictly monotone variational inequalities

Michael Patriksson (mipat@math.chalmers.se) Department of Mathematics Chalmers University of Technology S-412 96 Gothenburg, Sweden

Abstract

Merit functions utilized to monitor the convergence of sequential quadratic programming (SQP) methods for nonlinear programs and variational inequality problems have in common that they include a penalty function for the explicit constraints, the value of the penalty parameter for which is subject to the requirement of being large enough compared to estimates of the optimal Lagrange multipliers. In existing applications of the SQP algorithm to variational inequality problems, the possible choices of merit functions used in descent algorithms are also limited by conditions which require the knowledge of problem parameters.

This paper introduces a merit function for use in SQP methods for possibly non-strictly monotone variational inequality problems which does not include an explicit penalty function, and whose application in descent algorithms does not require the knowledge of any problem parameters. This function is an extension of the merit function of Marcotte and Zhu (1995) to primal–dual variational inequality problems. Among its other properties, it is directionally differentiable, and exact for strongly monotone problems. Based on the new merit function, we establish the convergence of a general algorithm for primal– dual variational inequalities which includes an adaptive SQP algorithm as a special case.

Keywords: Variational inequalities, gap function, descent algorithm, sequential quadratic programming.

1 Introduction

Consider the following instance of the variational inequality problem:

F (x^{∗}) + N_{X∩G}(x^{∗}) ∋ 0^{n},  (1)

where X ⊂ ℜ^{n} is a nonempty, closed, convex and bounded set, G := { x ∈ ℜ^{n} | g_{i}(x) ≤ 0, i = 1, …, m }, where each function g_{i} : ℜ^{n} ↦ ℜ is convex and in C^{2}. We assume that X ∩ G ≠ ∅ and that a Slater constraint qualification holds, that is, that there exists a point x ∈ X with g_{i}(x) < 0, i = 1, …, m. Further, we assume that F : X ↦ ℜ^{n} is monotone, Lipschitz continuous and in C^{1} on X. N_{S}(x) denotes the normal cone to the closed and convex set S at x, that is,

N_{S}(x) = \begin{cases}\{ z ∈ ℜ^{n} | z^{T}(y − x) ≤ 0, ∀y ∈ S \}, & x ∈ S, \\ ∅, & x ∉ S. \end{cases}  (2)

With these assumptions, it is clear that the solution set, SOL(F, X ∩ G), of (1), is nonempty, closed, convex and bounded.

We consider applications of (1) in which the ground set X is simple, for example a polytope, while G is defined by complicating constraints, such as when some of the functions g_{i} are nonlinear. In the development of a computational method for (1), we consider a relaxation approach wherein the functions g_{i} are iteratively linearized, thus iteratively replacing G by polyhedral approximations. Examples of such a method are sequential linear programming (SLP) and sequential quadratic programming (SQP). (We may also consider the case where the set X is not included in the original problem formulation, but is an a priori given trust region for the algorithm, although we have chosen not to describe the methodology in the framework of trust region methods.)

We introduce the following equivalent primal–dual formulation of (1). Introducing multipliers λ_{i} ∈ ℜ_{+}, i = 1, …, m, for the constraints defining G results in

(\begin{matrix}F (x^{∗}) + ∇g(x^{∗})^{T}λ^{∗} \\ −g(x^{∗}) \end{matrix}) + N_{X×ℜ_{+}^{m}}(x^{∗}, λ^{∗}) ∋ 0^{n+m}.  (3)

This variational inequality in the variables (x, λ) describes the Karush–Kuhn–Tucker (KKT) conditions for (1); under the given Slater constraint qualification, the solutions in x coincide ([Tob86, HaP90]).

In the SQP algorithm for the solution of (3) the search-direction finding subproblem defined at a given iterate, (x^{t}, λ^{t}) ∈ X × ℜ_{+}^{m}, is the linearization of (3) at (x^{t}, λ^{t}): find y^{t} ∈ X ∩ T (x^{t}) such that

[F (x^{t}) + H(x^{t}, λ^{t})(y^{t} − x^{t})]^{T}(z − y^{t}) ≥ 0,  ∀z ∈ X ∩ T (x^{t}),  (4)

where

H(x, λ) := ∇_{x}[F (x) + ∇g(x)^{T}λ]  (5)

is the Jacobian of the Lagrangean of (1) with respect to x, and

T (x) := { y ∈ ℜ^{n} | g(x) + ∇g(x)(y − x) ≤ 0^{m} },  x ∈ X  (6)

is the linearization of the set G defined at x.

A new iterate is usually defined by means of an inexact line search in the primal space, along the direction of d^{t} := y^{t} − x^{t} in a penalty merit function for (1) [equivalently for (3)]. The penalty merit function utilized is the sum of a merit function for (1) and a penalty function for the set G. So, for nonlinear programming, which is obtained from (1) when F ≡ ∇f for some real-valued (objective) function f : X ↦ ℜ, the function most often considered is (e.g., [Han77, Fle87, Psh94, Ber95])

f(x) + r ∑_{i=1}^{m} max{0, g_{i}(x)}, x ∈ X,

where r is a positive penalty parameter, while in applications to variational inequality problems, the objective function f must be replaced by a merit (or, gap) function for (1). Taji and Fukushima [TaF95] use the merit function

ψ_{TF}(x) := maximum_{y∈X} F (x)^{T}(x − y) − (1/2)(y − x)^{T}Q(y − x),  (7a)
subject to g(x) + ∇g(x)(y − x) ≤ 0^{m},  (7b)

defined on X, where Q ∈ ℜ^{n×n} is a symmetric and positive definite matrix.

Common to the existing analyses in applications of SQP algorithms in nonlinear programming and to variational inequality problems is that the value of the penalty parameter r needs to be sufficiently large in order for the penalty merit function to be exact, and (conversely) for the SQP subproblem to yield descent at every nonstationary point. The value of r is related to predictions on some norm of a vector λ^{∗} of Lagrange multipliers for the explicit constraints; for example, the following condition is present in [Han77, Psh94, TaF95]:

r ≥ sup_{t}{ ∥λ∥_{∞} | λ ∈ Λ(x^{t}) },  (8)

where Λ(x) denotes the set of Lagrange multipliers for the linearized constraints (6) in the solution to (4) defined at x, and ∥ · ∥_{∞} denotes the maximum norm.

In the case of variational inequality problems, the analysis in [TaF95] introduces the further requirement on the problem that F is strongly monotone (recall that F is strongly monotone on X if, for some m_{F} > 0, [F (x) − F (y)]^{T}(x − y) ≥ m_{F} ∥x − y∥^{2} holds for all x, y ∈ X), and the possible choices of matrices Q in the merit function (7) for (1) are restricted to those for which ∥Q∥ < 2m_{F} holds.

Since an estimate of neither the size of a multiplier vector λ^{∗} nor the modulus m_{F} of strong monotonicity is available a priori, estimates must be constructed either through experiments or adaptively in the algorithm.

Our approach to solving the problem (3) introduces some novelties in SQP methods. First, we introduce a merit (or, gap) function for (1) which is based on the same linearization of the constraints defining the set G as the SQP subproblem. This merit function extends the primal gap function introduced by Marcotte and Zhu [MaZ95] to the primal–dual setting, as well as the merit function (7) utilized in [TaF95, TaF96] in descent algorithms for (3). The analysis of this merit function (which differs substantially from that in [TaF95, TaF96] and from previous analyses of exact penalty functions) allows for the first time the penalty parameter r to take on any non-negative value. The explanation for this possibility is that the merit function introduced has an inherent strive for feasibility (which, for example, the function f in the case of nonlinear programming has not).

Another novelty is the introduction of a scaling parameter in the merit function. (This was earlier proposed in [MaZ95] in primal applications, but it is here developed further and put to an effective use in the primal–dual setting.) This scaling parameter serves the purpose of adaptively adjusting the merit function so that at any point outside the solution set SOL(F, X∩G) of (3), the SQP subproblem solution eventually yields descent with respect to the adjusted merit function. In so doing, we remove the condition on the a priori choice of the merit function present in the analysis in [TaF95]. In particular, the scaling enables us to execute the algorithm without the knowledge (or estimation) of any problem parameters. (In the case where F is strongly monotone, the rescaling will only be made a finite number of times, resulting in an exact penalty merit function satisfying the above mentioned requirement on the merit function in [TaF95, TaF96]; cf. Corollary 3.4.) We stress that the scaling parameter does not have an interpretation as a penalty parameter, since (in the strongly monotone case) its final value mentioned above is only related to the problem data in the sense of the modulus m_{F} of strong monotonicity of F but not to any optimal vector λ^{∗} of Lagrange multipliers for the explicit constraints.

The new merit function and the new analysis allows us to establish convergence of the SQP algorithm for non-strictly monotone operators F. We note however that, as in [TaF95], the SQP subproblem has an unorthodox feature, in utilizing as a multiplier estimate λ in the Jacobian mapping (5) of the SQP subproblem (4) the multiplier solution that is supplied in the evaluation of the merit function, in place of a multiplier estimate obtained from a previous solution of (4).

The rest of the paper is organized as follows. In the next section, we introduce a class of merit functions for (1), and study its most important properties. In Section 3, we introduce the iterative algorithm, which includes an adaptive SQP algorithm as a special case. The algorithm is analyzed in Section 4, and Section 5 compares the analysis to the ones in [TaF95, TaF96] for a projection algorithm and an SQP algorithm for (3). The paper concludes with some observations and remarks.

2 A merit function

The class of merit functions used defines an extension to primal–dual variational inequality problems of the differentiable gap functions for primal variational inequality problems which have a long history (see, e.g., [Auc89, Fuk92, Pat93a, Pat93b, WFM93, ZhM93, LaP94, Pat94, ZhM94, Fuk96, MaZ95, Pat97, Pat98]).

Let φ : X × X ↦ ℜ^{n} be a C^{1} function on X × X of the form φ(y, x), strictly convex in y for each fixed x ∈ X, and with the additional property that φ(x, x) = 0 and ∇_{y}φ(x, x) = 0^{n} for all x ∈ X. Let α > 0, and consider the function

ψ_{α}(x) := maximum_{y∈X} L_{α}(y, x) := F (x)^{T}(x − y) − (1/α)φ(y, x),  (9a)
subject to g(x) + ∇g(x)(y − x) ≤ 0^{m},  (9b)

defined on X.

We first establish a characterization of SOL(F, X ∩ G) in terms of the fixed points of the problem (9).

Proposition 2.1 (A fixed point characterization of SOL(F, X ∩G)). x ∈ SOL(F, X ∩ G) if and only if x solves (9).

Proof. Let x ∈ SOL(F, X ∩ G). Then, it is easily seen that x ∈ SOL(F, X ∩ T (x)). Let y solve (9). Then, [F (x)+(1/α)∇_{y}φ(y, x)]^{T}(z −y) ≥ 0 holds for all z ∈ X ∩T (x). Since y ∈ X ∩ T (x), F (x)^{T}(y − x) ≥ 0 holds, which implies that (1/α)∇_{y}φ(y, x)^{T}(x − y) ≥ 0. But the strict convexity of φ(·, x) then implies that y = x must hold, since otherwise we reach a contradiction from the strict monotonicity of ∇_{y}φ(·, x) and the assumptions on φ.

Conversely, assume that x solves (9). Then, x ∈ X ∩ G must hold, and by its variational inequality characterization,

F (x)^{T}(z − x) ≥ 0,  ∀z ∈ X ∩ T (x) ⊇ X ∩ G,  (10)

and hence, x ∈ SOL(F, X ∩ G).

Proposition 2.2 (ψ_{α} is a merit function for (1)). ψ_{α}(x) ≥ 0 holds for all x ∈ X ∩ G. Further, x ∈ X ∩ G and ψ_{α}(x) = 0 hold if and only if x ∈ SOL(F, X ∩ G).

Proof. Let x ∈ X ∩ G. It is clear from the choice y = x in (9) that ψ_{α}(x) ≥ 0 holds.

[⟹] Let x ∈ X ∩ G and ψ_{α}(x) = 0 hold. That x ∈ X ∩ T (x) implies that [F (x) + (1/α)∇_{y}φ(y, x)]^{T}(x − y) ≥ 0. But

0 = ψ_{α}(x) = F (x)^{T}(x − y) − (1/α)φ(y, x)
≥ −(1/α)[∇_{y}φ(y, x)^{T}(x − y) + φ(y, x)] ≥ (1/α)φ(x, x) = 0,

where the last inequality is strict by the strict convexity of φ(·, x), unless y = x holds. Proposition 2.1 then implies that x ∈ SOL(F, X ∩ G).

[⟸] Let x solve (9). Then, ψ_{α}(x) = 0 immediately follows. Further, since y = x holds, (9b) implies that x ∈ X ∩ G.

We next investigate the continuity and differentiability of the merit function ψ_{α}.

Proposition 2.3 (Continuity of ψ_{α}). The merit function ψ_{α} is continuous on X.

Proof. The mapping x ↦ T (x) defined in (6) is continuous on X ([TaF96, Prop. 2.5]), and ψ_{α} is finite on X, whence the result follows from the continuity and boundedness of L_{α} on X × X.

The analysis of the differentiability properties of ψ_{α} requires the explicit use of the KKT conditions for (9), which, given x ∈ X, are:

F (x) + (1/α)∇_{y}φ(y, x) + ∇g(x)^{T}p + N_{X}(y) ∋ 0^{n},  (11a)
p ≥ 0^{m},  (11b)
p^{T}[g(x) + ∇g(x)(y − x)] = 0,  (11c)
g(x) + ∇g(x)(y − x) ≤ 0^{m}.  (11d)

We let P (x) denote the set of solutions in p to (11), and further introduce the notation

H(x, p) := ∇_{x}[F (x) + ∇g(x)^{T}p],  p ∈ P (x).  (12)

Proposition 2.4 (Directional differentiability of ψ_{α}). The merit function ψ_{α} is directionally differentiable on X in any direction d ∈ ℜ^{n}, with

ψ′_{α}(x; d) = min_{p∈P (x)}{[F (x) − H(x, p)(y − x) − (1/α)∇_{x}φ(y, x)]^{T}d},

where y is the unique solution to (9).

Proof. The result follows from [Hog73, Thm. 2].

Although the merit function ψ_{α} has an inherent strive for feasibility with respect to G, we consider augmenting ψ_{α} with a penalty function, as follows:

ψ_{α,r}(x) := ψ_{α}(x) + r ∑_{i=1}^{m} max{0, g_{i}(x)},  r ≥ 0,  x ∈ X.

Clearly, ψ_{α,r} is a continuous merit function for (1). The following result establishes that the directional derivative of ψ_{α,r} in the direction of y−x is strictly monotonically decreasing in r ≥ 0. While r = 0 will be shown to be sufficient for establishing the validity of the algorithm, a positive value of r may still be beneficial, through the addition of another force directed towards feasibility.

Proposition 2.5 (ψ′_{α,r}(x; y−x) is strictly monotonically decreasing in r ≥ 0). It holds that ψ′_{α,r}(x; y − x) is strictly monotonically decreasing in r. In particular, then,

ψ′_{α,r}(x; y − x) ≤ ψ′_{α}(x; y − x),  r ≥ 0.  (13)

Proof. The additional terms in the expression of ψ′_{α,r}(x; d) are

r ∑_{i∈I_{+}(x)} ∇g_{i}(x)^{T}d + r ∑_{i∈I_{0}(x)} max{0, ∇g_{i}(x)^{T}d},  (14)

where

I_{+}(x) := { i = 1, …, m | g_{i}(x) > 0 }; I_{0}(x) := { i = 1, …, m | g_{i}(x) = 0 }.

By (11d), ∇g_{i}(x)^{T}d ≤ −g_{i}(x) = 0, i ∈ I_{0}(x), so the second term in (14) is zero. Further, by the same relation, ∇g_{i}(x)^{T}d ≤ −g_{i}(x) < 0, i ∈ I_{+}(x), so the first term in (14) is non-positive, and strictly monotonically decreasing in r. The result follows.

3 A modified descent algorithm for variational inequalities

We introduce a class of search direction subproblems in the class of cost approximation methods ([Pat93b]) for the solution (3) which extend the search direction finding subproblems of the algorithms of [Pat93a, Pat93b, WFM93, ZhM93, Pat94, ZhM94, MaZ95] to the explicit treatment of constraints and to the present primal–dual setting.

For any α > 0, let Φ_{α} : X ×X ×ℜ_{+}^{m} ↦ ℜ^{n} be a continuous mapping on X ×X ×ℜ_{+}^{m} of the form Φ_{α}(y, x, p), monotone and in C^{1} on X with respect to y. Given (x, p) ∈ X × ℜ_{+}^{m}, we consider replacing F by Φ_{α}(·, x, p); the error made is subtracted off through a fixed error term. The search-direction finding subproblem thus is to find y ∈ X ∩ T (x) such that

[Φ_{α}(y, x, p) + F (x) − Φ_{α}(x, x, p)]^{T}(z − y) ≥ 0,  ∀z ∈ X ∩ T (x).  (15)

If

Φ_{α}(·, x, p) = (1/α)∇_{y}φ(·, x),  x ∈ X,  (16)

then the problems (9) and (15) coincide, whence the search direction is defined by the point y that defines the current value of the merit function; the possible choice of Φ_{α} is however more general. In our convergence analysis, we will assume that either (16) holds, or the choice of Φ_{α} corresponds to an (approximate) Newton subproblem; the latter includes the SQP subproblem as a special case.

We next establish the descent properties of the search directions obtained from the solution of (15). We then need the following definition, which extends the one in [MaZ95] to the primal–dual setting.

Definition 3.1 (γ-strong descent). The vector d ∈ ℜ^{n} defines a γ-strong descent direction for the merit function ψ_{α,r} at x if

ψ′_{α,r}(x; d) ≤ −γψ_{α}(x),  γ ∈ (0, 1).  (17)

The next result extends one from [MaZ95] to the primal–dual setting.

Proposition 3.2 (Descent properties). Let α > 0. Let either Φ_{α} be chosen such that

∥∇_{y}Φ_{α}(y, x, p) − H(x, p)∥ ≤ δ(α),  x, y ∈ Y, p ∈ P (x),  (18)

for some function δ depending on problem data only, or (16) hold. Let x ∈ X \ SOL(F, X ∩ G), y solve (15), and d := y − x. Then, either d defines a γ-strong descent direction for ψ_{α,r} at x, for any r ≥ 0, or

ψ_{α}(x) ≤ 1/(1 − γ)[δ(α) + 1/α]b,  (19)

for some b > 0.

Proof. We consider the first case for Φ_{α}. We first note that the direction d := y − x also satisfies the conclusion (13) of Proposition 2.5, arguments for which are very similar, based on the KKT conditions for (15). Let w denote the solution to (9). Then, by Proposition 2.4,

ψ′_{α,r}(x; d) ≤ [F (x) − H(x, p)(w − x) − (1/α)∇_{x}φ(w, x)]^{T}d
≤ −ψ_{α}(x) + F (x)^{T}(x − w) − (1/α)φ(w, x)
+ [F (x) − H(x, p)(w − x) − (1/α)∇_{x}φ(w, x)]^{T}d
+ [F (x) + Φ_{α}(y, x, p) − Φ_{α}(x, x, p)]^{T}(w − y)
= −ψ_{α}(x) − d^{T}H(x, p)d
+ [Φ_{α}(y, x, p) − Φ_{α}(x, x, p) − H(x, p)d]^{T}(w − y)
− (1/α)[φ(w, x) + ∇_{x}φ(w, x)^{T}d].

The second row in the last equality is written as

[Φ_{α}(y, x, p) − Φ_{α}(x, x, p) − H(x, p)d]^{T}([x − y] + [w − x]);

the first term is less than d^{T}H(x, p)d, by the monotonicity of Φ_{α}(·, x, p), while the second term can be shown to be less than (1/2)δ(α)[∥d∥^{2}+∥w−x∥^{2}] by the assumption (18). We conclude that, with

θ(x, α) := (1/2)δ(α)[∥d∥^{2} + ∥w − x∥^{2}] − (1/α)[φ(w, x) + ∇_{x}φ(w, x)^{T}d],  (20)

for some b > 0,

ψ′_{α,r}(x; d) ≤ −ψ_{α}(x) + θ(x, α) ≤ −ψ_{α}(x) + [δ(α) + 1/α]b

holds, since X is bounded and φ and ∇_{x}φ are continuous. If x ∉ SOL(F, X ∩ G), then it follows that either d defines a γ-strong descent direction for ψ_{α,r} at x or that (19) holds.

In the second case for Φ_{α}, w = y holds; the second row thus cancels out, and the conclusion holds with δ(α) = 0.

Instance 3.3 (An SQP algorithm). Let Φ_{α}(y, x, p) := H(x, p)y, p ∈ P (x). Then, the CA subproblem is to find a y ∈ X ∩ T (x) such that

[F (x) + H(x, p)(y − x)]^{T} (z − y) ≥ 0,  ∀z ∈ X ∩ T (x).  (21)

This is the subproblem of an SQP algorithm in which a subset of the constraints are linearized, and where the multiplier estimate p is taken from the calculation of ψ_{α}(x).

We note that in an SQP algorithm that uses ψ_{α,r} as a merit function, the above result is applicable to monotone mappings F and for arbitrary choices of the penalty parameter r ≥ 0, because, by construction, (18) holds with δ(α) = 0.

Corollary 3.4 (Descent under strong monotonicity). In addition to the assumptions of Proposition 3.2, assume that F is strongly monotone on X. Let either the search direction d be given by the SQP subproblem described above or let (16) hold.

(a) For every x ∈ X \ SOL(F, X ∩ G), there exists an \overline{α} > 0 such that

α ≥ \overline{α}  ⟹  ψ′_{α,r}(x; d) ≤ −ψ_{α}(x).

(b) Let further φ(y, x) := (1/2)(y − x)^{T}Q(y − x), for some symmetric and positive definite matrix Q. Then, for every x ∈ X \ SOL(F, X ∩ G),

α ≥ ∥Q∥/(2m_{F})  ⟹  ψ′_{α,r}(x; d) ≤ −ψ_{α}(x).

Proof.

(a) The proof of Proposition 3.2 shows that

ψ′_{α,r}(x; d) ≤ −ψ_{α}(x) − d^{T}∇F (x)d − (1/α)[φ(y, x) + ∇_{x}φ(y, x)^{T}d],

whence the result follows by the boundedness of X, and the continuity of φ and ∇_{x}φ.

(b) The above estimate reduces to

ψ′_{α,r}(x; d) ≤ −ψ_{α}(x) − d^{T}[∇F (x) − 1/(2α)Q]d,

and the result follows.

The result establishes that the merit function constructed is exact for large enough values of α whenever F is strongly monotone, in the sense that

ψ′_{α,r}(x; d) ≥ 0 and x ∈ X ∩ G  ⟺  x ∈ SOL(F, X ∩ G).

The requirement in (b) on the value of α (albeit with strict inequality) is present in the convergence conditions for the SQP algorithm of Taji and Fukushima [TaF95] based on the same merit function, but their convergence analysis is different, and requires in addition that the value of r fulfills a condition of the form (8).

We are now ready to state the algorithm; it is given in Table 1.

Table 1: A modified descent algorithm

0. (Initialization): Choose an initial point x^{0} ∈ X, let α_{0} > 0, Δα > 0, γ ∈ (0, 1), β ∈ (0, 1), η ∈ (0, 1), s ∈ (0, 1], and r ≥ 0. Set t := 0.

1. (Search direction generation): Let

ψ_{α_{t}}(x^{t}) := maximum_{y∈X∩T (x^{t})} L_{α_{t}}(y, x^{t}) := F (x^{t})^{T}(x^{t} − y) − (1/α_{t})φ(y, x^{t}). (22)

If the second alternative for Φ_{α} is chosen, then let y^{t} be the solution to (22), otherwise, let y^{t} ∈ X ∩ T (x^{t}) be a vector such that

[Φ_{α_{t}}(y^{t}, x^{t}, p^{t}) + F (x^{t}) − Φ_{α_{t}}(x^{t}, x^{t}, p^{t})]^{T}(z − y^{t}) ≥ 0, ∀z ∈ X ∩ T (x^{t}), (23)

where p^{t} ∈ P (x^{t}) is arbitrary. The resulting search direction is d^{t} := y^{t} − x^{t}.

2. (Termination criterion): If x^{t} solves (23) or (22) → Stop [(x^{t}, p^{t}) solves (3)]. Otherwise, continue.

3. (Armijo line search or null step): If ψ_{α_{t}}(x^{t}) ≤ θ(x^{t}, α_{t})/(1 − γ), where θ(x^{t}, α_{t}) is defined by (20), then let α_{t+1} := α_{t} + Δα and x^{t+1} := x^{t}; otherwise, let α_{t+1} := α_{t} and x^{t+1} := x^{t} + ℓ_{t}d^{t}, where ℓ_{t} := sβ^{i} for the smallest non-negative integer i such that

ψ_{α_{t},r}(x^{t} + sβ^{i}d^{t}) − ψ_{α_{t},r}(x^{t}) ≤ ηsβ^{i}ψ′_{α_{t},r}(x^{t}; d^{t}).  (24)

4. (Termination criterion): If x^{t} is acceptable → Stop. Otherwise, go to Step 1 with t := t + 1.

Remark 3.5 (Observations on the algorithm). (a) The validity of the termination criterion in Step 2 is clear from the relation (10) [the case (23)] and Proposition 2.1 [the case (22)].

(b) The rationale for the updating of α_{t} is clear from the proof of Proposition 3.2; if either (18) holds for a function δ with the property that {δ(α_{t})} → 0 when {α_{t}} → ∞ or if (16) holds, then the last equality in that proof shows that whenever x^{t} is not a solution to (1), by increasing the value of α_{t}, the directional derivative ψ′_{α_{t},r}(x^{t}; d^{t}) will eventually be negative.

(c) The updating rule for α_{t} can also be motivated from the point of view of obtaining stationary points to the correct merit function: if a given iterate x^{t} is a stationary point for the current merit function used but x^{t} does not solve VIP(F, X ∩ G), then the updating rule is so designed that it adjusts the merit function so that eventually x^{t} is no longer stationary.

(4) If iteration t − 1 included an Armijo line search, then, at iteration t, the solution to (22), the value of p^{t} used in (23), and the value of ψ_{α_{t},r}(x^{t}) all are supplied automatically from the use of the Armijo rule at iteration t − 1.

4 Convergence analysis

Before we turn to the convergence of the proposed algorithm, we need the following technical lemmas.

Lemma 4.1 (Boundedness of P (x)). For each x ∈ X, the set P (x) is nonempty, closed and bounded.

Proof. The first two properties follow from the Slater CQ and (11). Let y be the solution to (9b), p ∈ P (x), and ν ∈ N_{X}(y) satisfy (11a). Let \overline{x} ∈ X be such that g_{i}(\overline{x}) < 0 for all i = 1, …, m. Then,

0 ≤ [F (x) + (1/α)∇_{y}φ(y, x) + ∇g(x)^{T}p + ν]^{T}(\overline{x} − y)

≤ [F (x) + (1/α)∇_{y}φ(y, x)]^{T}(\overline{x} − y)

+ ∑_{i=1}^{m} p_{i}[∇g_{i}(x)^{T}(x − y) + g_{i}(\overline{x}) − g_{i}(x)]

= [F (x) + (1/α)∇_{y}φ(y, x)]^{T}(\overline{x} − y) + ∑_{i=1}^{m} p_{i}g_{i}(\overline{x}),

where we have used (11b) and (11c), the definition (2) of the normal cone to X at y, and the convexity of g_{i}, i = 1, …, m. It therefore follows that

0 ≤ ∑_{i=1}^{m} p_{i} ≤ \frac{[F (x) + (1/α)∇_{y}φ(y, x)]^{T}(\overline{x} − y)}{min_{i∈\{1,... ,m\}}\{−g_{i}(\overline{x})\}},

and the result follows.

Lemma 4.2 (Continuity of ψ_{·}(·)). Assume that X ⊃ {x^{t}} → x ∈ X and ℜ_{++} ⊃ {α_{t}} → +∞. Then,

{ψ_{α_{t}}(x^{t})} → ψ_{∞}(x) := maximum_{y∈X∩T (x)} F (x)^{T}(x − y).

Proof. Let ε > 0 be arbitrary. First, we note that ψ_{∞} is continuous on X (see the proof of Proposition 2.3), and thus

|ψ_{∞}(x^{t}) − ψ_{∞}(x)| ≤ ε/2, t ≥ τ_{1}.

Second, ψ_{·}(x) is continuous as a function of α for any fixed value of x ∈ X (by arguments similar to those for ψ_{α}(·) in Proposition 2.3, and hence,

|ψ_{α_{t}}(x) − ψ_{∞}(x)| ≤ ε/2, t ≥ τ_{2}.

By the above two inequalities,

|ψ_{α_{t}}(x^{t}) − ψ_{∞}(x)| ≤ ε, t ≥ max{τ_{1}, τ_{2}},

and the result follows.

Theorem 4.3 (Global convergence). In addition to the assumptions of Proposition 3.2, let the function δ be such that {δ(α)} → 0 when α → ∞. Let {(x^{t}, p^{t})} be a sequence of primal and dual iterates generated by the algorithm of Table 1. Then, either the sequence {(x^{t}, p^{t})} is finite, whence the last iterate (x^{t}, p^{t}) is a solution to (3), or the sequence {(x^{t}, p^{t})} is infinite, whence it is bounded, any accumulation point is a solution to (3), and

{ minimum_{(x,λ) solves (3)} ∥(x^{t}, p^{t}) − (x, λ)∥} → 0.  (25)

Proof. The conclusion in the case of finite termination is clear from the construction of (23) and (22).

Clearly, the sequence {x^{t}} is bounded, since X is bounded. The same is true for the sequence {p^{t}}, by the boundedness of {x^{t}} and by Lemma 4.1.

We next distinguish two cases.

({α_{t}} → ∞) Let x^{∞} be any accumulation point of {x^{t}}, corresponding to some subsequence T . This assumption, together with the proof of Proposition 3.2, establish that then, ψ_{α_{t}}(x^{t}) ≤ [δ(α_{t}) + 1/α_{t}]b/(1 − γ) must hold for infinitely many t ∈ T . Since {δ(α_{t})} → 0 holds by Step 3, {ψ_{α_{t}}(x^{t})}_{t∈T} → 0. Lemma 4.2 establishes that ψ_{∞}(x^{∞}) = 0. In a manner similar to that in the proof of Proposition 2.2, we conclude that x^{∞} solves (9) at x^{∞} for α = +∞, and that x^{∞} ∈ G therefore holds. Hence, x^{∞} ∈ SOL(F, X ∩ G) follows. Turning to the proof for the sequence {p^{t}}, let p^{∞} be any of its accumulation points. The fact that x^{∞} solves (9) at x^{∞} for α = +∞ then implies that (11) is satisfied with x = y = x^{∞}, p = p^{∞} and α = +∞, which implies that (x^{∞}, p^{∞}) is a solution to (3).

(α_{t} = \overline{α}, t ≥ τ) By the continuity of ψ_{\overline{α},r}, the Armijo rule (24) is well-defined. We will show that {d^{t}} → 0^{n}. The proof proceeds by contradiction. If {d^{t}} ↛ 0^{n}, then as \{ψ_{\overline{α},r}(x^{t+1}) − ψ_{\overline{α},r}(x^{t})\} → 0 must hold, there must be a subsequence T such that \{ℓ_{t}\}_{t∈T} → 0 holds. There must then be a \overline{τ} ≥ τ such that

ψ_{\overline{α},r}(x^{t} + [ℓ_{t}/β]d^{t}) − ψ_{\overline{α},r}(x^{t}) > −η[ℓ_{t}/β]ψ′_{\overline{α},r}(x^{t}; d^{t}),  t ≥ \overline{τ}, t ∈ T . (26)

Let d^{∞} be an accumulation point of {d^{t}}_{t∈T}; the existence of an accumulation point follows since {d^{t}} is bounded. Dividing (26) by ℓ_{t}/β and taking the limit of T , we obtain by the directional differentiability of ψ_{\overline{α},r} that ψ′_{\overline{α},r}(x^{∞}; d^{∞}) ≥ 0. In the limit of T of the inequality (17), we obtain that ψ′_{\overline{α},r}(x^{∞}; d^{∞}) ≤ −γψ_{\overline{α},r}(x^{∞}). If the righthand side of this inequality is zero, then it follows that x^{∞} solves (9) at x^{∞}, and therefore x^{∞} ∈ SOL(F, X ∩ G) holds. If ψ_{\overline{α},r}(x^{∞}) > 0 holds, then we have reached a contradiction. In this case, we conclude that {d^{t}} → 0^{n}, and we again conclude that x^{∞} ∈ SOL(F, X ∩G) holds, this time by Proposition 2.1. Turning to the proof for the sequence {p^{t}}, we let p^{∞} be any accumulation point thereof, and note that {d^{t}} → 0^{n} implies from (11), together with the fact that ∇_{y}φ(x^{∞}, x^{∞}) = 0^{n}, that (x^{∞}, p^{∞}) is a solution to (3).

Remark 4.4 (On step length selection rules). We observe that the proof establishes that any step length rule that provides a decrease in ψ_{α_{t},r} that is at least as large as that of the Armijo rule (24) is a valid choice. This facilitates a plentiful of alternatives for more efficient choices of step length rules. For example, the line search can be replaced by a more general multi-dimensional search along the lines of simplicial decomposition methods; this approach is analyzed further in [Pat98, Chapter 9].

The following result shows that the modified descent algorithm finitely turns into a descent approach when F is strongly monotone. [The SQP method under case (b) may be viewed as an adaptive version of the SQP method of [TaF95], albeit under milder convergence conditions.]

Corollary 4.5 (Finite reduction to a descent algorithm). In addition to the assumptions of Theorem 4.3, assume that F is strongly monotone on X. Let either (16) hold or (18) hold with δ(α) = 0.

(a) There exists a finite integer τ such that α_{t} = \overline{α}, for all t ≥ τ.

(b) Assume further that φ(y, x) := (1/2)(y − x)^{T}Q(y − x), for some symmetric and positive definite matrix Q. Then, \overline{α} ≤ max\{α_{0}, ∥Q∥/(2m_{F}) + Δα\}.

Proof. The result follows from Theorem 4.3 and Corollary 3.4.

The following result validates a more active involvement of the penalty parameter r in the algorithm.

Corollary 4.6 (Adaptive penalty parameter). Let the assumptions of Theorem 4.3 hold. In the algorithm of Table 1, consider allowing the parameter r to be updated arbitrarily within a bounded interval 0 ≤ r ≤ \overline{r}, whenever a null step is taken. Then, the conclusion of Theorem 4.3 holds for this modified algorithm.

Proof. In the first case ({α_{t}} → ∞), the value of r is immaterial to the proof. In the second case (α_{t} = \overline{α}, t ≥ τ), the value of r is not updated after iteration τ, whence the proof reduces to the original one.

Remark 4.7 (On the convergence rate of the SQP method). The merit function ψ_{α} is differentiable at some point x ∈ X whenever the set P (x) of multipliers for (9b) is a singleton. (This condition holds if the normals ∇g_{i}(x) of the constraints active at y are linearly independent and strict complementarity holds there; see [FiM68, Thm. 6].) If this condition holds uniformly over x ∈ X, then it is possible to establish a linear convergence rate in the primal space of the algorithm whenever F is strongly monotone, along the lines of existing analyses of primal SQP methods (e.g., [Pat98]).

Under these assumptions, the SQP method based on the subproblem (4) is locally superlinearly convergent, and quadratically convergent under additional assumptions; see [GaM76]. It is not yet clear if such results are precluded for the algorithm of this paper by the fact that the multiplier estimate p^{t} is instead chosen in the set P (x^{t}) associated with the merit function. As remarked in [TaF95], however, under the above-mentioned additional assumptions, the multiplier vector λ^{∗} is unique, in which case the two sequences converge to the same point; if we can guarantee that the unit step is accepted by the Armijo rule close to the solution, then at least a superlinear convergence rate is achieved.

5 Two applications

We discuss two applications of Theorem 4.3, to a projection algorithm and to an SQP algorithm.

5.1 A modified projection algorithm

Let φ(y, x) := (1/2)(y −x)^{T}Q(y −x), for some symmetric and positive definite matrix Q, and let (16) hold. Then, for any r ≥ 0, Theorem 4.3 applies. The algorithm thus constructed is a modified projection algorithm, wherein the strictly convex, quadratic subproblems are solved over the set X ∩ T (x^{t}), and the matrix Q is adaptively scaled by the parameter α_{t} whenever the direction obtained from (22) does not yield descent.

A related projection algorithm is given by Taji and Fukushima [TaF96]. Their problem is obtained from (1) by letting X := ℜ^{n}, and we identify their algorithm in this case by setting α_{t} := 1 [cf. (7)]. Their convergence result relies on the monotone decrease in their merit function; in order to guarantee this descent property, the following assumptions must be introduced in their analysis:

1. ∇F (x) is positive definite on ℜ^{n}; and

2. r is chosen so that r ≥ sup_{t}{ ∥p∥_{∞} | p ∈ P (x^{t}) }, where P (x^{t}) is the set of multipliers for the linearized constraints (7b).

They also include the assumption that the generated sequence {x^{t}} is bounded. (In the present paper, we have instead assumed that the ground set X is bounded.)

5.2 An SQP algorithm

Our second, and most interesting application, is to SQP methods for (1). Given x^{t} ∈ X, the SQP method proceeds as follows. We construct a prediction of the multiplier vector λ^{∗} of (3) by solving (22) and extracting an arbitrary multiplier vector p^{t} ∈ P (x^{t}). The search-direction finding subproblem of the SQP scheme then is to find y^{t} ∈ X ∩ T (x^{t}) such that (4) holds, where λ^{t} is replaced by p^{t}.

We then note that (4) is obtained from (23) by choosing Φ_{α}(y, x, p) := H(x, p)(y− x), p ∈ P (x). Further, (18) holds with δ(α) = 0, and therefore Theorem 4.3 applies. The analysis provided in Theorem 4.3 shows that this SQP method for (1) is globally convergent for non-strictly monotone problem mappings F, and further that the penalty parameter r can be chosen arbitrarily in ℜ_{+}.

We also note that in the case where F ≡ ∇f for some real-valued function f : X ↦ ℜ, the above adaptive SQP method is applicable to the nonlinear programming problem whenever f is convex.

This analysis improves that of the SQP method in [TaF95]. The problem is obtained by letting X := ℜ^{n}, and their algorithm by choosing α_{t} := 1 and moreover the merit function as the projection-based measure (7). The progress of the algorithm relies on the descent properties of the merit function, which makes it necessary to introduce the following assumptions in the analysis:

1. F is strongly monotone on ℜ^{n};

2. r is chosen so that r ≥ sup_{t}{ ∥p∥_{∞} | p ∈ P (x^{t}) }; and

3. ∥Q∥ < 2m_{F}.

Convergence is established under the additional presumption that the sequence {x^{t}} is bounded.

6 Observations and final remarks

The convergence analyses of [TaF95, TaF96] for the above two algorithms do not cover the convergence of the sequence {p^{t}} of multiplier estimates.

The conditions 2. and 3. above are difficult to observe a priori. We note also again in passing that condition 2. is present in some analyses of SQP algorithms applied to nonlinear optimization problems (e.g., [Han77, Psh94]). Further, as is illustrated in Corollary 4.5, the requirement 3. present in the analysis of [TaF95] is not present here, since the function φ is automatically scaled in order to yield descent. By doing so, we gain the additional advantage of not requiring the knowledge or estimation of any problem parameters, instead fulfilling the requirement 3. eventually in the case of strongly monotone problems (cf. Corollary 3.4).

The present SQP algorithm and its convergence analysis extends and improves, respectively, that of primal Newton methods in [MaD87, TFI93], and primal–dual Newton methods in [MaD89].

Recent articles on iterative methods for variational inequality problems, for example [ZhM93, MaZ95, Kon97], and in particular on modified projection methods ([Ius94, SoT96, Sun96, He97]), show that one may reach convergence results under milder conditions when one introduces adaptivity. The above analysis serves as a further illustration that this route of development is worthy of further study also for other algorithms.

We finally note that in the context of nonlinear optimization, recent experience with modifications of SQP algorithms that do not utilize a penalty function, but rather a filter using a dominance concept adapted from multiobjective optimization, shows promise, albeit no convergence analysis for these methods is available at present ([Zop95, FlL97]). A convergence result is however available for the more basic approach of SLP in combination with trust region approaches ([FLT98]), which would suggest the possibility of applying more general non-penalty methods.

Acknowledgement

The presentation of this article benefitted from discussions with Professor Torbjörn Larsson.

References

[Auc89] G. Auchmuty (1989), “Variational principles for variational inequalities,” Numerical Functional Analysis and Optimization, vol. 10, pp. 863–874.

[Ber95] D. P. Bertsekas. Nonlinear Programming, Athena Scientific, Belmont, MA, 1995.

[FiM68] A. V. Fiacco and G. McCormick (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons,, New York, NY. Also published as volume 4 in the Classics in Applied Mathematics Series, SIAM, Philadelphia, PA, 1990.

[Fle87] R. Fletcher (1987). Practical Methods of Optimization, John Wiley & Sons, Chichester, U.K., second ed.

[FlL97] R. Fletcher and S. Leyffer (1997), “Nonlinear programming without a penalty function,” Numerical Analysis Report NA/171, Department of Mathematics, University of Dundee, Dundee, Scotland, U.K.

[FLT98] R. Fletcher, S. Leyffer and Ph. L. Toint (1998), “On the global convergence of an SLP-filter algorithm,” Numerical Analysis Report NA/183, Department of Mathematics, University of Dundee, Dundee, Scotland, U.K.

[Fuk92] M. Fukushima (1992), “Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,” Mathematical Programming, vol. 53, pp. 99–110.

[Fuk96] M. Fukushima (1996), “Merit functions for variational inequality and complementarity problems,” In: Nonlinear Optimization and Applications, Proceedings of the International School of Mathematics “G. Stampacchia” 21st Workshop on Nonlinear Optimization and Applications, held June 13–21, 1995, in Erice, Italy, G. Di Pillo and F. Giannessi (eds.), Plenum Press, New York, NY, pp. 155–170.

[GaM76] U. M. Garcia Palomares and O. L. Mangasarian (1976), “Superlinearly convergent quasi-Newton algorithms for nonlinearly constrained optimization problems,” Mathematical Programming, vol. 11, pp. 1–13.

[Han77] S. P. Han (1977), “A globally convergent method for nonlinear programming,” Journal of Optimization Theory and Applications, vol. 22, pp. 297– 309.

[HaP90] P. T. Harker and J.-S. Pang (1990), “Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,” Mathematical Programming, vol. 48, pp. 161– 220.

[He97] B. He (1997), “A class of projection and contraction methods for monotone variational inequalities,” Applied Mathematics & Optimization, vol. 35, pp. 69–76.

[Hog73] W. W. Hogan (1973), “Directional derivatives for extremal-value functions with applications to the completely convex case,” Operations Research, vol. 21, pp. 188–209.

[Ius94] A. I. Iusem (1994), “An iterative algorithm for the variational inequality problem,” Computational and Applied Mathematics, vol. 13, pp. 103–114.

[Kon97] I. V. Konnov (1997), “A class of combined iterative methods for solving variational inequalities,” Journal of Optimization Theory and Applications, vol. 94, pp. 677–693.

[LaP94] T. Larsson and M. Patriksson (1994), “A class of gap functions for variational inequalities,” Mathematical Programming, vol. 64, pp. 53–79.

[MaD87] P. Marcotte and J.-P. Dussault (1987), “A note on a globally convergent Ne”wton method for solving monotone variational inequalities, Operations Research Letters, vol. 6, pp. 35–42.

[MaD89] P. Marcotte and J.-P. Dussault (1989), “A sequential linear programming algorithm for solving monotone variational inequalities,” SIAM Journal on Control and Optimization, vol. 27, pp. 1260–1278.

[MaZ95] P. Marcotte and D. Zhu (1995), “Global convergence of descent processes for solving non strictly monotone variational inequalities,” Computational Optimization and Applications, vol. 4, pp. 127–138.

[Pat93a] M. Patriksson (1993), “A unified description of iterative algorithms for traffic equilibria,” European Journal of Operational Research, vol. 71, pp. 154–176.

[Pat93b] M. Patriksson (1993), A unified framework of descent algorithms for nonlinear programs and variational inequalities, PhD thesis, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden.

[Pat94] M. Patriksson (1994), “On the convergence of descent methods for monotone variational inequalities,” Operations Research Letters, vol. 16, pp. 265–269.

[Pat97] M. Patriksson (1997), “Merit functions and descent algorithms for a class of variational inequality problems,” Optimization, vol. 41, pp. 37–55.

[Pat98] M. Patriksson (1998). Nonlinear Programming and Variational Inequality Problems: A Unified Approach, Kluwer Academic Publishers, Dordrecht, The Netherlands.

[Psh94] B. N. Pshenichnyj (1994). The Linearization Method for Constrained Optimization, vol. 22 of Springer Series in Computational Mathematics, Springer-Verlag, Berlin. Translated from the Russian by S. S. Wilson.

[SoT96] M. V. Solodov and P. Tseng (1996), “Modified projection-type method for monotone variational inequalities,” SIAM Journal on Control and Optimization, vol. 34, pp. 1814–1830.

[Sun96] D. Sun (1996), “A class of iterative methods for solving nonlinear projection equations,” Journal of Optimization Theory and Applications, vol. 91, pp. 123–140.

[TaF95] K. Taji and M. Fukushima (1995), “A globally convergent Newton method for solving variational inequality problems with inequality constraints,” in Recent Advances in Nonsmooth Optimization, D.-Z. Du, L. Qi, and R. S. Womersley, eds., World Scientific Publishing Co, Singapore, pp. 405–417.

[TaF96] K. Taji and M. Fukushima (1996), “A new merit function and a successive quadratic programming algorithm for variational inequality problems,” SIAM Journal on Optimization, vol. 6, pp. 704–713.

[TFI93] K. Taji, M. Fukushima, and T. Ibaraki (1993), “A globally convergent Newton method for solving strongly monotone variational inequalities,” Mathematical Programming, vol. 58, pp. 369–383.

[Tob86] R. L. Tobin (1986), “Sensitivity analysis for variational inequalities,” Journal of Optimization Theory and Applications, vol. 48, pp. 191–204.

[WFM93] J. H. Wu, M. Florian, and P. Marcotte (1993), “A general descent framework for the monotone variational inequality problem,” Mathematical Programming, vol. 61, pp. 281–300.

[ZhM93] D. L. Zhu and P. Marcotte (1993), “Modified descent methods for solving the monotone variational inequality problem,” Operations Research Letters, vol. 14, pp. 111–120.

[ZhM94] D. L. Zhu and P. Marcotte (1994), “An extended descent framework for variational inequalities,” Journal of Optimization Theory and Applications, vol. 80, pp. 349–366.

[Zop95] C. Zoppke-Donaldson (1995), A tolerance-tube approach to sequential quadratic programming with applications, PhD thesis, Department of Mathematics and Computer Science, University of Dundee, Dundee, Scotland, U.K.