Acerca del autor

Berc Rustem is Professor of Computational Methods in Operations Research at the Imperial College of Science, Technology, and Medicine, London, and the author of "Projection Methods in Constrained Optimisation and Applications to Optimal Policy Decisions and Algorithms for Nonlinear Programming and Multiple-Objective Decisions". Melendres Howe, a doctoral graduate of Imperial College, is currently a Treasury Officer at the Asian Development Bank. Previously, she worked in the City of London, as Senior Analyst at a Nomura and Vice President (Currency) at JP Morgan.

Fragmento. © Reproducción autorizada. Todos los derechos reservados.

Algorithms for Worst-case Design and Applications to Risk Management

PRINCETON UNIVERSITY PRESS

Contents

Preface............................................................................................................xiiiChapter 1. Introduction to minimax.................................................................................1Chapter 2. A survey of continuous minimax algorithms...............................................................23Chapter 3. Algorithms for computing saddle points..................................................................37Chapter 4. A quasi-Newton algorithm for continuous minimax.........................................................63Chapter 5. Numerical experiments with continuous minimax algorithms................................................93Chapter 6. Minimax as a robust strategy for discrete rival scenarios...............................................121Chapter 7. Discrete minimax algorithm for nonlinear equality and inequality constrained models.....................139Chapter 8. A continuous minimax strategy for options hedging.......................................................179Chapter 9. Minimax and asset allocation problems...................................................................247Chapter 10. Asset/liability management under uncertainty...........................................................291Chapter 11. Robust currency management.............................................................................341Index..............................................................................................................381

Chapter One

We consider the problem of minimizing a nondifferentiable function, defined by the maximum of an inner function. We refer to this objective function as the max-function. In practical applications of minimax, the max-function takes the form of a maximized error, or disutility, function. For example, portfolio selection models in finance can be formulated in a scenario-based framework where the max-function takes the form of a maximized risk measure across all given scenarios. To solve the minimax problem, algorithms requiring derivative information cannot be used directly and the usual methods that do not require gradients are inadequate for this purpose. Instead of gradients, we need to consider generalized gradients or subgradients to formulate smooth methods for nonsmooth problems.

The minimax notation is introduced with relevant concepts in convex analysis and nonsmooth optimization. We consider the basic theory of continuous minimax, characterized by continuous values of maximizing and minimizing variables, and associated optimality conditions. These need to be satisfied at the solution generated by all algorithms. The problem of discrete minimax, with continuous minimization but discrete maximization variables, and related conditions are considered in Chapters 6 and 7.

1 BACKGROUND AND NOTATION

Equation and section numbering follow the following rule: (1.2.3) refers to Equation 3 in Chapter 1, Section 2. In Chapter 1 only, this is referred to as (2.3), elsewhere as (1.2.3). Chapter 1, Section 2 is referred to in Chapter 1 only as Section 2, elsewhere as Section 1.2.

In this book, we consider strategies, algorithms, properties and applications of worst-case design problems. When taking decisions under uncertainty, it is desirable to evaluate the best policy in view of the worst-case uncertain effect. Essentially, this entails minimax formulations in which the best decision and the worst case is determined simultaneously. In this sense, optimality is defined over all possible values of the uncertain effects as opposed to certain likely realizations. Worst-case design is useful in all disciplines with rival representations of the same system. For example, in economics Chow (1979) and Becker et al. (1986) consider rival macroeconomic models of the same economy. A similar approach to resource allocation is discussed in Pang and Yu (1989). The robustness property is explored in Hansen et al. (1998). In finance, Howe et al. (1994, 1996), Dert and Oldenkamp (1997), Howe and Rustem (1997), Ibanez (1998) and Rustem et al. (2000) consider worst-case decisions in options pricing and portfolio optimization. In engineering, Ben-Tal and Nemirovski (1993, 1994) discuss truss topology design under rival load scenarios. In control systems, H⁸-control theory is essentially an equivalent minimax formulation for the uncertainties in the system and this aspect is explored in Basar and Bernhard (1991). Rival representations can be characterized either in terms of a discrete choice, such as two or more models of the same system, or as values from a continuous range, such as all the values an uncertain variable may take within an upper and lower bound.

The worst-case design or minimax problem can thus be formulated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1)

where x [member of] Rⁿ is a column vector of real numbers, denoting the decision variables in the n-dimensional Euclidian space. The vector y represents the uncertain variables and is defined over the feasible set Y. An equivalent problem to the above formulation is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is the max-function. If Y is a set of continuous variables, then the problem is known as continuous minimax. An example for such a set is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the lower and upper bounds on the ith element of y. Algorithms for this problem are discussed in detail in Chapters 2–5.

If Y consists of a discrete set of values, the corresponding problem is known as discrete minimax. We consider equality and inequality constraints on x in particular for the case of discrete min-max. The problem is expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where fⁱ(x) is the value corresponding to the ith member of the discrete set {1, 2, ..., m} over which the maximum is evaluated and g, h are vectors of equality and inequality constraints. Properties of, and algorithms for, this formulation are considered in Chapters 6 and 7.

In this section, we review some of the basic concepts used elsewhere in the book. Some of the more preliminary material is covered in Comments and Notes (CN 1–CN 11) at the end of the chapter. We start by considering the closed line segment joining x and z, denoted by [x, z],

[x, z] [equivalent to] {w [member of] Rⁿ | w = ?x + (1 - ?)z, 0 = ? = 1} (1.2)

and by (x, z) the corresponding open line segment.

Convexity is invoked extensively in minimax. We define this property for sets and functions. A set C [subset] Rⁿ is called convex if [x, z] [subset] ITLITL for all x, z [member of] ITLITL. The linear combination

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is called a convex combination of vectors x₁, ..., x_J [member of] Rⁿ if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The convex hull of a set ITLITL [subset] Rⁿ, denoted by conv ITLITL, is the set of all convex combinations of points in ITLITL.

Let ITLITL be a convex set. A function f : C [subset] Rⁿ [right arrow] R¹ is said to be convex if

f(?x + (1 - ?)z) = ?f(x) 1 (1 - ?)f(z) (1:3)

for x, z [member of] ITLITL and ? [member of] (0, 1). If strict inequality holds for x [not equal to] z and ? [member of] (0, 1), then f is strictly convex. A function defined on ITLITL is said to be (strictly) concave if the function f = -g is (strictly) convex.

Lemma 1.1 Let f(x) [member of] C¹ (see CN 3). Then, f is convex over a convex set C if and only if

f(z) = f(x) + [for all]f(x)(z - x), [for all]z, x [member of] C.

The function is strictly convex if this inequality is strict.

Proof. Let f be convex. Then, we have

f(?x + (1 - ?)z) = ?f(x) + (1 - ?)f(z), [for all]? [member of] [0, 1]

and hence

f(?x + (1 - ?)z) - f(z)/? = f(x) - f(z).

This expression yields the required inequality for ? [right arrow] 0. Let

f(z) = f(x) + [for all]f(x)(z - x), [for all]z, x [member of] C

and

x = ?x₁ + (1 - ?)y

for some x₁ [member of] ITLITL and ? [member of] [0, 1]. We have the inequalities

f(x₁) = f(x) + [for all]f(x)(x₁ - x)

f(y) = f(x) + [for all]f(x)(y - x).

Multiplying the first of these inequalities by ? and the second by (1 - ?) and adding yields

?f(x₁) + (1 - ?)f(y) = f(x) + [for all]f(x)(?x₁ + (1 - ?)y - x).

Substituting x = ?x₁ + (1 - ?)y yields

?f(x₁) + (1 - ?)f(y) = f(?x₁ + (1 - ?)y).

Lemma 1.2 Let f (x) [member of] C². Then, f is convex (strictly convex) over a convex set C containing an interior point if and only if the Hessian matrix [for all]²f(x) of f is positive semi-definite (positive definite) (see CN 4) throughout C.

Proof. Using the second order Taylor expansion of f (see CN 5), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some ? [member of] [0, 1] (<·,·> is defined in CN 2). If the Hessian is positive semi-definite everywhere, we have

f(y) = f(x) + (1.4)

and, in view of Lemma 1.1, this establishes the convexity of f.

We show that if [for all]²f(x) is not positive semi-definite for some x [member of] ITLITL, then f is not convex. Let [for all]²f(x) not be positive semi-definite for some x [member of] ITLITL. By continuity of [for all]²f(x) it can be assumed, without loss of generality that x is an interior point of C. There is a y [member of] ITLITL such that

2f(x)(x - y)> < 0.

Again, by continuity of the Hessian, y may be selected such that

2f(x + ?(y - x))(x - y)> < 0, [for all]? [member of] [0, 1].

In view of the Taylor expansion above, (1.4) does not hold and by Lemma 1.1, f is not convex.

An important property of convexity of f is the uniqueness of its minimum, as stated in the following result.

Lemma 1.3 Let f be a convex function defined over the convex set C. Then, any local minimum of f is also a global minimum (see CN 11).

Proof. Suppose that x₁ is a local minimum. Suppose also that there is another point x₂ [member of] C, x₁ [not equal to] x₂, with f(x₂) < f(x₁). Then, for ax₁ + (1 - a)x₂, a [member of] (0; 1), we have

f(ax₁ + (1 - a)x₂) = af(x₁) + 1 - a)f(x₂) < f(x₁)

which contradicts that x₁ is a local minimum point.

If f(?x) = ?f(x) for all ? = 0, then f is said to be positively homogeneous. If

f(x + w) = f(x) + f(w), [for all]x, w [member of] Rⁿ

then f is subadditive. A positively homogeneous subadditive function is always convex. A convex function f : Rⁿ [right arrow] R¹ is locally Lipschitz continuous (see CN 8) at x, for any x [member of] Rⁿ (Makela and Neittaanmaki, 1992, p. 8, Theorem 2.1.1).

The concept of linear (in)dependence of a set of vectors is used extensively, in particular for the analysis and characterization of the gradients of the max-function, in conjunction with Caratheodory's Theorem which we also cover in this section. We commence with a definition of linear independence.

1.1 Linear Independence

A set of vectors {x₁, ..., x_r} in Rⁿ is linearly independent if and only if the equality

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.5) is achieved for a^j = 0, j = 1, ..., r. If r = n + 1, any vectors x₁, ..., x_r in Rⁿ are linearly dependent. Hence there exist numbers ß¹, ..., ß^r such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6)

We note that ß^j can be positive or nonpositive. If r = n + 2, then any vectors x₁, ..., x_r in Rⁿ are linearly dependent with (1.6) including the additional condition that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.7)

To verify that (1.7) holds for r = n + 2, we represent

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.8)

Since r = n + 2 > n + 1, x_n+2 can be represented as a linear combination of {x₁, ..., x_n+1} as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Returning to (1.8),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, (1.7) holds for r = n + 2. The argument can be straightforwardly extended to r > n 1 2.

An equivalent, and shorter, demonstration of (1.7) is done by considering the n + 1 dimensional vectors

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where x^k_i is the ith element, i = 1, ..., n, of [bar.x]_k. There are numbers ß^k, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], satisfying

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is equivalent to (1.7).

1.2 Tangent Cone, Normal Cone and Epigraph

The tangent cone of a convex set ITLITL, at x [member of] ITLITL, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.9)

The normal cone of the convex set ITLITL, at x [member of] ITLITL, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.10)

The epigraph of a function f : Rⁿ [right arrow] R¹ is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.11)

The epigraph of a convex function f : Rⁿ [right arrow] R¹ is a closed convex set (Makela and Neittaanmaki, 1992, Theorem 2.3.7).

1.3 Subgradients and Subdifferentials of Convex Functions

The subdifferential of a convex function f : Rⁿ [right arrow] R¹, at x [member of] Rⁿ, is the set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Each element g [member of] [partial derivative]f(x) is called a subgradient of f at x. The directional derivative in the direction v [member of] Rⁿ satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.13)

More generally, the Clarke (1983) generalized derivative of a locally Lipschitz function f at x in the direction v [member of] Rⁿ is defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.14)

The following important result is used to define a subgradient of the max-function where the maximizer is nonunique, in terms of the subdifferential.

Theorem 1.1 (Caratheodory's Theorem) Let G be a set in the finite dimensional Euclidian space, G [subset or equal to] Rⁿ. Then, any vector may be expressed as a convex combination of at most n + 1 vectors in G.

Proof. This result is widely known (e.g., Demyanov and Malozemov, 1974, Appendix 2, Lemma 1.1). Its proof does provide some insight for the subsequent discussion. Consider the definition of the convex hull of G

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.15)

Suppose that some x [member of] G cannot be represented by (1.15) with less than n + 2 terms (after those with a^k = 0 have been discarded), that is, r = n + 2 in any representation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.16)

From the discussion on linear independence, if r = n 1 2, there exist numbers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.17)

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Vector x can be expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.18)

To show the equivalence between (1.16) and (1.18), we expand (1.18) to yield

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In view of (1.17), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Considering positive and nonpositive ß^k separately, we see that [bar.a]^k = 0, k [member of] {1, ..., r}. At least one [bar.a]^k must vanish and this corresponds to subscript

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, x is a convex combination of at most r - 1 vectors of G. Iterating this procedure sufficiently many times, we reach a representation r = n + 1, (1.17) is no longer satisfied, and we have the desired result.

We invoke Caratheodory's Theorem in the context of the subdifferential

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.19)

Using Caratheodory's Theorem, g can be characterized by the convex combination of at most n + 1 vectors [for all]_x f(x, y). To verify this, suppose that a subgradient g [member of] [partial derivative]F(x) = conv G has no representation of type (1.19), for less than n + 2 vectors (after vectors [for all]_xf(x, y)] with associated a^y = 0 are discarded). Hence, r = n + 2 in the representation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From the discussion on linear dependence, because r = n + 2, these exist numbers ß^y such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(Continues...)

Excerpted from Algorithms for Worst-case Design and Applications to Risk Managementby Berç Rustem Melendres Howe Copyright © 2002 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.