Partial Linearization Methods in Nonlinear Programming^{1}

M. Patriksson^{2}

Communicated by D.G. Luenberger

1The author wishes to thank Drs. K. Holmberg, T. Larsson, and A. Migdalas for their helpful comments. 2Lic. Phil., Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden.

Abstract. In this paper, we characterize a class of feasible direction methods in nonlinear programming through the concept of partial linearization of the objective function. Based on a feasible point, the objective is replaced by an arbitrary convex and continuously differentiable function, and the error is taken into account by a first order approximation of it. A new feasible point is defined through a line search with respect to the original objective, towards the solution of the approximate problem. Global convergence results are given for exact and approximate line searches, and possible interpretations are made. We present some instances of the general algorithm, and discuss extensions to nondifferentiable programming.

Key Words. Feasible direction methods, partial linearization, regularization, nondifferentiable programming.

1. Introduction

The purpose of this paper is to unify a number of feasible direction methods in nonlinear programming. Examples of these are the method of Frank and Wolfe and constrained Newton methods. The problem studied is

(P)  min_{x∈X} T (x),

where T : ℜ^{n} ↦ ℜ is continuous, and X is assumed compact and convex with a nonempty interior. These conditions ensure the existence of a solution to (P).

Let the function f(x, y) be convex and continuously differentiable with respect to x, and continuous with respect to y. The idea of the partial linearization method is to use the function f (x, x^{(l)}) in iteration l instead of the original objective T, supposedly with an

easier problem than (P) as a result. The error made, T (x) − f (x, x^{(l)}), is taken into account by approximating it with a first order Taylor expansion around the feasible point x^{(l)}. The solution to this approximate problem defines a descent direction for the original objective T; a line search in this direction gives a new iteration point.

We are now ready to state the algorithm, and establish its global convergence.

2. The Partial Linearization Algorithm

In order to establish the properties of the partial linearization algorithm, it will first be stated for a problem over a compact and convex feasible set, where the original objective T is pseudoconvex and continuously differentiable.

The general algorithm works as follows.

In iteration l, the objective function is expressed as

T (x) = f (x, x^{(l)}) + (T (x) − f (x, x^{(l)})) .  (1)

The second term can be seen as expressing the error when replacing the original objective, T, by the function f (·, x^{(l)}). The idea is then to take this error into account by replacing it with a first order Taylor expansion around x^{(l)}.

The subproblem solved in iteration l then is

(PL-SUB^{(l)})  min_{x∈X} T^{(l)} (x),

where

T^{(l)} (x) = f (x, x^{(l)}) + T (x^{(l)}) − f (x^{(l)}, x^{(l)}) + [∇T (x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} (x − x^{(l)}) ,

and where ∇_{x}f(x, y) denotes the gradient of f(x, y) with respect to x.

An optimal solution to this convex problem, \overline{x}^{(l)}, defines a direction d^{(l)} =^{def} \overline{x}^{(l)} − x^{(l)}, which is a feasible descent direction with respect to T, if not x^{(l)} solves (PL-SUB^{(l)}), in which case x^{(l)} is an optimal solution to (P). [This is to be shown in Theorem 2.1.] A line search with respect to T is then made in the direction d^{(l)}, and a new iteration point x^{(l+1)} is obtained. Under the assumptions made on (P), any accumulation point of the sequence {x^{(l)}}_{l=1}^{∞} is optimal to (P), for any initial feasible point x^{(0)}. [This is shown in Theorem 2.2.]

Theorem 2.1 Assume that x^{(l)} is a feasible point in (P), and that \overline{x}^{(l)} solves (PL-SUB^{(l)}). If x^{(l)} solves (PL-SUB^{(l)}), then x^{(l)} is optimal in (P). Otherwise, the direction d^{(l)} = \overline{x}^{(l)}−x^{(l)} is a feasible descent direction with respect to T.

Proof If x^{(l)} does not solve (PL-SUB^{(l)}), then by the convexity of T^{(l)}, and the fact that ∇T (x^{(l)}) = ∇T^{(l)} (x^{(l)}), we have that

∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) < 0,

and by the convexity of X the direction d^{(l)} = \overline{x}^{(l)} − x^{(l)} is a feasible descent direction with respect to T.

Since \overline{x}^{(l)} solves (PL-SUB^{(l)}), the following variational inequality holds [Bazaraa and Shetty, Ref. 1, Theorem 3.4.3]:

[∇_{x}f (\overline{x}^{(l)}, x^{(l)}) + ∇T (x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} (x − \overline{x}^{(l)}) ≥ 0, ∀ x ∈ X.  (2)

If x^{(l)} also solves the subproblem, then by replacing \overline{x}^{(l)} with x^{(l)} above, we obtain

∇T (x^{(l)})^{T} (x − x^{(l)}) ≥ 0, ∀ x ∈ X,

which, by the pseudoconvexity of T, yields that x^{(l)} solves (P). □

Theorem 2.2 The partial linearization algorithm either terminates in a finite number of main iterations or it generates an infinite sequence {x^{(l)}} such that any accumulation point is an optimal solution to (P).

Proof The proof is a modification of the ones provided by Larsson and Migdalas (Ref. 2) and Larsson and Patriksson (Ref. 3), which in turn are based on the convergence proof of the Frank-Wolfe algorithm, provided by Martos (Ref. 4).

If the algorithm terminates in some iteration l, we have from Theorem 2.1 that

T^{(l)} (\overline{x}^{(l)}) = T^{(l)} (x^{(l)})

and x^{(l)} then is optimal in (P). Assume therefore that T^{(l)} (\overline{x}^{(l)}) ≠ T^{(l)} (x^{(l)}) for all iterations l.

By Theorem 2.1, the sequence {d^{(l)}} consists of directions of descent. Therefore,

T (x^{(l+1)}) = min_{α_{l}∈[0,\overline{α}_{l}]} T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) < T (x^{(l)}) ,  (3)

where \overline{α}_{l} is the maximal steplength in the direction d^{(l)}. Thus, \{T (x^{(l)})\} is a monotonically decreasing sequence which is bounded from below since X is compact and T continuous. Furthermore, according to Weierstrass’ theorem, the sequence {x^{(l)}} must have at least one accumulation point, say x^{∗} ∈ X, which is then a limit point of a convergent subsequence {x^{(l)}}_{l∈L}. We then have the following.

lim_{l∈L} T (x^{(l)}) = T (x^{∗})  (4)

By (4) we have that

lim_{l∈L} [T (x^{(l+1)}) − T (x^{(l)})] = 0.  (5)

Again, according to Weierstrass’ theorem, the sequence \{\overline{x}^{(l)}\} has at least one accumulation point, say \overline{x}, being a limit point of a sequence L̂ ⊂ L. By (3) we have that

T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) ≥ T (x^{(l+1)}) , ∀ α_{l} ∈ [0, \overline{α}_{l}] .

Then,

T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)}) ≥ T (x^{(l+1)}) − T (x^{(l)}) ,

for all α_{l} ∈ [0, \overline{α}_{l}]. By (5),

lim_{l∈L̂} [T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)})] ≥ 0,

and, by choosing α_{l} so that lim_{l∈L̂} α_{l} = 0, we obtain

lim_{l∈L̂} [\frac{T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)})}{α_{l}} ] ≥ 0,

and the limit exists due to the strict differentiability of T [Rockafellar, Ref. 5, Theorem 4F]. The limit is equal to the directional derivative of T (x^{∗}) in the direction \overline{x} − x^{∗} [Ref. 5, Equation (3.5)], and hence

∇T (x^{∗})^{T} (\overline{x} − x^{∗}) ≥ 0.  (6)

Since \overline{x}^{(l)} solves (PL-SUB^{(l)}), then from (2) we obtain [Ref. 1, Theorem 3.4.3]

[∇_{x}f (\overline{x}^{(l)}, x^{(l)}) + ∇T (x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} (x − \overline{x}^{(l)}) ≥ 0, ∀ x ∈ X.

Taking the limit over L̂ yields

[∇_{x}f (\overline{x}, x^{∗}) + ∇T (x^{∗}) − ∇_{x}f (x^{∗}, x^{∗})]^{T} (x − \overline{x}) ≥ 0, ∀ x ∈ X.  (7)

Choosing x = x^{∗}, and noting the convexity of f(x, y) with respect to x, we obtain that

∇T (x^{∗})^{T} (x^{∗} − \overline{x}) ≥ 0.

This implies, by (6), that

∇T (x^{∗})^{T}(x^{∗} − \overline{x}) = 0.  (8)

If either component is zero, x^{∗} solves (P), by the pseudoconvexity of T and by (7), respectively. Assume therefore that x^{∗} ≠ \overline{x}, and that ∇T (x^{∗}) ≠ 0.

According to (7), \overline{x} solves the subproblem defined by x^{∗}. If we denote the subproblem objective by T^{∗}(x), then we have that T^{∗}(\overline{x}) ≤ T^{∗}(x^{∗}), i.e., that

f(\overline{x}, x^{∗}) − f(x^{∗}, x^{∗}) + [∇T (x^{∗}) − ∇_{x}f(x^{∗}, x^{∗})]^{T} (\overline{x} − x^{∗}) ≤ 0,

which by (8) and the convexity of f yields that

f(\overline{x}, x^{∗}) = f(x^{∗}, x^{∗}) + ∇_{x}f(x^{∗}, x^{∗})^{T}(\overline{x} − x^{∗}).

But this in turn implies that

T^{∗}(\overline{x}) = lim_{l∈L̂} T^{(l)} (\overline{x}^{(l)})
= f(\overline{x}, x^{∗}) + T (x^{∗}) − f(x^{∗}, x^{∗}) + [∇T (x^{∗}) − ∇_{x}f(x^{∗}, x^{∗})]^{T} (\overline{x} − x^{∗})
= T (x^{∗}).

But since T^{∗}(x^{∗}) = T (x^{∗}), we have that x^{∗} also solves the subproblem defined by x^{∗}. Replacing \overline{x} by x^{∗} in (7), we obtain that

∇T (x^{∗})^{T} (x − x^{∗}) ≥ 0, ∀ x ∈ X,

which is the desired result. □

Under the additional assumption that T (x) has a Lipschitzian gradient, i.e., that there exists a positive constant K such that

∥∇T (x^{1}) − ∇T (x^{2})∥ ≤ K ∥x^{1} − x^{2}∥ , ∀ x^{1}, x^{2} ∈ X,  (9)

then it is possible to show that the partial linearization algorithm is globally convergent even when line searches are made only approximately. [A sufficient condition for Lipschitz continuity of ∇T is continuous differentiability of T, since the feasible set is assumed compact.] As an example, consider the case of replacing it with an Armijo (Ref. 6) steplength rule where the point x^{(l+1)} is calculated as x^{(l+1)} = x^{(l)} + β^{−ī} (\overline{x}^{(l)} − x^{(l)}), where ī is the smallest integer i for which

T (x^{(l)} + β^{−i} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)}) ≤ εβ^{−i}∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) ,  (10)

where ε ∈ (0, 1) and β > 1. Below, we establish the global convergence of the modified algorithm.

Theorem 2.3 Under the additional condition (9), the partial linearization algorithm is globally convergent with exact line searches replaced by the Armijo steplength rule (10).

Proof We will show that any convergent subsequence L̂ of the sequences {x^{(l)}}_{l=1}^{∞} and

\{\overline{x}^{(l)}\}_{l=1}^{∞} satisfies

lim_{l∈L̂} ∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) = ∇T (x^{∗})^{T}(\overline{x} − x^{∗}) = 0,

i.e., equivalent to (8). The proof then follows using exactly the same arguments as in the proof of Theorem 2.2.

By Theorem 2.1, the sequence {d^{(l)}} consists of feasible directions of descent. Hence,

∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) < 0,

and by (10),

T (x^{(l+1)}) ≤ T (x^{(l)}) , ∀ l.

Indeed, by the construction of the steplength rule,

T (x^{(l+1)}) ≤ T (x^{(l)}) + εα_{l}∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) .  (11)

This inequality is valid, since (10) can always be satisfied within a finite number of trial steps. The proof of this fact, given below, is a modification of a part of the convergence proof for the Frank-Wolfe algorithm of Pshenichny and Danilin (Ref. 7, p. 172).

Using Taylor’s formula and the condition (9),

T (x^{(l)} + α (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)}) = ∫_{0}^{α} ∇T (x^{(l)} + s (\overline{x}^{(l)} − x^{(l)}))^{T} (\overline{x}^{(l)} − x^{(l)}) ds
≤ α∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) + ∫_{0}^{α} sK ∥\overline{x}^{(l)} − x^{(l)}∥^{2} ds
= α∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) + \frac{1}{2}α^{2}K ∥\overline{x}^{(l)} − x^{(l)}∥^{2}.

(12)

From (12) we obtain, by choosing

α ≤ 2 (ε − 1) \frac{∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})}{K ∥\overline{x}^{(l)} − x^{(l)}∥^{2}},

that

T (x^{(l)} + α (\overline{x}^{(l)} − x^{(l)})) ≤ T (x^{(l)}) + εα∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) .

Replacing α with β^{−i}, we see that ī is the smallest integer to satisfy

β^{−i} ≤ 2 (ε − 1) \frac{∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})}{K ∥\overline{x}^{(l)} − x^{(l)}∥^{2}}.

Hence,

βα_{l} = β^{−(ī−1)} > 2 (ε − 1) \frac{∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})}{K ∥\overline{x}^{(l)} − x^{(l)}∥^{2}},

i.e.,

α_{l} > \frac{2 (ε − 1)}{β} \frac{∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})}{K ∥\overline{x}^{(l)} − x^{(l)}∥^{2}}.  (13)

Hence, the Inequality (10) will be satisfied after a finite number of steps with a steplength satisfying (13).

Noting that ∥\overline{x}^{(l)} − x^{(l)}∥ is bounded from above by a positive constant, say C, because of the compactness of X, by (11) and (13) we obtain

T (x^{(l+1)}) − T (x^{(l)}) ≤ \frac{2ε (ε − 1)}{β} \frac{[∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})]^{2}}{KC^{2}} .  (14)

Summing (14) for all l ≤ m − 1, we obtain

T (x^{(m)}) − T (x^{(0)}) ≤ −\frac{2ε(ε − 1)}{βKC^{2}} ∑_{l=1}^{m−1} [∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})]^{2} .

Using the fact that T (x) is bounded from below on X by, say \underline{T},

\begin{aligned}∑_{l=1}^{m−1} [∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})]^{2} & ≤ & \frac{βKC^{2}}{2ε(ε − 1)} (T (x^{(0)}) − T (x^{(m)})) \\ & ≤ & \frac{βKC^{2}}{2ε(ε − 1)} (T (x^{(0)}) − \underline{T} ). \end{aligned}

It follows that the series

∑_{l=1}^{∞} [∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)})]^{2}

is convergent, and hence,

lim_{l→∞} ∇T (x^{(l)})^{T} (\overline{x}^{(l)} − x^{(l)}) = 0.  (15)

By using the same arguments as in Theorem 2.2, we may choose subsequences of {x^{(l)}} and

\{\overline{x}^{(l)}\} so that

lim_{l∈L} x^{(l)} = x^{∗} and lim_{l∈L̂} \overline{x}^{(l)} = \overline{x}.

By (15),

∇T (x^{∗})^{T}(\overline{x} − x^{∗}) = 0,

which completes the proof. □

3. Interpretations and Some Instances

The convergence proof of Theorem 2.2 implies several properties of the partial linearization algorithm.

A nice property of the method of Frank and Wolfe (Ref. 8), which may be recognized by the choice of the function f(x, y) ≡ 0, is that, for convex problems, a termination criterion is available through the lower bound on the optimal objective value, obtained from the linear subproblem. In the partial linearization algorithm, this termination criterion is, in general, not valid since the error function, T (x) − f(x, y), is not convex. However, by Theorem 2.2,

T (x^{(l)}) − T^{(l)} (\overline{x}^{(l)}) > 0

whenever x^{(l)} is not a solution to (P), and this difference tends towards zero when the iterations proceed. Hence, the difference between the objective value and the corresponding optimal subproblem value may still be utilized in a termination criterion.

If the function f(x, y) is chosen strictly convex with respect to x, then the subproblem (PL-SUB^{(l)}) is strictly convex, and the solution, \overline{x}^{(l)}, is unique. This implies the possibility of utilizing dual techniques for the solution of (PL-SUB^{(l)}); furthermore, the termination criterion T^{(l)} (\overline{x}^{(l)}) − T^{(l)} (x^{(l)}) = 0 is replaced by \overline{x}^{(l)} = x^{(l)}, and it is easily shown that any accumulation point of the sequence of subproblem solutions is a solution to (P). Hence, the choice of strictly convex functions f(x, y) corresponds to making better and better approximations of the original objective, in the sense that in the limit the original problem is solved by the subproblem solution.

If the function f(x, y) is chosen so that

∇_{x}f(x, y) = 0 if x = y,  (31)

then the subproblem of the partial linearization algorithm is equivalent to

min_{x∈X} ∇T (x^{(l)})^{T} (x − x^{(l)}) + f (x, x^{(l)}) .

Algorithms of this type are studied by Migdalas (Ref. 9), under the name of regularized Frank-Wolfe algorithms. The above expression provides a nice interpretation of the algorithmic class as partial linearization methods as opposed to complete linearization methods, such as the Frank-Wolfe algorithm. In the Frank-Wolfe algorithm, the first order Taylor expansion, which is valid only locally around x^{(l)}, is used globally in the subproblem phase. The subproblem solved in a partial linearization method introduces a regularization term in the objective function of the Frank-Wolfe subproblem, restricting the difference between the current point x^{(l)} and the subproblem solution \overline{x}^{(l)} to some measured distance. By retaining the nonlinearity of the original objective function, partial linearization methods will therefore avoid the tailing-off phenomena inherent in the Frank-Wolfe method, caused by the generation of extreme point solutions. This was the original idea behind the first formulation of a partial linearization method (Ref. 3), where the objective is described as the sum of a strictly convex and differentiable function and a differentiable but not necessarily convex function. The subproblem then is defined by a linearization of the nonconvex part. Also, it is pointed out the possibility of choosing the strictly convex function separable to utilize separability in the constraints. This is demonstrated in the case of traffic equilibrium problems in Refs. 10 and 11.

The partial linearization method may also be used to regularize not strictly convex problems by iteratively adding a strictly convex function to the original objective, as shown below.

Assume that the objective function T (x) is convex but not strictly convex. Assume also that the function f(x, y) is strictly convex with respect to x. Let

\overline{f}(x, y) = T (x) + f(x, y),

which then is strictly convex with respect to x. Rewrite the objective as in (1), i.e., let

\begin{aligned}T (x) & = & \overline{f}(x, y) + (T (x) − \overline{f}(x, y)) \\ & = & T (x) + f(x, y) + (−f(x, y)) . \end{aligned}

The subproblem solved in the partial linearization method then is to minimize

T^{(l)}(x) = T (x) + f (x, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})^{T} (x − x^{(l)}) ,

and if f is chosen to satisfy (31), the subproblem objective equals

T^{(l)}(x) = T (x) + f (x, x^{(l)}) ,

i.e., the subproblem introduces a regularization of the original objective by adding to it a strictly convex function. [For a general discussion on regularization methods in nonlinear programming, see, e.g., Ref. 12.]

As an example, consider the function

f(x, y) = \frac{c}{2}(x − y)^{T}I(x − y) = \frac{c}{2} ∥x − y∥_{2}^{2},

where c > 0. The subproblem, given a feasible point x^{(l)}, then is equal to the minimization of the function

T (x) + \frac{c}{2} ∥x − x^{(l)}∥_{2}^{2} ,

which is equivalent to the subproblem of the proximal point algorithm (Ref. 13).

This also suggests the possibility of using partial linearization methods for nondifferentiable problems; this is further discussed in Section 4.

3.1. Some Instances of the Partial Linearization Algorithm

By choosing the function f(x, y) in various ways, well known feasible direction methods are recognized. Below we list a few such methods. For further discussions, we refer to Ref. 11.

f(x, y)  Algorithm

0  Frank-Wolfe
\frac{1}{2}x^{T}∇^{2}T (y)x  constrained Newton
\frac{1}{2}x^{T}B(y)x  constrained quasi-Newton
T (x) + \frac{c}{2} ∥x − y∥^{2}  proximal point
∑_{i=1}^{n} ∫_{0}^{∑_{j≠i} y_{j}+x_{i}} \frac{∂T (s)}{∂x_{i}}ds nonlinear Jacobi

Note that when T (x) is only pseudoconvex, the Hessian ∇^{2}T (x) is not necessarily positive semidefinite; however constrained Newton methods can always be modified by adding a positive definite matrix to the Hessian, e.g., let

f(x, y) = \frac{1}{2}x^{T} (∇^{2}T (y) + εI) x,

where ε > 0 is sufficiently large so that the matrix ∇^{2}T (y) + εI is (at least) positive semidefinite.

4. Nondifferentiable Programming

In this section we extend the partial linearization algorithm to nondifferentiable programming. Let the objective T (x) be given as

T (x) = g(x) + h(x),  (48)

where g(x) : ℜ^{n} ↦ (−∞, +∞] is a closed and proper convex function and h(x) : ℜ^{n} ↦ (−∞, +∞] is continuously differentiable on X. The problem of minimizing T over the compact and convex set X will be referred to as (NP).

A Frank-Wolfe type algorithm for nondifferentiable problems is defined through a linearization of the continuously differentiable part of the objective, i.e., in iteration l,

T^{(l)}(x) = g(x) + h (x^{(l)}) + ∇h (x^{(l)})^{T} (x − x^{(l)}) .

Mine and Fukushima (Ref. 14) propose such a descent method, coupled with exact line searches on T. The algorithm is applied to unconstrained problems; it is shown that, under a compactness assumption on the level set of T (x^{(0)}) and a strict convexity assumption on g(x), any accumulation point of the sequence {x^{(l)}} is a critical point, i.e., that 0 belongs to the Clarke (Ref. 15) generalized subdifferential of T at an accumulation point x^{∗}, or

−∇h (x^{∗}) ∈ ∂g (x^{∗}) .

The algorithm is extended by Fukushima and Mine (Ref. 16), where a proximal point type method is applied. The subproblem in iteration l is to minimize

g(x) + h (x^{(l)}) + ∇h (x^{(l)})^{T} (x − x^{(l)}) + \frac{c_{l}}{2} ∥x − x^{(l)}∥^{2},

where c_{l} > 0. Furthermore, the exact line search is replaced by a modified Armijo steplength rule. They establish the convergence towards a critical point x^{∗}, and also a linear rate of convergence, provided that ∇^{2}h (x^{∗}) is strictly positive definite and that c_{l} ≡ c is chosen large enough.

Extending the partial linearization algorithm to nondifferentiable programming, let in iteration l the objective be described as

T (x) = (g(x) + f (x, x^{(l)})) + (h(x) − f (x, x^{(l)})) ,

and the subproblem is defined through a linearization of the second term.

We may identify the algorithm in Ref. 14 by the choice of f ≡ 0, and the proximal point algorithm in Ref. 16 is obtained by letting f(x, y) = \frac{c}{2} ∥x − y∥^{2}. [The possibility of making subproblems strictly convex by adding and subtracting a strictly convex function is discussed in Ref. 14.]

Fukushima (Ref. 17) further develops the method in Ref. 16, for constrained problems. The subproblem used may be defined by letting f (x, x^{(l)}) = \frac{1}{2}x^{T}B_{l}x, and by linearizing nonlinear constraint functions. The matrix B_{l} is assumed positive definite. The method of Kiwiel (Ref. 18) resembles the method of Ref. 16, but includes polyhedral approximations of g in each step of the algorithm to simplify the computation of search directions.

We will show that the partial linearization algorithm described above extends the results obtained in Refs. 14 and 16 in the sense that the partial linearization algorithm is convergent towards critical points, and that approximate line searches may be used.

The results are given in three theorems. First we show that the subproblem solutions yield descent directions. Then we prove the convergence of two versions of the algorithm, where the line search is made exactly and by applying a modified Armijo steplength rule, respectively.

The first theorem is a generalization of Theorem 2.1.

Theorem 4.1 Assume that x^{(l)} is feasible in (NP), and that \overline{x}^{(l)} solves (PL-SUB^{(l)}). If x^{(l)} solves (PL-SUB^{(l)}), then x^{(l)} is a critical point in (NP). Otherwise, the direction d^{(l)} = \overline{x}^{(l)} − x^{(l)} is a feasible descent direction with respect to T.

Proof The proof extends Lemma 3.2 in Ref. 14, where it is also assumed that the function g is strictly convex on its domain, and is based on Theorem 2.1.

We will show that for any x^{(l)} the directional derivative of T in the direction d^{(l)} is nonpositive, and that it is strictly negative if x^{(l)} is not a critical point, i.e., that

T^{(l)} (\overline{x}^{(l)}) < T^{(l)} (x^{(l)}) implies T′ (x^{(l)}; d^{(l)}) < 0.

T′ (x^{(l)}; d^{(l)}) =^{def} lim_{λ→0_{+}} \frac{1}{λ} [T (x^{(l)} + λd^{(l)}) − T (x^{(l)})]
= sup_{u∈∂g(x^{(l)})} [∇h (x^{(l)}) + u]^{T} d^{(l)}
= ∇h (x^{(l)})^{T} d^{(l)} + sup_{u∈∂g(x^{(l)})} u^{T}d^{(l)},

where the second equality follows from Ref. 19, Theorem 23.4.

If x^{(l)} does not solve the subproblem, then by the convexity of f(x, y) with respect to x it is easy to show that

∇h (x^{(l)})^{T} d^{(l)} < g (x^{(l)}) − g (\overline{x}^{(l)}) .

Using this fact it follows, by the convexity of g, that

T′ (x^{(l)}; d^{(l)}) < g (x^{(l)}) − g (\overline{x}^{(l)}) + sup_{u∈∂g(x^{(l)})} u^{T}d^{(l)} ≤ 0.

Hence, the direction d^{(l)} is a feasible descent direction with respect to T. However, if x^{(l)} solves the subproblem, we then have that the variational inequality

[u^{(l)} + ∇h (x^{(l)})]^{T} (x − x^{(l)}) ≥ 0, ∀ x ∈ X

holds for some u^{(l)} ∈ ∂g (x^{(l)}). Hence, x^{(l)} is a critical point for the problem (NP), and, in the case of convex functions h, this is a sufficient condition for global optimality of the point x^{(l)} in the problem (NP) [Ref. 1, Theorem 3.4.3]. This completes the proof. □

Theorem 4.2 The partial linearization algorithm applied to (NP) either terminates in a finite number of main iterations or it generates an infinite sequence {x^{(l)}} such that any accumulation point is a critical point in (NP). Especially, if the function h(x) is convex, then the algorithm is globally convergent.

Proof The proof is a modification of the one given in Theorem 2.2.

According to Theorem 4.1, the algorithm terminates in a finite number of main iterations if the subproblem in iteration l is solved by x^{(l)}. Assume therefore that

T^{(l)} (\overline{x}^{(l)}) < T^{(l)} (x^{(l)})

for all iterations l.

By the same arguments as in the proof of Theorem 2.2, the algorithm yields descent directions, and we may choose a subsequence L̂ such that x^{(l)} and \overline{x}^{(l)} has limit points x^{∗} and \overline{x}, respectively. It follows that

T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)}) ≥ T (x^{(l+1)}) − T (x^{(l)}) ,

for all α_{l} ∈ [0, \overline{α}_{l}]. Since T (x^{(l+1)}) − T (x^{(l)}) tends to zero in L̂, we have that

lim_{l∈L̂} [T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)})] ≥ 0.  (49)

Choose the sequence of α_{l} so that α_{l} tends to zero in L̂. The upper subderivative of T at x^{∗} with respect to the direction d^{∗} = \overline{x} − x^{∗} is defined as

T^{↑} (x^{∗}; d^{∗}) = lim sup_{l∈L̂^{x^{(l)}\underrightarrow{T}x^{∗}}} inf_{d^{(l)}→d^{∗}} \frac{T (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − T (x^{(l)})}{α_{l}}.

The convex function g is finite everywhere, since it is continuous on the compact set X. Hence by Theorem 3G of Ref. 5 the subderivative of g at x^{∗} with respect to d^{∗} satisfies the relation

g^{↑} (x^{∗}; \overline{x} − x^{∗}) = g′ (x^{∗}; \overline{x} − x^{∗}) .

Now, the function h is continuously differentiable, and hence the limit of

\frac{h (x^{(l)} + α_{l} (\overline{x}^{(l)} − x^{(l)})) − h (x^{(l)})}{α_{l}}

exists and is equal to ∇h (x^{∗})^{T} (\overline{x} − x^{∗}) [Ref. 5, Theorem 4F]. By Theorem 4.4.a of Ref. 20,

T^{↑} (x^{∗}; d^{∗}) = g′ (x^{∗}; \overline{x} − x^{∗}) + ∇h (x^{∗})^{T} (\overline{x} − x^{∗}) ,  (50)

which is nonnegative by (49).

Theorem 23.4 of Ref. 19 yields that

g′ (x^{∗}; \overline{x} − x^{∗}) = sup_{u∈∂g(x^{∗})} u^{T} (\overline{x} − x^{∗}) ,

and the supremum is attained in, say u^{∗} ∈ ∂g (x^{∗}), since ∂g (x^{∗}) is compact [see Ref. 19, Theorem 24.7 and Ref. 21, Theorem 1.7]. Hence, from (50) there exists a subgradient u^{∗} of g in the point x^{∗} such that

[u^{∗} + ∇h (x^{∗})]^{T} (\overline{x} − x^{∗}) ≥ 0.  (51)

Hence, in the limit the subproblem does not yield a descent direction.

In iteration l, the subproblem is equivalent to the following variational inequality problem [Ref. 1, Theorem 3.4.3]: there exists a subgradient \overline{u}^{(l)} of g at \overline{x}^{(l)} such that for all x ∈ X,

[\overline{u}^{(l)} + ∇_{x}f (\overline{x}^{(l)}, x^{(l)}) + ∇h (x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} (x − \overline{x}^{(l)}) ≥ 0.  (52)

Noting that if \overline{u}^{(l)} ∈ ∂g (\overline{x}^{(l)}), then by the compactness of ∂g (\overline{x}^{(l)}) for all l, a subsequence of L̂ of the subgradients \overline{u}^{(l)} converges towards a point \overline{u}, which by Theorem 24.4 of Ref. 19 satisfies \overline{u} ∈ ∂g (\overline{x}).

Hence, taking the limit over this subsequence, (52) yields

[\overline{u} + ∇_{x}f (\overline{x}, x^{∗}) + ∇h (x^{∗}) − ∇_{x}f (x^{∗}, x^{∗})]^{T} (x − x^{∗}) ≥ 0, ∀ x ∈ X,  (53)

which implies that \overline{x} solves the subproblem of the partial linearization algorithm defined by the point x^{∗}.

By the monotonicity of ∇_{x}f (x, y) with respect to x, (53) implies, by the choice of x = \overline{x}, that

[\overline{u} + ∇h (x^{∗})]^{T} (x^{∗} − \overline{x}) ≥ 0.  (54)

Summing (51) and (54), we obtain that

[\overline{u} − u^{∗}]^{T} (x^{∗} − \overline{x}) ≥ 0.

But by the definition of convexity of g in the points \overline{x} and x^{∗}, the inequality is reversed, so that, in fact,

[\overline{u} − u^{∗}]^{T} (x^{∗} − \overline{x}) = 0.

Substituting this in (54),

[u^{∗} + ∇h (x^{∗})]^{T} (x^{∗} − \overline{x}) ≥ 0,

which by (51) implies

[u^{∗} + ∇h (x^{∗})]^{T} (x^{∗} − \overline{x}) = 0.

Using the same arguments as in the proof of Theorem 2.2, we may conclude that

T^{∗} (\overline{x}) = T^{∗} (x^{∗}) ,

so by (53) there exists a subgradient u^{∗} of g at x^{∗} so that

[u^{∗} + ∇h (x^{∗})]^{T} (x − x^{∗}) ≥ 0, ∀ x ∈ X.

Note that if h is convex, then the variational inequality above is, by the convexity of T, both necessary and sufficient for global optimality of x^{∗} in (NP) [Ref. 1, Theorem 3.4.3]. This completes the proof. □

If g is the indicator function of a closed and convex set S ⊂ ℜ^{n}, it follows from the above proof that the algorithm is globally convergent also when h is only pseudoconvex.

In Theorem 4.1 we in fact proved a more general result than stated, i.e., from the proof it follows that any decrease in the subproblem objective function T^{(l)} from the point x^{(l)} is sufficient to yield a descent direction with respect to the original objective T. This implies, in turn, the possibility of truncating the process of solving (PL-SUB^{(l)}) before reaching its optimal solution, and introduces a trade-off between solving the subproblem accurately and obtaining sufficiently steep descent directions. In Ref. 11 the global convergence of such a scheme is given in the differentiable case, under the condition that at least one step of a descent method is performed on (PL-SUB^{(l)}) in each iteration l, and that this descent method has a closed algorithmic map. This result immediately carries over to the nondifferentiable case. [This way of obtaining search directions finitely by truncating the subproblem algorithm may also be seen as an alternative to the approximation scheme of Kiwiel (Ref. 18).]

The partial linearization method may be extended to inexact line searches also in the case of nondifferentiability by introducing a Lipschitz condition on the differentiable part of the objective, and by restricting f(x, y) to be strictly convex with respect to x. The Armijo steplength rule is modified as follows. The point x^{(l+1)} is obtained by finding the smallest integer ī such that

T (x^{(l)} + β^{−i}d^{(l)}) − T (x^{(l)}) ≤ −εβ^{−i} [∇_{x}f (\overline{x}^{(l)}, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)},  (55)

where d^{(l)} = \overline{x}^{(l)} − x^{(l)}.

Theorem 4.3 Under the additional assumptions that the function h(x) has a Lipschitzian gradient, and that the function f(x, y) is strictly convex with respect to x, the partial linearization algorithm, applied to (NP) using the modified Armijo steplength formula (55), is convergent in the same sense as in Theorem 4.2.

Proof The Lipschitz continuity assumption on ∇h implies, by (12), that for all α ≥ 0,

h (x^{(l)} + αd^{(l)}) − h (x^{(l)}) ≤ α∇h (x^{(l)})^{T} d^{(l)} + \frac{1}{2}α^{2}K ∥d^{(l)}∥^{2} ,  (56)

where K denotes the Lipschitz constant, and where d^{(l)} = \overline{x}^{(l)} − x^{(l)}. Also, for all α ∈ [0, 1],

\begin{aligned}g (x^{(l)} + αd^{(l)}) − g (x^{(l)}) & = & ∫_{0}^{α} g′ (x^{(l)} + sd^{(l)}; d^{(l)}) ds \\ & ≤ & −αg′ (x^{(l)} + d^{(l)}; −d^{(l)}) \\ & = & α inf_{u∈∂g(\overline{x}^{(l)})} u^{T}d^{(l)} \\ & ≤ & α\overline{u}^{(l)}^{T}d^{(l)}, \end{aligned}  (57)

where the first equality follows from Corollary 24.2.1 of Ref. 19 and the first inequality from Theorem 24.1 of the same reference. Note that the subgradient \overline{u}^{(l)} is arbitrary in ∂g (\overline{x}^{(l)}), but will be chosen equal to a particular one, derived below.

From

\overline{x}^{(l)} ∈ arg min_{x∈X} T^{(l)}(x),

we have by (52) that there exists a subgradient \overline{u}^{(l)} of g at the point \overline{x}^{(l)} so that

[\overline{u}^{(l)} + ∇_{x}f (\overline{x}^{(l)}, x^{(l)}) + ∇h (x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)} ≤ 0,  (58)

which implies, by using (56) and (57), that

T (x^{(l)} + αd^{(l)}) − T (x^{(l)}) ≤ −α [∇_{x}f (\overline{x}^{(l)}, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)} + \frac{1}{2}α^{2}K ∥d^{(l)}∥^{2} .

(59)

By replacing ∇T (x^{(l)})^{T} d^{(l)} by − [∇_{x}f (\overline{x}^{(l)}, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)} in the proof of Theorem 2.3, we may conclude that the modified Armijo line search (55) is finite, and that the series

∑_{l=1}^{∞} ([∇_{x}f (\overline{x}^{(l)}, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)})^{2}

is convergent.

Hence,

lim_{l→∞} [∇_{x}f (\overline{x}^{(l)}, x^{(l)}) − ∇_{x}f (x^{(l)}, x^{(l)})]^{T} d^{(l)} = 0,

and we may choose subsequences of \{x^{(l)}\} and \{\overline{x}^{(l)}\} so that

lim_{l∈L} x^{(l)} = x^{∗} and lim_{l∈L̂} \overline{x}^{(l)} = \overline{x},

and we thereby obtain that

[∇_{x}f (\overline{x}, x^{∗}) − ∇_{x}f (x^{∗}, x^{∗})]^{T} (\overline{x} − x^{∗}) = 0.

By the strict convexity of f(x, y) with respect to x, this implies that

x^{∗} = \overline{x}.

Using this in the limit of (58) [cf. Equation (53)], there exists a subgradient u^{∗} of ∂g (x^{∗}) such that

[u^{∗} + ∇h (x^{∗})]^{T} (x − x^{∗}) ≥ 0, ∀ x ∈ X,

which completes the proof. □

Note that convergence cannot be ensured with the modified Armijo line search (55) if h(x) ≡ 0, i.e., for totally nondifferentiable convex programs, while the convergence proof for the algorithm under exact line searches still applies. If on the other hand, g(x) ≡ 0, then (NP) reduces to (P), and the algorithms in this section reduces to those described in Section 2. It is interesting to note that the modified Armijo line search (55), which is dependent on the choice of the approximating function f(x, y), generalizes the one used in Ref. 16. This method may be identified by choosing f(x, y) = \frac{c}{2} ∥x − y∥^{2}, and the corresponding line search (55) would then be to choose the smallest integer ī such that

T (x^{(l)} + β^{−i}d^{(l)}) − T (x^{(l)}) ≤ −cεβ^{−i} ∥d^{(l)}∥^{2} ,

and, indeed, this is the line search employed in Ref. 16.

5. Discussion

In this paper we have introduced a classification of iterative algorithms for convex constrained programming based on partial linearizations of equivalent reformulations of the original objective function. This class of algorithms, which is referred to as partial linearization methods, includes the well known Frank and Wolfe method and constrained Newton-type methods, but also induces new algorithms. Under mild convexity assumptions the algorithm is shown to be globally convergent with or without exact line searches, and for both differentiable and nondifferentiable programming. The function f is arbitrary, and may therefore be chosen to utilize problem structure. An important example is for problems (P) with a nonseparable objective to be minimized over a Cartesian product of sets. Separability is then induced by choosing f separable with respect to this set, see Refs. 2, 10 and 11.

The Frank-Wolfe algorithm is known to have an arithmetic rate of convergence (Ref. 22), and constrained Newton methods have convergence rates ranging from linear to quadratic [Ref. 7, Section III.3]. Hence, instances of the partial linearization algorithm have rates of convergence ranging from arithmetic to quadratic. It would be of interest to further study the theoretical convergence rate of iterative methods in the framework of partial linearization algorithms, as well as studying practical choices of the function f(x, y) for different types of problems.

One of the nice features of the algorithmic class is that efficient second order methods may be defined for nondifferentiable problems, by applying second order approximations to the differentiable part. Convex constrained problems with partially differentiable objectives arise when solving nonlinear continuous problems with Benders decomposition techniques (Refs. 23 and 24). Efficient methods for solving the Benders master problem can be studied in the context of partial linearization methods. Other applications are in dual approaches for large-scale linearly constrained convex programming, where the dual problem may be formulated as a convex and partially differentiable program, and for iterative use in exact penalty methods for differentiable convex programming.

The partial linearization algorithm has recently been extended to finite-dimensional variational inequalities, and shown to include well known methods such as projection type algorithms, linearization methods and diagonalization algorithms, disregarding the line search, see Refs. 3 and 11. Especially interesting is that partial linearization methods induce valid merit functions for asymmetric variational inequalities, and that, as a consequence, line searches with respect to these merit functions may be introduced in classical successive approximation methods to accelerate convergence. The recently presented descent method of Fukushima (Ref. 25) is an instance of this class of methods.

References

[1] Bazaraa, M.S., and Shetty, C.M., Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, New York, New York, 1979.

[2] Larsson, T., and Migdalas, A., An Algorithm for Nonlinear Programs over Cartesian Product Sets, Optimization, Vol. 21, pp. 535-542, 1990.

[3] Larsson, T., and Patriksson, M., A Generalized Gap Function for Variational Inequalities, Report LiTH-MAT-R-90-18, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1990.

[4] Martos, B., Nonlinear Programming Theory and Methods, North-Holland, Amsterdam, Holland, 1975.

[5] Rockafellar, R.T., The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions, Heldermann Verlag, Berlin, Germany, 1981.

[6] Armijo, L., Minimization of Functions Having Lipschitz Continuous Partial Derivatives, Pacific Journal of Mathematics, Vol. 16, pp. 1-3, 1964.

[7] Pshenichny, B.N., and Danilin, Yu. M., Numerical Methods in Extremal Problems, MIR Publishers, Moscow, Russia, 1978.

[8] Frank, M., and Wolfe, P., An algorithm for Quadratic Programming, Naval Research Logistics Quarterly, Vol. 3, pp. 95-110, 1956.

[9] Migdalas, A., A Regularization of the Frank-Wolfe Algorithm, Report LiTH-MAT-R-90-10, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1990.

[10] Larsson, T., Migdalas, A., and Patriksson, M., A Partial Linearization Method for the Traffic Assignment Problem, Report LiTH-MAT-R-89-06, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1989.

[11] Patriksson, M., A Unified Description of Iterative Algorithms for Traffic Equilibria, European Journal of Operational Research, forthcoming.

[12] Polyak, B.T., Introduction to Optimization, Optimization Software, New York, New York, 1987.

[13] Rockafellar, R.T., Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97-116, 1976.

[14] Mine, H., and Fukushima, M., A Minimization Method for the Sum of a Convex Function and a Continuously Differentiable Function, Journal of Optimization Theory and Applications, Vol. 33, pp. 9-23, 1981.

[15] Clarke, F.H., Generalized Gradients and Applications, Transactions of the American Mathematical Society, Vol. 205, pp. 247-262, 1975.

[16] Fukushima, M., and Mine, H., A Generalized Proximal Point Algorithm for Certain Non-Convex Minimization Problems, International Journal of Systems Sciences, Vol. 12, pp. 989-1000, 1981.

[17] Fukushima, M., A Successive Quadratic Programming Method for a Class of Constrained Nonsmooth Optimization Problems, Mathematical Programming, Vol. 49, pp. 231-251, 1991.

[18] Kiwiel, K.C., A Method for Minimizing the Sum of a Convex Function and a Continuously Differentiable Function, Journal of Optimization Theory and Applications, Vol. 48, pp. 437-449, 1986.

[19] Rockafellar, R.T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

[20] Rudin, W., Principles of Mathematical Analysis, 3rd Edition, McGraw-Hill, Singapore, Republic of Singapore, 1985.

[21] Shor, N.Z., Minimization Methods for Non-Differentiable Functions, Springer-Verlag, Berlin, Germany, 1985.

[22] Canon, M.D., and Cullum, C.D., A Tight Upper Bound on the Rate of Convergence of the Frank-Wolfe Algorithm, SIAM Journal on Control, Vol. 6, pp. 509-516, 1968.

[23] Florian, M., and Nguyen, S., A Method for Computing Network Equilibrium with Elastic Demands, Transportation Science, Vol. 8, pp. 321-332, 1974.

[24] Holmberg, K., and Jörnsten, K.O., Cross Decomposition Applied to the Stochastic Transportation Problem, European Journal of Operational Research, Vol. 17, pp. 361-368, 1984.

[25] Fukushima, M., Equivalent Differentiable Optimization Problems and Descent Methods for Asymmetric Variational Inequality Problems, Mathematical Programming, Vol. 53, pp. 99-110, 1992.