Section I

Multicriteria Decision Making Support

Annals of Operations Research 51(1994)3-13

3

Interactive decision making: Equivalence of modified formulations Be W Rustem

Department of Computing, Imperial College of Science, Technology & Medicine, 180 Queen's Gate, London SW7 2BZ, UK

We discuss the use of a quadratic norm for departures from the bliss value of a decision problem under conflicting objectives. The use of a quadratic norm is, for example, of interest within the dynamic framework of optimal control. The symmetric nature of the quadratic norm is relaxed to allow for nonsymmetric preferences. The possibility of tailoring the quadratic objective function to generate optimal policies which are acceptable to the policy maker is explored with two alternative interactive algorithms. One of these is for objective functions with diagonal weighting matrices and uses updates of the bliss values. The second algorithm proceeds by updating nondiagonal weights, while keeping the bliss values fixed. The equivalence of both algorithms is established. Keywords: Multiple objectives, quadratic programming, decision support, interactive algorithms.

1.

Introduction

Let ~ e R n be the bliss value of a multi-objective decision problem. Consider the determination of the relative importance of attaining the different elements of ~ . The attainment of different elements of ~ generally represent conflicting objectives. W e adopt a quadratic objective for measuring deviations from the bliss value. The quadratic function is of interest, for example, within the framework of optimal control. In section 2, we describe a way of avoiding, if required, the symmetric nature of the quadratic function. We consider two interactive methods for the specification of the quadratic objective. The purpose of both methods is to tailor the objective function such that the optimally generated solution of the decision problem is also politically acceptable to the decision maker. The first is a method for the specification of the quadratic objective with a diagonal weighting matrix. The second method is for the specification of the weights and generates a nondiagonal weighting matrix. Consider the linear-quadratic optimal decision problem

rain{( x-~,D( x-~))INTx=b}, © J.C. Baltzer AG, Science Publishers

(1.1)

4

B. Rustem, Interactive decision making

where x ~ En, b ~ Em is a fixed vector, D is a diagonal matrix with nonnegative elements, ~ is the bliss value of x or the unconstrained optimum of the quadratic objective. The columns of matrix N ~ n:n×m are assumed, without loss of generality, to be linearly independent. The diagonal weighting matrix in (1.1) occurs in economic decision making and in general in linear-quadratic optimal control problems. In the latter case, (1.1) can be regarded as the transcription of the dynamic problem into static form (see e.g. [6]). PROBLEM STATEMENT

Let f~ ___ E" denote the set of policies acceptable to the decision maker. We assume that there does not exist an analytical characterization of f~ and that f~ exists only in the mind of the decision maker. If an explicit characterization of f~ was possible, it could be used to augment the constraints of (1.1) and the resultant problem could easily be solved. An analytical characterization is both inherently difficult, or impossible, and sometimes also politically undesirable from the decision maker's point of view. The problem is to tailor an objective function for which the optimal solution of (1.1), x*, also satisfies x ° ~ fL We discuss two types of solutions to the above problem. The first involves modifications to ~ and keeps D fixed as a diagonal matrix. This is discussed in section 3. The second involves modifications to D and generates a nondiagonal weighting matrix while keeping ~ fixed and is discussed in section 4. We also discuss the equivalence of both methods. The desirability of a diagonal D is due to computational reasons as well as the interpretation of the problem and the optimal solution. Non-diagonal weighting matrices can be diagonalized by appropriate transformations of the variables. However, such transformations lead to computational complications, particularly in relation to the constraints. A more important aspect is the difficulty of assigning an interpretation to the off-diagonal elements of a general symmetric weighting matrix. These elements are usually understood to represent trade-offs between achieving alternative objectives. However, they are difficult to assign an interpretation as distinct from the diagonal elements, which represent the relative importance of each objective. Also, for linearquadratic dynamic problems, solved via dynamic programming, maintaining the block diagonality of D, in terms of the time structure, is desirable at least for the physical interpretation of the resultant optimal linear feedback laws. This contrasts with the case when non-diagonal weighting matrices have to be factorized and the original variables have to be transformed in order to obtain feedback laws which may only apply to the transformed variables. In most economic decision making problems under conflicting objectives, the precise value of the weighting matrix is not known. Even a judicious choice of the weighting matrix need not necessarily yield a solution of problem (1.1) that is in the set of acceptable policies, I). In section 3, we discuss an iterative algorithm,

B. Rustem, Interactive decision making

5

involving interactions with the decision maker, to specify a diagonal quadratic objective function that generates a solution of (1.1) which is acceptable to the decision maker. The algorithm involves the modification of the bliss value. In section 4, the method is shown to be equivalent to an alternative method involving the re-specification of the general non-diagonal symmetric matrix [9, 10]. In the latter method, the bliss values remain fixed hut the weighting matrix is altered and does not maintain a diagonal structure. This correspondence is helpful computationally as diagonal matrices are simpler to compute. Conversely, the correspondence provides the non-diagonal weighting matrix that would generate the same optimal solution as the one obtained by modifying the bliss values. In addition, the correspondence can be used to discuss the complexity and polynomial time termination property of the algorithms by invoking the results in Rustem [7] and Rustem and Velupillai [11].

2.

Nonsymmetric quadratic functions

The quadratic function direction from the bliss value the bliss value, the quadratic it would penalise departures therefore, the problem

(1.1) assigns equal importance to deviations in either of a variable. Thus, if a variable could do better than objective penalises such a departure just as much as of the variable in the inferior direction. Consider,

I

}

rrhn ~ di(xi-~i)~ I NTx=b ,

(2.1)

where the superscript i denotes the ith variable, d i e [0,~) is the corresponding weight and (.)+ = min{0, x / - ~i}. Extending a similar approach in linear pro.gram,ming, for each variable requiring non-symmetric penalisation, we define x i - ~ ' = x~. - x~_, where x/+, x/_ > 0 and

xi+ : xi+ = x i _ ~i

if

x i _ ~i > O,

=0

if

xi--~i
x/:x/_ = 0

if

xi_~i>O,

=--(xi-- ~ i) if

xi-- ~i
Thus, either x/_ = 0 or x/+ = 0 or both. In addition to the nonnegativity restrictions, we therefore have to impose the constraints (x/_)(x~) = 0. Since in vector notation we have, x = x ÷ - x_ + ~ , we can express the above minimization problem as min f ~

i=1

di(xl+)2+p~.~ n (xi)(xi+) i=1

[NTi-NT]

X+] x_ = b - NT~ ; X+,X_ ~ 0},

(2.2)

6

B. Rustem, Interactive decision making

where p > 0 is a sufficiently large penalty parameter chosen to ensure that, in view o f the nonnegativit.y constraints, the minimum value of (xi_)(xi+) is realised at either xL = 0 or x~. = 0. We have thus reduced the nonsymmetric problem to a symmetric problem. The weighting matrix of the objective function in (2.2) is given by

o'1 As Q is not diagonal, only the algorithm discussed in section 4 is applicable for the specification of this weighting matrix. The algorithm will replace D with a nondiagonal matrix. The application of the algorithm for this case has to ensure that zero weighting on (x_) 2 is maintained by concentrating on the departures of x÷ from 0 and allowing free movements in x_. This is consistent with the original formulation in (2.1)*.We start with the simpler case of specifying a diagonal objective function in section 3.

3.

Diagonal quadratic objective functions

We consider a solution to problem 1 based on keeping the diagonal weighting matrix fixed and updating the desired or bliss values. In the next section, we discuss an alternative solution that generates nondiagonal weighting matrices. We establish the equivalence of both solutions, provided the initial weighting matrix is diagonal in either case. Let (1.1) be solved for a given weighting matrix D and a given initial vector of bliss values ~0. The solution is denoted by x0 = arg min{ ( X - ~ o , D ( x - ~ o ) )

I NTx=b}.

The solution is presented to the decision maker who is required to respond by either declaring that x0 ~ f~, or if x0 ~ t2, the decision maker is required to specify the modified form of x 0 that is in f~. The decision problem we wish to consider can now be formulated as the computation of the policy, optimally determined via (1.1), but which also is acceptable to the policy maker and is hence in the set t2. We assume that { x I NXx = b } n f~ ~ 0 . The decision maker's preferred alternative to x 0 is denoted by Xp. By definition, we have xp ~ [2 but not necessarily Xp ~ { x I NTx = b } n t2. In case the latter is true, such a preferred alternative would conceptually solve the decision problem. Let *In the terminology of section 4, the vector 5 specified by the policy maker only requires modifications in the optimal solution for the variables corresponding to x÷. Variable values x_ are not penalised, hence desirable. The policy maker is thus satisfied with these. Thus, the elements of 8, corresponding to x_ are always zero.

B. Rustem, Interactive decision making

7

80 = Xp - x0, where 80 is the correction vector that needs to be added to x0 in order to ensure that x0 + 80 ~ ~. Using 80, we can revise the bliss value as G 1 = G0 + a0 80 where a0 > 0 is a scalar. Using this new bliss value, problem (1.1) is solved once again to yield a new optimal solution, xl. This solution is shown below to have desirable characteristics. However, as there is no guarantee that xl ~ ~ , the above procedure may need to be repeated. The resulting algorithm is summarized below. We discuss the complexity and termination properties of the algorithm in Rustem [7] and Rustem and Velupillai [11]. ALGORITHM: UPDATESOF BLISSVALUESWITH A FIXED DIAGONALWEIGHTINGMATRIX Step O: Given D, G0, the sequence {ak} and the constraints, set k = 0.

Step 1: Compute the solution of the optimization problem Xk = arg min { (x - Gk, D ( x - Gk) ) IN t x = b}.

(3.1)

Step 2: Interact with the decision maker. If Xk ~ f~, stop. Otherwise, the decision maker is required to specify the preferred value Xp, and hence, 8k = Xp - xk.

(3.2)

Step 3: Update the bliss values Gk+l = Gk + akdk,

setk=k+landgoto

(3.3)

stepl.

The relationship of Xk+l, Xk and ak, 8k is summarized in the following results. The choice of the objective function may also be based on criteria other than xk ~ ~ . For example, in the linear stochastic dynamical systems, the weighting matrices might be chosen to yield a stable minimum variance controller (see Engwerda and Otter [1 ]). However, in the present study we consider the equivalence properties of the approach adopted in this section to re-specification, discussed in section 4, of nondiagonal weighting matrices while keeping G fixed. This equivalence also provides the key to the complexity and convergence of the policy design process. In addition, as it is possible to decompose a symmetric matrix into a sequence of rank one updates (see Fiacco and McCormick [2]), the method in this section and the equivalence result allow the possibility of expressing non diagonal weighting matrices in terms of diagonalized objective functions. An alternative characterization of the problem would be in terms of finding a solution that simply satisfies the constraints and f~, without any optimality requirement. One difficulty of this approach is that f~ needs to be explicitly specified. Let us assume that this was possible and that fl was characterized by the intersection of a finite number of linear inequalities. It can then be shown that both the above algorithm and the algorithm in the next section are related to Khachian's [4,5] algorithm for computing a feasible solution to a system of linear inequalities. In this framework, the vector 8is determined by one of the (linear) constraints bounding the

8

B. Rustem, Interactive decision making

set f~. In particular, 6 is related to the gradient of a constraint characterizing ~ , violated at xk [8, 11]. By invoking Khachian's result, we can thereby obtain a polynomial time complexity for both algorithms. The added advantage of the two algorithms in this paper is that they relate each iteration with an objective function and optimality that is useful to the decision maker. Since the set of acceptable policies, ~ , does not exist anywhere except in the mind of the decision maker, the interpretation and specification of t~ is aided by the optimality, at each iteration, o f the quadratic objective function. PROPOSITION I Assume that D is positive semi-definite, the optimal solution and Lagrange multipliers can be written as Xk+l = X k + otkZ ( Z T D Z ) -1 ZT D ~k,

(3.4)

where Z ~ p×(~-m) is an orthogonal matrix* such that Z T N = O, and ~,k+l = ~'k -- a k ( N T N ) - I N T D [ I - z ( Z T D Z ) -l zT D ) t~k.

(3.5)

Proof

To establish (3.4), we note that Xk+l --Xk ~ { x l N T x = 0} and, as N r Z = 0, any such vector can be written as a linear combination of the columns of Z. Thus, we have Xk÷i -- Xk = Z w , for some vector w ~ En-m and from the first order optimality condition of (3.1) we can write ZT D [Zw + Xk -- ~ k -- Ctk t~k] = ZT N ~,k+I = 0

and thus Xk+I -- Xk = Z W = - Z

( Z T D Z ) -1 Z T D [Xk-- ~ k -- ak t~k].

(3.6)

From the optimality condition at iteration k, we have Z T D [ Xk -- ~k] = ZT N ~,k = O. Thus, expression (3.4) follows from (3.6). For (3.5), we use the optimality condition at k + 1 to yield &k+l = ( N T N ) - t N T D [Xk+l- Xk + Xk - ~ k - ak 6k].

(3.7)

Using (3.4) and the optimality condition at k, D (xk - X ~ ) = N ~,k, leads to expression (3.5). O

*The numerically stable way of generating Z is by considering the QR decomposition of N. The matrix Z is given by the last n - m columns of the matrix Q of this decomposition (see Gill et al. [3]).

B. Rustem, Interactive decision making

4.

9

The diagonal version of non-diagonal quadratic forms

We consider the equivalence of the algorithm in section 3 with a method generating nondiagonal weighting matrices, discussed in Rustem et al. [9], and Rustem and Velupillai [10]. The complexity of the former is discussed in Rustem and Velupillai [11], by exploiting this equivalence. The following algorithm uses the same tSk as in the algorithm in section 3. It keeps the bliss values fixed but updates the weighting matrix of the quadratic optimization problem. ALGORITHM: FIXED BLISS VALUES AND NON-DIAGONAL WEIGHTING MATRIX

Step 0: Given a positive semi-definite weighting matrix Q0, the sequence #k, the bliss values ~ d and the constraints, set k = 0.

Step 1: Compute the solution of the optimization problem xk = arg min{ (x - ~d, Qk (x - ~d) ) INTx = b}.

(4.1)

Step 2: Interact with the decision maker. If Xk ~ f~, stop. Otherwise, the decision maker is required to specify the preferred value xp, and hence, tSk= Xp -- Xk.

Step 3: Update the weighting matrix ak + l = Oh + #k

Setk=k+l

(4.2)

and go to step 1.

The matrix Qk computed in the algorithm above is in general non-diagonal. It is shown below that starting with an initial diagonal matrix, the above algorithm and the algorithm in section 3 are equivalent. At each stage, the non-diagonal version above has a constant diagonal equivalent in the algorithm of section 3. The equivalent results to proposition 1 related to the above algorithm are discussed in Rustem and Velupillai [10]. We summarize these results. When Qk is positive semidefinite, each subsequent iterate of the above algorithm is given by Xk+ 1 = Xk + & k Z ( Z T a k Z ) - l ZTakt~k,

~.k.l = "~.k-&k(NTN)-INTQk(I-Z(ZTQkz)-IZTQk)t~k,

k=(

l k< k,ak(xk ' Ok k ) + ]2k
(4.3a) (4.3b) (4.3c)

(see Rustem and Velupillai [10, theorems 1, 2, lemma 2]). We now show the equivalence of the solution of the two quadratic optimization problems: one with the diagonal weighting matrix fixed and only the bliss

10

B. Rustem, Interactive decision making

values modified, and the other with the bliss values fixed and only the diagonal matrix modified to a non-diagonal form. PROPOSITION 2 Let Q / b e nonsingular. Then, there e x i s t / z k, txk and t ~ / s u c h that for Qk 8k ~T Qk Qk+l = Qk + ldk
~ k + l = ~ k -t'O~kt~k ,

(4.4)

we have arg min{
- ~k+l,

Qk(x - ~k+l)>l NTx = b}

(4.5) = arg min{l NTx = b}. Moreover, we have &k = tXk. If tXk, #k are restricted such that txk, #k ~ 0, then the choice of Sk is restricted by the inequality < Sk, Qk(Xk -- ~k)> < O. Proof* Consider the optimality conditions of the minimization problems on both sides of (4.5). With the solution and the Lagrange multipliers denoted respectively by Xk+l,~k+l, the left-hand side yields Qk(Xk+l -- ~'~k+l) -- N/Lk+l = 0.

The right-hand side yields

Qk+gk

Qk- (Xk+1 -~t~ k ) -

ak>

N~k+ 1 = O.

Equating both optimality conditions, we have

and hence ~k+l = ~ k +trk t~k, where ak = - # k


)>

(4.6)

(¢~k,Qk ~k)

*The above proposition clearly holds for Qk = D. Qk+I is D with a rank-one update and hence, in general, it is no longer diagonal. When Qk is singular, (4.4) can be written as Qk~k+l = Qk(~k + ¢xk8k) from which the relevant parts of ~k+l can be recovered. For example, when Qk = D, a diagonal matrix, only those elements of ~k+I corresponding to nonzero diagonal elements of D can be recovered. The correspondence of ~k given by (4.3c) and ~k can be established in the same way as in the following proof except that (4.3a) is used for xk+1.

B. Rustem, Interactive decision making

11

It can be shown that {zk in (4.6) and &k in (4.3c) are equivalent (see Rustem [7]). The inequality (~k, Q~ (x~ - ~k)) < 0 ensures that ak,/Zk < 0. To demonstrate this when Q~+~is given as above, we see that otk given by (4.6) is equivalent to &k and this is nonnegative if the above inequality and/z~ > 0 are satisfied. When the bliss value is being updated and an equivalent update to Qk is being computed, then for ak > O, and I.tk =-otk (~,Q~(x~+l - ~

)>"

(4.7)

We now show that (~k, Qk (xk- ~k)) < 0 ~ (Sk, Qk (xk+l - ~ ) ) < 0. The inequality (xk+i - xk, Qk+l (xk+l -- ~k)) < 0 follows from the optimality of xk+l for the quadratic optimization with Qk+t. Using the expression for Q~+~, we have 0 >_(xk+ - xk,Qk+ (xk+

)>

= (xk+l -xk,Qk(xk+1

(t~k,Qk t~k)

(Xk+l - xk, Qk( k>
)>.

Since (xk+l - xk, Qk (xk - ~k)) > 0 follows from the optimality of xk with Qk, and (6k, Qk(xk+l- xk)) > 0 holds if (~k, Qk(xk- ~k)) < 0 (see Rustem and Velupillai [11, lemma 2]), then we have (6k, Qk (xk+ l - ~k)) < 0 =~ #k > 0 and the corresponding #k is given by (4.7). [] The method can also be extended to the nonlinear constrained case when the diagonal equivalent of a non-diagonal quadratic function is desired. The useful analytical equivalence of cx and & cannot be established exactly in the nonlinear case. Clearly, if the departure of xk+l from xk is sufficiently small, then this equivalence can also be established by invoking a mean value theorem and thereby using a local linear representation of the constraints (see e.g. Rustem and Velupillai [11, theorem 5]). The following corollary summarizes the extension. COROLLARY (THE EXTENSIONTO NONLINEARCONSTRAINTS) Let ~k+l and Qk+l be defined by (4.4) and let the constraints be given by G = {x~ n:ntg(x) = 0},

(4.8)

where g is twice differentiable and g: Fn --->n:m. Then the equivalence arg nfm {(xk --~ k + l,Qk(xk --~ k +1)) Ix ~-G } = arg min {(xk - ~k, Qk +1(xk- ~ k )) Ix ~ G }

holds for ak given by (4.6).

12

B. Rustem, Interactive decision making

Proof

The proof follows from the equivalence of the first order optimality [] conditions. The extension to nonlinear constraints is thus easily implementable as the basic ingredients that enter ak axe t~k and Xk+l. Both of these vectors are known when any one of the two quadratic problems have already been solved. Proposition 2 relates the effect of a single update of Qk that yields Qk+i or a single update of ~k that yields ~k+l. As a corollary, we consider the sequence {Qk} generated by the algorithm in this section and the corresponding sequence {~k} generated by the algorithm in section 1. THEOREM I (THE DIAGONALIZIBILITY OF QUADRATIC FORMS)

Let the sequence {Qk} be generated by (4.2) and {~k} be generated by (3.3), let Q0 = D, then the equivalence between the diagonal and non-diagonal quadratic optimizations arg min{(x - ~ k ,D(x - ~ k )) I NT x = b} (4.9a) = a r g m i n { < x - ~ o , Q k ( x - ~ o ))I NTx = b} holds if

k-I

D ~ k = D ~ o - ~_~ #i aiai"



i=0

(4.9b)

Proof

(4.9b) follows from the following equivalence of the optimality conditions of both problems

L

S " N r , g J'

[]

The complexity of the above algorithm and that in section 3 can be discussed, for f~ characterized by linear inequalities whose gradients are related to 8. We invoke the equivalence of the above algorithm to the algorithm in section 3, and the relation of the former to Khachian's [4, 5] algorithm for linear programming. As Khachian's algorithm is known to be convergent in polynomial time, its equivalence to the above algorithms would ensure the same convergence rate. It is shown in Rustem and Velupillai [11, theorems 1 and 7] that the algorithm in this section is equivalent to Khachian's algorithm provided that ~0 on the right of the equivalence (4.9a) is shifted, at every k, in a way that will only affect the stepsize ak or &k above (see Rustem [7]).

B. Rustem, Interactive decision making

5.

13

Concluding remarks

The problem of decision making under conflicting objectives is formulated as the optimization of a weighted quadratic function of these objectives. The possibility of constructing quadratic objective functions with diagonal weighting matrices is desirable both in terms of computational convenience and interpretability. An approach is discussed for interactively tailoring such objectives. An equivalent interactive approach is also provided for the nondiagonal weighting matrix case which becomes useful when considering nonsymmetric objective functions. The extension to nonlinear constraints permits the wider applicability of the results.

References [1] J.C. Engwerda and P.W. Otter, On the choice of weighting matrices in the minimum variance controller, Automatica 25(1989)279-285. [2] A.V.Fiacco and G.P. McCormick, Nonlinear Programming: Sequential UnconstrainedMinimization Techniques (Wiley, New York, 1968). [3] P.E. Gill, W. Murray and M.H. Wright, Practical Optimization (Academic Press, London-New York, 1981). [4] L.G. Khachian, A polynomial algorithm in linear programming, Sov. Math. Doklady 20(1979) 191-194. [5] L.G. Khachian, Polynomial algorithms in linear programming, USSR Comp. Math. and Math. Phys. 20(1980)53-72. [6] E. Polak, Computational Methods in Optimization (Academic Press, New York and London, 1971). [7] B. Rustem, On the diagonalizibility of quadratic forms and the arbitrariness of shadow prices, in: Modelling and Control of National Economies, ed. N. Christodoulakis (Pergamon, Oxford, 1990). [8] B. Rustem, The diagonalizibility of quadratic functions and the arbitrariness of shadow prices, Automatica 27(1991)573-578. [9] B. Rustem, K. Velupillai and J. Westcott, Respecifying the weighting matrix of a quadratic objective function, Automatica 14(1978)567-582. [10] B. Rustem, K. Velupillai, Constructing objective functions for macroeconomic decision models: A formalization of Ragnar Frisch's approach, PROPE Discussion Paper No. 69, Imperial College, London, 1991. [11] B. Rustem and K. Velupillai, Constructing objective functions for macroeconomic decision models: On the complexity of the policy design process, PROPE Discussion Paper No. 84, Imperial College, London (1991).