, . 5‘ L.» . flygi‘g . :.
‘KL‘K'U‘I'S’L “J. ‘1 ' “1,7,4,
4 4M - ' 1 ‘
«7"?»qu ., W km “‘51, 33;»...«0
‘ \ ~:"é“:‘§&£:§-l §mq¥¥ : 3372 {U
3.9379551.“ é;
2‘2} H‘Ififf'xé
IW -' '

Ti‘qél»

-u..pr‘

. . . . .
- ...

mug-21%
JN‘I.’ ‘-

, ‘U
abrii

‘ .

9')
-_.. £133;
n7“:

1% "
9‘ '~ ' "W.
.n ,3“ 42;}. ’3;- t
' .‘ r ‘ ‘
43 fl 5%,.“ £327; $5
. . I Anacfi‘r \w .-
‘ .14 u 4 ~ ‘

1 ‘ ,h
I :. ‘ 5:?2 "fi:
v. ' . n 8?:- d1“
‘» .mme» - w,
‘ w--.,n.','~:.;sg,‘ec,..
.0“, . H . . .1; v? 3‘, '1 .{v )6
5‘. ‘ . ‘ “ .3' ‘: . 2‘ »

13;?!“ . ‘ - ‘ ~ ’ ‘ $9,.“ 1 WW" 23"}
‘ _ . ‘V!_:‘ .41 n::n.

‘ . , - ’u‘ . . 1-“ /~ 9“ 'f 9 '8'.”

. ' ‘ fix‘ fitkwniw': ‘ i’é ' ¢

. r," ‘5’; ru'?’

ill-Jul}.

\\
1

C. ‘VI

{'“V . I"
cum, .,. w. ,.
c.5?!. .19; "if" “
“fif'fli‘rwkr‘ ‘
.....,,... ...«
.. -3323.

namtz. 0.
f &¢y.¢-l-y
4.4. Dam-r
(an;

 

 

"ll"lllllllll‘lllll' : ,

' LIBRARY
Michigan State
University |

 

 

 

This is to certify that the

thesis entitled

ON 1389944 oanmZDmON en
NON'HIEQAQCJMCAL bEcOMmsn-tw

presented by

AM 9AA

has been accepted towards fulfillment
of the requirements for

MS degree in W‘CPL Emirléeeadé

Date JULY 20; l98‘l l

0-7639 MS U is an Affirmative Action/Equal Opportunity Institution

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES reunion or heron one due.“ ' k

 

 

 

 

DATE’DUE‘ DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

L;_T_=l l

MSU Is An Affirmative Action/Equal Opportunity Institution

 

 

ON DESIGN OPTIMIZATION BY

NON-I-IIERARCHICAL DECOMPOSITION

BY

JianPan

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Mechanical Engineering
1989

@0420 M

ABSTRACT

ON DESIGN OPTIMIZATION BY

NON-HIERARCHICAL DECOMPOSITION

BY

Jian Pan

An algorithm for the optimal design of non-hierarchical systems by
decomposition is developed based on rigorous analytical results. In the algorithm, a
global problem is decomposed into smaller subproblems. The same objective and
constraints are present in all subproblems and the solution of the global problem is
obtained by solving each subproblem in sequence. The concept of pseudo optimal point
is introduced to signify the fact that a point that satisfies the optimality conditions of all
subproblems is not optimal for the global problem. A strategy to move away from
pseudo optimal points while improving the global objecfive is described. In the presence
of redundancy, the algorithm proceeds as usual after removal of all redundant
constraints in subproblem optimization. Implementation issues are discussed and

numerical examples are given for illustration.

To my parents

ACKNOWLEDGMENTS

I feel indebted to Professor Alejandro R. Diaz. His patient guidence and
illuminating discussion are crucial to the completion of the thesis. His help is beyond

academy. He has provided all the convenience for typing and printing this manuscript.

Special thanks to Professor Joseph Whitesell and Professor Mukesh V. Gandhi

for serving in my Graduating Committee and reviewing this manuscript.

I would like to express my deep thank to the Li Foundation, Inc. of New York
for providing me a two year scholarship. This work is also partially supported by the
National Science Foundation and its support is gratefully appreciated.

Last, but not the least, I would like to thank Dr. Keshun Liu for offering me his
invaluable friendship.

iv

TABLE OF CONTENTS

LIST OF FIGURES .......................................... vii
INTRODUCTION ............................................ 1
LITERATURE REVIEW ....................................... 9

2.1 Cumulative Constraint Approach in Decomposition of Hierarchical

Systems ............................................. 11
2.2 Penalty Approach in Decomposition of Hierarchical Systems ...... 14
2.3 Strategies in Decomposition of Non-hierarchical Systems ........ l6
BACKGROUND ........................................... 18
NON —HIERARCHICAL SYSTEM DECOMPOSITION ................. 22
4.1 Problem Statement .................................. 22
4.2 Derivation of the Algorithm ............................ 26
4.3 Redundancy ...................................... 35
4.4 A Procedure to Identify the Set of Redundant Constraints ........ 48
4.5 Infeasible Starting Points .............................. 50

V

vi

4.6 Convex Approximations of Non-local State Variables ........... 51
4.7 Use of Optimum Sensitivity Derivatives .................... 53
4.8 Summary of Chapter 4 ................................ 54
NUMERICAL EXAMPLES .................................... 56
5.1 Example 1 ........................................ 56
5.2 Example 2 ........................................ 59
5.3 Example 3 ........................................ 62
REMARKS AND CONCLUSIONS .............................. 70
APPENDIX ............................................... 73

BIBLIOGRAPHY. . L ....................................... 77

LIST OF FIGURES

Figure Page
1 Hierarchical system ................................. 2

2 Network system .................................... 2

3 A drive and control system for a transfer mechanism ............ 4

4 Example of solution by decomposition ..................... 6

5 Moving away from pseudo optimal point .................... 6

6 A three level hierarchical system ......................... 11
7 Coupling between subsystems of a hierarchical structure ......... 11

8 A sequential algorithm for non-hierarchical system decomposition . . .23

9 Existence of a redundant constraint ........................ 37
10 Counterexample 1: proposition 4.3.1 is not true ............... 41
11 Counterexample 2: proposition 4.3.1 is not true ............... 42
12 Iteration history for example 1: exact function ................. 58

vii

13

14

15

16

17

viii

Iteration history for example 1: convex approximations ........... 58
Iteration history for example 2: exact function ................. 62
Conicalclutch........... ........................... 65
Iteration history for example 3: exact function ................. 69

Iteration history for example 3: convex approximations ........... 69

CHAPTERI

INTRODUCTION

Decomposition in optimal design refers to a strategy whereby an optimization
problem is solved iteratively by making design changes only in a subset of the design
space at each step. The optimization problem solved in this fashion is usually called the
decomposed problem . There are several reasons why one may choose to solve the
decomposed problem, rather than the original problem in the full design space. For
example, decomposition is necessary when the solution of the problem as a whole is
cost-prohibitive or impractical due to the size of the problem, i.e., because of the large
dimension of the design space. It is important to realize, however, that size is not the
only reason why a decomposition strategy should be considered. Optimal design
decomposition also makes it possible to study systems formed by subsystems whose
analyses correspond to different engineering disciplines. In the decomposed problem,
each subsystem can be analyzed locally, using local expertise and the theoretical and
computational methods most suitable to the specific subproblem. For instance, to obtain
the optimal design of a complex engineering system, it is advisable to employ a

decomposition strategy and consider its modules (e.g., engine, suspension and

structure) separately, instead of solving the problem in the whole design space. It is this

2

feature, rather than the problem size, that motivates the present work.

literature. In non-hierarchical or network decomposition, a global system is
decomposed into smaller subsystems such that there exists information transmission
between any two subsystems. In hierarchical or multilevel decomposition, a global
problem is decomposed into a hierarchy of smaller subsystems and coupling is permitted
only between a high level subsystem and its subordinate subsystems at the lower

hierarchical level. Graphic representations of the two decomposition models are given

Two basic forms of decomposition in optimal design have been considered in the

Fig. 1 and Fig. 2.

 

Figure 1. Hierarchical system

Subsystem 1

ws indicate information
flow between subsystems

 

 

l Subsystem 2 K i Subsystem 3 I

 

Figure 2. Network system

In Fig. 1 and Fig. 2, a box represents a subsystem which defines an
optimization subproblem and its corresponding design subspace. A connection between
two boxes describes information transfer to and from the corresponding subproblems.
From the figures, it is clear that a hierarchically decomposed problem can be modelled
by a tree while the more complex non-hierarchical problem corresponds to a network. In
either decomposition strategy, optimizations are performed in subsystems and the
solution of the global problem is obtained by Combining subsystem optimal results
according to some specific decomposition algorithm. This thesis deals with one such
algorithm for the optimization of non-hierarchical systems.

The design of many engineering systems can be modelled as a non-hierarchical
optimization problem. As an example, consider the optimal design of a drive and control
system for a transfer mechanism shown schematically in Fig. 3. An automatic assembly
machine consists of two major components: a transfer mechanism to move the work to a
prescribed station, and a system to power and control the transfer mechanism. In [W1]
and [W2], a crank and connecting rod are used as a transfer mechanism, and an electric
motor driving a speed reducer via a clutch is selected to power the crank. The design of
the drive and control system as a whole and of each element can be carried out
separately. The problems are coupled, however, since clutch and speed reducer must be
such that the overall system behavior requirements are satisfied, e.g., the minimum
motor speed resulting when the clutch is engaged must be greater than the minimum
allowable motor speed, and the time required to accelerate the speed reducer input shaft
from the time of clutch engagement to normal operating speed of motor must be within
bounds. Of all the clutches and speed reducers that satisfy the drive and control system
(DC system) design requirements, we seek the detailed designs such that the DC system
possesses the minimum weight. It is apparently that optimal design of the DC system

can be naturally decomposed into three optimization subproblems:

Problem 1: overall system design
Problem 2: clutch detailed design
Problem 3: speed reducer detailed design

A mathematical model of the example will be formulated later and the problem
will be solved by the non-hierarchical optimization algorithm derived in this thesis.

 

 

 

 

 

 

 

 

r—fi
e e r
l l L SEED
“ma-
'-I E'"
CLUTCH 7 / / //

Figure 3. A drive and control system for a transfer mechanism

To illustrate some of the difficulties associated with the decomposition in optimal
design, consider the following very simple example:

Problem P:
. 2
Fmd x e R that
Minimizes f(X1,X2)= -X1-2X2
Subject to g1(x1,x7)=x2-x1SO
32(x1,x2)=x2+x1-4 $0

This problem will be decomposed into two subproblems, labeled by P1 and P2,
defined as follows:

Problem P1:
Find x1 e R1 that
Minimizes f(x1,x2°)= -x1-2x2°
501310“ t0 31(X1,X2°)=X2°'X150
82(X1’X2°)=Xz°+xr'4 $0
Problem P2:
Find x2 e R1 that
Minimizes f(x1°,x7_)= -x1°-2x2
501350“ t0 g1(x1°,x2)=x2-x1°50
32(X1°.X2)=X2+Xt°-4 s0

The solution of problem P will be obtained by solving P1 and P2 instead of P.
Several strategies to solve P1 and P2 in order to get the solution of problem P are

suggested below.

Starting from (x?,xg)=(1,0.5), suppose that P1 and P2 are solved

sequentially using as reference points x10 and x20, the solution of the previously solved
subproblem. If P1 were solved first, the procedure gets 'stuck' at (3.5,0.5) (Fig. 4). If
P2 were solved first, after a sequence P2 and P1, the process would stop at (3,1). Points
(3.5,0.5) and (3,1) satisfy the optimality conditions for both P1 and P2 but neither is
an optimal solution of P. We call these points pseudo optimal. There is an infinite
number of such points, and excluding luck, a strategy based on a straight, sequential

solution of the subproblems will get stuck at a pseudo optimal point, and fail to produce
the optimal point. Notice also that if P1 and P2 were solved simultaneously and their

answers combined, the result would be the infeasible point (3.5 ,1) ( see Fig. 4).

As illustrated above, if all subproblems are solved in sequence, the process will

get stuck at a pseudo optimal point. It is necessary to have a strategy to move away from

P1, P2
simultaneous

 

 

 

X1

‘7

Figure 5. Moving away from pseudo optimal points

pseudo optimal points. A possible strategy may be based on an intermediate step that
moves away from one of the active constraints. The search can be restarted from the
new point and continued until a new pseudo optimal point is found. When applied to

the previous example, the iteration history would look like Fig. 5.

An algorithm for the optimal design of a non-hierarchical system by
decomposition is presented in the thesis. The algorithm solves all subproblems in
sequence and includes a strategy to move away from pseudo optimal points. Clearly,
the procedure cannot compete in speed and efficiency with methods that allow arbitrary
motions in the whole design space. However, the intention here is not to increase speed
but to address problems that must be solved in their decomposed form, with limited
information. In the typical problem addressed here, the global problem consists of
subproblems corresponding to different engineering disciplines. In each subproblem,
the same objective from the global problem is minimized by a group of experts in the
particular discipline. Also, only a subset of the global design variables are allowed to
change in each subproblem, and only the local state variables can be computed exactly.
All subproblems must satisfy the same set of system behavior constraints and coupling
may exist between any two subsystems, i.e., each subproblem optimization may require
the analysis and optimization results from other subsystems. This is the standard, non-
hierarchical optimization problem discussed by Sobieszczanski—Sobieski in [$3] and
also considered in this thesis. Strategies for the solution of such problems given later

are based on previous results presented in [D1].

The thesis is organized as follows: Chapter 2 gives a literature review on the
subject of decomposition in optimal structural design. Chapter 3 presents main results
from optimization theory that are essential to the understanding of the development of

the thesis. An algorithm to solve non-hierarchical problems by decomposition is

8
discussed in Chapter 4. Numerical examples are provided in Chapter 5 to illustrate the
results derived in the thesis. Remarks and conclusions about the decomposition strategy

are included in Chapter 6.

CHAPTERZ

LITERATURE REVIEW

To solve an optimal design problem by decomposition, the problem is first
decomposed into smaller subproblems and optimizations are carried out on the
subproblems. There are several questions that should be answered in all decomposition

strategies to insure subproblem optimal results converge to the global solution:

1. How to maintain a global feasible design , at which all constraints of the
global problem are satisfied, if the reference point in subproblem optimization is globally

feasible.

2. What information can correctly represent the coupling between subproblems

and how to use this information to guide subproblem optimization to the global solution.

The cumulative constraint concept [S4] and the penalty method [HI] are two
approaches commonly used in the literatm‘e to answer the first question for hierarchical
system decomposition. The cumulative constraint is a scalar which represents the
satisfaction or violation of a set of constraints. A negative value of the cumulative
constraint means that all constraints in the set are inactive. Using the cumulative

constraint concept, each subsystem at lower hierarchical levels seeks to minimize its

10
own cumulative constraint, formed by local constraints, while the top level subsystem

minimizes the global objective keeping all subsystem cumulative constraints within

bounds.

In the penalty method approach, a penalty function for each subproblem is
constructed by adding a penalty term formed via constraint violations to the global.
objective. The penalty function is then minimized in its corresponding subsystem

optimization.

To answer the second question, one must first realize that each subsystem
optimization is performed by fixing the non-local design variables. Intuitively,
subsystem optimimtions are closely related to the sensitivity and stability analysis due to
parametric variations in nonlinear programming. Thus, optimum sensitivity derivatives
and Lagrange multiplier vectors associated with subproblem optimal solutions can be

used to represent the coupling among subsystems.

Various decomposition methods and implementations in structural design have
appeared in the literature. Much of the work on multilevel optimization is based on
exploiting specific structure of the problem. Many engineering systems can be
decomposed in the hierarchical fashion shown in Fig. 1. A three level hierarchical
system is shown in Fig. 6. At the top level, a simplified optimization model represents
the overall behavior of the system. At the lower levels, subproblems optimize detailed
representations of system components. An important property of systems of this kind is
that no coupling between subsystems at the same hierarchy level exists. A 'parent'
problem only requires information from its 'children' subproblems and from its own
'parent'. Optimization methods suited for these problems are outlined in the following

sections.

 

 

 

 

 

 

 

 

 

 

 

Figure 6. A three level hierarchical system

 

 

High level
subsystem
Results from high Lower level subsystem optimization
level subsystem results 8:. optimum sensitivity
analysis derivatives w.r.t. parameters

 

No lateral links between
subsystems at the same [3:352:11
hierarchical level _>

 

Figure 7. Coupling between subsystems of a hierarchical structure

2.1 Cumulative Constraint Approach in Decomposition of Hierarchical Systems

A linear decomposition method for optimization of hierarchical systems is
proposed by J. Sobieszczanski-Sobieski in [S4]. The coupling between subsystems at

different hierarchical levels is enforced by the transfer of optimum sensitivity derivative

12

information. As shown in Fig. 7, the analysis proceeds from top to bottom, so that
output from analysis of a higher level subsystem becomes input for analyses of the
subordinated subsystems. Since there is no information transmission across
subsystems at the same hierarchy level, the subsystems can be analyzed concurrently.
After one top-to-bottom cycle of analysis is performed, one optimization cycle proceeds
from the bottom up as described below for the three level hierarchical example shown in
Fig. 6.

In each subsystem at the bottom level, design variables are local physical
quantities and all input received from the middle level subsystem is treated as fixed
parameters. The cumulative constraint of the subsystem constraints is the objective
function. The cumulative constraint is a single number that measures the degree of
satisfaction or violation of an entire set of constraints. The Kresselrrreier—Steinhauser (K-

8) function is adopted in [84] as the cumulative constraint. It has the form:

= g-LN (20:93!»
I

where

gi ; subsystem constraint

9; user defined coefficient

A negative value of the K-S function means that all subsystem constraints 81 are

inactive.

Subsystems in the middle level have their own design variables. Again, input
from the top subsystem is considered as fixed parameters. Objective function of each
subproblem is the cumulative constraint function for a set of local constraints. In

addition, a linear approximation of the minimum values of the cumulative constraint

13
functions transmitted from the bottom level subsystems is added to the set of local

constraints.

The top level problem seeks to minimize the global system objective using a set
of top level physical quantities as design variables. The top level problem has, as
constraints, bounds on first order Taylor's expansions of the minimum values of the

cumulative constraint functions of the middle level problems.

The approach outlined above has been successful in several applications reported
in [88] and [W 3], although convergence of the procedure is not justified theoretically.
To increase the efficiency of the method, J. M. Barthelemy et al [Bl] suggest two
optimization techniques widely used in single-level optimization: constraint
approximation and temporary constraint deletion. The first technique deals with
replacing the analytical objective and constraint functions by a sequence of inexpensive
convex approximations. The second technique involves reoptimizing only those

subproblems that have violated critical or nearly critical constraints.

In the linear decomposition method described above, the minimum value of the
cumulative constraint of a subsystem is approximated using a first order Taylor's
expansion via optimum sensitivity derivatives. A. R. Parkinson et al [P2] present an
alternative strategy that uses low order polynominal approximations of the cumulative
constraint functions obtained from a least square fit of actual values at carefully selected
points in the design space. The fundamental difference between the decomposition
strategy discussed in [PZ] and in [S4] is the way in which the minimum values of the
cumulative constraints are approximated. The method has been successftu applied to

several example problems to demonstrate its usefulness.

14

2.2 Penalty Approach in Decomposition of Hierarchical Systems

The work of R. T. Hafka [1-11] is an example of a decomposition algorithm

based on a penalty function approach. The following two-level system discussed in
[Hl] illustrates the approach. Let y denote the vector of global design variables and xi,

i=1, s be the vectors of local design variables, where s is the number of

subproblems. The global problem is:

Find y and xi that

l 1' . . =
8

Objective function: f = f0(y) + Zfi(y,x i)
i

Subject to:

Global constraints: gj(y) 2 0 j=1, , m

Subsystem local constraints:

853(an I) 20 i=1, ... S j=1, ... “i
where “i is the number of local constraints for the i-th subsystem.

The solution of the global problem is obtained by a penalty approach solving a

series of problems, defined below, for fixed penalty parameters r and ri such that

r, ri -) O . This is an extended interior penalty method since the function P below is

selected to be an extended interior penalty function. The global problem becomes:

Find y and xi that

15

11...:

s m s “i
Max in) = foo) + X f it” i) +2113 j(m1 + ZZPIgiJ-(ya i).ril
i=1 j=1 i=1j=l

The above problem is decomposed into following subproblems:

8
Minimize ¢(y.r) = ¢o(y.r) + 2t,(y.r,>

[>0 i=1
"I
where ¢0(y.r) = too) + 211g J.(yinri
j=l
nl
and ¢i(y.ri)=;niglfi(y.xi)+ Pigij(y.xi).rill
i t j=l

This multilevel algorithm takes a single Newton iteration to minimize each 4) i ,

followed by a single Newton iteration to minimize (b , and then each subsystem (bi is

updated. This constitutes one iteration of the multilevel optimization algorithm.
Continuing the procedure will converge to the solution of the original problem. The
penalty approach given in [Hl] successfully exploits the additively separable form of the
objective function and the special structure of the constraints. Computational results are

given for a portal frame and show substantial time savings over a single-level approach.

In [81] L. A. Schmit Jr. solves a minimum weight design problem including
buckling constraints via a multilevel approach. He decomposes the primary problem into
a system level design minimizing total structure weight and a set of uncoupled
component level problems with component stiffness change as objective functions. A

sequentially unconstrained minimization technique based on the extended interior penalty

16
function and a modified Newton's method for unconstrained minimization are used in

this work.

In [Kl] U. Kirsch, M. Reiss and U. Shamir propose a method to solve a
structural design problem by partitioning the general optimization problem into a number

of small subproblems. The design variable vector is partitioned into a number of vectors
x 1’ x 2, x 3, . . ., x NS , where NS is the number of substructures. When optimizing a

single substructure i, only the values of the corresponding local design variables X i are
found, whereas the values of the non-local design variables are kept constant. The
optimum value of each xi is determined sequentially by an iterative process.
Optimization of a substructure is based on transforming the constrained problem into a
series of unconstrained problems using exterior penalty functions for the constraints.

The partitioning and solution strategies of the proposed approach are problem

dependent.

2.3 Strategies in Decomposition of Non-hierarchical Systems

Systems that are not amenable to hierarchical decomposition are known as
network or non-hierarchical systems. By network it is meant that a subsystem can send
output to and receive input from any other subsystem. Fig. 2 showed a network system
example. Few papers deal with problems of this nature in the design optimization
literature. In [S3] 1. Sobieszczanski-Sobieski suggests a procedure for non-hierarchical
system optimization. It includes system analysis, optimum sensitivity analysis, and
optimization carried out in design subspaces corresponding to the subsystems. A
coordination strategy is used to distribute constraint violations among the subsystems. It
is suggested that all subspace Optimizations are performed concurrently. No operational
experience with the procedure is reported.

17

Another approach proposed by A. Dfaz [D1] decomposes a non-hierarchical
system into coupled subsystems. A fuzzy set based approach is used at all levels to
model the optimization objective. The contribution of subproblem goals to the overall
system goal is modeled using set operations. While solving the subproblems, convex
approximations of non-local constraints are included, in addition to the local constraints,
to insure global feasibility. The global solution is obtained by solving each subproblem
in sequence. The success of this approach depends on the order in which the
subproblems are solved. A numerical example reported in the paper shows convergence
of the method.

The work cited above is representative of the recent literature in multilevel
optimization methods in structural design. Multilevel optimization techniques in other
fields are described by D. M. Nachane in [N1]. This is a methodological survey
emphasizing the discussion of methods most suitable for applications in other
disciplines. Early work in large-scale mathematical programming can also be found in
[G 1].

CHAPT'ER3

BACKGROUND

The derivation of a dwomposition algorithm presenwd later in Chapter 4 is based
on well-known results of nonlinear programming. Lagrange multipliers and optimum
sensitivity derivatives are two important concepts that will be used extensively in later
chapters. This chapter provides the necessary material that will facilitate understanding
of the development of the decomposition algorithm.

Given a nonlinear programming problerrr, named the primal problem, there
exists a problem that is closely associated with it, named the Lagrangian dual problem.

These two problems are given below.
Primal Problem PP
Find x e X, X c R'1 that
Minimizes f(x)
Subjectto gi(x)SO i=1, m

where f and gi are real valued scalar functions.

18

19
The Lagrangian junction of problem PP is defined as:

m
L(x,u) 5 f(x) + 2 ui gi(x)
i=1

Associawd with PP is the following problem:
Lagrangian Dual Problem DP
Find u e R”I that

Maximizes min {L(x,u): x e X}
X

Subject to u20

The ith component of u, ui, is referred to as the dual variable or Lagrange
multiplier associated with the constraint gi(x)SO.

Optimum sensitivity analysis investigates the sensitivity of the solution to an
optimization problem to variations in the problem's parameters. It yields derivatives of
the optimum values of the objective function and design variables with respect to the
parameters. We will see in the next chapter that these derivatives represent the coupling
between subsystems in system decomposition of optimal design. The following basic

sensitivity theorems from [F1] will be used extensively in the next chapter.

Consider the general problem of determining a local solution x*(e) of problem
P1(e)'

Problem 91(2):

Find xeRnthat

Minimizes f(x,e)

20

Subject to gi(x,e)SO i=1,...m
where e is a parameter vector in Rk. The Lagrangian function of Pl(e) is:

L(x,u,e) a f(x,e) + guigi(x,e)
i=1

Let x*(e) be the solution to problem P1(e) for 8 near 0 and u*(e) be the

associated Lagrange multiplier vector. Then the local optimal value function is defined as

f'(e) a f(x‘(e),e) and the optimum value Lagrangian is defined as
L'(e) = L[x"(e),u*(e),e] . Throughout the thesis, the gradient operator V is taken
with respect to design variables of an optimization problem, unless otherwise specified.

Theorem 3.1 Basic Sensitivity Theorem

If

(i) The functions defining Pl(e) are twice continuously differentiable in x and
their gradients with respect to x and the constraints are once continuously differentiable

in e in a neighborhood of (x*, 0).

(ii) The second-order sufficient conditions for a local minimum of 91(0) hold at
x*, with associated Lagrange multipliers u*.

(iii) The gradients V gi (x*,0), for i such that gi(x*,0)=0, are linearly
independent.

(iv) ui*>0 when gi(x*,0)=0, i=1, m, i.e., strict complementary slackness

holds.

Then,

21

(a) x* is a local isolated minimizing point of problem Pl(0) and the associated

Lagrange multiplier u* is unique.

(b) For 2 in a neighborhood of 0, there exists a unique, once continuously
differentiable vector function y*(e)=[x*(e), u*(e)]T satisfying the second-order
sufficient conditions for a local minimum of problem Pl(e) such that y*(0) -:-'[x*, u*] ,
and hence x*(e) is a locally unique minimum of problem 91(2) with associated unique

Lagrange multipliers u*(e).

(c) For 8 near 0, the set of binding inequalities is unchanged, strict
complementary slackness holds, and the binding constraint gradients are linearly

independent at x*(e).
Theorem 3.2 Sensitivity of the optimal value function '

It the conditions of Theorem 3.1 hold for problem for problem 91(2) , and if the
problem functions are twice continuously differentiable in (x, 8) near (x*, 0) then, in a

neighborhood of 2:0,
(3) 9(8)=L*(8)
(b) ng.(€)= VeL'(e)

m
= Vef(e) + zui(e)v,gi(e) = v, f(e) + u(e)TVeg(e)
l

CHAPTER 4

NON-HIERARCHICAL SYSTEM DECOMPOSITION

An algorithm for optimal design of non-hierarchical system by decomposition
will be developed in this chapter. Its development is based on several propositions
derived here. In order to facilitate the understanding of the organization of this chapter, a
general flow diagram of the algorithm is given in Fig. 8.

4.1 Problem Statement

Fig. 2 shows an example of the network type system optimization problem that
will be considered in this thesis. Let x E X. X C R“ , be the vector of design
variables and let 3(3) 6 Y. Y C Rr be a r-tuple vector of state variables (e.g.,
stresses, weight or displacement) to be used in the computation of objective and
constraint functions. The general optimization problem calls for finding a set of design
variables x e X. that minimizes a scalar objective function f(x,y(x)) subject to system

constraints g(x,y(x))50. Only inequality constraints are considered in the general

22

23

A DECOMPOSE THE GLOBAL PROBLEM INTop
SMALLER SUBPROBLEMS (SECTION 4. up

4

SET AN INITINAL DESIGN. .
IF THE INITINAL POINT IS INFEASIBLE, A PENALTY
FUNCTION APPROACH IS USED TO FIND A FEASIBLE
DESIGN (SEE SECTION 4.5)

l

SOLVE THE p SUBPROBLEMS IN SEQUENCE UNTIL
AN OPTIMAL OR PSEUDO OPTIMAL POINT “—1
(DEFINITION 4.2.1) 13 FOUND

l

IF IN SOME SUBPROBLEM, THE NUMBER OF ACITVE
CONSTRAINTS IS GREATER THAN THE NUMBER OF ITS
LOCAL DESIGN VARIABLES, IDENTIFY THE SET OF
REDUNDANT CONSTRAINTS (DEFINITION 4.3.3) BASED
ON A PROCEDURE IN SECTION 4.4

a. l

GLOBAL OP'I'IMALITY
w CONDITIONS SATISFIED?

lite

MOVE AWAY FROM PSEUDO OPTIMAL POINTS BASED

ON PROPOSITIONS 4.2.2 AND 4.2.3. (SECTION 4.2) _..

REMOVE ALL REDUNDANT CONSTRAINTS IF THEY EXIST
(SECTION 4.3)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figrne 8. A sequential algorithm for non-hierarchical system decomposition

24

optimization problem. With this notation, the global (not decomposed) problem has the

following form:

Global Problem P (no decomposition)
Find xe X C R“ that
Minimizes f(x,y(x)) (1.a)
Subject to g(x,y(x))50, ge Rm. (l.b)

where 8(x.y(x»={gl(x,y(x)). 32(X.y(x)). ....gm(X.y(X))lT.

Problem P is to be decomposed into several smaller subproblems. The
decomposition is accomplished by partitioning the vector of the design variables x into a
number of uncoupled vectors x1 , x2.....,xP. p is the number of subsystems. In
general, each subsystem represents a particular physical aspect of the global system and
it is prescribed to be analyzed by experts in the local engineering discipline (e.g.,
structural design, engine design).

The following features characterize the problem and are fundamental in the

construction of the solution strategy:

1. Although the decomposition is carried out on the domain X, the state Space Y
is partitioned accordingly. As the consequence of the decomposition, each subsystem
has only the knowledge necessary to compute only its local subset {yiry '2, . . - ryir‘}of

state variables y.

2. The optimization of each subsystem changes only the local design variables xi

in the design subdomain Xi CX and evaluates its own state variables. However, all

25
subsystems minimize the same global objective function f and must satisfy all of the

system constraints in g.
Summary of Problem Decomposition

i. The original vector of design variables x is partitioned into p uncoupled

vectors x1 , x2.....,xP, where xi 6 xi ; Rn' and therefore, x is the direct sum of the
xi's, i.e., x =x1$x2$ - - - O x”. Let Rn' be the usual Euclidean space of
dimension ni and Rn',Rn',...,Rn' be design subspaces of the global design space
R“ . Each design optimization in Rn‘ changes only local variables rti , and is called
the i-th subproblem optimization. Notice that a variable of x that is optimized in one

subproblem will not be a design variable in any other subproblems.

ii. The vector of state variables y(x) is decomposed into p vectors

31(3), 320‘), . .., rpm of dimensions 1'1. r2, ..., rp, respectively, where

yi(x)e Yi,YicY.

iii. The vector y i(x) can be evaluated only in the i-th subproblem and is called
the local state variable of the i-th subproblem, i=1, ..., p. One or several entries of y
may appear in the objective or in any of the constraint functions. Since y is, potentially,

a function of any of the local variables x1 , x2.....,xP, all subsystems are coupled.
iv. Each subproblem optinrization includes all constraints.
v. All subproblems seek to optimize the same objective function f.

Subproblems constructed in this way are coupled by non-local state variables
and non-local design variables. Let P1, P2, ..., PP denote the p optimization

subproblems. Define x0 a [x10 , x2°,....,xP°} where the x506 X5 ,j=l,2,...p, are

26
fixed parameters. x0 is the reference design for the problem Pi. Each subproblem has

the following form:
Problem Pi (x0)
e ’1'
Find xie x1: R that
Minimizes f(xi, y(xi))lxo (2.a)
Subject to g(xi,y(xi))ixoso, ge Rm. (2.b)

while fixing the non-local variables xi, j¢i at their respective reference values id". The

notation

f(xi, y(xi)).,o af([x1° , x20...,xi,..,xP0} , y([x1° , x20...,xi,..,xPO}))
and

g(xi,y(xi))|xo a g({x1° , x2°,..,xi,..,xP°} ,y({x1° , x20...,xi,..,xPO} ))

is used for simplicity.

4.2 Derivation of the Algorithm

An algorithm for optimal design of non-hierarchical systems by decomposition
developed in this section is based on the following propositions, derived by assunring

that.
(a) all functions can be evaluated exactly for each subproblem,

(b) the number of active constraints of each subproblem in the optimization

process is always less than that of local design variables.

27

Later, if there is a function in some subproblem depends on non-local state
variables, convex approximations will be introduced to approximate the non-local state
variables. Also, if at some point a subproblem violates assumption (b), it will be shown
later that there exist redundant constraints in the subproblem, and the propositions stated
below are still applicable to the subproblem after removal of all redundant constraints.

Proposition 4.2.1 below states that under what conditions a point x that satisfy
the Karush-Kuhn-Tucker (KKT) conditions of all subproblems Pi is also a KKT point
for the global problem P. KKT points of the subproblems that are not optimal points of
P are defined later as pseudo optimal points. Propositions 4.2.2 and 4.2.3 will provide
a strategy to move away from pseudo optimal points while improving the global

objective.
Proposition 4.2.1

Let x'=[x1‘,x2',...,xP'], where x'e X C Rn , xi'e Xi, be the vector of global

design variables. If

(i). Each It" is a KKT point for the subproblem Pi(x'), with Lagrange

multiplier vector N’-

09- Each component of I." in Pi(x"') has the same value for all subproblems,

i.e.,
11%;?- xxp‘q,’ (3)

Then the point x" is a KKT point of the global problem P with Lagrange multiplier

vector 1".

28

To prove Proposition 4.2.1, note first that at x', the stationary conditions of the
Lagrangian functions with respect to xi for Pi, i=1, p, are the same as the stationary
conditions of the Lagrangian function for P with respect to x. In addition, each Pi
includes all the constraints, the complementary slackness conditions of each Pi are the

same as the global problem P. This completes the proof.

Proposition 4.2.1 can be used to check whether a given point satisfies the global
KKT conditions. From Fig. 4 and Fig. 5, it is possible for a point x'={x1’, xz’, ...,
xP'] to be a KKT point of all subproblems and yet be a non-optimal point of P if its
associated Lagrange multipliers are not all equal. We call this point pseudo optimal.

Definition 4.2.1

A point x'={x1',x2',...,xP'} is said to be a pseudo optimal point for problem
P if

(i). Each xi‘ satisfies the KKT conditions for problem Pi(x"'), with multiplier

vector 1".

(ii). There exists an active constraint gk and a pair of problems Pi and Pi, such

i I'
that Akatkk.

The operational significance of pseudo optimal points is the following: if
subproblems Pi are solved sequentially, using as the reference point the last available
solution, the solution process is likely to stop at a pseudo optimal point before reaching
a true KKT point. At the pseudo optimal point, no further progress will be possible. A
special step must be taken to move away from the pseudo optimal point along a feasible
descent direction. The following proposition suggests a procedure to find a feasible

descent direction for f in some design subspace Xi ; Rn’.

29
Proposition 4.2.2

(i). Let x0 be a pseudo optimal point of problem P. Let N , r=1, 2, ..., p, be
the Lagrange multiplier vectors of the subproblems P‘(x°). Let f° be the value of f at

x0.
(ii). Assume that the conditions of Theorem 3.2 hold.

(iii). Select indices i, j and k, so that there exists an active constraint gk at x0 in

problems Pi and P5 with
73 ti o
It > It >
(iv). Let xi'(e) be the solution to the perturbed subproblem
Problem Pi(x°(0)) :
e e n‘
Find x‘e xl C R that
Minimizes f(xi, y(xi))|xo (4.a)
Subject to g(xi,y(xi)).,,cs - e , (4.b)
where 3 =I31r€2,...,€m I -
(v). With rti fixed at the value xi" (8), let xi' be the solution to the subproblem
Problem Pi(x°(e)) :
. e “I
Find xJe XJ C R that
Minimizes f(xi, y(xl))|xo(g) (5.a)

Subject to g(xj.y(xj))lx0(e)5 0 . (S-b)

30

where x°(e) E [x1°,x2°,..., xi*(e),..., x90}. Let f"(e) be the value of f at the solution

to problem Pj(x°(e)) in (5).

If components of the right-hand-side perturbation vector 2 of (4) are chosen by
the rule:

es={; iiff ::: fors=1,...,mande>0,

then
t‘(e) < f0

Note first that the existence of a constraint gk in condition (iii) with the desired
properties follows from the definition of pseudo optimal point and Proposition 4.2.1.
Consider now the problem Pl(x°(e)) in (5). In a neighborhood of 8=0, the solution xi"
is effectively parametized by a through xi‘(e). Applying Theorem 3.2, to Pi, we have,

df
de

 

~3g 'ag i
-31 ’__§_ .31. 1—153;
" at +11: Be -(axi kaxijae (6)

where all quantities are evaluated at 8=0. Also, since x0 is pseudo optimal, xi‘(0)

satisfies the KKT conditions for problem Pi(x°)

- a
(1"— + zx‘ i): o (7)

axi s saxi

Combining (6) and ('7), obtain

31

e )3 '
(If i ags "3!- '3x‘ _
d3 =( Elsaxi +JM‘ axi Be _

3g - . 3 ~
J l ngX' l gsax‘
=(1t-1 axtar- 2* This?) ‘8)

Sat]:

 

where the sum is over the active constraints at x0. But, from the Theorem 3.1, if gs is

active at e=0, g is identically zero in a neighborhood of 8=0. Therefore

dgs ags ags axi

 

army—xix“ <9)
andsince
_a_gs_ if
1
={0If others-wise (0)
(8), (9) and (10) canbeused to obtain
df’ 1' i 11
e ' (AK-xi) ( )

Finally, from condition (iii), we have

Q

(If
d8

 

<0

Since the solution to Pi(x°(e)) is feasible and different from x0, this implies that t‘(e) <
f0 for small positive 8. Therefore, the solution to Pl(x°(e)) is better than x0, i.e., the
procedure get 'unstuck' from the pseudo optimal point. This result can be used to move
away from pseudo optimal points.

From the previous result, at a pseudo optimal point, the combination of a

solution to Pi followed by Pi will produce a new feasible point with reduced objective

32
provided that Pi has a solution for a given value of 8. Choosing a too large may make
the feasible space of problem (4) empty. To avoid this difficulty it is convenient to

replace problem Pi(x°(0)) in (4) by the following equivalent problem:
Problem Pi(x°(0)):
n I
Find xie xi C R that
Minimizes A(xi,).°) (12.a)
Subject to gs(xi,y(xi))|xos O , s=l,2,...,m s¢k (12.b)
where A(xi,2.°) is the augmented Lagrangian function.
A(Xi.3\-°)=f(xi.)'(xi))ixo+7~° gk(xi,y(xi))ixo+ 1'2 (gk(Xi.Y(Xi))lxo)2 (12-0)

2.0 and DC are scalars. The following proposition guarantees that problem (12). is
equivalent to problem (4).

Proposition 4.2.3

i. Let x' be a unique solution to the problem:

Find x that
Minimizes f(x) (13.8)
Subject to g(x)50, ge Rm (l3.b)

with associated Lagrange multiplier vector 1'. Suppose that V90.
ii. Let x0 be a solution to the problem:

Find x that

33
Nfinimizcs A(x.>~°)= f(X) + 1° sit(x) + r2( gk(X))2 (14.a)
Subject to gs(x)SO, s=l,2,...,m; S¢=k (14.b)
where r>0 is a given scalar.
If 29>”; then
gk(x°)=-£<O

Proposition 4.2.3 states that, provided that 1° is greater that 1"}, the solutions
to (12) and (4) are equivalent. Problem (12) shifts the control on the step size fiom e to
r and avoids the possibility of making the feasible space empty by picking 8 too large.

To show equivalence of the two problems one must first realize that for r large
enough (but bounded), x* is also the minimizer of A(x,h*k). Therefore,

f(x“) + 1'1: 81:09) + 1’2( gk(X*))2 S f(X°) + a-"'It 8k(x°) + r2( gk(X°))2

(15)
Next, define the Lagrangian function L as
Lo.) ! rrrin f(x) + rzgior) + i. gk(x)
:6 G
where G a {x: gs(x) 50; s: k}.
It follows that
wasn‘t) <16)

sinceListheLagrangianassociatedwith

min f(x) + r2gi(x)
xeG

34
which has solution (rum) . Combining (15) and (16), obtain
(Lo-Lng(x°) so
Since x* is unique, (15) implies that gk(x°)¢0 and hence L°>L*k will force

gk(x°)<0, as desired.

A strategy to solve the global problem in (1) by decomposition based on the
propositions derived above can be summarized as follows: the solution of the global
problem P in (1) will be obtained by solving each subproblem of (2) in sequence. Once
a pseudo optimal point x0 of problem P is found, proposition 4.2.1 is used to check if
x0 satisfies the global KKT conditions. If not, propositions 4.2.2 and 4.2.3 suggest a
procedure such that the global objective can be further improved by sequentially solving
subproblems Pi(x°(0)) and Pj(x°(e)), defined in (12) and (5). The main steps of the
algorithm are listed as following:

Given a feasible reference point x0:

Step 1. If x0 satisfies the conditions in proposition 4.2.1, stop and output the global
optimal solution x0.

Step 2. If x° is not pseudo optimal, solve all subproblems in sequential order.
Step 3. Ifx° is pseudo optimal, identify indices i, j, and k such that

11> 11> 0
Then solve, in sequence, Pi and Pi defined by equations (12) and (5)

Step 4. Update the reference point with the latest point and restart the procedure at step
1.

35

To apply this algorithm in practical applications, we must consider the case in
which the number of active constraints of some subproblem in the optimization process
is greater than that of local design variables, i.e., assumption (b) made at the beginning
of the section does not hold. It will be shown in Section 4.3 that if this is the case, there
exist redundant constraints in the subproblem. A procedure to identify the set of
redundant constraints will be given in Section 4.4. Other implementation issues such as
infeasible starting point, evaluation of non-local functions via convex approximations,
and the use of optimum sensitivity derivatives will be discussed in Section 4.5, 4.6, and
4.7, respectively. In the last section, Section 4.8, a summary of the results derived in
this chapter will be given.

4.3 Redundancy

Proposition 4.2.1 checks the global optimality conditions, while propositions
4.2.2 and 4.2.3 are useful in the construction of a strategy that can go past pseudo
optimal points. However, they are not sufficient to guarantee convergence of the
decomposition algorithm in the presence of redundant constraints . Redundancy often
occurs in a subproblem if the number of active constraints at the solution is greater than
the number of design variables. Even if the solution to the global problem P is a regular
point of the constraints, redundancy is inevitable in the decomposed problems because
the number of constraints is the same in the global problem and in all subproblems,
regardless of the dimension of the local design subspace R”. For instance, in the
example of Fig. 4 and Fig. 5, there are two active constraints at the optimum point but
the local subspaces are only of dimension 1 (n1=n2=1). Neither in P1 nor in P2 will the
gradients of the active constraints be linearly independent at the optimum. This feature

can cause difficulties in the convergence of the algorithm used to solve the local

36
subproblems since the existence of redundancy in subproblems will not satisfy the
conditions for propositions in Section 4.2. In this case, it will be shown that proposition
4.2.2 and 4.2.3 are still true if redundant constraints are removed from Pi(x°(0)) of (4)
and PJ'(x°(e)) of (5).

Definition 4.3.1

It. . . . .
A vector as R rs a linear non-negative combination of vectors

bl’ ..., ”N where use R",ifthere exist non-negative scalars a1. ..., GIN, not all

N

ofthem zero, such that a = 2 ash s.
s=l

Let x0 Elxlo , x20.....,xP°} be a feasible reference point for the generic i-th
subproblem Pi (x0), and the notation xi" E{x1° , x20.....,xi‘,....,xP°] is used for

simplicity (see equations (2)). Let Ai = (j: gj(x i I) = O} , be the set of indices of active
constraints at x” in Pi (x0). As usual, the gradient operator V denotes the partial
3( ' )

derivatives with respect to local design variables xi, i.e., V( - ) = —a—i— .
x

Definition 4.3.2

0 O m e
Let L(x‘,h) .= f(x‘) + Zlhsgu') be the Lagrangian function of problem Pi
s=

(x0). x” is said to be a pseudo optimal irregular point or simply an irregular point of
Pi (x0) if:

(i). x” is feasible.
(ii). There is a multiplier vector at 2 o, It 6 R‘“ , such that VL(xi,i.) = 0.

(iii). xsgsori‘): o s = 1. m.

37

(iv). The vectors V g s(x i ‘) for s 6 Ai are not linearly independent in Rni.

Because of (iv), there is an infinite number of multiplier vectors associated with

X". Note that if all the vectors Vg 80‘1") for s 6 Ai were linearly independent in

R“, an irregular point would be a KKT point.

Definition 4.3.3
A constraint 8 t is a redundant constraint of Pi (x0) at xi", if
(i). St is active at X”.
(ii). xi‘ is an irregular point for Pi (x0).

(iii). V g tor”) is a linear non-negative combination of vectors Vgs(xi I) ,

where sense Ai'

An example of redundant constraint is depicted in Fig. 9.

 

 

 

 

x2 ‘ gl==0 g2=0 _ g3=0
Feasible
region
Ob' . e . . . l x
in this direction
Optimum .
- g3. redundant
I solution constraint
‘ Gradient of g2
>-
Gradient of g1 Gradient of g3 x1

Figure 9. Existence of a redundant constraint

38

The following proposition states that at an irregular point, there is a redundant
constraint . As before, Ai is the set of indices of active constraints at X”. Let K A be the

cardinality of A i . Redundancy often occurs when the number of local design variables

in Pi(x°), ni, is less than the number of active constraints. Thus, we assume ni < K A

in the following discussion.

Proposition 4.3.1

At an irregular point x” of Pi (x0), let P be the set of feasible directions for Pi

(x0) at xi",
F: [de Rn‘: ng(xi*)dso for all je Ai}.

If xi‘ is a regular point of constraints in the global problem P, and if F has at least one

non-zero element, then,
(i). There is a redundant constraint St in Pi (x0) at x”.

(ii). Removal of 8! from Pi (x0) will not change F, the set of feasible

directions for Pi (x0) at x”, i.e.,
I n' i* . .
F ={deR l:ng(x )dSOforalljeAi,j¢t}.
then F’=F.
Outline of proof:

let A = {V gj(x i"'): j e A i] , be the set of gradient vectors of active constraints

in A i , and H( A) be the convex hull of A (see Appendix). For an active constraint

39
St at x", t 6 Ai and Vgt 6 Hal.) from the definition of a convex hull. Using

Caratheodory's theorem (Appendix),
n.+l
V3,: 2 Bngs. Vgse A (17)
F1
n,+l
and ZBS=1andBSZOfors=L...,ni+1.
s=l

II
where "i isthedimensionof R '.

Case 1. Ifthere exists an index t, te Ai , such that Vgt does not appear in

the right hand side of (17).

Then V g t can be expressed as a linear non-negative combinations of elements

of A differentfrom Vgt. By definition, a, is aredundant constraint.
Case2. Forany te Ai’ Vgt appearsintherighthandsideof(l7).

Since the maximum number of linearly independent vectors in R“i is ni and

ni < KA, then there exist scalars 0J3, s=1, ni + 1, not all of them zero, such
that
n,+l
0’ Econgs=0 (13)
s=l

foranyscalar 0. Combining (17)and(l8), for any te Ai ,

 

n,+1 n,+1
Vgt = 833ng3 - 0’ 351(03ng
n,+l

= 2 (Bta-trcos)Vgs (19)
s=l

Select t 6 Ai , and O is chosen such that

E;
a)

=minimum '( szms>0}=0' (20)
t lSsS(n,+l)

(03

Note that 0 >0. By construction, for all s=1, ..., ni + 1,

BS - on), 2 O
and

BI — cart: 0
Define now

as: 3s“ oms (21)
Substituting (21) into (19),

n,+1
Vgt= sElangs (22)

where 11,20 for all S=L ..., ni+ 1 and at=0 .as needed. By definition, gt is

a redundant constraint. This proves (i).

To verify (ii), it is clear that F g F’. Conversely, for each element d t; F’.
V g td S 0 fiom (22), hence I! e F. Thus, F=F’.

41
It must be emphasized that for proposition 4.3.1 to be true, the conditions
(i). x” is a regular point of constraints in the global problem P,
(ii). F has at least one non-zero element,

must hold. Examples which violate the above two conditions are given below to show
that proposition 4.3.1 is not true.

"2 A

g2=0
Objective rmmmrzed’ ‘ '
along this direction

  
  
  
  

Gradient of g2 Feasible
reagion in global

design space

 

 

/// \ fi/ gl=0
Global optimal solution:

. non-regular point of the constraints

 

 

pxl

Figure 10. Counterexample l: proposition 4.3.1 is not true

In Fig. 10, if the two dimensional global problem is decomposed into two, one
dimensional subproblems, proposition 4.3.1 does not hold in either subproblems at the
global optimal solution. In Fig. 11 below, the feasible region of the subproblem is a
point. At this point, proposition 4.3.1 does not hold.

42

x2 A 81=° g2=O
Gradient of g3
Oblecfivcnfinimiwd Feasible setin the desi
. . . . gn
m this direction subspace is a point

i / g3=0

Gradient of gl Gradient of g2

 

 

Figure 11. Counterexample 2: proposition 4.3.1 is not true

Using the definitions of redundant constraint and pseudo optimal irregular point
we have the following proposition:

Proposition 4.3.2

At an irregular point xi" of Pi (x0), If 8 t is a redundant constraint at x”, then

(i). x" is associated with a multiplier vector 12 O . whose component

corresponding to g t, Lt, is zero.

(ii). xi‘ is either an irregular point or a KKT point for Pi (x0) without the

Comm 3 I‘

Proposition 4.3.2 states that if xi" is an irregular point of Pi (x0), it is a KKT
point with a unique Lagrange multiplier vector satisfying strict complementary slackness
condition for Pi (x0) with all redundant constraints removed. Equivalently, xi" is an
irregular point for Pi (x0) associated with a unique Lagrange multiplier vector
2. 2 0 and A. e Rm , whose components corresponding to redundant constraints are

zero, and whose components associated with non-redundant constraints are positive.

43
This unique Lagrange multiplier vector here is called the exact Lagrange multiplier vector
for Pi (x0).

With the introduction of the redundancy concept, we are now ready to expand
the definition of pseudo Optimal point (definition 4.2.1), propositions 4.2.2 and 4.2.3.

Definition 4.3.4 (with redundancy)
A point x'={x1",x2",...,xP*} is said to be a pseudo optimal point if

(i). Each x” is a KKT point or an irregular point for problem Pi(x‘), with exact
Lagrange multiplier vector 23",

(ii). There exists some non-redundant constraint g; in a pair of problems Pi

. ' i
and PJ, such that 3.; :6 11:.

In the presence of redundancy, propositions 4.2.2 and 4.2.3 will no longer be
true because the conditions of Theorem 3.1 and 3.2 do not hold. Propositions 4.3.3 and
4.3.4 derived below show that after removal of all redundant constraints in Pi(x°(0))
and PJ'(x°(e)). defined in (4) and (5), a feasible descent direction can still be found to
move away from pseudo optimal points.

In agreement with the notation in proposition 4.2.2, define x0 E { x 1° ,
x20.....,xP°] to be a pseudo optimal point for the global problem P of (1). Let Ai be the

set of indices of active constraints at x0 in subproblem Pi(x0(0)) of (4). Let R, and Ii be
twosubsetsofAi with Ai = Ri u Ii and Ri n Ii =O,definedby

Ri is the set of indices of redundant constraints of and

Ii is a set of indices of active constraints whose gradient vectors with respect to

design variables are linearly independent in the design subspace Rni.

44

Let sets Aj’ Rj and Ij for PJ'(x0(e)) in (5) be defined similarly. From proposition

4.3.2 and the definition 4.3.3, for a redundant constraint gt of Pi(x°(0)), t e R i, it

istrue that

8
—.- = a —_i’ where as 2 O (23.a)

..T: 2 a —g—., where u 20 (21b)

Proposition 4.3.3

If problem Pi(x0(0)) of (4) is solved with all redundant constraints removed,
and the right hand sides ofthe constraints are perturbed according to the rule

then, for any redundant constraint gt of Pi(x°(0)), t e Ri’

dgt
“E's-SO.

Proof

Since I e Ri’ 8 doesnot appearexplicitlyinconstraint gt.

 

45

dgt agtaxi ags axi
affififlf, “835’s:

383 axi
fife-are?) ‘2‘”

where the second equality is obtained from (23.a). From Theorem 3.1, if g is active at
8=0, gs is identically zero in a neighborhood of 8=0. Therefore

dgs_ 3gs agsa_xi_
Ema—+35% -° <25)

Since the right hand sides of the constraints are perturbed according to the rule

(26)

Combining (24), (25) and (26), we have

dgt 3gs
a: =£21a.<- as“)
=-akso

Propositions 4.3.3 states that if redundant constraints are removed from problem
Pi(x°(o)) defined by equations (4), the solutions to Pi(x°(o)) without including the
redundant constraints will not violate the redundant constraints. The next proposition

will state a similar result for problem Pj(x°(e)).
Proposition 4.3.4

If

 

45

(i). Problem Pi(x0(o)) of (4) is solved with all redundant constraints removed,
and the right hand sides of the constraints are perturbed according to the rule

(ii). At the solution of Pi(x0(0)), xi*(e), problem PJ'(x0(e)) is solved with all

redundant constraints removed.

Then, for any redundant constraint gt of Pj(x°(e)), te Rj,

dgt 0
ES .

Proof:

The solution to problem Pj(x°(e)), xj'(xi"(e)), is implicitly affected by 8
through xi‘(e), the solution to problem Pi(x°(0)). Thus,

dgt agt axi agt 3x)... 8x"
= . + . 0
dc 3,1 38 3x1 3,0" as

 

 

(27)

If gt(x°) is redundant in Pi(x°(0)). then

Emitter:

de " axi as so

from proposition 4.3.3. Otherwise,

SEE- agt
Bxi 35 --

by equations (25) and (26). Thus, in either case,

47
East; (28)
. S 0
3x‘ 35
The second term in (27) can be rewritten using (23.b) as

agt an!" axi‘ = 2 a Began.” axi"
ax’BX" 3": eel, sarr’ 3!" 33

8g 8x3. 3x"
= 2 a, S 1 (29)
£1, 8( 3x1 3X‘ 38

In Pl(x°(e)) of (5), gs is non-redundant. From Theorem 3.1, solving Pl(x°(e)) without

redundant constraints, the set of active constraints remains unchanged if e is small

enough. Thus,

 

dgs __ ags +gaxj. _

dxl - 3xi axj 3x" - (30)

Combining (29) and (30), we have

agt axj. 8x" 38 3 i‘ 38
. ., = 2‘. .——.S— " = 2 - 3 31
3x’ axl 38 sel’as( 3x1 3e: ) 9311a“ 58) ( )

 

. 3
By equations (25) and (26), if gs(x°) is redundant in P'(x°(0)), then 3%": =
Otherwise, - 95.35 5 0. Therefore, (31) becomes
3g J" i*
t 8x 8x 5 O (32)

dg
Combining (28) and (32), d—e‘ _<. o.

48

Propositions 4.3.4 states that if redundant constraints are removed from problem
Pj(x°(e)) of equations (5), the solutions to Pi(x°(e)) with all redundant constraints
removed will not violate the redundant constraints. Therefore, if there exist redundant
constraints at a pseudo optimal point x°, a procedure based on propositions 4.2.2 and
4.2.3 can still be constructed to move away from x0 while improving the global
objective provided that redundant constraints are deleted first.

4.4 A Procedure to Identify the Set of Redundant Constraints

In this section, a strategy to identify redundant constraints among the set of

active constraints is described. The following notation is adopted.

Let x°'=‘[x1° , x20.....,xP°} be an irregular point for problem Pi (x0) for
some i. Let A be the set of active constraints at x0 and let K A be the cardinality of A,

i.e., the number of active constraints at x0. Let R and I be two subset of Ai with
A= Ru I and Rh I =O,whereRis the setof redundantconsuaints andIis the set
of active constraints whose gradient vectors with respect to design variables of Pi(x°)
are linearly independent in the design subspace Rni. Redundancy often occurs when the

number of local design variables in Pi (x0), ni, is less than the number of active

constraints. Thus, we assume ni < K A. Let A be the ni x K A Jacobian matrix

associated with A. Column vectors of A are gradient vectors of active constraints in A.

The following procedure can be used to construct the subset R, and the subset I.
Procedure of identifying the set of redundant constraints:

Input: The set of active constraints A at x0 (see equations (2)).

49

Output: The set of redundant constraints R and the set of active constraints 1
whose gradient vectors with respect to design variables of Pi (x0) are linearly

independent in the design subspace Rni.

Step1. Initially,letA05A, K0=KA’ n=0 and R050.

‘1 .
Step 2. If the columns of A are linearly independent in R'“, stop. Set
R: R" and IaAn andoutputRandI.

Step3. Pickanarbitraryconstraint 3,, of An,set n=n+1.

-I
Step 4. Let A" nA" - [gs], Kn=K,H- 1. Consider the following

system of constraints,
'1
A u = V g s (33)

k
where u“ 20, u"I e R ".
If (33) has a non-trivial basic feasible solution, go to Step 5. Else, go to Step 6.
"l "l
Step5. Set R ER U gs,andgotoStep2.

Step 6. Pick an arbitrary constraint 3,, of A", set T] = 11 - l, and go to Step

To verify this procedure, note first that at each iteration, if (33) has a basic

Tl
feasible solution, then V g s is a linear non-negative combination of columns of A .

Thus, if the process terminates, the gradient of each element of the output set R is a
linear non-negative combination of gradients of elements in the output set I. R is not

empty since x0 is an irregular point for problem Pi (x0). By definition, R is the set of

50
redundant constraints. The termination criterion guarantees the gradient vectors of

elements in set I are linearly independent in R”.

Next, we need to show that the process will terminate. It is known that If
columns of Kn are not linearly independent in R“, there must be at least one redundant
constraint. Thus, there exists an active constraint 8 s of A" , such that step 4 has a non-
trivial basic solution. Since the cardinality of set A is finite, the procedure will take only
a finite number of steps.

In the next three sections, Section 4.5, 4.6 and 4.7, other implementation issues
such as infeasible starting point, evaluation of non-local functions via convex
approximations, and the use of optimum sensitivity derivatives will be discussed. A

summary of the results derived in this chapter will be given in Section 4.8.

4.5 Infeasible Starting Points

The sequential solution scheme to solve the decomposed problem requires the
computation of Lagrange multipliers to move away from pseudo optimal points. To
obtain meaningful Lagrange multipliers, it is necessary to have a feasible reference point
x°. If the initial design violates some of the constraints, one needs to find a feasible
design first. With this in mind, instead of solving each subproblem pi(x°) as defined in
equations (2), a sequence of modified subproblems MPi(x°) with augmented
Lagrangian function as objectives are solved first, in order to find a feasible design.

Problem MPi(x°):
o n‘
Find x‘e Xi ‘3 R that

l["'

51

A<xi.u) = f(xi.y(xi»

X

. + 2 (ukgk+ rkgi) (34.a)
ltsv

 

Subject to

gjtxi.y(x‘))| ,so is v (341»
X

where V is a set of indices of violated constraints and uk20 and rk>0 are positive

parameters. Notice that the objective reduces to the exterior penalty function when uk=0.

Suppose that the feasible set for the global problem P is not empty. If rk is large

enough, A(xi,ui) will be dominated by the constraint violation. A sequence of solutions
of problems MPi(x°) for i=1, ..., p will move quickly towards a feasible point. As soon
as a feasible point in found, the usual subproblem Pi(x°) as defined in equations (2) will

be solved. The use of an augmented Lagrangian function avoids the necessity of using
too large penalty parameter rk.

4.6 Convex Approximations of Non-local State Variables

The results presented above were all developed under the assumption that all
state variables in y(x) can be computed in all of the subproblems, i.e., all constraints
can be evaluated exactly for each subproblem. However, an important application of
decomposition involves precisely problems in which only some of the state variables
can be computed exactly in each of the subproblems. To deal with this kind of problem,
convex approximations of non-local state variables can be used to retain feasibility

within iterations.

52

In [D1] a strategy based on convex approximations was introduced to replace
non-local constraints in decomposed problems. Convex approximations to differentiable
functions were introduced by Stames and Haftka in [S9] and have the desirable feature
of being 'conservative' , in the sense that, if E0!) is the convex approximation of g(x),

the set g(x) S O is often (but unfortunately not always) contained in the set g(x)S0.
Because of this feature, convex approximations can be used to evaluate constraints that
depend on non-local state variables. For example, if ij is not a local state variable in
problem Pi (x0) (i.e., the means to evaluate ij exactly are not available in Pi), the
following approximation can be used instead:

ay’, ayj . .
.. IO) _. r _ lo
] (Xir X +r52(.)[axik ] X! (X: xl’

Bxi
X. X

 

 

Vi(xi;X°)= y’(X°)+ '31

r
(35)

where the (4») sum is over positive derivatives while the (-) sum is over the negative

derivatives of ij . Concave approximations reverse (+) and (-). The notation

Yifii :X 0) indicates that the approximation is defined on Xi and made with reference to

the point x°. Problem Pi(x°) in (2) would be replaced by

Problem Pi (x0) (with convex approximations)

Define x0 E [x10 , x20.....,xP°} where the x506 Xi ,j=l,2,...p are fixed

parameters. x0 is the reference design for the problem Pi. Let
ii 1' {yiryizunyir‘} bethe localarrd yjms {yxi),yj(i),.. .,y’r(2 } bethe non-

local state variables of Pi.

“I
Find xiexic R that

53

Minimizes f(xi.yi.Yj(i)) Ix. (36.a)
Subject to g(xidiJKn)”. S 0, ge Rm. (36.b)

and to the step-size constraint
Ixis - xgil S A xis, s=l,2,...ni (36.c)-

The step-size constraint is needed to prevent motion into areas where the convex
approximation is no longer valid. In practice this constraint is only needed in regions far

away from the optimal point.

In many design problems f and g are monotonic functions of the state variables.

The type of approximation used in (36) depends on whether the objective and the
constraints are increasing or decreasing functions of yjéi) . Convex approximations are
used for increasing functions of viii) while concave approximations are preferred if the

functions decrease with vi“).

4.7 Use of Optimum Sensitivity Derivatives

In problem Pi (x0) described in equations (36), the non-local state variables
y’f’ are approximated using convex approximation (see (35)). If the reference point x0

is optimal for some subproblem Pj, then the partial derivatives used in (35) can be

obtained via optimum sensitivity analysis:

54

[2:3, t:—-::l (it—if).

X X

 

8x10
Sensitivity derivatives of optimum solutions with respect to parameters ( axi J can
r

X

be, found in [F1] and [B2].

The use of optimum sensitivity derivatives is illustrated by a simple example.
Suppose that if the objective f in the problem of Fig. 4 were not an explicit function of

the local variable x1, for instance,

f(Xl.xz)=-X2

it could not be affected by optimization in the space X1=[x1}. In this case f in problem
Pl must be approximated by

f(xrxg) = f( x‘l’,x

=-x°+12. x -x°
2 2(1 1)

 

    

“g(xl-x?) =

where the sensitivity of t‘ to changes in X: in P2( X?) is used and g2 was assumed
active. Optimum sensitivity derivatives of state variables yjéi) can be computed using

formulas such as those developed in [S6].

4.8 Summary of Chapter 4

A general decomposition algorithm has been developed to solve the non-

hierarchical problem P defined by equations (1). The procedure first decomposes

55
problem P into smaller subproblems Pi(x°) of the form described by equations (2), then
solves each of the subproblems in sequence. Once a pseudo optimal point x° is found,
two subproblems Pi(x°(0)) and Pj(x°(e)), defined by (4) and (5) are selected and
solved in an order based on the relative magnitude of the Lagrange multipliers of the two
subproblems. To avoid numerical difficulties, Pi(x°(0)) in (4) is replaced by an
equivalent problem defined by equations (12) which employs an augmented Lagrangian
function. It has been proved that solutions of Pi(x°(0)) and Pj(x°(e)) in (12) and (5)
will move away from pseudo optimal point x° while improving the global objective. In
case that there exist redundant constraints in Pi(x°(0)) and/or in Pj(x°(e)), it has been
shown that solutions of Pi(x°(0)) and Pj(x°(e)) with redundant constraints removed
will still move away from pseudo optimal point x° while improving the global objective.
Strategies dealing with infeasible initial designs and the evaluation of non-local state

variables have been presented.

CHAPTERS

NUMERICAL EXAMPLES

5.1 Example 1

The following example from [HZ] (Problem 103, pg. 112) illustrates the non-
hierarchical decomposition solution procedure. The effectiveness of convex
approximations of non-local functions is demonstrated using this example. The
augmented Lagrangian function approach to find a feasible design is also tested. The
global problem P is:

Problem P: Find xe R7 that

.. -l 2 -3 0.5 -l -2 -l -0.5
f—lelx2 x4x6 x7 +15xl x2 x3x4x5 x7

-2 -l -2 2 2 -l 0.5 -2
+20x1 x2x4 xs x6+25xlx2x3 x5 x6 x7

subject to

_ 0.5 -l -2 3 -2 0.5
g1-0.5x1 x3 x6 x.7+0.7xlx2x3 xfix7

-l -0.5 2/3 1/4_
-I-O.2x2 x3x4 x6 X7 150

56

57

-().5x x—l l l —l 2

.g2=l.3xl 2 3x; x6+0.8x3x; x5 x6
+ 3.1x11xg-5 xfxglxlf — 1s 0
g3 = 2xlx'3;l'5x5xg1 X?!” + 0.1x'2'1x30‘5x5x21xf'5
+ x‘l'lxzxg°5xS + 0.65 x22x3x5x'6'1x7- l S 0
g 4 = 0.2 xizxzx;1 xgsxi/3 + 0.3x?‘5xix 3x¥3xgzl3x¥4
+ 0.4 x'1'3x32x3x5x37/44- 0.5x32x4xg‘5- 1 S 0
0.01 S xi 5 10

This problem was decomposed into the 3 subproblems:
P1: with local variables x1={x1,x2] and local functions f and g2.
P2: with local variables X2=[X3,X4} and local functions f and g1.
P3: with local variables x3={x5,x5,x7} and local functions f, g3 and g4.

At the solution of the global problem as a whole, the optimum objective value is
127. The problem was solved first assuming that all functions can be evaluated exactly
in all subproblems and then using convex approximations for the non-local functions.

The starting point is in both cases the (feasible) point
x°={4.0,0.60,2.71,8.74,1.90,196.0.01 ]

Solve P, P2 and P3 in sequence until a pseudo optimal point is found.
Propositions 4.2.2 and 4.2.3 are used to move away from pseudo optimal points.
Iteration histories are shown in Fig. 12 and Fig. 13. The horizontal axis shows which
problem subspace was used in the given iteration to find a new point. If two subspaces
are shown, it indicates that the reference point was pseudo optimal and a motion away

from an active constraint was necessary.

58

 

 

 

1362
f
132
Global solution /
127 /
I l I l l I l J I >
Starting X1 X3 X1 X3 X1 X3 X1 X1 X1 Design
Point X2 X2 X2 X2 X2 Subspace

Figure 12. Iteration history for example 1: exact function

1362

      

Global solution

127 /

142

 

 

 

i i i i i i i L i >
- x1 x1 x3 x1 x3 x1
Star'trng X3 x2 x1 x2 x3 x2 I .gn

Point Subspace

Figure 13. Iteration history for example 1: convex approximations

59

The effect of the convex approximations was not significant, even though no
step size control was used. The algorithm was also started from an infeasible reference
point and a feasible point was found using the augmented Lagrangian function in one
cycle of solution Pl-Pz-P3, both using exact and approximate functions. In both cases,
the algorithm terminates since the global objective improvement in several cycles of

solution Pl-Pz-P3 is very small.

The iteration history shows that the most significant gains are achieved in the
step away from a pseudo optimal point. This may indicate that the use of the augmented
Lagrangian function more often within iterations may prove fruitful.

The effect of redundancy was not felt. Constraints g1, g2 and g3 are all active at
the optimum point, g3 is degenerate in problems P1 and P2. A standard generalized
reduced gradient algorithm was used to solve the local subproblems.

5.2 Example 2

This example from [B4] (Alkylation problem, pg. 559-560) is used to
demonstrate the effectiveness of the non-hierarchical decomposition algorithm in the
presence of severe redundancy. It is deliberately chosen since it has 14 constraints and
only 7 design variables. At the global optimum, there are 5 active constraints.

Global problem P
Find xe R7 that

If"

60

f=1.715x1+0.035 xlx6+4.0565 x3-1-10x2
-0.063x3x5+ 3000

Subject to

g1: 0.005955 xf5+ 0.0882929 xglx
- 0.117563 x6— 15 0

3

g2= 1.1088 xlxgl + 0. 130353x1x31

- -1 2-
0.006603 x1x3 x(5 150
33: 0.000662 x§+ 0.017240 x 5- 0.005660 x4
- 0.019121x6- 15 0

_ -l -1 -1
g4 - 56.7597 x5 + 1.08702 x5 x6 + 0.32175x4x5
- 0.037620 xglxg- 1 s 0

- ' -l -l
g5-0.006198x7+ 246.23ll6x2x3 x4
- 25.1256x2x31-150
- -l -1 -1
g6--161.190x7 -l-5000.0x2x3 x7
- -l -1 -l_
489510.0x2x3 x4 x7 ISO

g7: 4.4333 x31 + 0.330xglx7- 1 s 0
g8=0.022556 x5-0.007595 x7-1SO
g9=0.000610x3- 0.0005 x1- 1 SO

glo = 0.819672 xlxg1 + 0.819672 x31 - 1 s 0
gll =24500 .0x2x31x21 - 250.0x2x31 -1 S 0

g12=0.010204 x4+ 0.000012 xalx x4 --15 0

3

61

gl3=0.0000625 x1x6+0.0000625 xl
-0.00007625 x3-ISO

gl4=l.22xilx +xII-x6-ISO

3
1.0 5x152000.0
1.0 5 x2 S 120.0
1.0 5x3 55000.0
85.0 5 x4 5 93.0
90.0 5x5595.0

305x6$120

145.0 S x7 5 162.0

The global problem is solved as a whole and the optimal value of objective
function is 1049. At the global optimum, five constraints are active, they are: g 1. g 3.

g 6’ 39. and 312 . Problem P is decomposed into 3 subproblems:

P13 with local variables x1={x1,x5] and all constraints.
P23 with local variables x2=[x2,)t4,x6} and all constraints.
P33 with local variables x3=[X3,X7} and all constraints.

Each subproblem is solved by assuming that all functions can be evaluated
exactly. Given a feasible starting point x°=[1745, 110, 3048, 89.2, 92.8, 8, 145}, P1,
P2 and P3 are solved in sequence. If there exist redundant constraints, they are identified

and the algorithm proceeds as usual with the redundant constraints removed. The

62
algorithm is successfully applied to problem P to deal with redundancy at pseudo
optimal points. A standard generalized reduced gradient method is used for optimization
within each subspace. The algorithm terminates when the global objective improvement
is very small in several cycles of solution Pl-Pz-P3. The iteration history is given in Fig.
14.

 

 

 

2126
f 1072
1049
Global solution
I 1 1 1 1 ,
Starting x1 x2 x3 x3 x2 Design
P0111! X2 X1 Subspace
Figure 14. Iteration history for example 2: exact function
5.3 Example 3

In this section, the mathematical model for optimal design of the drive and
control system described in Chapter 1 is given and the non-hierarchical optimization
algorithm is applied to solved the problem. As stated in Chapter 1, the problem consists
of three optimization subproblems:

P1: overall system design

63
P2: clutch detailed design
P3: spwd reducer detailed design
Parameters of the electric motor are data, given as follows:
Rotary moment of inertia = 0.178 slug-ft2
Average torque of motor in operating spwd range = 60 lb-ft
Minimum allowable motor speed = 151 rad/sec
Motor speed at the time of clutch engagement = 187 rad/sec
Operating speedofmotor underload = 183 rad/sec

Optimization models of the three subproblems can now be formulated using the

above information.
Design variables of pl:
x1: clutch capacity ( lb-ft)
x2: rotary moment of inertia of clutch input section ( slug-ftz)
x3: rotary moment of inertia of clutch output section ( slug~ft2 )
x4: speed reducer efficiency
x5: rotary moment of inertia of the speed reducer input section ( slug-ft2)
x5: speed ratio

Overall system behavior requirements:

64
(i). Clutch slippage time S allowable value.

(ii). Minimum motor speed resulting when clutch is engaged S minimum

allowable motor spwd.

(iii). Time required for the motor to accelerate to the normal operating speed S
allowable value.

(iv). Heat generated at the clutch face S allowable value.

Mathematical expressions of the above constraints are given below.

g1=—18]——0.25S0

B-A

187A
=——- 650
82 A-B 3

g3=—1—8-ZL-i-0.2550

(A-B)C C
g4=x1(D-E)-1000S0

where

“10:1
0.178+X2

B _ xlx4
" -2
X3+ x5+ 20.8)(5

 

C = 60X4
0.178+ x2+ x3+ x5+ 20.8ng

 

D__ 34969 A 187 )2

-———(—

E = 0.5B(—1-87—)2
B-A

65

It is decided to use a cone clutch in the drive and control system. The geometric

configuration of the cone clutch is show in Fig. 15, where 3 is chosen to be 12.50.

 

 

   
   

 

 

 

 
       

 

 

 

 

 

 

 

  

 

 

 

 

“T—

\
Inner Outer

diam diameter

'

8

a

_Y_
Figure 15. Conical clutch

Mg" Variables of P2;

x7: clutch inner radius ( ft )

x3: clutch outer radius (ft )

Clutch design requirements:

(i). Torque transmitwd by clutch S clutch capacity.
- 2 2

g5 -— Xl- 27280.7 X7(X8- X7) S 0

(ii). Geometric restrictions based on experience.

= 9.24(x8— XL) _ 0.5 S 0

(X8+ X7)

9. 24(X8- X7) 5 0
(Kg-F X7)

 

 

g7= 0.3-

(iii). Maximum shear stress of clutch S allowable value.

_ 17367.43x8x7 _ 3 2 x105

88- $0
(x§+ x%)

 

(iv). Rotary moment of inertia of clutch required in P1 equals to that computed
in 92.

89 = 7-14(X3- x-;)(xg+ x7)4 - X2 = o
810 = 7-14(X8" X7XX8+ x7)4 - x3 = O

A worm gear drive is selected as the speed reducer in the drive and control

system. The pressure angle normal to the gear teeth is chosen to be 25°.
Design variables of 93:
x9: worm pitch diameter ( ft )
x10: gear pitch diameter ( ft )
x11: gearfacewidth(ft)
x12: gear module (ft)
Design requirements for the speed reducer are:

(i). Rotary moment of inertia of speed reducer required in P1 equals to that
computed in P3.

67
g“: 19.88x3x10x6- x5 = 0

(ii). speed reducer efficiency required in P1 equals to that computed in P3.

0.91-0.0286x10xglx51
0.91+0.0286x6x9x1'01

 

812 = X4- = 0

(iii). Gear bending stress S allowable value.

g13 =1125x1xf6xf11xf21- 4.26 x105 5 0

(iv). gear contact fatigue strength requirement.

 

3.5 X10 4’ X6)
x61‘101‘11

-7.13x106S0

 

g14 = 3.7258 ><104‘[2

(v). Geometric restrictions based on experience.

F
815 X9 1.7

F
mfg-x950

where

F .___, (1524-2 X]Q)0.875

All three subproblems seek to minimize the weight (lb) of the drive and control

system.

Weight = 21.45(x2+ x3)(x3+ x7)"2 + 128.7 x5x§2+ 407.15x¥(,xl 1
+ 1836er x7)(xs+ x7)2 + 2558. 2 x3 X10X6

Bounds on design variables of the three subproblems are given as follows:

100leS1000

68

0.01szS200
0.01SX3S200
0.01 SX4S1
0.01 Sx5S200
1Sx6S400
0.015x7S2
0.01ngSZ
0.01SX9S5
0.015x10S5
0.01Sx11S1

0.01 S 2:12 51

Starting from a feasible point x°=(130.443, 0.0238, 0.0305, 0.6835, 0.01,
73.3351, 0.274, 0.3043, 0.3379, 1.6937}, Pl, P2 and P3 are solved in sequence
including all constraints in each subproblem. First, each subproblem is solved by
assuming that all functions can be computed exactly. The iteration history is shown in
Fig. 16. At the above starting point, each subproblem is also solved by assuming that
only local functions can be evaluated exactly, while non-local functions are replaced by

convex approximations. The iteration history is given in Fig. 17.

326.16 L

 

 

 

 

 

 

Weight
64.57
Global solution /
I + 4
52.1 ------------------
l l l l >
Starting X2 X3 x1 X1 Design
Point x3 X3 Subspace
Figure 16. Iteration history for example 3: exact function
326.16
Weight
65.07
Global solution /
I
52.1 - -----------------
1 1 1 1 1 1 ,
Starting X2 X3 X1 X1 X1 X1 Design
Point x3 x3 X3 X3 Subspace

Figure 17. Iteration history for example 3: convex approximations

Iml’ II

 

CHAPTER6

REMARKS AND CONCLUSIONS

The solution of a global problem P of (1) was obtained in the thesis by changing
only a subset of the global design space at each step. An algorithm to solve the
decomposed problem was developed based on rigorous analytical results. The algorithm
requires the sequential solution of all subproblems and leads to global convergence. The
concept of pseudo optimal point has been introduced to represent the fact that a point
which satisfies local optimality conditions is not necessarily the global Optimum
solution. In fact, in a non-hierarchical optimization problem, there are infinite number of
pseudo optimal points. A strategy to move away from pseudo optimal points while still
improving the global objective was discussed. It should be noted that redundancy often
occurs in the global design space decomposition if all constraints are included in each
subproblem optimization. In the presence of redundancy, the overall process proceeds
as usual after removal of all the redundant constraints in each subproblem optimization.
This is verified by the second example. Numerical experience shows that the augmented
Lagrangian function method seems to be a good choice in minimization of constraint
violations. Convex approximation of non-local state variables works well to insure the

global feasibility in the example problems.

70

71

It is observed from the numerical experience that the global objective always
achieves a large improvement when moving away from pseudo optimal points. This

phenomenon suggests that future research direction may seek to explore this feature to

speed up convergence.

It should be realized that the sensitivity theorems in Chapter 3 require that the set
of active constraints remains unchanged when the parameters vary from their initial
values. Therefore, propositions 4.2.2 will theoretically fail if the set of active constraints
changes when solving Pi(x°(0)) (see equations (4)), or Pj(x°(e)) (equations (5)).
However, numerical experience shows that the strategy based on proposition 4.2.2 to
move away from pseudo optimal points while improving the global objective is still

useful even in the case when the set of active constraints changes.

From the analytical results derived in Chapter 4, it is clear that optimum
sensitivity derivatives and Lagrange multipliers of each subsystem are essential to
represent the coupling among subsystems of a non-hierarchical problem. It is
conceivable that some interpretation of optimum sensitivity derivatives and Lagrange
multipliers of each subsystem may lead to an algorithm that allows the simultaneous
solution of all subproblerrrs, which will greatly increase the speed of non-hierarchical

system optimization.

The sequential solution of each subproblem will not be as efficient as the
solution of the global problem as a whole. Furthermore, the identification of redundant
constraints for each subproblem at a pseudo optimal point adds more computational
burden to the decomposition algorithm presented in the thesis. However, the algorithm
will show its merit in the optimization problems that must be solved in their

decomposed form. If all subproblems could be solved simultaneously, the speed of the

72
decomposition algorithm would be greatly increased. Further research is required to
realize this ultimate goal.

APPENDIX

APPENDIX

This appendix lists several standard results in optimization theory that are used
throughout the thesis, and which are not included in Chapter 3 for brevity.

Consider the general problem of determining a local solution x(e) of problem
P1(e):

Problem Pl(e):
rind x e R“ that
Minirrrizes ' f(x,e)
Subject to gi(x,e)SO i=1,...m
where e is a parameter vector in Rk. TheLagrangian function of Pl(e) is:

L(x,u,e) af(x,e) + IZn',uigi(x,e)
'--1

Theorem 1. Second-order sufficient optimality conditions for a strict local solution of
problem P‘te) [Fl]

If the functions defining problem 131(0) are twice continuously differentiable in
a neighborhood of x“, then x“ is a strict local minimizing point of problem 131(0) (i.e.,

there is a neighborhood of x“ such that there does not exist any feasible x at x * where

73

 

7.4
f(x,0) s f(x‘,0)) ifthere exist Lagrange multiplier vector u" e R‘“ such that the first

Karush-Kuhn-Tucker conditions hold, i.e.,

gi(x',0) S 0 i=1,...m
ui'gi(x',0)=0 i= 1,...m
u.'20 , i=1,...m

VL(x',u‘,0) a Vf(x"',0) + tIn.‘,u'i‘Vgi(x"',0)
i=1

and, further, if

vai L(x"',u",0)z > 0 for all 2 at 0 and 2 at 0 such that
Vgi(x*,0)z 20 for all i, where gi(x‘,0) =0

Vgi(x’,0)z =0 for all i, where tr‘i >0

An important special case of problem 91(2) is the right-hand-side perturbations
of the constraints. For this case problem Pl(e) is reduced to problem P2( 6) :

Problem P2(e):
Find it 6 RI. that
Minimims f(x)

Subject to gi(x) Se i=1,...m
where e is a parameter vector in Rk.The Lagrangian of P2(c) is defined as:

m
th.u.e> :- £00 + 231%th - e)
1:

-‘I-‘_-mrnl.~‘ ' W‘_q

75

Theorem 2. First-order changes in the optimal value function for P2( 8) [F1]

If

(i) The functions defining P2( 8) are twice continuously differentiable in x in a

neighborhood of x*.

(ii) The second-order sufficient conditions for a local minimum of P2(0) hold
at x“, with associated Lagrange multipliers u*.

(iii) The gradients V x g i (x *) (for i such that gi(x*)=0) are linearly
independent.

(iv) ui“>0 when gi(x*)=0 (i=1, m) (i.e., strict complementary slackness

holds).
then,

(a) x“ is a local isolated minimizing point of problem 19(0) and the associated
Lagrange multiplier u* is unique.

(b) For e in a neighborhood of 0, there exists a unique, once continuously
differentiable vector function y*(e)=[x*(e), u"'(e)]T satisfying the second-order
sufficient conditions for a local minimum of problem P2( 0) such that y*(0)=[x* ,
u*]=y*, and hence x*(e) is a locally unique minimum of problem P2(e) with

associated unique Lagrange multipliers u*(e).
(c) For e in a neighborhood of 0,

f‘te) = le‘te).u‘(e).e1 = L’te)

76

(d) For 8 near 0, the set of binding inequalities is unchanged, strict
complementary slackness holds, and the binding constraint gradients are linearly

independent at x*(e).

(e) For a in a neighborhood of 0 the gradient of the optimal value function is
Vaf'(e) = u’(e) .

Lets be an arbitrary set in R“. The convex hull of s, denoted by H(S), is the

collection of all convex combinations of elements of S, i.e., a vector 3 e H(S) if and

onlyifacanbeexpressedas

N
a = 2 Bsbs
s=l

N
£B=1and8820 for s=l,...,N

s=l
whereNisapositiveintegerand b1, b2, ..., bN e S.The following theorem givesan

upper bound for the integer N.
Theorem 3. Caratheodory Theorem [B3]

LetSbeanarbitrarysetin Rn.If ae H(S),thenacanbeexpressedas

n+1
a= 23:”:

s=l

n+1

where Elfl=land 5320 for s=l, ..., n+ land bl’ b2...,bn+le S.

BIBLIOGRAPHY

 

BIBLIOGRAPHY

[Bl] Barthelemy, J. M. and Riley, M.F., "Improved Multilevel Optimization Approach
for the Design of complex Engineering Systems," AIAA J., Vol. 26, No. 3, March
1988, pp. 353-360.

[B2] Barthelemy, J. M. and Sobieszczanski-Sobieski, 1., "Optimum Sensitivity
Derivatives of Objective Functions in Nonlinear programming," AIAA J., Vol. 21, No.
6, June 1983, pp913-915.

[B3] Bazaraa, M.S. and Shetty, C.M., "Nonlinear Programming, Theory and
Algorithms,” John Wiley and Sons, 1979.

[B4] Beightler, C. S. and Phillips, D. T., "Applied Geometric Programming," John
Wiley and Sons, 1976.

[D1] Diaz. A. R., ”Fuzzy Set Applications in Engineering Optimization. Multilevel
Fuzzy Optimization," in Second NASA/Air Force Symposium On Recent Experiences
in Multidisciplinary Analysis and Optimization. Langley Research Center, Hampton,
Virginia, September 28-30, 1988.

[F1] Fiacco, A.V., "Introduction to Sensitivity and Stability Analysis in Nonlinear
Programming," Academic Press, New York, 1983.

[G1] Geoffrion, A. M., "Elements of Large-scale Mathematical Programming," Part I
and II, Management Science, Vol. 16, No. 11, July, 1970, pp652-691.

77

78

[HI] Haftka, R. T., "An Improved Computational Approach for Multilevel Optimum
Design," J. Struct. Mechanics, Vol 12(2), 1984, pp. 245-261.

[HZ] Hock, W. and Schittkowski, K., "Test Examples for Nonlinear Programming
Codes," Springer Verlag, New York, 1981.

[Kl] Kirsch, U., Reiss, M. and Shamir, U., "Optimum Design by Partitioning into
Substructures," J. of Structure Division, ASCE, Jan. 1972, pp. 249-267.

[Ll] Lasdon, L. S., "Duality and Decomposition in Mathematical Programming," IEEE
Transactions on System and Cybernetics, Vol. SSC-4, No. 2, July 1968, pp. 86-100.

[M1] Minoux, M., "Mathematical Programming Theory and Algorithms," John Wiley
and Sons, 1986.

[N1] Nachane, D. M., "Optimization Methods in Multilevel System: A Methodological
Survey," European Journal of Operational Research, 21(1984), pp25-38.

[P1] Padula, S.L. and Sobieszczanski-Sobieski, J., "A Computer Simulator for
Development of Engineering System Design Methodologies," ICED 87, Boston, MA,
August 1987.

[P2] Parkinson, A., Balling, R., Wu, A. and Free, J. , "A General Strategy for
Decomposing Large Design Problems Based on Optimization and Statistical Test Plans,"
ICED 87, Boston, MA, August 1987.

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

79

[SI] Schmit Jr., L.A. and Ramanathan, R.K., "Multilevel Approach to Minimum
Weight Design including Bucking Constraints," AIAA J., Vol. 16, No. 2, Feb. 1978,
pp97-104.

[S2] Schrijver, A., "Theory of Linear and Integer Programming," John Wiley and
Sons, 1986.

[S3] Sobieszczanski-Sobieski, J. , "Optinrization by Decomposition: A Step from
Hierarchic to Non-Hierarchic Systems", in Second NASA/Air Force Symposium On
Recent Experiences in Multidisciplinary Analysis and Optimization. Langley Research
Center, Hampton, Virginia, September 28-30, 1988.

[S4] Sobieszczanski-Sobieski, J., "A linear Decomposition Method for Large
Optimization Problems- Blueprint for Development," NASA TM-83248, 1982.

[SS] Sobieszczanski-Sobieski, J ., "Sensitivity Analysis and Multidisciplinary
Optimization for Aircraft Design: Recent Advances and Results," 16th Congress of the
Intn'l Council of the Aeronautical Sciences, Jerusalem, Israel, 1988.

[S6] Sobieszczanski-Sobieski, J., "On the Sensitivity of Complex, Internally Coupled
Systems," AIAA Paper 88-2378, AIAA/ASME/AHS 29th Structures, Structural
Dynamics and Materials Conference, Williamsburg, VA, April 18-20, 1988.

[S7] Sobieszczanski-Sobieski, J., Bloebaum, C.L. and Hajela, P., "Sensitivity of
Control-Augmented Structure Obtained by a System Decomposition Method," AIAA
Paper 88-2205, AIAA/ASME/AHS 29th Structures, Structural Dynamics and Materials
Conference, Williamsburg, VA, April 18-20, 1988.

[S8] Sobieszczanski-Sobieski, J., James, BB. and Riley, M.F., "Structural Sizing by
Generalized, Multilevel Optimization, AIAA J. Vol. 25, No. 1, January 1987, pp. 139.

80

[S9] Spotts, M.F., "Design of Machine Elements," 6th Edition, Prentice-Hall, Inc.,
Englewood Cliffs, New Jersey, 1985.

[810] Stames, J.H. and Haftka, R.T., "Preliminary Design of Composite Wings for
Buckling, Strength, and Displacement Constraints," J. Aircraft, 16(8), 1979, pp. 564-
570.

[W1] West, P. and Noon, W. D. , "Determine the'Operating Characteristics of a Drive
and Control System for a Transfer Mechanism," General Motors Engineering Journal,
Oct-Nov.-Dec., 1957.

[W2] West, P. and Noon, W. D., "Solution to the Previous Problem: Determine the
Operating Characteristics of a Drive and Control System for a Transfer Mechanism,"
General Motors Engineering Journal, Jan.-Feb.-Mar., 1958.

[W3] Wrenn, GA. and Dovi, A.R., "Multilevel Decomposition Approach to the
Preliminary Sizing of a Transport Aircraft.Wing," AIAA/ASME/ASCE/AHS 28th
Structures, Dynamics, and Materials Conference, Monterey, Cal., April 6-8, 1987,
AIAA Paper No.87-0714-CP.

 

1.. 1 .. I .
Elia‘i‘iu'd‘fi':

nrcnran STATE UNIV. LIBRARIES
“HIWWWWNWINIIHIIHmllllHllllllllWWl
31293006279610