World Bank Development Research Center Discussion Papers No. 21 LINEAR TRANSFORMATIONS I N MATHEMATICAL PROGRA.M':J.NG bY Wilfred Candler and Roger Norton r t January 1977 *- - * 8 NOTE: isc cuss ion Papers a r e preliminary materials circulated t o " s t i m u l a t e d i s c u s s i o n and c r i t i c a l comment. References i n p u b l i c a t i o n t~ Discussion Papers should b e c l e a r e d w i t 3 t h e a u t h o r ( s ) t o p r o t e c t t h e t e n t a t i v e c h a r a c t e r of t h e s e papers. TABLE OF CONTENTS - 1. Introduction 2. A Simple Logarithmic Transformation 3. A h"ay!or Expansion Transformation 4. A Growth Rate Transformation 5. Separable Transformations 6. Non-Separable Transformations 7. A Multiple Logarithmic Transformation 8. An Application to the CES Function 9. A Concluding Note LINEAR TRANSFORI4ATIONS I// .MTHEMATICA&-._PROGRAMMING ViZfred Candler and Roger Norton* In troduction This paper considers a number of useful transformations which can permit some mathematical programming problems t o be approximated, with any desired degree of accuracy, by l i n e a r programing. The transformations a r e motivated primarily by the p o s s i b i l i t y of applications t o problems i n economics, with s p e c i a l reference t o large-scale models. . The p r i n c i p a l aim of t h i s paper is t o f a c i l i t a t e the wider use of applied numerical models by delineating a number of simple procedures which, by e f f e c t i n g l i n e a r i z a t i o n , permit use of t h e powerful simplex algorithm and its successors t o a t t a i n solutions. P a r t of t h e paper is expository: it draws together several existing transformations and presents them i n a common notation. I n other sections, t h e paper's scope i e extended with some a d d i t i o n a l transformations developed f o r p r a c t i c a l purposes by the authors. We s t a r t with a mathematical programming problem: f i n d an n-vector -x such t h a t a , t Z = f (2) a min (1) , - subject t o : pi(?)- - ... ,m , - I 9 ki i = 1, (2) ' d L where f k ) and g (x) a r e continuous and convex f u n c t i a s . i - * I I m * Wilfred Candler is a t the Economics Branch, Agriculture Canada. Ottawa; and Roger Norton is a t the Development Research Center, World Bank, Washington, D.C. These organizations do not necessarily subscribe t o the views expressed here. The authors would l i k e t o thank J.J. Bisschop and J.H. Duloy f o r helpful discussions of some of t h e points i n t h e paper. The problem of e f f i c i e n t l y representing t h t s problem a s a i i n e a r progrsmming problem can be stated a s follows: find a vector such that Z = 5 Z l a min subject t o ' ' Y -> 0 ( 5 ) where A, -b, and c a r e matrices and vectors of constants, the dimension - of A is usually greater than mxn and the dimensions of b, c and - - conform t o those of A. In the following, we begin with the simplest transformations of (1) - (2) i n t o (3) - ( 5 ) , and move t o more complex cases. Most of the transformations a r e designed t o promote computational efficiency by economizing on the number of rats i n the new problem, a t the expense of a greater number of columns. A Simp le liogarit h i c Transformation then the posynomial functions f(x) and gi(x) - - a r e continuous and convex, and they take the Cobb-Douglas form frequently encountered i n econornics. We get an exact transformation t o linear programming by solving the equivalent problem: Find an n-vector y such that: a min subject t o (2). where yj = log xj, and hi = log A r e s t r i c t i o n on t h i s transformation is t h a t a l l k > 0 . i A T q l o r Expansion Tranafonnation - If f(x) - and g (x) a r e continuous and differentiable, then the i - device of a Taylor expansion can be used t o approximate: and - , r h 0 where the problem is the selection of a vector of deviations Y - (2 - -x) rather than -x. This approach requiies definition of an i n i t i a l s t a r t i n g , ! point solution xo, - - but can be iterated over successively improved values .. To assume that the second and higher order terms Q indeed remain I small we can require the deviation vector = (xO - x) t o remain within prespecified l i m i t s . Separable Transformatiom If f(x) - can be written a s the sum of concave functions and gi(z) can be written a s the sum of individual convex functions: then the problem can be tackled a s separable programming [ 5 ] . I n thils case the functions f (x ) and g (x ) a r e simply evaluated over suit- j j i j j able ranges of and the linear programming problem becomes: fir-d Xj; such that Y ~ k subject t o "jk -:* 0 W where - 1 . W The y a r e partitioning variables and t h e Xj Y j k Xjk k j k X3k ' i - a r e constants which give the value of corresponding t o each point X~ - t . i n the partitioning. Separable pro@amming car. be seen t o involve Ylk m grid linearization, where the grids never have more than two dimensions. Non-SeparabZe ~rmJomation8 I f gi(x) and f (x) - - cannot be written as the sum of individual convex functions, we can still, i n principle, define a grid o r "net" of values of -x. Say each element of x is defined for - k relevant values, and f and gi a r e evaluated f o r a l l combinations of these elements. This would give kn points t o be evaluated, and the scope of the dimens:Lonality problem is evident. Such an approach might be practicable i f some form of "implicit evaluation" could be used t o r e s t r i c t the domain of the programming variables a p r i o r i , and/or sequential definition of the relevant domain and associated net could be devised. Alternatively, i f a problem is semi-separable, i n t h e senae t h a t , say, the f i r s t and second variables i n t e r a c t but the others a r e i~G~ependent, then i t might be worth defining a two-dimensional net f o r the - variables x and x i 1 2 - - '2 I4u 2 tiple Log& M c h.ansformations I Quadratic and geometric programming problems can be linearized with varying degrees of f a c i l i t y v i a a l l these techniques, but perh'aps the most d i r e c t procedure is a multiple logarithmic transformation. We use t h i s term when t h e functions i n equations (1) and (2) take the signomial form: a f(" L b o knj xj a min E O j k k A s f o r the Cobb-Douglas case, w e r e q u i r e t h a t A number of s p e c i a l algorithms have been developed f o r t h e geometric programming problem [ I ] . As -how-n here, an appropriate logarithmic trans- formation w i l l allow t h i s prcsblem t o b e approximated with any desired degree of accuracy a s a l i n e a r program. f Let us consider a t y p i c a l term: It is clear that (23) and (24) a r e linear functions of such subject t o pi(?) " 1bik tik = ki k - -11 This is a strong s u f f i c i e n t condition,'^ much weaker s u f f i c i e n t condition r e f e r s t o t h e Hessian matrix of the functions which must be p o s i t i v e semi-definite. Thus (23) and (24) nay be higher- degree polynom?als provided t h a t t h e i r ranges a r e s u i t a b l y r e s t r i c t e d . The transformation t o (26) &a2 f?? can be achieved v i a approxi- mations i n logarithms. F i r s t we have t o p a r t i t i o n t h e relevant range of t and each x i n t o an appropriate number of segments s o that i k 1 * ... t i = 0, ,m = Uikr t i k r ik r and * * where and xjs a r e parameters, and t i k r Again, these partitlonings may be viewed a s grids i n two dimensions. Now we can w r i t e * log x - * = 0; 'js 'ijk js ,IUikr log'ikr j9s r The linear programming system (26) - (31) is a transformation of :he non- l i n e a r problem (23) - (24). To economize OR the number of constrainte, (28) and (29) can be substituted i n t o (26), so t h a t t h e f u l l problem beeches (30) and (31) plus .: Each variable partitioned requires one additional "convex combination con- s t r a i n t " l i k e those i n (30). However, the approximation involved i n the partitioning9 may be made a r b i t r a r i l y close without increasihg the number of constraints i n t h e problem: t h i s is done by increasing the number of points i n the partitioning9 by enlarging the magnitude of the sets { r ) and Since the x can be replaced by tire segment variables y 1 s 1 and the by the u the transformed problem can be represented t i k r ' i n tableau format a s follows: ... Uikl ' r u ikp B :(5) = 1bok llj xj ojic k = 1bok antilog (1 aojk log x ) 1 1: 1 1 bok antilog (log tok) The critical transition from the second to the third line of (34) can be assured if we write the following expression in the linear programming vzriables "j and tok - 1 aojk log x = log t j ok 3 But given the pertitionings (28) and (29), equation (35) in fact is equivalent to (31). A similar liqe of reasoning applies to the transformations of An App Zicationtd CES "unctions Given thib logarithmic transformation approach, it should also -. be noted that we ran equally handle signo-isl funaiona of signomial + .. functions. A degenerate example is the constant-E&S ticity-of m gubstitution (CES) function, which is used often in economics: - 2/ The multiple logarithmic transformation as defined here is similar to a linearization used by Duffin in a theoreticai context [3]. where the e l a s t i c i t y of s u b s t i t u t i o n is 0 l / ( l + ~ ) , A, 6, h, P a r e parameters and K and L a r e variables. I f h < 1, t h e function is convex, and t h e multiple logarithmic - transformetion may be applied t o (36) t o incorporate it i n a l i n e a r programming model. A s before, tranaf ormations must be defined and v a r i a b l e s mus.t be partitioned: let - U 6 ~ ' - ~ (37) and Then we can write: * * -PI - (log Lt)vt - 1 (log V )B = -log ( 1 6) t 9 Q 9 * * - 1(log Tr) h Y r- 1 (1% Yu) $U = - 1% A r u with (The asterisked symbols are parameters.) If K and L are'required a s explicit variables (for use elsea where i n the model), then two more equations are added: Equations (46) - (Sl), plus (52) - (53) i f needed, a r e entered i n t o the l i n e a r program t o represent (36). This treatment may be p a r t i c u l a r l y useful f o r large-scale models which a r e otherwise l i n e a r except f o r a few equations l i k e (36). A Concludinq Note I n discussing useful transformaticns i n the context of mathema- t i c a l programming, a t t e n t i o n should a l s o be drawn t o t h e work of Cocks [2] and Hazell (41 on s t o c h a s t i c variables. Cocks provides a l i n e a r i z a t i o n i n the event t h a t t h e c o e f f i c i e n t s of a l i n e a r program follow a d i s c r e t e d i s t r i b u t i o n . Hazell has defined a l i n e a r programing transformation which e ~ t i m a t e st h e standard deviation of a d i s t r i b u t i o n , given a d i s c r e t e set of sample observations. REFERENCES [I] Avriel, M., and A.C. Williams, "An Extension of Geometric Programming with Applications in Engineering Optimization," Journal of Engineering Xathematics, Vol. 5, No. 3, 1971, pp. 187-194. [2] Cocks, K.D., "Discrete Stochastic Programming," Managen.ent Science, Vol. 15, September, 1968, pp. 72-79. (31 Duffin, R.J., "~inearizinpGeometric ~rograms,"SIAM Review, Vol. 12, No. 2, April 1970, pp. 211-227. (41 Hazell, P.B.R., "A Linear Alternative to Quadratic and Semi-variance Programming for Farm Planning under uncertainty," American Journal of Agricultural Economics, Vol. 53, 1971, pp. 53-62. [5] Miller, C., "The Simplex Method for Local Separable ~rogramming," in R.L. Graves and P. Wolfe (eds.), Recent Advances in Mathematical Programming, New York: Wiley, 1963, pp. 89-100.