NASA Technica_ Memorandum 102662

Overcoming the Bellman's "Curse of Dimensionality"

in Large Optimization Problems

Jaroslaw Sobieszczanski-Sobieski

April 1990

Nabonal Aeronautics and

Space Administration

Langley Research Center

Hampton, Virginia 23665-522:3

OVERCOMING THE BELLIVIAN'S "CUtLSE OF DIMENSIONALITY" IN LARGE

OPTIMIZATION PROBLEMS

Jaroslaw Sobieszczanski-So bieski

NASA Langley Research Center

Hampton, Virginia U.S.A.

ABSTRACT

Decomposition of large problems into a hierarchic pyramid of subproblems was proposed in the literature

as a means for optimization of engineering systems too large for "all-in-one" optimization. This decomposition was established heuristically. The paper shows that the dynamic programing (DP) method due to

Bellman when augmented with an optimum sensitivity analysis provides a mathematical basis for the above

decomposition, and overcomes the "curse of dimensionality" that limited the original formulation of DP.

Numerical examples are cited.

INTRODUCTION

Engineering optimization problems, e.g., maximization of aircraft performance, are usually computationally expensive and depend o_ the correct simulation of interaction of many parts and disciplines, Therefore

these problems are natural candidates for optimization by decomposition that converts one large problem

into a set of coordinated sm_dler problems. This paper shows that the linear decomposition method, whose

applications recently appeared in the literature, may be viewed as an extension and generalization of the wellestablished algorithm of D_amic Programing due to Bellman (ref. 1). In particular, this method alleviates

to a large extent the algorithm limitation known as "the curse of dimensionality".

DYNAMIC :?ROGRAMING AS OPTIMIZATION BY DECOMPOSITION

Dynamic Programing, originally due to Bellman (ref. 1), is perhaps the best mathematically established

method for optimization by decomposition. Briefly summarized, the method applies to a system that may

be represented by a train of the "black boxes" as in figure 1 (called the stages in ref. 1). The black boxes

are mathematical models o:_ the physical parts or conceptual aspects (engineering disciplines) of a large

problem, and they are unified by a flow of information from the n-th box through the intermediate boxes

ending with the 1-st box. _ i-th box receives an input vector Si+l from its predecessor, an input vector of

design variables X/, and outputs a vector S/ that b_omes an input to the successor box ]-l. The i-th box

also outputs a quantity/Q interpreted as a component of the objective function of the entire system. Each

{Si} must be reducible to a function of a single variable, .si, Si = f(s_), and, because 3i = f(Si+l, Ki) and

P_ = f(S_+l,Xi), it follows that Si = f(si+l,Xi), P_ = f(s_+l,Xi), and ._i = f(si+l,Xi).

The problem of finding a set of vectors -Yi, i = 1... n, that minimizes the sum of Ri, i = 1 ... n. is

solved by starting with the 1-st box at the end of the train. The variable s2 governing the input $2 is

assumed to vary within an interval of interest. Several values of s2 distributed over that interval are set and
an optimization problem, constrained or unconstrained, is solved to find {X1 } so as to minimize R1 at each

value. That solution yields {X1}opt = f(s2) and Rlmin = f(s2), either in a discrete (a look-up table) form

or in a continuous form interpolated between the al values assumed above, dependently on the nature of the

problem.

Moving up to the 2-nd box, one seeks for each of the several values of a3 in an interval of interest an

optimal {X2 } (denoted {X2 }opt) that minimizes the sum R2 + Rlmia. One must consider that s2 = f (._3, X2)

and that for each value of .s2, there are {X1}opt and Rlmia already known from the optimizations that have

been executed for box 1. This operation generates the values of {X2}opt =/(.s3) and (R2 + Rlmin)min.

The procedure continues recursively from box i to box i + 1, carrying forward {Xj }opt, and (Rj + (R j-1 +

(_1-2.-. + (R2 + Rlmin)mia)min)min...)rain, j = 1... i, through the initial box in the train, i -- n, whereby

the minimum sum of all R/'s and a complete set of {Xi}opt's gets established. The procedure rests on the

fundamental principle formulated by Bellman which asserts that the set of {Xj }, j = 1... n, is optimal when

its subset for j = 1...i taken for any i minimizes the sum of Rj, j = 1...i, for Si+l input _ven from the

remainder of the train.

The procedure computational cost heavily depends on the aforementioned assumptions of Si = f(ai)

where si is a single variable. Indeed, if ai were a vector of m elements, P_mia would grow from a line plot

into a hypersurface in m dimensions. Assuming a quadratic representation of that hypersurface (the lowest

order nonlinear approximation), the number of discrete points at which optimizations would have to be

performed would grow proportional to the square of m, thus quickly destroying advantages of the procedure

as a computational cost saver. Bellman called this the "curse of dimensionality" and regarded it as a barrier

limiting applicability of the method.

OVERCOMING THE CURSE OF DIMENSIONALITY

Optimum sensitivity analysis formulated in ref. 2 provides a means for generalization of the above

procedure to include ai defined as a vector of m elements. The optimum sensitivity analysis algorithm

yields derivatives of the optimal {X} and R with respect to the parameters of the optimization problem

(unconstrained or constrained). Taking box 1 as an example, {$2} may now be defined as {$2} = f({a2}),

where {a2} is a vector of elements S2k, k = 1... m. For {s2} given, one may find {X1}opt and minimum of

R1 and their derivatives with respect to each S2k , regarded as an optimization parameter. Using the notation

D(X1, a2k) and D(R1, S2k) for these derivatives, the linear part of the Taylor series enables one to express

{Xl}op t and Rlmm as continuous, albeit approximate, functions of {s2}:

{X1 }opt = fl({.s2}) = ({Xl }opt)o ÷ [D(X1, .S2k)lA{s2 } (1)

&mm = f({.'2}) = + (2)

The Bellman's Dynamic Programing procedure may now be executed using the above approximations

in place of {Xl}opt = f(s2) and Rlmin = f(s2), otherwise the procedure remains unchanged. The

new component in the modified procedure is the optimum sensitivity analysis to be executed after each

opt_mi_.ation involving boxes 1, (2 + 1), (3 + 2 + 1),... n, recursively. Because the linear relationships, eqs. 1

and 2, introduce errors whose control requires move limits on design variables in each optimization, the entire

procedure has to be repeated p times until satisfactory convergence is attained. In this case, the number p

depends on the nonlinearities of the problem at hand. Consequently, because there is only one optimization

in each box in one pass, the number of optimizations required to converge the procedure is pn. Ttfm is in

contrast to nmm, which is necessary for the original procedure. The curse of dimensionality with respect

to m is removed. The ratio tm/nmm = p/mm tends to be very small for large m and renders the modified

procedure usable where the original one would be prohibitively expensive.

However, unlike the original procedure, the modified procedure relies on the continuity of the approximation function in eqs. I and 2; hence, it cannot accommodate discrete design variables.
HIERARCHIC DECOMPOSITION

Further generalizationof the modified procedure ispossibleifthe boxes in the trainmay be partitioned

internallyas shown in figure2. This figureshows the boxes splitinternallyinto smaller ones. In this

scheme, the trainof boxes t_at was horizontalin figurei isdepicted verticallyto form a pyramid whose

levels correspond to the box_ in figure 1. A typical level is popuJated by several boxes that formed a single

box in figure 1. The pyramicLal arrangement emphasizes the hierarchic dependence of the boxes in level i

("children") on the information transmitted from a box located at the level above j > i ("parent"), with

the underlying assumption tb at the boxes at the same level ("siblings") do not exchange information with

each other directly. Similar tc the system shown in figure 1, the behavior information from each box flows in

figure 2 from the parent to the children, or from the top level n down to level 1. The optimization information

from each box flows in the opposite direction. This information includes the optimum sensitivity derivatives

that enable optimization in e_h parent box to be performed taking into account the effect of its {X} on the

optimization results in all boxes descendent from that parent.

Thus, the above decomposition scheme first developed heuristically in ref. 3 is shown to be a generalization

of the Bellman's Dynamic Pr_graming. The scheme became known a.s hierarchic, linear decomposition.

APPLICATION EXAMPLES

Since its introduction in ref. 3, optimization by hierarchic linear decomposition has been demonstrated

to be useful in several applicz.tions. For example, in ref. 4 it was used to develop structural optimization by

substructuring. This case is illustrated by a portal framework (figure 3a) shown decomposed in fig-_re 3b. The

procedure histogram in figure 3c exhibits satisfactory convergence characteristics. Analytical information

flowing down the pyramid consisted of the internal forces and cross-section stiffness properties as parameters

of optimization. Optimal cro;_s-sectional dimensions, minimal values of the cumulative constraints and their

sensitivity derivatives with respect to the above parameters were transmitted in the opposite direction.

An example of the procedure application to a multidisciplinary problem of optimization of a transport

aircraft for performance under constraints drawn from major contributing disciplines was described in ref. 5.

The aircraft, its decomposition scheme, and a histogram of the optimization procedure axe shown in figure 4,

a, b, and c, respectively. The case featured over 1000 design variables and constraints and demonstrated

a mathematical link from tae design detail (e.g., wing panel cross-sectional dimensions) to the system

performance (e.g., the mission fuel). The procedure convergence was smooth and rapid as seen in figure 4c.

CONCLUSIONS

It is shown that the Bellman's method for decomposition of large optimization problems known as

Dynamic Programing may b,._generalized to encompass the cases when the information transmitted between

the parts of the system is a f_mction of many variables. The key component of the modified procedure is the

derivatives of optimum with respect to the optimization parameters. Application examples illustrate and

verify the procedure.

REFERENCES

1. Bellman, R.: Adaptive Control Processes: A Gaided Tour; Princeton University Press, t961.

2. Barthelemy, J. F.; and Sobieszczanski-Sobieski, J.: Optimum Sensitivity Derivatives of Objective

Functions in Nonlinear Frograming; AIAA J, Vol. 22, No. 6, June 1983, pp. 913-915.

3. Sobieszczanski-Sobieski, J.: A Linear Decomposition Method for Large Optimization

Problems--Blueprint for Development; NASA TM 83248, February 1982.

3
4. Sobieszczanski-Sobieski, J.; James, ]3. B.; and Dovi, A. R.: Structural Optimization by Multilevel

Decomposition; AIAA J., Vol. 23, No. 11, November 1985, pp. 1775-1782.

5. Wrenn, G. A.; and Dovi, A. R.: Multilevel Decomposition Approach to the Preliminary Sizing of a

Transport Aircraft Wing; AIAA Journal of A£rcre2t, Vol. 25, No. 7, July 1988, pp. 632-638.

flow Xi .

Xl_ mlmhcrmg mlenllonally b_kw_rd

[_ Si÷l l_---q li_L_,.. -- i ._

Ri/ the last ,¢lal_,_

Fig. 1: Train of black boxes

Hierarchic, Decomposed System

i- - - _ - - - 14 system

_, L__J r least delalt

I'_ F-] '3 subsystems

_ ........ t

l i 2 sub-subsystems

,..................

most detail

Optimization

Analysis

Fig. 2: Hierarchic decomposition

OD,'imizalion

a)

b)

t _=20 i _udo4_- _

• 240 n ,_

_L,,A_- ! _ , %22P

|

, _._f'-:-=:--=-_ __.2_ _

J

, x 2 x,M

;8

a)

220 x 103 gOxlO 3

210; oCaml 80_ 0 Ca_e 1

200_ :_Case2 _ 70_N_ _3C_=_'

Bl_full 190 I_

180_ SO$0_1(_)°°

170 40 '

#,_'_ 0 2 4 G B 101214 0 2 4 G 8 101214

Fig. 4: Aircraft optimized by decomposition

o_c_e fu_ctx_n 6 _ _

3 S_n(jle level results • _terahons

3 Multilevel resullS - Cycles

Fig. 3: Portal framework optimized by

decomposition

, ,_ircraft

' perfort_ance,

b)

IY t

/i?' \

"4

• .- _<__,!

ORIGINAL PAGE IS

OF POOR QUALITY

4
NallOn_ Ae_Dr_u_s ar_

S_ace _ralc_

1. Report No.

NASA TM- 102662

4, Title and Subtitle

Overcoming the Bellman's

Fteport Documentation Page

2. Government Access=on No.

'Curse of Dimensionality" in

3. Reclpient's Catalog No.

5. Report Date

April 1990

Large Optimization Probler_s

7. Author(s)

Jaroslaw Sobieszczanski-S,)bieski

9. Performing Organization Name and Address

NASA Langley Research Center

Hampton, VA 23665

12. Sponsoring Agency Name and Address

National Aeronautics and Space

Washington, DC 20546-0001

Administration

6. Performing Organization Code

8. Performing Organization Report No.

10. Work Unit No.

505-63-01

11. Contract or Grant No.

13. Tyl_'e of Report and Period Covered

Technical Memorandum

14. Sponsoring' Agency Code

15. Supplementaw Notes

To be presented at the Second Pan American

January 2-5, 1991, Valparaiso, Chile.

Congress of Applied Mechanics,

16. Abstract

Decomposition of large problems into a hierarchic pyramid of subproblems was

proposed in the literature as a means for optimization of engineering systems too

large for "all-in-one" optimization. This decomposition was established heuristically. The paper shows that the dynamic programming (DP) method due to Bellman

was augmented with an opl:imum sensitivity analysis provides a mathematical basis

for the above decomposit-ion, and overcomes the "curse of dimensionality" that

limited the original forr_ulation of DP. Numerical examples are cited.

17. Key Words (Suggested 'by Author(s))

Decomposition

Dynamic Programing

optimization

19. SecuriW Classif. (of this report)

Unclassified

NASA FORM 1626 OCT B6

18. Distribution Statement

Unclassified - Unlimited

Subject Category 05

20. Security Classif. (of this page)

Unclassified

21. No. of pages

5

22. Price

A02