5th Conference on Optimization Techniques Part I [1 ed.] 3540065830, 9783540065838 [PDF]

Zitiervorschau

Editorial Board D. Gries • P. Brinch Hansen • C. Moter • G. Seegmfiller • N. Wirth

Prof. Dr. R. Conti Istituto di Matematica "Ulisse Dini" Universit5 di Firenze Viale Morgagni 67/A 1-50134 Firenze/Italia Prof. Dr. Antonio Ruberti Istituto di Automatica Universit5 di Roma Via Eudossiana 18 1-00184 Roma/Italia

AMS Subject Classifications (1970): 49-02, 49A40, 49B20, 49B35, 49B40, 49C05, 49DXX, 65K05, 68A25, 68A45, 90-02, 90C05, 90C20, 90C30, 90C50, 90C99, 90D05, 90D25, 93-02, 93B05, 93B10, 93B20, 93B30, 93B35, 93C20, 93E05, 93E20

49C10, 90C10, 90D99, 93B99,

ISBN 3-540-06583-0 Springer-Verlag Berlin , Heidelberg ' New York ISBN 0-387-06583-0 Springer-Verlag New York • Heidelberg - Berlin This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks, Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, tt~e amount o(the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin. Heidelberg i973. Library of Congress Catalog Card Number 73-20818. Printed in Germany. Offsetprinting and bookbinding: Julius Beltz, Hemsbach/Bergstr.

PREFACE

T h e s e P r o c e e d i n g s a r e b a s e d on the p a p e r s p r e s e n t e d at the 5th I F I P C o n f e r e n c e on O p t i m i z a t i o n T e c h n i q u e s h e l d in R o m e , l~Iay 7-11, 1973. T h e C o n f e r e n c e w a s s p o n s o r e d by the I F I P T e c h n i c a l C o m m i t t e e on O p t i m i z a t i o n ( T C - 7 ) and by the C o n s i g l i o N a z i o n a l e d e l l e R i c e r c h e (Italian N a t i o n a l R e s e a r c h

Council). The

Conference

was

and their application Major

emphasis

including:

devoted

to recent advances

to modelling,

identification

of the Conference

Environmental

An interesting

was

Systems,

feature

recent application

Soeio-economic

Systems,

was

Proceedings

the papers

in which

are divided

the methodological

those dealing with various The R. Conti,

International A. Ruberti

W. J. Karplus L. S. Pontryagin

Previously

(USA),

application

Program

J. L. Lions

optimization

aspects

Systems.

of specialists

engineering.

In the first are collected

are emphasized;

in the second

areas. of the Conference

Fe de Veubeke

(France),

E. Rofman

of systems

volumes.

Committee

(Italy) Chairmen,

(USSR),

published

into two

areas,

Biological

the participation

both in control theory and in the field of application The

techniques

and control of large systems.

on the most

of the Conference

in optimization

G. Marehuk

(Argentina),

consisted

(Belgium), (USSR),

of:

E. Goto (Japan), C. Oleeh

J. Stoer (FRG),

(Poland),

J.H. Westcott

(UK).

conferences:

Colloquium

on Methods of Optimization. (Lecture Notes in Mathematics,

Held in Novosibirsk/USSR, Vol. 112)

Symposium

on Optimization. Held in Nice, June 1969. (Lecture Notes in Mathematics, Vol. 132)

Computing

Methods in Optimization Problems. (Lecture Notes in Operation Research

June

1968.

Held in San Remo, September and Mathematical Economics,

1968. Vol. 14)

TABLE OF CONTENTS

SYSTEM

MODELLING

AND

IDENTIFICATION

I d e n t i f i c a t i o n of S y s t e m s S u b j e c t t o R a n d o m State D i s t u r b a n c e A. V. B a l a k r i s h n a n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

A d a p t i v e C o m p a r t i m e n t a l S t r u c t u r e s in B i o l o g y and S o c i e t y R. R. M o h l e r , W. D. S m i t h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

On the O p t i m a l Size of S y s t e m Model M. Z. Dajani .................................................

33

Information-theoretic Methods for Modelling and Analysing Large Systems R. E. Rink ...................................................

37

A New

Criterion for Modelling Systems L. W. Taylor, Jr .............................................

46

Stochastic Extension and Functional Restrictions of Ill-posed Estimation Problems E. Mosca ...................................................

57

Regression Operator Application to Some A. Szymanski

69

in Infinite Dimensional Vector Spaces and Its Identification Problems ...............................................

An Approach to Identification and Optimization in Quality Control W. Runggaldier, G.R. Jacur ................................... On Optimal Estimation Y. A. Rosanov ~

and Innovation

Processes

Identification de Domaines J. C e a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

T h e M o d e l l i n g of E d i b l e Oil F a t M i x t u r e s J. O. G r a y , J . A . A i n s l e y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

DISTRIBUTED

83

92 103

SYSTEMS

F r e e B o u n d a r y P r o b l e m s and I m p u l s e C o n t r o l J. L. L i o n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

116

A C o n v e x P r o g r a m m i n g Method in H i l b e r t S p a c e and Its A p p l i c a t i o n s to O p t i m a l C o n t r o l of S y s t e m s D e s c r i b e d by P a r a b o l i c E q u a t i o n s K. M a l a n o w s k i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

124

~ p a p e r not r e c e i v e d

VI

About

Some Free C. Baiocchi

Boundary Problems Connected with Hydraulics .................................................

I 37

M4thode de D4composition Appliqu~e au Contr61e Optimal de Systbmes Distribu4s A. Bensoussan, R. Glowinski, J.L. Lions .......................

14 !

Approximation of Optimal Control Problems of Systems Described by Boundary-value Mixed Problems of Dirichlet-Neumann Type P. Colli Franzone ............................................

] 52

Control

GAME

of Parabolic P. K. C. Wang

Systems with Boundary Conditions Involving ................................................

Time-Delays ] 65

THEORY

Characterization of Cones of Functions Isomorphic to Cones of Convex Functions J. -P. Aubin .................................................

174

Necessary Conditions and Sufficient Conditions for Pareto Optimality in a Multicriterion Perturbed System J. -L. Goffin, A. Haurie .......................................

] 84

A Unified Theory Differential Games C. Marchal

194

About

PATTERN

of Deterministic

Two-Players

Zero-Sum

..................................................

Optimality of Time of Pursuit M. S. Nikol'skii ...............................................

202

RECOGNITION

Algebraic Automata E. Astesiano,

and Optimal Solutions in Pattern Recognition G. Costa ........................................

A New Feature Selection Procedure for Pattern Recognition Based Supervised Learning J. Kittler .................................................... On Recognition Descriptions S. T y s z k o

A Classification G. Walch

of High ~

Deformed

Patterns

by Means

206 on 218

of Multilevel

...................................................

Problem in Medical Radioscintigraphy ......................................................

The Dynamic Clusters Method and Optimization in Non-Hierarchical Clustering E. Diday .....................................................

~paper not received

250

241

Vll

OPTIMAL

CONTROL

A Maximum Principle for General Constrained Optimal Control Problems - An Epsilon Technique Approach J . W. M e r s k y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

259

O p t i m a l C o n t r o l of S y s t e m s G o v e r n e d b y V a r i a t i o n a l I n e q u a l i t i e s J. P . Y v o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

265

O n D e t e r m i n i n g t h e S u b m a n i f o l d s of S t a t e S p a c e W h e r e t h e O p t i m a l Value Surface Has an Infinite Derivative H. L. S t a l f o r d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

276

C o n t r o l of A f f i n e S y s t e m s w i t h M e m o r y M. C. D e l f o u r , S . K . M i t t e r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

292

C o m p u t a t i o n a l M e t h o d s in H i l b e r t S p a c e f o r O p t i m a l C o n t r o l P r o b l e m s with Delays A. P . W i e r z b i c k i , A . H a t k o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

304

S u f f i c i e n t C o n d i t i o n s of O p t i m a l i t y f o r C o n t i n g e n t E q u a t i o n s V. I. B l a g o d a t s k i h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

319

V a r i a t i o n a l A p p r o x i m a t i o n s of S o m e O p t i m a l C o n t r o l P r o b l e m s T. Z o l e z z i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

329

Norm P e r t u r b a t i o n o:[ S u p r e m u m Problems J. Baranger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

333

O n T w o Conjectures about the Closed-Loop Time-Optimal Control P. Brunovsk~ ................................................

341

C o u p l i n g of S t a t e V a r i a b l e s in t h e O p t i m a l L o w T h r u s t O r b i t a l Transfer Problem R. H e n r i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

345

O p t i m i z a t i o n of t h e A m m o n i a O x i d a t i o n P r o c e s s U s e d i n t h e M a n u f a c t u r e of N i t r i c A c i d P. U r o n e n , E. K i u k a a n n i e m i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

360

STOCHASTIC

CONTROL

S t o c h a s t i c C o n t r o l w i t h a t M o s t D e n u m e r a b l e N u m b e r of C o r r e c t i o n s J. Z a b c z y k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

370

D e s i g n of O p t i m a l I n c o m p l e t e S t a t e F e e d b a c k C o n t r o l l e r s f o r L a r g e Linear Constant Systems W.J. Naeije, P. Valk, O.H. Bosgra ............................

375

C o n t r o l of a N o n L i n e a r S t o c h a s t i c B o u n d a r y V a l u e P r o b l e m J. P . K e r n e v e z , J. P . Q u a d r a t , M. V i o t . . . . . . . . . . . . . . . . . . . . . . . . .

389

An A l g o r i t h m to E s t i m a t e S u b - O p t i m a l P r e s e n t V a l u e s f o r U n i c h a i n Markov Processes with Alternative Reward Structures S. D a s G u p t a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

399

VIII MATHEMATICAL Some Penalty

PROGRAMMING

Recent Developments in Nonlinear Programming G. Zoutendijk ................................................

407

Methods and Augmented Lagrangians in Nonlinear Programming R. T. Rockafellar .............................................

4t8

On INF-Compaet Mathematical Programs R. J. -B. Wets ................................................ Nonconvex Quadratic Programs, Integer Linear Programs F. Giannessi, E. Tomasin

Linear

Complementarity

Problems,

426 and 437

.....................................

A Widely Convergent Minimization Algorithm with Quadratic Termination Property G. Treccani .................................................

450

A Heuristic Approach E. Biondi, P.C.

460

A New

to Combinatorial Optimization Problems Palermo ......................................

Solution for the General L. B. Kov~cs

Set Covering

Problem 471

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A Theoretical Prediction of the Input-Output Table E. Klafszky .................................................. An

484

Improved Algorithm for Pseudo-Boolean Programming S.Walukiewicz, L. SZomifiski, M. Faner .........................

493

Numerical Algorithms for Global Extremum Search J. Evtushenko ................................................

NUMERICAL

505

METHODS

Generalized Sequential Gradient-Restoration to Problems with Bounded Control, Bounded Rate of the State A. Miele, J.N. Damoulakis ~

Algorith with Applications State, and Bounded Time-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Gradient Techniques for Computation of Stationary Points E. K. Blum ...................................................

509

Parameterization and Graphic Aid in Gradient Methods J. -P. Peltier .................................................

517

Les Algorithmes de Coordination dans la M~thode Mixte d'Optimisation Deux Niveaux G. Grateloup, A° Titli, T. Lef~vre ..............................

~paper

not received

& 526

IX

Applications of Decomposition and Multi-Level Techniques to the Optimization of Distributed Parameter Systems Ph. Cambon, L. Le Letty .....................................

538

Attempt to Solve a Combinatorial of Extension-Reduction E. Spedicato, G. Tagliabue

554

Problem

in the Continuum

by a Method

....................................

Contents

of Part

(Lecture

Notes

URBAN Some

AND

in Computer

SOCIETY

Science,

Vol.

4)

SYSTEMS

Aspects of Urban Systems of Relevance to Optimization Techniques D. Bayliss ..................................................

Selection of Optimal S. Czamanski Optimal An

II

Industrial Clusters for Regional Development ................................................

Investment S. Giulianelli,

9

Policies in Transportation Networks A. La Bella .....................................

On-Line Optimization Procedure C. J. Macleod, A. J. AI-Khalili

for an Urban Traffic System .................................

Hierarchical Strategies for the On-Line Control of Urban Road Signals M. G. Singh ..................................................

I

22 31

Traffic

Application of Optimization Approach to the Problem of Land Use Plan Design K. C. Sinha, A. J. Hartmann ....................................

42

60

Some Optimization Problems in the Analysis of Urban and Municipal Systems E. J. Beltrami ~ ................................................ Combinatorial Optimization and Preference Pattern Aggregation J. M. Blin, A. B. Whinston ......................................

73

A Microsimulation Model of the Health Care System in the United States: The Role of the Physician Services Sector D. E. Yett, L. Drabek, M.D. Intriligator, L.J. Kimbell ............

85

COMPUTER

AND

COMMUNICATION

NETWORKS

A Model for F i n i t e Storage M e s s a g e Switching Networks F" B o r g o n o v o , L. F r a t t a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

On C o n s t r a i n e d D i a m e t e r and M e d i u m O p t i m a l Spanning T r e e s F. Maffioli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

110

S i m u l a t i o n T e c h n i q u e s f o r the Study of M o d u l a t e d C o m m u n i c a t i o n Channels J. K. Skwirzynski .............................................

118

~ p a p e r not r e c e i v e d

XII

Gestion Optimale Virtuelle E. Gelenbe,

d'un Ordinateur D. Potier,

Multiprogramme

A. Brandwajn,

~ M@moire

J. Lenfant

................

State-Space Approach in Problem-Solving Optimization A. S. Vincentelli, M. Somalvico ................................

132 144

SYSTEMS

ENVIRONMENTAL Perturbation Theory G. I. Marchuk

and the Statement of Inverse Problems ...............................................

159

A Model for the Evaluation of Alternative Policies for Atmospheric Pollutant Source Emissions R. Aguilar, L. F. G. de Cevallos, P. G. de Cos, F. G6mez-Pallete, G. Martfnez Sanchez .........................................

167

Mathematical Modelling of a Nordic Hydrological System, and the Use of a Simplified Run-Off Model in the Stochastic Optimal Control of a Hydroelectrical Power System M. Fjeld, S. L. Meyer, S. Aam ................................

179

A Two-Dimensional C. Chignoli,

203

Model for the Lagoon of Venice R. Rabagliati ....................................

Sea Level Prediction Models for Venice A. Artegiani, A. Giommoni, A. Goldmann, P. Sguazzero, A. Tomasin .................................................

213

Optimal Estuary Control Theory W. Hullett

222

Aeration:

An Application

of Distributed

Parameter

..................................................

Interactive Simulation Program for Water Flood Routing Systems F. Greco, L. Panattoni ....................................... An

Automatic River Planning E. Martino, B. Simeone,

Operating System (ARPOS) T. Toffoli ............................

On the Optimal Control on an Infinite Planning Horizon of Consumption, Pollution, Population, and Natural Resource Use A. Haurie, M.P. Polls, P. Yansouni ...........................

ECONOMIC Limited

231 241

251

MODELS

Role of Entropy in Information Economics J. Marschak .................................................

On a Dual Control Approach to the Pricing Policies of a Trading Specialist M. Aoki .....................................................

264

272

XIII

Problems of Optimal Investments with Finite Lifetime Capital B. Nicoletti, L. Mariani ...................................... Some

Economic Models M. J. H. Mogridge

Utilization of Heuristics J. Christoffersen,

283

of Markets ............................................

295

in Manufacturing Planning and Optimization P. Falster, E. Suonsivu, B. Sv~irdson ..........

303

Economic Simulation of a Small Chemical Plant G. Burgess, G. L. Wells ....................................... An

313

Optimal Growth Model for the Hungarian National Economy I. Ligeti .....................................................

BIOLOGICAL

324

SYSTEMS

On Optimization of Health Care Systems J. If. Milsum ................................................ Theoretical and Operational the Circulatory System B. Abbiati, R. Fumero

Problems

in Driving

, F. M. Monteveechi,

a Physical C. Parrella

335

Model

of

..........

347

Modelling, Simulation, Identification and Optimal Control of Large Biochemical Systems J. P. Kernevez ..............................................

3S7

Mod@lisation du Transfert Gazeux Pulmonaire et Caleul Automatique de la Capacit@ de Diffusion D. Silvie, H. Robin~ C. Boulenguez .............................

366

A Model for the Generation of the Muscle Force During Saccadie Eye Movements A. Cerutti, F. Peterlongo, R. Sehmid ~ ......................... On Some Models of the Muscle Spindle C. Badi, G. Borgonovo, L. Divieti

paper

not received

.............................

378

IDENTIFICATION OF SYSTEMS SUBJECT TO ~OM STATE DISTURBANCE by A.V. Balakrishnan Department of System Science University of California, Los Angeles* ABSTRACT A theory of identification of a class of linear systems --lumped and distributed -in the presence of state or process noise. As a specific application~the problem of of identifying aircraft stability -- control derivatives in turbulence is considered, and results obtained on actual flight data are included. INTRODUCTION The conscious use of mathematical models in system optimization has been growing rapidly in recent years. Perhaps the most spectacular exan~le is the "world model" of Forrester [i]. If it is assumed that a model, before it can be used to predict the future, must first be verified on currently available data, then we are faced with the problem of "system identification" -- of estimating unknown parameters in the model based on obserw~d data. There is a large engineering literature (see [2]) on the subject of system identification and parameter estimation; much of it is however, in the nature of a collection of techniques with little or no precise mathematical framework. Often the authors make ad hoc simplifications for the avowed reason that the otherwise the mathematics involved is too complex. Whereas such a point of view may be harmless when theory plays a secondary role, as in the design of a physical system which can and is finally tested in the laboratory before the design is finalized, the situation is quite different in the identification problem where the end result is a set of numbers and we have really no means of being certain of their accuracy. Surely this would argue for extreme care in the mathematical formulation and analysis, and make the identification problem basically a mathematical and computational one. In this paper we study the problem of identifying a linear system with time continuous description (rather than the discrete-time as in the bulk of the engineering literature), and furthermore taking into account unknown inputs (modelled as random state disturbance), usually omitted for reasons of mathematical complexity. Such a formulation turns out to be actually necessary in the practical problem of estimating afrcraft parameters from flight data in turbulence, see [3]. More specifically, we can state the problem as follows: The observation y(t;~), (in the usual notation, ~ denotes the "sample point" corresponding to the random process) has the form: y(t;~) = s(t;~) + n!(t;~)

(i.i)

where nl(t;~) is the unaw~idable measurement errors modelled as a white Gaussian process (as a reasonable idealization of a band-limited process of band-width large compared to that of the process s(t;~)). The system is assumed to be linear in its response to the (known) input u(t), and to the unknown ("state") disturbance, assumed to be a physically realizable Gaussian process, and hence we can write: t t s(t;~) = ~ o B(t-S) u(s)ds + ~ o F(t-s) n2(s;~)ds

(1.2)

Research supported in part under Grant No. 73-2492, Applied Mathematics Division, AFOSR U.S. Air Force.

where F(.) is determined from the spectral density of the disturbance process. We have omitted initial conditions, as we may, since we shall assume that the system is stable, that in fact: ilB(t) lj + llF(t) ll = 0(exp -kt),

k > 0

(i.3)

and allow for long observation time (only asymptotic properties of estimates are considered). We may also assume that the measurement noise in (i.I) is independent of the disturbance. The identification problem is that of estimating unknown parameters in the functions B(.), and F(.), from the observation y(s,~), 0 s s S T, and the given known input u(s), 0 s s ~ T. Both nl(t,e) and n2(t,~) are white Gaussian with unit spectral density (matrix), and are independent of each other. It should be noted that instrument errors such as calibration error, bias error, timedelays etc., in the observation y(t;~) are supposed to be known and corrected for. Although seemingly simple, this formulation we hasten to point out, includes all known identification (and control) problems for linear systems. For example, the most commonly stated version: ½(t) = A x(t) + B u(t) + F nl(t;~)

(1.4)

y(t) = C x(t) + n2(t;~)

(1.5)

is obviously of this form; in fact we readily see that: F(t) = C e At F B(t) = C e At B and that (1.3) is satisfied if A is stable. The main simplification occurring in this example is of course that fact that the Laplace transforms of F(.) and B(.) are rational. In particular, (1.4) and (1.5) represent a "lumped parameter system," governed by ordinary differential equations. Our model includes also "distributed parameter" systems, governed by partial differential equations. For example, let G be a region in three-space dimensions with boundary F. Then we may consider a structure of the form (we omit the details): 8f = ~ a ~--~

$2f ij ~x i ~x. + n(t,.,~) 3

(1.6)

f(t,~) on F = u(t,.) y(t) = C f(t,.) + nl(t,~)

(1.7)

where C is a linear transformation with finite dimensional range. "Solving" (1.6), we see that (1.7) can again be expressed in the terms (i.i), (1.2). What is important to note is that the formulation (i.I), (1.2) requires only the specification (within unknown parameters) of the functions B(.) and F(.). Yet another example is one in which the state space is finite dimensional but the state noise does not have a rational spectrum. A practical instance of this is the problem of identifying aircraft parameters in turbulence characterized by the Von Karman spectrum. In other words, the Laplace transform of B(.) is rational, but: 2 I o

e2~ift F(t)dt

f4 k (a+f2) 17/6

Although we shall not go into it here, we wish to note that it is also possible to formulate stochastic control problems in terms of (i.i), (1.2). Thus we may seek to minimize T fE[Qs(t;m), o

s(t;~)] dt

subject to constraints on the control n(t), which is required to be adapted to the observation process y(t,~). See [4] for more on this. Estimation Theory Let @ denote the vector of unknown parameters that we need to identify. We shall assume that there is a true value go (in^other words, no "model" error), and that it lies in a known interval, I(0). Let e T denote an estimate of 0o based on y(s), 0 ~ s s T. We shall be interested only in estimates with the following two properties: (i) (ii)

asymptotically unbiased: consistent:

E(~T) + 0o

@T converges in a suitable sense to O ° as T + infinity

We shall show that it is possible to find an estimate with these properties by invoking the classical method of "maximum likelihood." For this we can proceed along one of two [essentially equivalent, as we shall show] points of view concerning the noise process nl(t;~). In the first (the Ito or Wiener process point of view), we write (i.i) in the integrated version: t Y(t;~) = I s(o;~)d~ + Wl(t;e) (2.1) Jo where Wl(t;~) is a Wiener process on C(0,T), the Banach space of continuous functions on [O,T]. Then for each fixed @ (assuming or "given" 0) the process Y(t;~), 0 ~ t ! T with sample functions in C[0,T], induces a measure thereon which is absolutely continuous wit~ respect to the Wiener measure (induced by Wl(t,e)). Moreover we can then calculate the corresponding Radon-Nikodym derivative, which is then our "likelihood" functional, denoted p(Y;O;T), and the maximum likelihood estimate 0T is the value of @ which yields the maximum in 1.0 (or, actually in a subinterval). The ca$culation of the derivative p(Y;O;T) can be accomplished by one of two ways. The first method is to use the Krein factorization technique (see his monograph [5]). Thus let tL re(t;8) = 2, B(t-s) u(s)ds (2.2) % 2

and let R(@;t;s) = E[(s(t;~) - m(t))(s(s; 0 dot representing derivatives. have:

This is probably stronger than we need.

Then we

Theorem Under conditions (1.3) and (3.1), there exist linear transformations B, F, mapping Ep and Em into ~ such that t

X(t ;0~) =

/

T(t-S)(m U(S)~-FD n(s ;~)I as

Jo

-

(3.2)

i

being the generalized solution of : x(t;W) = A x(t;w) + B u(t) + FD n(t;~)

(3.3)

where A is the operator with: domain of A = [fEJ~,

f absolutely continuous and derivative f ' ~ . ~ ] ,

Af = f' and T(t) is the semigroup generated by A. can be expressed:

Moreover (1.2), or equivalently (2o14),

y(t;~) = C x(t;~) + G n(t;~)

(3.4)

where C is a linear bounded transformation mapping j ~ i n t o

E n.

Here B can be taken

as: B u ~ (-L) ~

B(s+nL)u

,

ueE P

O F w ~ (-L)

~

F(s+ne)w

o where L is

a fixed

positive Ch =

gi

,

wEE

m

number, and then C is defined L

by:

/ o h(s)ds ' hg~%o

Proof Although the genesis of this representation was by a long and tedious route, it can be verified quite quickly. First of all, the conditions (1.3) and (3.1) yield the convergence in the norm of ~Y{ of both series: B(s+nL)u

and

o

~ o

Next, it is immediately verified that CT(t)B = B(t)u,

t >- 0

CT(t)F w = F(t)w, t >_ 0

#(s+nL)w

The interested reader will find it useful to rewrite (3.3) as a nonhomogeneous first order partial differential equation. Note that the state space we have obtained need have no relation to the original state space, if any. The state space we have obtained is reduced, and the controllable part coincides with the controllable part of the original state space. See [9]. The controllable part is finite dimensional if and only if the Laplace transforms or B(.) and F(.) are rational. Using this representation, we shall next provide a (constructive, "real-time") characterization of (~. In fact, formally, the final results can be written exactly as in the case where the state space is finite dimensional. The proofs however will be quite different. First let us fix @, and let t y(t;~) = y(t;~) -re(t;0); x(t;~) = x(t;~) - fT(t-s)Bu(s)ds Note first of all that

t

x(t;~) =

fT(t-s)

FD n(s;m)ds

(3.5)

and hence E(]l~(t;~)ll

2) < =

0!

t ST

0-
~ . favorable or unfavorable to the growth of x I.

is

The only parameter to 3be d~termined

is dlj, the "depth of modulation," which will be seen to be related to the transmission.

We may remark in passing that, if (Hf i ) is considered to he a composite

control variable, the dynamic system is of the

J bilinear type, a class whose

excellent controllability and performance qualities have been analyzed elsewhere [3,4,5]. Consider the difference equation y(t+l) = y(t) + y(t)[a+n(t)]

d [i + ~ Sgn(x(t) - x)].

(3)

41

This is equivalent to the equation z(t+l) ~ y(t+l) y(t) " - 1 = a[l + ..n(t) ...a

] [i + ~d

Sgn(x(t) - x)].

(4)

This transformation would correspond, in an actual identification process, to taking the data {y(t)}, forming the ratios of successive values, and subtracting unity. The precise relationship between T(x,z') and d depends on the statistics of x(t) and n(t).

If the data {x} come from a stationary process, the "normal" value

could be taken as that value which is exceeded by one-half the data. equivalent to assuming that Sgn(x(t)-x) is binary with probabilities regardless of the distribution of x(t) itself.

This is

(1/2, 1/2),

Also, in many cases of large scale

systems (e.g. socio-economic) the fluctuations n(t) represent the aggregate decision noise of a collection of individuals, hence will tend to be normally distributed. Under these particular assumptions, a Monte Carlo simulation was used to deterA mine the transmission T(x,z') for various values of c and d, where c/2 is the standard deviation of n(t)/a. tors and z' computed.

Values of x and n were generated by random number genera-

The simulated "data" {x} and {z} were then scaled and sorted

into L=I6 quantum intervals and the entropies calculated from the frequency estimates of probability. The resulting transmission values are plotted in Figure i, as functions of d/2 with c/2 as parameter.

Clearly, the transmission value alone is not enough to de-

termine d if c is also ~known, as would usually be the case with real data. The residual entropy H(z'Ix ) provides the entra information that is needed, ^

and it is plotted in Figure 2.

If the measured entropy (e.g. H(z'Ix ) = 1.85 nats)

is drawn as a horizontal line on Figure 2. the intersections of that line with the parametric family provide several pairs of values (c/2, d/2) which, when transferred to Figure i, can be fitted to a curve as shown.

The intersection of this curve with

the horizontal line corresponding to the measured value of transmission (e.g.

^

T = .563) gives the values of c/2 and d/2 (e.g. c/2=0.25 and d/2=0.435). For the multivariable case where, for example, the interactions of (sl-rl) variables {xi.} with x I are to be modelled by equations of the form of (i) and (2), the data can 3be transformed as above to yield {Zl}.

If the standard deviations of

m I and n I are known, the corresponding curves of Figure i can be used directly to find the value of dlj/2 for each measured net transmission T(xi. , Xl'). J If, on the other hand, the standard deviation of nl, say, is unknown, but it is known that ml=O and that all interactions are of the type flj rather than glj" then Figures i and 2 can be used together to estimate the dlj/2 values.

(This case

may occur, for example, in socio-economic systems where birth rates and capital generation rates result from individual decisions and have, in the aggregate, both causal and random fluctuations, whereas death rates and depreciation rates do not.) The procedure involves simply taking the interactions one by one, treating the other

42

0.7" T(x,z')

0.6

/

0.5

\ \ I

0.]

0.4

0.3

0.2

0.i

0

-----+ 0.I

figure i.

~{(z'

~

0.2

1

0.3

i

0.4

0 ~.6

0.5

t

0,7

0.8

d/2

Transmission as a function of d/2, with c/2 as parameter.

I~)~

2.2

2.0

i. 8 =

3

c~0

4

0.1

1.6

1.4

1.2

1.0

d/2 0

figure 2.

Residual Entropy as a function of d/2, with c/2 as parameter

43

factors as a resultant, normally-distributed "noise ~ factor (a+nl)j~k ~ flj (xij) 5 (a+~Ik) with residual entropy ^

^

^

H(Zl'IXik) = H(zI') - T(Xik, Zl). Here nlk has a complicated expansion in terms of n I and the functions

dlj 2

Sgn (xi.

- ~i),

j ¢ k,

3 3 and the only justification for treating it as having a normal distribution lies in the tendency toward normality for functions of many stochastic variables, i.e. the law of large numbers. In the more general case where both types of interactions flj and glj are known to exist and the standard deviations of n i and m.l are unknown, more general procedures than those developed here will be needed. Information and Perform~ance Quite apart from the parametric type of model discussed in the last section, there are some direct inferences that can be made about the potential performance of a large system, based on the transmission diagram.

This is possible because

there is, in any feedback control system, an intimate relationship between the amount of information available to the controller and the error performance of the system.

In fact, it can he shown [6] that if the error entropy is taken as the

measure of performance for a linear system, the reduction in error entropy achieved by feedback control is bounded by the information available to the controller. Each state variable in a large system may be imagined to have a local controller which is receiving information about the values of certain other variables over separate communication channels,

corresponding to those paths in the

transmission diagram which impinge on the state variable in question.

These chan-

nels represent a certain composite channel capacity ("information-gathering capacity" would be a more descriptive term) that is available to the local controller. This composite local information capacity is not, however~ simply the sum of the impinging transmission rates.

The latter must be smaller than capacity if the

channel reliability is to be adequate.

Although Shannon's Coding Theorem shows

that error-free transmission can be achieved at rates approaching the channel capacity, this can only be achieved at the expense of increasingly long time-delays for encoding and decoding the data, and arbitrarily long delays cannot be tolerated in real-time control.

On the other hand, the total transmission rate will not be un-

necessarily small, either, since control effectiveness increases with the amount of reliable data that is used. and capacity.

Thus, there is some optimal transmission between zero

44

It has been shown [7] that, if the plant and controller are linear and certain other conditions are met, the optimal feedback transmission rate R satisfied the equation 2R = nE(R), where n is the number of state variables being transmitted and E(R) is the channel reliability function. capacity~

This equation always has a unique solution between zero and

Conversely~ if the transmission rate and n are known, the channel capa-

city can be found as C(R,n). Thus, the composite local capacity C 1 available for the control of state variable x I can be estimated by calculating the total net transmission rate sl-r I R1=¥

Z

T(xi.,x l'Ixil ...... x.

, x .....

x.

)

j=l 3 /j-i lj+l ISl-r 1 where T is the sampling (coding) time interval, and then calculating C 1 = C(Kl,Sl-rl)The total information capacity in the system is then n C:ZC.. t i=l

1

Consider now the potential performance of the system in the extreme case where the total information-gathering capacity C t is centralized, i.e. where all ~'local control" of state variables is replaced by a centralized controller which has the objective of optimizing a single performance index for the system as a whole. If that performance index is the mean square state error and if the inherent "plant" mechanisms of the system are linear (not an unreasonable assumption for many socio-economic processes like population, capital, etc., as mentioned previously), then the optimum form of control law is linear state feedback and the separation theorem applies,

in this case it can be shown [7,8] that the total mean

square state error (m.s.e.) is bounded by E[ 11x(t)-Xoptimumil 2 ] ! N2 (T) i~2~i (T).=

~+nF,(Cnt',CTt)' r )

e 2 (T)

(5)

where the summation gives the m.s.e, due to estimation error, i.e. limited information, and e2(T) is the m. Soe. resulting from the controller's limitations alone. N2(T) is the mean square state disturbance that would be caused by the exogenous noise acting on the uncontrolled system over the sample interval T and y(T) is the square of the largest eigenvalue of the state transition matrix of the uncontrolled system.

The %i(T) are the squares of the largest eigenvalues of matrices ~i which

govern the estimation-induced state error dynamics according to the expression Ax(t) =

~ ~i[x(t-iT) - x(t-iT)], i=2

where x(t-iT) is the real-time controller's estimate of the state vector of time (t-iT),

The function F is defined by

45

F(n,Ct,T) = (2A+k) exp [-2R~ CtT/n] where A is an algebraic function of n, Ct, and T~ k is a parameter between zero and one which measures the relative entropy power of the exogenous noise source compared to that of a white Gaussian source, and Rt* is the solution of the equation 2Rt* = nE(Rt* ). Several important conclusions can be drawn from the bound (5). For given state dimension n and controller gain matrix, the m.s.e, is a function of only Ct, the total information capacity, and T, the sampling-codlng time.

There exists the

possibility of information instability if i - y(T)'F(n,Ct,T) is not greater than zero.

In particular, if llm T+0 [2A(n'Ct'T) + k] > i,

then T must be greater than zero for the system to be informationally stable [8]. This result differs from the case of ordinary sampled-data control, where only e2(T) is present in the m.s.e, and the optimum sampling interval T is always zero. Thus, for given n,Ct, and optimum central controller, there exists a Top t ~ 0 which minimizes the bound (5). The relationship between these minimum values and Ct provides the link between the potential performance of a large-scale system and its transmission diagram.

REFERENCES l,

Watanabe, S., IRE Transactions on Information Theory, PGIT-4, 84 (1954).

2.

Conant, R., "Detecting Subsystems of a Complex System, '~ IEEE Transactions o_~n Systems, Man, and Cybernetics, pp. 550-553, (1972).

3.

Rink, R. E. and R. R. Mohler, "Completely Controllable Bilinear Systems," SIAM Journal on Control, Vol. 6, 477-487 (1968).

4.

Mohler, R. R. and R. E. Rink, "Control with a Multipllcative Mode, ~' Journal of Basic EngineerlnE, Vol. 91, 201-206 (1968).

5.

Mohler, R. R., Bilinear Control Processes, with Application t__ooEngineering, Ecology, @nd Medicine, Academic Press, N.Y. (1973).

6.

Wiedemann, H. L., "Entropy Analysis of Feedback Control Systems," in Advances in Control Systems, C. T. Leondes, Ed., Academic Press, N.Y., Vol. 7 (1969).

7.

Rink, R. E., "Optimal Utilization of Fixed-Capacity Channels in Feedback Control," Automatica, Vol. 9, 251-255 (March 1973).

8.

Rink, R. E., "Coded-Data Control of Linear Systems," (to be published).

A NEW CRITERION FOR MODELING SYSTEMS By Lawrence W. Taylor~ Jr. NASA Langley Research Center Hampton~ Virginia

The problem of modeling systems continues to receive considerable attention because of its importance and because of the difficulties involved. A wealth of information has accumulated in the technical literature on the subject of systems identification and parameter estimation; references i through 5 are offered as s~mmaries. The problem that has received most attention is one in which the form of the system dynamics is known 3 input and noisy output data are available~ and only the values of the unknown model parameters are sought which optimize a likelihood function or the mean-square response error. It would seem with the variety of estin~tes~ the aigorithms~ the error bounds~ and the convergence proofs~ and the numerical examples that exist for these systems identification problems, that any difficulties in obtaining accurate estimates of the unknown parameter values should be a thing of the past. Unfortunately~ difficulties continue to confront the analyst. Perhaps the most important reason for difficulties in modeling systems is that we do not know the form of the system dynamics. Consequently, the analyst must try a number of candidate forms and obtain estimates for each. He is then confronted with the problem of choosing one of them with little or no basis on which to base his selection. It is tempting to use a model with many parameters since it will fit the measured response error best. Unfortunately, it is often the case that a simpler model would be better for predicting the system's response because the fewer number of unknown parameters could be estimated with greater accuracy. It is this problem of the analyst that this paper addresses and offers a criterion which can be used to select the best candidate model. Specifically~ a numerical example will be used to illustrate the notions expressed in references 4~ 6, and 7.

SYSTEMB IDENTIFICATION

WITH MODEL FORMAT KNOWN

The systems identification problem of determining the parameters of a linear, constant-coefficient model will he considered for several types of estimates. It will be shown that maximum-likelihood estimates can be identical to those which minimize the mean-square response error. The subject algorithm~ therefore, can be used to obtain a variety of similar estimates. Attention is also given to the calculation of the gradient that is involved in the algorithm and to the Cramer-Rao bound which indicates the variance of the estimates. Problem Statement The problem considered is that of determining the values of certain model parameters which are best with regard to a particular criterion, if the input and noisy measurements of the response of a linear, constant-coefficient system are given. The system to be identified is defined b y t h e following equations: i = Ax + Bu

y = Fx + Fu + b

z = y + n

where x, u, y~ b, n~ z are the state, control, calculated response, bias, noise 3 and measured response, respectively. The unknown parameters will form a vector c. The matrices A, B, F, and G and the vectors b and x(O) are functions of c. Minimum Response Error Estimate One criterion that is often used in systems identification is the mean-squ~re difference between the measured response and that given by the model. A cost function which is proportional to the mean-square error can be written as

47

N

(zi - Yi)~Dl(zi " Yi)

J : [ i=l

where D 1 is a weighting matrix and a time integral. The estimate of c

i is a time index. is then

The summation approximates

c=ARG c

where

ARG MIN

means that vector

c

which minimizes the cost function

Linearize the calculated response vector c

y

H.

with respect to the unknown parameter

Yi = Yi 0 + VcYi(C - CO) where of y

Yio is the nominal response calculated by using Co~ Vcy i with respect to c~ and c O is the nominal c vector.

Substituting Yi into the expression for which minimizes J yields

J

is the gradient

and solving for the value of

c

If this relationship is applied iteratively to update the calculated nominal response and its gradient with respect to the unknown parameter vector~ the minimumresponse error estimate ~ will result. The method has been called quasilinearization and modified Newton-Raphson. The latter seems more appropriate since the Newton-Raphson (ref. l) method would give

Ck+ 1 = ck +

J

cJ

where N

VcJk : -2 Z

(VcYik)~Dl(zi - Yik )

i=l N

N

Vc2Jk = 2 ~ (VcYik)TDiVcYik - 2 ~ (Vc2yik)TDl(Zi_ Yik ) i=l i=l The second term of Vc2Jk diminishes as the response error (z i - Yik) diminishes. The modified Newton-Raphson method is identical to quasi-linearization if the term is neglected. Maximum Conditional Likelihood Estimate Another criterion that is often used is to select of the measured response when c is given

: ARG MAX{P(zlc)} e

c

to maximize the likelihood

48

where -i

P(zlc)

=

~

(~)N(I~)/21MIIN/2

exP I" g

i=l

(zi " yi)TMI

(zi " Yi

The maximum conditional likelihood estimate of the unknown parameters will be the set of values of c which maximize P(zlc)~ if it is recognized that y is a function of c. If it is noted that the max_imization of P ~ I c ) occurs for the value of c which minimizes the exponent~ the maximum conditional likelihood estimate is the ~ same as that which minimizes the mean-square response error provided the weighting matrix D 1 equals Ml'l. Maximum Unconditional Likelihood (Bayesian) Estimate The unconditional probability density function of

z

can be expressed as

P(z) = P(zlelP(e) The probability of c relates to the a priori information available for before use is made of the measurements z. The unconditional probability of

z

c

is then N

1

exp~

P z) : ( )[( =) mC )l/21mlNl2LM21112

T

-1

~ (zi-Yl) M1 (zi'Yi)

7 i=l

. !2(~ - °o)~M2"i(° " c°~ Again~ the expression is maximized by minimizing the exponent. gradient with respect to c equal to zero and solving yields ^ ^ ck+l = Ck +

T -I ( ~ Y i k > M1 VCYik + M2"

%i:l -

M

Setting the

-1 (vcTyikl~M1

(z i - Yik)

:i

2 -lt^ ~ek - c0 )I

An identical estimate would have resulted if a weighted sum of mean-square response error and the mean-square difference of c and its a priori value are minimized~ provided the weighting matrices used equaled the appropriate inverse error covariance matrices. Consequently, the same algorithm can be used for both estimates

a = ~a ~ i ~ l (zi - Yi)~-i (zi-Yi) +(c- Co)~M2-1(c- co Variance of the Estimates A very important aspect of systems identification is the quality of the estimates. Since the estimates themselves can be considered to be random numbers~ it

49

is useful to consider their variance~ or specifically their error covariance matrix. The Cramer-Rao bound (ref. l) provides an estimate of the error covarlance matrix.

E~-

Ctrue)(~-Ctrue)~

= ~, (VcYi)TMl-~cYi + M 2=I

If the a priori information is not used#

M2 -1

will be the null m t r i x .

Importance of Testin6 Results The importance of testing a model once estimates of the unknown parameters have been made~ cannot be overemphasized. The test can be to predict response measurements not included as part of the data used in obtaining the model parameters. If the fit errorj J, is greater for this test than for a similar test using a model with fewer unknown parameters, it would indicate that the data base is insufficient for the more ccmplicated model. The testing should be repeated and the number of model parameters reduced until the fit error for the test is greater for a simpler model. The testing procedure should be used even if the model format is "known" since the data base can easily lack the quantity and the quality for estimating all of the model parameters with sufficient accuracy. Reference 4 provides an example of a model which failed a test of predicting the system's response. Figure 1 shows how the fit error varied for both the data used to determine the model parameters and that of the test~ versus the number of model parameters. The lo~er curve shows that as additional unknown parameters are included, the fit error decreases. When the models were tested by predicting independent response measurements ~ however~ the upper curve shows the models having more tmknownparameters performed more poorly than simpler models. Fortunately, more data were available but had not been used in the interest of reducing the computational effort. When four times the data were used to determine the parameters of the same models~ the results shown in figure 2 were more successful. The fit error for the predicted response tests continued to decrease as the number of unknown model parameters increased~ thereby validating the more ccmplicated models. Unless such tests are performed~ the analyst is not assured of the validity of his model. Unfortunately~ reserving part of the data for testing is costly. A means of making such tests without requiring independent data is discussed in a later section of the paper.

SY~

IDENTIFICATION WITH MODEL FORMAT UNKNOWN

One never knows in an absolute sense what the model format is of any physical system because it is impossible to obtain complete isolation. Even if the model format was known with certainty, it is necessary to test one's results against a simpler model~ a point made in an earlier section. Regardless of the causej the requirement is the same: a number of candidate models must be compared on a basis which reflects the performance of each in achieving the modelts intended use. For the purpose of this discussion~ it will be assumed that the model's intended use is to predict the response of a system and that a meaningful measure of the model's performance is a weighted mean-square error. A Criterion for Com~arin6 Candidate Models Let us continue the discussion of the problem stated earlier using the same notation. The weighted mean-squ~re response error w h i c h ~ s minimized by the minimum response error estimate was

50

N

J = L (z i - yi)TDl(Zi - yi ) i=l Let us denote the weighted mean-square response error which corresponds to testing the model's performance in predicting the system's response as N

= ~

(zli - yi)TDl(zli - yi )

i=l where z I is measured response data that is not part of z which is used to determine the model parameters. For canvenience, we cansider the inputj uj to be identical in both eases. The criterion suggested for comparing candidate models is the expected value of j1. If it is possible to express the expected value~ E{J1}~ in terms not involving actual data for zl~ then a considerable saving in data can be made and improved estimates will result from being able to use all available data for estimating. Let us examine first the expected value of the fit error with respect to the data used to determine estimates of the unknown parameters. We can express the response error as z

Y = Ytrue + n - y ~ Ytrue + n - Ytrue - c-VY(~ - Ctrue) = n - V y ( c^ - Ctrue )

assuming the response can be !inearized with respect to the model parameters over the range in which they are in error. The expected value of the fit error,

= Ei

E{JI} , becomes

" Yl)%l(zi - Yl

= E~ ~n-

(VcYi)(~-

Ctrue)~TDl~n - (VcYi)(~ - ctl~le

~i=l Expanding we get

:

_

=l

+ E

Dl(VeYi)(o

-

~i=l

(a T

Ctrue)(VcYi) Dl(VcYi)(c - ctr u

5i If a maximum likelihood estimate is used, or if 'the minimum mean-square response error estimate is used with a weighting equal to the measurement error covariauce matrix 3 then we can write D I = M -I

= Ctrue +

=l

J [%=1

J

Again, linearization is assumed and it is noted that zi - Ytrue i = n i After substituting we get

E{J}=E(7.niTM-ini ) _2EpTQ-) where N

i=l N

i=l Next, let us examine e~ected fit error E{J} of a model used to predict response measurements, zl, which are independent of the data z, used to determine the estimates of the model. We can again express the expected fit error as

E(~)

= E(i=~1 nliTDlnli~ -2E~i=~ 1 nliTDiVcYi( ~ _ Ctrue~

+ E~I=~1 (~T_ cTru~(VcYi)TD1VcYi(~. Ctrue~ Note that the onl~v difference between the above expression and that obtained earlier for E{J} is that the noise vector is nI instead of n. The same expression can be used for ~ as before since it is the estimate of c based on the data, z, that is desired.

52

~ = Ctrue +|i=~l

(VcYi)TM-1VcY

(VcYi)TM-ln

Substituting the above expression for @j and M-I for Di we get

-

~E

nliTM-iVcYi Q-I i=~l(VCYi)TM-Inj

M

~i=l + E o tel qua

;

16~ I = [~ + ~ )

lorsqu'il

n'y

apas

TI(~,~] 2

o

A Q de c o n t r a i n t e ,

la

= o. (3.3)'

et

[3.4)

on d ~ m o n t r e

la

PROPOSITION 3.1 : Q est un point critique d e ~ s i

[3.7] Naturellement

et seulement si

G£{x)

< o

V x68

Go[x]

> o

V x~

on a l a

Si £ est optimal alors £ est critique. Ainsi les relations

(3.7] constituent une

une condition n6cessaire pour qua l'ouvert ~ soit une solution du probl~me 2,

4

APPROXIMATION D'UN POINT CRITIQUE.

Ella est bas~e sur les conditions

[3.7] d'optimallt6

: soit £ , de~inissons

T(~) per

x e T[~)< si

l'ensemble

o6 G~

s'annulle

(3.7]'

£

On a donc l ' a l g o r i t h m e

f

> G~(x]

< o

e s t de mesure n u l l e ,

= T[~)

suivant :

~O donne £n+ 1 = T [ £ n]

n

=

oji~...

[3.7)

s'~crit

lO0

Naturel!ement,

11 ~auOra modifier cat elgorithme si 0 ~

n'entreine pas

T[~)~. Cat algorithme a donn@ d'excellents r@sultats num@riques, ayent en g@n@ral lieu apr@s une ou deux iterations,

la convergence

toutefois,

le convergence

th6orique de cat algorithme reste encore ~ @teblir.

CAS PARTICULIER

1

[Etudi6 par BENDALI -

DJAADANE - Th@se de 3i~me cycle - Universit@ d'Alger]

L~ouvert ~ sst d6fini comma l'image d'un ouvert fixe B delR n par une application t----# x = XCa,t) qui d6pend d'un param~tre a e K K est un ensemble compact et J e s t

CIR p.

; Ainsi la "vraie" variable n'est pas ~ mais a

done une fonction de a :

Pour d@terminer grad J(e], on commence par calculer Tl[a,ga)

c

=

j

G~[x] du -

I

g~[x) du, o~ en r@alit~

~+~ G est indic@

TI[e,~a)

=

par a ~ en ~ait cette relation s'~crit

~ Ga[X[e+~e,~)]

J(a+~a,t)

dt -

j

Ge(X(a,t))

B cO J repr@sente l e Jacobien du changement de v a r i a b l e .

J[a,t]

dt

B

A partir de l&, en

d@veloppant G

et J, l~in#iniment petit 6tent ~a, on obtient la dife@rentielle e de J par rapport & 6a et donc le gradient de J en a. On psut alors utiliser n'importe quelle m6thode du type gradient.

CAS PARTICULIER

2 :

-[a-$amiii~-~-d]ouverts

[@tudi@ par KOENIG et ZOLESIO] de~R n est d@finie comma @tent l'image d'une partie (1-

d'un espace de Banach A par une application u v@rifiant 1as propri~t6s s~ivantes

:

u est injec~ive

La "vraie" variable a ~

~

peut alors Etre un @16ment delR n [example 2) ou

un @l~ment d~un espaee eonctionnel

[probl@me "& fronti@re libra")

On salt eussi dens ce cas expliciter le gradient.

101

CAS PARTICULIER 3 : Dens ~ 2 pour simplifier,

~ est rep6r6 ~ l'aide d'une fonctlon

x;

La "vraie" variable est ici ~ .

1

Oervieux

et Palmerlo obtiennent,

en passant par les relations

m~diaires

[3.1],

[3.2),

int~r-

[3.3),

une

relation du type : 0

J(~+

1

h ,

) = J(~]

+ h

Ge 0

(t).

~(t]

dt ....

/

Catte lois h est l'infiniment

petit

; on a n6glig~ les termes d'ordre

sup6rieur ~ 1 ; Cette relation permet de savoir dens quelle "direction" pour d~terminer J ; de plus si on avait t --4 on pourrait

obtenir ~aeilement

CAS PARTICULIER

4

= ~

du gradient,

iu~z~

le gradient de J par rapport ~

et en les modiflant

approximations

CIR p,

a.

les principes de la m@thode classique

pour les app3iquer au probl~me actuel, un algorithme

sont boris mais inf~rieurs toutefois successives.

: ouverts

~ sera rep@r@ par un ensemble d'indices

~i ; En reprenant

J.CEA, A, GIOAN et J~ MICHEL proposent tats num@rlques

a~K

~i ; en fait les w i sont des "@l@ments ~inis"

de D, deux ~ deux disjoints.

In

il faut sa d@placer

teEO,l],

:

On suppose que ~ = i ~ l

=

~(a,t)

convergent,

Les r~sul-

& eeux de la m6thode des

I02

BI

BL

IOGRAPHIE

Nous donnons une bibliographie cas partiouliers BERGMAN S., SCHIFFER

@tudi@s

tr@s sommaire,

limit@e aux

;

M.

Kernel functions in mathematical

and elliptic differential physics,

Academic Press,

equations

New-YorK,

1953

CEA J., GIOAN Aoj MICHEL J. @uelques r@sultats

sur l'identification

A para~tre dens "CALCOLO"

CHENAIS O.,

Un r@sultat d'existence de domaine,

de domeines.

1973.

dens un probl~me d'identification

note eux C.R. Acad, Sci. PARIS,

t 276,

[12 F6v.

1973].

OERVIEUX.

PALMERIO.

A. B.

Identification Oirichlet,

(20 Novembre

HADAMARD.

J.

de fronti@re

dens l e c e s

d'un probl~me de

note aux C.R. Aced Sci. PARIS,

t.275

1972).

M6moire sur le probl~me d'analyse relati# & l'@quilibre des plaques ~lastlques dadamard,

C.N.R.S.,

encastr@es,

PARIS,

oeuvres de Jacques

iB68.

KOENIG. M.

Sur la location d'un domaine de forme donn@e,

ZOLESIO,

cycle,

J.P°

I,M,S.P.,

Universit~

de NICE,

th~se 3i~me

13 Mars 1973.

THE MODELLING OF EDIBLE OIL FAT MIXTURES J.O. G r a y - J.A. Ainsley Dept. of Electrical Engineering U.M.I.S.T. Sackville Street, Manchester U.K.

Introduction

This paper is concerned with a practical application of straightforward modelling and optimisation methods to an industrial process which promises to yield very attractive economic returns.

The process consists of the large scale batch pro-

duction of edible oil fat mixtures such as margarine and shortening products.

The batch production of edible oil fat mixtures requires the mixing of quantities of raw material to meet both economic and taste criteria.

The latter is the more

difficult to quantify but it is found that the variation with temperature of the ratio of the liquid to solid phase of the mixture has an important bearing on its taste and tactile properties and hence on the acceptability of the product.

A

measure of this ratio is obtained by dilatometerymeasurements at specific temperafumes.

The dilatometerytemperature profile of a compound oil fat mixture is~ how-

ever, a highly non-linear function of the behaviour of the individual constituents and much skill and experience is required by the analyst in the determination of constituent fractional proportions to ensure that the final compound meets the required dilatation temperature specification.

Accurate computer models of this

non-linear behaviour for a range of compounds would be a valuable aid to the designer of edible oil fat mixtures both in speeding the design process and reducing wastage due to error.

This paper deals initially with the derivation from experimental data of regression models to describe the dilatation temperature profiles of binary and tertiary interactive oil fat mixtures.

These models are subsequently incorporated in a computer

design program to calculate mixture constituent ratios which will yield a best fit to any specified mixture dilatation temperature profile.

Economic restraints are

incorporated by setting an upper bound to the fractional proportion of any of the constituent components.

Such bounds will vary with the seasonal changes in raw

material costs and are at the discretion of the designer.

Dilatation and the oil correction factor

If a quantity of solid fat is heated, the volume of fat during heating can be represented by the curve ABCD in Figure i.

Between point A and point B the fat is

104

completely solid and between C and D it is in a purely liquid condition.

The

dilatation of a fat at any temperature is defined as the expansion during isothermal melting and is represented in Fi___gure 1 by the difference in respective volumes between the partially melted fat at point P and the subcooled liquid fat at point R. The dilatation is usually denoted by the symbol D T where the subscript refers to the temperature at which the dilatation is measured. Dilatation figures are usually 3 related to 25 grams of fat with the volume being expressed in mm .

The measurement of dilatation depends on a knowledge of the subcooled liquid line CQ which is normally difficult to determine experimentally due to the inherent instability of the subcooling process.

CQ must therefore be obtained by extrapola-

tion of the easily measured liquid line CD.

The coefficient of the oil thermal

expansion has been shown (1) to be of the form E = k + yT The constants I and 7 have been given a range of values by various experimenters (1) and, depending on the value used, the resulting dilatation figure can lie within a spread of 36 dilatation units at 20°C.

This spread narrows as the degree of extra-

polation decreases and, as it is impractical to determine coefficients k and 7 for every possible combination of fat and oils, some compromise figure must be determined and generally adopted in the measurements.

A degree of uncertainty is thus

present in any quoted dilatation figure and this will be reflected in the expected accuracy of any analytical model derived.

The modelling of binary mixtures

The data from six binary oil mixtures were available for modelling.

The mixtures

were as follows: !.

PALM OIL + LARD

2.

HARDENED FISH OIL + LARD

3.

HARDENED FISH 0IL + PALM OIL

4.

COCO OIL ÷ PALM OIL

5.

HARDENED FISH OIL + COCO OIL

6.

LARD + COCO OIL

The dilatations for each of these mixtures was measured at various compositions and the following temperatures: 20°C, 30°C and 37°C.

A typical set of experimental results is shown in F igur e 2 which demonstrates the general non-linear form of the mixing process.

To improve the symmetry of the raw

data a dimensionless dilatation d was adopted where

105

f(X ) d =

Here X ,

AX~ + BX8

X~ are the constituent concentrations,

A,B

and

- g(X )

are the respective pure component dilatations

f(X A)

is the raw data

g(X)

is a least squares regression model obtain from the raw data.

Polynomial forms of up to fourth order were determin~using a regression analysis computer program to obtain the optimum g(X e) function and, for each polynomial form, both the total and residual variances were calculated with the significance of the model being examined by means of the F test method (2).

A typical regression

result is shown in TABLE i where the F test percentage figure indicates the significance of the model.

The standard error is given in terms of dilatation units when

the model is applied to the original data.

The 95% confidence limits of the poly-

nomial coefficients are also listed.

TABLE 1 A typical regression result given by the F test method.

Binary mixture.

Hardened fish oil lard mixture d20 = 1 . 0 - 0.65XF + 0.57X~, 0.i 3 X ~ - 0.06X~ F-test 99%

Standard error ± 7 units

Coefficient

Limit

1.0

± 0.0O4

-0.65

± 0.01

0.57

± O.01

O.13

± 0.01

-0.06

± O. 01

The predicted error for the best d20 models of mixtures 2, 3, 4 and 5 lay within a band of approximately 40 dilatation units at an F test significance level of 99%. The most ill fitting model was that of mixture 1 where the predicted error band was 150 dilatation units.

At 30°C the error band was small for all mixtures due to a

more accurate oil correction figure and the smaller absolute values of the dilatations.

106

Modelling of tertiary mixtures

Four mixtures of oils consisting of three interactive components were modelled. These were: Io

HARDENED FISH OIL + PALM OIL • COCO OIL

2.

HARDENED FISH 0IL ÷ LARD ÷ PALM OIL

3.

HARDENED FISH OIL • LARD + COCO OIL

4.

LARD ÷ PALM 0IL ÷ COCO OIL

The measured dilatations of these mixtures were available at various concentrations and the following temperatures: 20°C, 30°C and 37°C.

In this case, as shown in

Figure 3,there are two possible ways of proceeding to formulate the model and a range of polynomial regression models were postulated which had the two general forms DT = K O t Kla + K2b • K3c + K4aa ÷ K5b~ ÷ K6c~

DT = K 0 ÷ Kla + K2b + K3c + K46~ac ÷ K56abc • K66aab where a, b, c = AX~ BX, CX ~ac ~ 6bc ~ 6ab = dac }A + el, % c

IB + CI' dab IA • B I

= i, 1.5, 2.0, 2.5 ..o The predicted D20 figures for for best models of mixtures i, 2 and 3 were within a band of 50 dilatation units at an F test significance level of 99%.

The correspond-

ing D30 and D37 figures for these mixtures were 40 and 20 dilatation units respectively.

The best model for mixture # produced corresponding error bands of 80, 90

and 94 dilatation units.

A typical regression result is shown in TABLE 2.

Here a

variable is declared redundant if the chance that it is redundant is in excess of

50%. TABLE 2 Typical regression result given by F test Tertiary Mixture Hardened fish oil/palm oil/coco oil mixture D20 = 1178 - 3.3FX F - 0.96PXp - 1.5CX C 0.19dFp FX F + PXp * 1.65dFc FX F ~ CX C ÷ 0.32Dcp CX C ÷ PXp + O°OO1 FX F 0.002 PXp F-test 9g.g

2

- 0.0004 CX C

2

2

Standard error ± 22 dilatation units

107

Coefficient 1178

Limit

Limit

Coefficient

± 4

0.O02

± 0.00017

-3.3

± 0.035

0.0004

± 0.00018

-0.96

± 0.049

0.19

± 0,039

-1.5

± 0.048

1.65

± O.037

± 0.00003

0.32

± O.O59

0.00!

The term - 0.0004 is redundant

Nuclear magnet± ¢ resonance spectroscopy

Nuclear magnetic resonance spectroscopy methods can be employed to give a direct reading of liquid in a solid/liquid sample and thus, in this case, it is possible to determine the solid fat index at any temperature and hence the dilatation figure. Due to errors in the oil correction calculation, more accurate models will only result if a more absolute measurement criterion such as the solid fat index is adopted.

Some preliminary measurements have been taken using this method and a

comparison with similar dilatometerymeasurements

is given in Figure 4.

Future

experimental data will be based entirely on NMRS measurements.

Synthesising o?timum three component oil mixtures

A computer program based on the simplex hill climbing routine and incorporating the best regression models of tertiary oil mixtures was devised to calculate the composition of a three component oil fat mixture which meets a required dilatation temperature specification. of computer store. (i)

The program which is written in Fortran IV requires 8K

There are eight steps in its execution.

The desired mixture dilatation values are entered.

(2)

The appropriate oil mixture is chosen.

(3)

Pure component dilatation values are entered.

(4)

The maximum desired value of each constituent in the mixture is chosen. This value will be determined by economic or other criteria at the disposal of the analyst.

The stoichiometric mixture relationship is assumed to be

satisfied. (5)

Starting point of search is chosen.

Data entry is now complete and the following steps are automatically undertaken by the program: (6)

By altering each constituent by ±0.5% six points circling the chosen starting point Po are obZained as shown in Figure 5.

(7)

The objective function e is obtained at each of the seven points

108

e = (E20 -o $20)2 t (E30 - S30 )2 + (E37 - $37 )2 where E20 ~ E30 ~ E37 are the mixture dilatations at 20°C~ 30°C and 37°C calculated from the regression models and $20, $30, $37 are the specified mixture dilatations.

(8)

The smallest objective function is determined and this point used as an initial point in a new search.

The search is terminated if the initial point has the

smallest value of objective function.

If the search meets a boundary then the

optimum solution is that point which crosses the boundary.

As shown in

Figure 5 the search near the apex of the triangle is essentially constrained to two directions.

No facility exists in the simple hill climbing program used to determine whether the minimum obtained is local or global.

Instead a map of the objective function is

printed out which can he visually scanned by the operator to obtain the global minimum search area~

Typical computer results are shown in TABLE 3 for four oil mixtures where a constant arbitrary dilatation profile is specified.

This profile was appropriate

for the first two oil mixtures and a good design resulted.

The D37 figure specified for mixture 3 was, however, unrealistically low as LARD PALM COCO mixtumes are generally characterised by D37 values in the range 50 ÷ 120 dilatation units.

The attempt by the hill climbing routine to meet this figure had

a subsequent deleterious effect on the D30 figure obtained.

A similar situation

occurs with the HSO,LARD.PALM.D30 mixture.

Discussion of results

The regression methods used in the derivation of the mixture models were found to be generally successful in dealing with the inherent non-linearities of component interaction and, once dilatation estimate errors are eliminated, better models should be obtained. Possible improvements in the optimisation program include the incorporation of a sensitivity routine to inform the operator as to which component variation has the greatest effect on the dilatation figures and the insertion of a command interceptor.

The latter routine would allow the operator to re-enter the design program

at any point, change a parameter value and exit directly to ascertain the effect of his action on the dilatation contour.

This would enable a fast iterative design to

be completed with a minimum of data entry.

109

As the entire program only occupies some 8k words of computer store it is suitable for use on a small, inexpensive, dedicated computer which could also be used for online control of the mixing system from the tank farm.

Alternatively, the program is

suitable for use on a time shared terminal connected via a land link to a remote central processor.

The economics of the latter approach are now being investigated.

A computer program of this type will completely remove the tedium of design calculation and ensure a specified dilatation temperature profile for the final product batch.

The associated reduction in product waste due to design error will, of

course, result in significantly lower production costing over a wide range of product mixtures.

Conclusions

The oil correction calculation gives rise to a large error in dilatation readings, particularly at low temperatures, and this error is reflected in the derived regression models.

A more absolute measurement technique than normal dilatometery

methods is thus necessary if accurate models are required.

The optimisation

program developed for synthesising oil mixtures is simple in concept~ easy to use and gives good results provided a realistic dilatation contour is specified.

References

(1)

Boekenoogen, H.A. 1966 Vol. i.

(2)

Perry, J~H. Book Co.).

Analysis and Characterisation of Oil Fats and Fat Products,

(Chichester: John Wiley - Interscience Publications).

Chemical En$ineers Handbook, 1963, 4th Edn. (New York: McGraw-Hill

~H

~ t

3

/ O.

Of course (2.2) obviously follows from the definition.

The proof of

(2.5) is immediate : if we consider the ~articular policy consists in ordering

~ (~i>~ O) at time

~xt which

t, then :

u(x,t) = inf Jxt(Vxt) ~< inf Jxt(Vxt) = I + inf Jx+~,t(Vx+~,t) hence (2.5) follows. The proofs of (2.4)(2.6) are much more complicated. (I) Of course one has to make here precise hypothesis on the nature of the Demand D(t,s) ; cf. A. Bensoussan and the A., loc.cit. (2) The operator A is determined by D . It is a second order (resp. first order) operator in the stechastic (resp. deterministic) case.

121

let us observe now that ( 2 . 4 ) . . . ( 2 . 7 )

is indeed a free boundary problem.

I~virtue of (2.6) there are two regions in say

S, one has

~

x [to, T ] ; in one region,

:

(2.9)

u = M(u)

and in the complementary region

au + A u - B-~

(2.1o)

The interface between

S

C

one has

:

f = 0 •

and

Some remarks are now in order

C

is a free boundary.

:

Remark 2. I. u ~ M(u) defined by ( 2 . 8 )

The non linear operator since to compute neighborhood

M(u)

of

is of non local type,

x it is not sufficient

at point

to know

u

in a

x.

Remark 2.2. Many other examples

or operators of the type of

arise in applications.

M

as given by

Cf. A.Bensoussan and the Author,

loc.

(2.8)

cir.

Remark 2.3. From the solution

u

one can derive the best policy (which exists)

this is an extension of the "s - S policy", also the Bibliographies

introduced

;

in [12][14](see

of these works).

Remark 2.4. In Section 2.3. below, we briefly consider the stationary case, over in a bounded domain blem is then to find

u

O of

~n

with smooth boundary

Au - f ~< 0 , in O

(2.12)

u - M(u)

(2.13)

We assume that ~)

~< 0 ,

(Au-f) (u-M(u))

~ A

= 0 ,

(2)

au

(2.14)

F (I); the pro-

satisfying

(2.11)

and

and more

=

0

on

I~

is given by (1.1) sm_d satisfies

(1.3).

CZ. [311) 3),for the interpretation of the problem. The introduction of a bounded domain O eliminates some technical difficulties. (2) Actually this boundary condition should be dropped at boundary points where u = M(u).

122

2.3.

Quasi v a r i a t i o n a l inequalities

The a n a l o g y between ( 2 . i l ) difference is that

.o.

(Q.V.I.).

(2.14)

and ( t . 4 )

...

(1.7)

is

clear

; the

~ , w h i c h is g i v e n in (1.5), is now "replaced" b y

M(u) which is not given. One can check that (2.11)

o.. (2.14) is equivalent to finding

u

such

that

(2.15)

I

a(u,v-u) ~ ( f , v - u )

V v ~ ~(u)

,

It u ( m u ) . The p r o b l e m (2.15) is called a quasi v a r i a t i o n a l inequalities One can show the existence

(Q.V.I.).

and uniqueness of a m a x i m a l solution

w h i c h can be obtained as the limit of solutions of V.I. Let us introduce

(2.!6)

u°

s o l u t i o n of the N e u m a n n p r o b l e m :

a(u°,v) = (f,v)

V v E HI(o)

u n , n >i 1 , as the solution of the

and let us define

a(u~,v-u ~) ~ ~,v-u n)

(2.17)

V.I.

:

7 v ~< m u d - l ) ,

One can show that (2.18) and obtain

u u

o

~ u

I

~

..° ~ u

n

~

..°

~ s o l u t i o n of (2.15), as the limit (in LP(~)

and HI(o) weakly)

of

u n as

V P

finite

n~

Remark 2.5. Algorithm (2.17) used jointly w i t h n u m e r i c a l technique for solving V.!. gives n u m e r i c a l methods for solving Q.V.I.

Cf. [2][9].

Remark 2.6. For n u m e r i c a l purposes,

one is of course faced w i t h the problem of dimen-

sionality. We shall report elsewhere on the use of d e c o m p o s i t i o n methods and sub-optimal policies.

123

BiBZIOGRAPHY

[I] C.Baiocchi,

C.R.Acad. Sc., 273 (1971), 1215-1218.

[2] A.Bensoussau, M.Goursat and J.~.Lions,

C.R.Acad.Sc.Ps~is, s@ance du

2 avril 1973. E3] A.Bensoussan and J.L.Lions, I) C.R. Acad. Sc. SEance du 2 avril 1973, 2) C.R. Acad. Sc. S@auce du 2 avril 1973, 3) Book in preparation, 4) Work to the memory of I.Petrowsky, Ousp.Nat. Nauk 1974 5) Int. Journal of Appl. mat. and Optimization. E4] H.Br~zis and G.Duvaut, C.R. Acad. Sc. Paris, t.276 (1973), 875-878. E5] H.Br~zis and G.Stampacchia, C.~,Acad. Sc. Paris, 276, (1973), 129-132. [6] G.Davaut and J.L.Iions,

In@quations en M@canique et en PhEsique,

Dunod ~ 1972. [7] G.Duvaut,

C.R. Acad. Sc. Paris, June 1973.

[8] R.Glowinski, J.L.Lions and R. Tr@moli~res, Book to appear, Dunod, 1974. [9] N.Goursat,

Report LABORIA,

1973.

[10]J.L.Lions and G.Stampacchia, Comm. Pure and Appl. Math XX (1967), 493-519. 11]J.P.qaudrat and ~.Viot, Report LABORIA, 12]H.Scarf

1973.

~ath.Neth. in the social sciences. Stanford Univ.Press, 1960.

13] G. Stampacchia

C.R.Acad. Sc. Paris. 258 (1964) 4413-44~6.

14] A.E. Veinott

J. SIAM Appl. Nath, 14,5, September 1966.

A CONVEX P R O G R A ~ I N G

~ETHOD IN HiLBERT SPACE A~D ITS APPLICATIONS

TO 0PTI~3~L C0h~ROL OF SYST~I~ DESCRIBED BY PARABOLIC EQUATIONS Kazimierz Nalanowski Polish Academy of Sciences Institute of Applied Cybernetics Warsaw, Poland 1. INTRODUCTION Some optimal control problems for systems described by partial differential equations can be reduced tion of a convex functional J(y)

[2, 6] to the

problem of minimiza-

on a closed convex and bounded set D

in a Hilbert space. However, this set (the so called attainability set) usually is not given in an explicit form. Therefore the direct minimization of the functional is very difficult. On the other hand it is comparatively easy to find the points of support of D by given supporting hyperplanes° It was Gilbert who first proposed[4] to use these points of support for construction of a sequence minimizing J(y). He considered the case of a quadratic functional defined on n-dimensional Euclidean space. It turne$ out that the speed of convergence of Gilbert's algorithm is comparatively law. Several attempts were made to improve the speed of convergence of Gilbert's procedure these methods delt with quadratic functionals defined

on

~, 8, 9]. All n-dimension-

al Euclidean space. In this paper all modifications of Gilbert's method are reduced to one general scheme, which is applied to the problem of minimization of a convex functional on closed, space. The use of this scheme

convex

and bounded set

in a

Hilbert

is proposed for solving an optimal

control

problem for parabolic equations. Some computations were performed and ~he three modifications of the method were compared on the basis of obtained numerical results. 2.C0kr~

PROGRA~L~IING PROBLEM AND AN !TERATiVE PROCEDURE FOR SOLVING IT

In a Hilbert space H there is given a closed, convex

and

bounded,

i.e. weakly compact [2,11] set D. ~oreover, a non-negative real convex functional J(Yl is defined on the space H. It is ass mmed that J(y) is two times continuously differentiable and its Hessian J"(yl satisfies the following conditions:

125

n~zll2~ (J"(ylz, zl ~< Nllzll2) Y y ~ D ,

Vz~H

(I)

where 0 < n ~ N ~ . The condition (I) implies that J(y) is strictly convex. Our purpose is to find an element Yopt g D called an optimal element satisfying the relation J(Yopt) = inf J(y). (2) y 6D Since J(y) is lower semicontinuous functional as a convex ~1] and the set D is weakly compact the point Yopt exists and it is unique due to the strict convexity of J(y). At the point Yopt the following necessary and sufficient condition of optimality has to be satisfied (-J' (Yopt) ,Y) ~

(-J' (Yopt) , Yopt ) ~/~& O.

(3)

To determine Yopt an iterative procedure is used based on minimization of some quadratic approximations of the functional J(y) on closed and convex subsets of D, which are constructed successively. To this end we define functionals Ji (y) ~ J(Y) + (J' (Yi)'y - Yi ) + ~ N(Y - Yi' y - Yi ) ,

(4a)

2i(Y) ~

(4b)

Ji(y)

and

J(Y) + (J~ (Yi),y - Yi) + ~ n(y - Yi' Y - Yi ) "

$i(y)

are quadratic functionals and Ji(Yi ) = ~(Yi ) = J(Yi ) •

(5a)

It follows from (q) that $i(Y) ~ J(Y) ~ J i ( Y ) We denote by

Yi 6 D i

the unique element satisfying the relation

Ji-1 (yi) =

Let

(Sb)

i~ Ji-1 (y)" Y£D i

(6)

Yi+l £ D by any arbitrary element such that (-J' (yi), y) ~< (-J'(yi), ~i+I ),

i. e. Yi+l is any point at which -J' (yi) supports D.

V y £D,

the hyperplane ~Ii

(7)

orthogonal

to

Theore m . If the family of closed, convex and bounded sets Di~ D is constructed in such a way that

[yil u

c Di+1

(8)

then the sequence {Yi~ is strongly convergent to Yopt"

126

The proof of Theorem is given in Appendix q. As it is shown in Appendix 2 the optimal value of the functional can be estimated as follows

max

O, J(y~, ) +

+

#(yopt~ ~

(J' (Y~) ' ~+~I (91

#(yi ) ,

where

In the particular case where

J(y) is a quadratic functional of the

form J(yl

= (z - y, z - yl

(IoI

where z ~ H is a given element, which does not belong to D, we have n= = N = 2,and the condition (71 takes on the form (z-yi,yl~(z-yi,Yi+11. In this case the estimation (9~ reduces to the following one 1 ~ max~ i

,

~

(z-~ ,z-y~l

(z-Y°Pt'z-Y°Pt) ~(z-Yi,z-Yi~(11)

3° SOi~ METHODS OF CONSTRUCTING THE SETS D i Note that

according to

Theorem the

iterative procedure

is con-

vergent to the optimal solution if the condition (81 is satisfied matter what are the forms of the sets

D i. However the speed

no

of con-

vergence depends very much on the shape of D i. We present three methods of constructing the family D i known from literature.In all these methods the sets D i are characterized by

fi-

nite number of parameters. a. Gilbert's method [4] This method is the simplest one. We start from any arbitrary point YO ~ D and at (i+q~-th

iteration

we

choose

as

Di+ I

the

segment

In this case the element Yi+1 can be easily found from the formula Yi+1 = Yi + ~C i+1(yi+q - yi I , where

n i+I = ~ n Hence the points

(-J' (yi),

i+n - yil

' ~(Yi+1 - Yi' ~i+I - Yi ~ J

(121

Yi+1 are determined in a very simple way.However

127

the speed of convergence in terms of the number of iterations is very [4]. This slow convergence is due to the fact that at each step we use only the information obtained in the last iteration (namely yi ) and we do not take into consideration the previous ones. To overcome this disadvantage the following modification was proposed: low

b. Barr's method [3] In this method as in the previous one we select an arbitrary tial point Y0 and we put D 1 = Fy0, Yl]' but as

o

coo

co v

F 1 : conv ~ i '

,oo

2 Yi'

...

-..

Di

ini-

we choose

:

o

i+1] ' Yi J '

(131

where y.3 l (j = 1, ..., i+1) denotes the vectors spanning the set D i . Every element y £ D i can be represented in the form a convex combination of y~, i.e. i+1

j=l i+1

where ~Cj ~ 0 ,

~ ~ j=l

= I.

(1~)

Hence~ in order to find the element Yi we have to determine the values ~ of the coefficients < J at which the function Ji_l(~) assumes its minimum subject to the constraints (14). This functional can be rewritten in the form i+1 A

%-I(y) = J(Yi-1) + (J' (Yi-1), ~ ,

~JY~) +

j=l -

,

: °o - [ < c i , ~- > + ~ ~ ,

d~

Yi

Yi-

=

Bi ~ > ]

where Co = j(yi_l) + 1 N(Yi_l, Yi_l)

are (i+l)-dimensional vectors Bi = { _ I

N(y~, yk)~i+l/i+l is (i+1)× (i+l}-dimensional

matrix)

('15)

128

J(Yopt ). i ---~o~ To this end first we shall prove that

(1.3)

lira (-J~ (Yi)' Yi+l - Yi ) = O. i --~o~ Let us assume that (1.3) is not satisfied.Then taking into account (7) ~e conclude that there exists a constant 6 > 0 such that for every integer m > O there exists a subscript ~ > m such that

(-J'(Y~), ~ +1 - Y9 )~ ~.

(1.4)

6

Let us denote

Y = Yr_ + ~ ( ~ + I - y ~

)' ~

(o,I).

u

It follows from (6) and (8) that

5~ (~) ~

~ (~ +1),

Vz~(O,ll.

Taking into consideration (4) and (1.4) we get 1 2

(-J'(y~l,y2 +I-Y~)>- ~IIY~+I-Y~

+~(-~'(y~l,~+1-y~

i+

where

(1.5)

~ =

sup

Ily - z l l 2 < ~ .

y,z e D

l>~tting

where

05= rain{l, £/N~]1 we get

{ ~N ' I

> 0 does not depend on ~ .

Taking into consideration (5b) and (1.6) we obtain

~(~) + - (J~11(~)'4 J(~) ~+1 - ~) J(~+l)\< ~?(Y~+I)+ ~ J~+l -

+

~ ]

135

or which contradicts the convergence of the sequence ~J(yi) ~ . This tradiction proves (1.3). Now let us prove 41.2). Denoting Y~ = Yi + ~ (Yopt -

Yi ),

con-

~g[0,1]

we get from (~) and (5)

(1.7)

~i (y~) : J(Yi ) + ~ (J' (Yi) 'Yopt - Yi ) +

nj~ 2 IIYopt - Yiil 2~
O.

In this case the minimal value of

$.(y) on

D is not greater then

},36

the minimal value of this functional on M i. This minimal value is assumed at the point

y, where

~i(y~ : ~J (Yi)" Taking into consideration that Yi+1 ~ ~i we get from (#b)

~

( (J' (Yi)' ~i+I - Yi) %

+ I) (J (yi), Yi+1 -Yi )" From (5b) ~ (2.1)~

the error of

(2.2) and (2,3) we obtain i-th iteration.

the estimation (9) of

ABOUT SOME FREE BOUNDARY PROBLEMS CONNECTED WITH HYDRAULICS CLAUDIO BAIOCCH_!I, Laboratorio di Analisi Numerica del C. N. R. PAVIA,

ITALY

N.I. DESCRIPTION OF THE PROBLEM Two water reservoirs,

of different levels, are separated by an

earth dam, which is assumed homogeneous,

isotropic and with impervious

basis. We ask for [he steady flow of the water between the reservoirs, and in particular for the flow r e g i o n ~ unknown part y= ~(x)

(or, in other words,

for the

of its boundary).

Denoting by D the dam, and by Yl and Y2 the water levels

(with Yl

greater than Y2; see picture I) the mathematical problem can be stated as follows

(see for instance L8J for the general treatment of this ty-

pe of problems):

]

Find a subset ~ function u=u(x,y)

~tu=Yl ( ~n

of D, bounded from above by a continuous decre~

sing function y= ~(x),

such that there exists in ~

an harmonic

which satisfies the boundaryGconditions:

on AF; u=y 2 on BC; u=y on C C ~

and FC~ ;~nU-0 on AB and FC

.

denoting the normal derivative; we point out that on the "free

boundary" we have both the Dirichlet and the Neumann condition).

x

PICTURE I

I38

In a paper of gle,

the origin

W(X,y):] y

LU(X,t)-

the new unknown W ~0;

g=-

St

for

I proved I

D is

a rectan-

AF and BE are vertical,

(x,y)6 ~

w(1-~w)

if

AB is

, setting:

function w satisfies

is defined

that,

;

w(x,y)=

0 for

(x,y)6D--~

the relations:

= 0

on D;

w=g

on

9D

on f~ D by the formula:

(Y-Yl) 2 (y_y2) 2 2 on AF; g= 2 on BC; g linear on AB; g=0 elsewhere.

The system precisely,

(I)r (2) can be studied

as a varionational

inequality;

d e n o t i n g by H I (D) the space of square summable

on D, whose K :

picture

is in A)

AW~I;

where g(x,y) (2)

(see _;I]' /2j)

30,a6X]0,yIC(in

D =

horizontal;

(I)

1971

first derivatives

~ v6HI

are also square summable,

(D) ; U ~_.0 on D; v : g

functions

and setting:

on ~ D~

the function w satisfies: (3)

w E K;

~v~K:

Vice-versa tion;

~_[gradw,grad(v-w)]dxdy~_

it is well known

(see ~9 ~ ) that

and we can proof that w solution of = ! (x,y) ~ D; w(x,y) ~

(4) ~

(and obviously boundary

problems

inequalities

theory;

(see [3], L4],ES~);

pe of the dam is a t r a p e z i u m

(see picture

w ~0;

A

w _~ I;

{ DyW=y-y I on AF Denoting

by

ge" of the dam

-q

w(1-~w)

treatment.

to a wide class of free

here I will

corresponding

theo-

and we will see later

allows us also a new numerical

cribe one of these problems,

(5)

on ~

) we get a solution of the free

At present we can apply similar methods boundary

setting:

In this way we obtain an existence-uniqueness

rem, via the v a r i o n a t i o n a l that this approach

(3) has a unique solu-

(3) is such that,

0 ~ ; u=y-D ~ w

graph of ~ = ~ - g D

problem.

~(w-v)dxdy.

limit myself to des-

to the case where the sha2). System

(I) becomes now:

= 0; w=g on FEB; w linear on AB;

(we reobtain w=g on ~ D if AF is vertical) . the value of DxW on AB, q represents

(which is now unknown;

in the previous

the "dischar

case i~.-was

2 2 2 -I). Now we can define, for real q: q= (YI-Y2) a ) 6 H I (D) ; v ~ 0 on D; v=g on FEB ; Vx=- q on AB] Kq = (~v and we must modify a bilinear

(3) into the formula

form associed with

"natural boundary

condition"

- A

(like

on AF is

9 ~

(6) following

(where a(u,v)

.~gradu,gradv dxdy) ):

whose

is

139

(6)

W q 6 Kq; ~ V 6 K q

:

Actually we can proof que value

q%

a(Wq,V-Wq) ~

(Wq-V)dxdy + 2

~AF(Y1_y )

(V-Wq)dy

(see (4 3 and ~7J ) that there exists a uni-

of q, such that

(4) with w = Wq~

gives the solution

of the free boundary problem; and this unique value of q can be carac~ terized as the unique value of q such that the corresponding w

solu-

tion of (6) is a "more regular" function, for instance w q 6 CI (D~.

PICTURE 2 N.3. NUMERICAL APPROACH In the cases where the shape of the dam is simple gle, or a trapezium) we discretized the problem

(like a rectan-

( (3) or (6) respec-

tively) by a finite difference scheme. In the first case we must solve the set of inequalities: I Wh~0;

AhWh

~ I;

Wh(1-AhWh ) = 0

in the interior gridpoints~

(7) wh = g

in the gridpoints of the boundary

where h is the mesh amplitude and ~ h sation of the Laplace operator;

is the usual 5-points discreti-

system (7) has a unique solution and

can be solved by means of an iterative scheme, with S.O.R. and proje~ tions

(for the details see L~J,[~J) ;

A h will be defined as the union

of the mesh with center in the gridpoints where w h > 0 ; Uh = Y-~2Wh result (8)

setting also

( ~2 discretizing Dy) we have the following convergence

(see L-SJ) :

u h converges to u in H 1 discrete; ~

= interior of lim ~ h . h-~0

140

In the second case we must m o d i f y i W h ~- 0; ~ h W h (9)

w h = g on FEB;

an a p p r o x i m a t i o n q(h)

in the interior g r i d p o i n t s

on A~7, ~ 2 Wh = Y-Yl on AF

J 1 W h = -q

and we m u s t add to the s o l u t i o n of of q ~

of the e q u a t i o n

fh(q)

that

is a convex,

q,--~fh(q)

(7) into:

Z I; W h ( 1 - ~ h W h) = 0

(9) an a l g o r i t h m for the choice of

In order to do it we look for the tooth

= 0 where fh (q) = ~ 2 W h (F); it can be proved s t r i c t l y d e c r e a s i n g function, w h i c h as-

sumes o p p o s i t e signe in two known points q0 and ql; the u n i q u e tooth of fh(q) q=q(h), we can proof notations

setting q(h)

and w h as the u n i q u e solution of

[seeO~J)

that q(h)

similars to the ones used in

c o n v e r g e s to q e

as

(9) w i t h

and

(with

(8) ) the c o n v e r g e n c e result

(8) is still valid. The n u m e r i c a l results o b t e i n e d by a p p l y i n g our m e t h o d show a good a g r e e m e n t w i t h the ones r e p o r t e d in the literature; for some comparisons.

we refer to ~ 5 #

We want to p o i n t out that the main advantages

of our m e t h o d from the n u m e r i c a l p o i n t of p r o g r a m m i n g and the speed of e x e c u t i o n

v i e w are the s e m p l i c i t y of

(in c o m p a r i s o n w i t h a classi-

cal d i f f e r e n c e m e t h o d we see that both e x e c u t i o n time and F o r t r a n sta tements n e c e s s a r y to p r o g r a m the a l g o r i t h m are reduced to about one third) ; m o r e o v e r our m e t h o d is r i g o r o u s from the m a t h e m a t i c a l point of view. REFERENCES I C. BAIOCCH[. Sur un p r o b l ~ m e ~ f r o n t i ~ r e libre t r a d u i s a n t le filtr~ ge des liquides ~ travers des m i l i e u x poreux. C. R. Acad. Sc. Paris

273 ( ~ 2 ~ )

1215-1217.

2 C. BAIOCCH!. Su un p r o b l e m a di frontiera libera connesso a q u e s t i o ni di idraulica. Ann. di Mat. 97 (1972) 13 7-127 3 C. BAIOCCH!, V. COMINCIOLI, L. GUERRI, G. VOLPI. Free b o u n d a r y problems in the theory of fluid flow through porous media: n u m e r i c a l approach. To appear in C a l c o l o 4 C. BAIOCCHI~ V. COMINCIOLI, E. MAGENES, G. POZZI. Free b o u n d a r y pr~ blems in the theory of fluid flow t h r o u g h porous media: e x i s t e n c e and u n i q u e n e s s theorems. To appear in Ann. di Mat. 5 C. BAIOCCHI~ E. M~GENES. P r o c e e d i n g s of the S y m p o s i u m "Metodi valutativi nella F i s i c a - M a t e m a t i c a " , Acc. Naz. Lincei, Rome dec 1972o 6 V. COMINCIOLI, L. GUERRI, G. VOLPI. Analisi n u m e r i c a di un p r o b l e m a di f r o n t i e r a libera c o n n e s s o col moto di un fluido a t t r a v e r s o un m e z z o poroso. Publ° N. 17 of Lab. Anal. Num. Pavia ( I ~ I ) 7 V. COMINCIOLI. Paper in preparation. 8 M. E~ HARR. G r o u n d w a t e r and seepage. Mc Graw Hill, N.Y.I 19 62 9 G. STAMPACCHIA. Formes b i l i n ~ a i r e s coercives sur les ensembles convexes. C. R. Acad. Sc. P a r i s , 2 5 8 (1964) 4413-4416.

METHODE DE DECOMPOSITION APPLIQUEE AU CONTROLE OPTIMAL DE SYSTEMES DISTRIBUES A. BENSOUSSAN, R. GLOWINSKI, J.L. LIONS (IRIA 78 - ROCQ~NCOURT

- FRMNCE)

INTRODUCTION Le but de ce travail est d'Etudier l'applieation des techniques de d6compositioncoordination ~ la resolution numErique des probl~mes de contr$1e optimal gouvernEs par des Equations aux dErivEes partielles.

L'approche retenue est celle procEdant par

d6composition du domaine o~ on ramgne, par un proegd~ it6ratif, la resolution du problgme de contr$1e optimal initial, ~ celle d'une suite de sous-problgmes de m~me nature relatifs ~ des sous-domaines rEalisant une partition du domaine initial. On dEgagera les principes de la mEthode sur un probl~me de contrSle oO l'Equation d'Etat est lingaire elliptique et le domaine rectangulaire, mais les techniques dgcrites cidessous s'appliquent ~ des gEomgtries plus compliquges et ~ des gquations d'Etat non linEaires,stationnaires

ou d'Evolution.

I - ETUDE DU PROBLEME GLOBAL I.I - NOTATIONS - HYPOTHESES. On eonsidgre un domaine

~$ ~

de la forme F2

Figure 1

et on note

~

U ~ [J % U ~

= r]

la

F4

fronti~re de ~ . L'Etat du syst~me

est donne par "Az = 0

z]

(1.1)

%Ur4

=0

F I UF2 oE

~z v = (Vl,V 2) est le contrSle ; v i E n2(Fi ) , i=l,2. Dans (I.I), ~n

repr6sente la

dgrivEe normale orient~e vers l'extSrieur de f~ . Le critgre est dEfini par (en remarquant que

(1.2)

J(v) =

/

J~

z = z(v) = z(x;v))

Iz(x) - Yd(X) 12dx + ~ I

lr

v2(x)dl~ 1 UF2

;

~ > 0 .

142 On consid~re !'ensemble

(reprfisentant les contraintes) !

(1.3)

2

l~ad = lad x Ua d

i

,

convexe fermg de L2(Fi ).

Uad

Le probl~me global est d~fini par (1.4)

Minimiser

J(v),

v E Nad .

1.2 - CONDITIONS NECESSAIRES ET SUFFISANTES D'OPTIMALITE. II est standard (cf. J.L. LIONS caract~ri~e

(I1 ) que (1.4) possgde une solution unique u,

par la condition d'Euler suivante

J/~

(1.5)

(Y-Yd)(z-y)dx + ~) !F

u(v-u)dF

>~

O

1 UF2 g

vEl~ad

, z=z(v),

On introduit l'gtat adjoint d~fini par £

t -AP = Y-Yd

(1.6)

y=z(u),

u ~ ~ad "

dans

plr3Ur4 = 0 I~ rlUr2 =o ;

alors (cf. J.L. LIONS

(I)),

(1.5) fiquivaut

¢

(1.7)

/ d

(p+~u)(v-u)dF ~ O,

Ii sera commode de r ~ c r i r e variationnelle.

'

u ~ Nad "

!es conditions d'optimalit~

sous forme d'une in~quation

On introduit !'espace de Hilbert

(1.8) o~

V v C ~ad

rl U~

={z] zE Nl(~), zlr3Ur4 =o}

v

HI(~) est l'espace de Sobolev d'ordre I.

On notera que (y,p) E g x g

. On a alors

t.1 Le.. triplet (y,p,u) (o_~ u est le contr61e optimal et

Thgorgme

y

l'~tat optimal) est

solution unique de !'in~quation variationnelle

(1.9)

f~ grad +

b

y grad z dx - / Fl U F2

[

(~)a+p) (v-u)dF

J F1 o3

a

et

b

(I) Le rSle de

uz dF + a(

> 0

grad p grad q dx -

lqz,q EIr ,v ~ l~ad , Y , P E ¥

Ur2

sont deux constantes positives arbitraires a

et

b

appara~tra au n ° 3.2

(1)

f

(y-yd)q dx)

, uE

l~ad ,

143

II - DECOMPOSITION 2.1 - HYPOTHESES - NOTATIONS. Pour ~conomiser les notations, on consid~re une d~composition de sous-domaines

~l,

~

(la g~n~ralisation F 31

an deux

sous domaines s'en d~duit aussitSt) r ~2

n

n

F2 ~2

F41

F42

Fisure 2

07, avec des notations ~videntes F3 = F3! U F32 F4 = F4; UF42 =

~! ~ ~

, suppos~e r~guli~re.

Pour i=|,2, on introduit les espaces de Hilbert (2.])

Vi = { z E

On pose

H](~i) I ziF3iU

F4 i

=0}

.

Yid = Yd I ~. i

On introduit le probl~me suivant : trouver (yi,Pi,Ui) fiant (2.2)

SY] = Y2

sur

LP]

sur

P2

dans

%ri x ¥ i

i x t;ad v~ri-

et

grad Yi grad z.dx - /

u.z. d F.

+

=~,2 1

(2.3)

i

/

a( i=1,2

~. 1

bC

1

(~u i + pi)(vi-ui)d ri) >

i=! ,2

• .

0

If z i, qi' vie %'i x gi

l

et

(2.4)

Zl = z2 [I

' ql = q21~

On a alors Th~or~me 2.1 Ii existe une solution unique de (2.2),(2.3)

donn~e par :

XUad

144

(2.5)

i Yi = restriction de y

~

~i

t

Pi = r e s t r i c t i o n

de

p

~

~i

l ui = restriction

de

u

~

ri

< D~monstration

D6finissons (yi,Pi,ui)

par (2.5). Alors d~apr~s (].I) et (1.6), on a

~AYi = 0 (2.6)

dans

Yil F3i U F4i

~i =

0

~Yi = ~-IFi ui ~f

i -A Pi = Yi - Yid 1

(2.7)

dans

%

=0

I pilr3i U r4i ~I

= O

Fi

f
0 , pour tout zi,q i EIi, viEN~d " Une telle solution est de plus unique. D~monstration Comme (yi,Pi,Ui) est solution de (2.2), (2.3), elle est d~finie de mani~re unique par (2.5). Soient alors (yi,Pi,ui,%,~)

et

(yi,Pi,Ui,%',D')

deux solutions ~ventuelles. On a (2.14)

/ (~-%')(z]-z2)d~ +/

(~-~')(ql-q2)d~ = 0

Mais l'application .

z 1

+

zil ~

V zi,qi ~ ~i .

146 1

de

¥i

->

H2 (I)

est g image dense et (2.14) implique alors

d'oN l'unicit~. Par ailleurs, on v~rifie que SY ! I

~Y2

X°--Tnl SPi

=

I

= --~n I~P2 = - ~n[l

III - METHODE DE COORDINATION 3. i - PRINCIPE DE LA METHODE. La m~thode propos~e est it~rative. Supposons que nous soyons ~ l'~tape ~= ,~k, "~= k

. On cherche alors

yk , pk , u k

r~alisant ~ >i O, V

dans le Th~or~me 2.2 et pour les valeurs pr~cgdentes de %

k, avec

zi,qi,vi comme

et N . Le probl~me se d~-

compose aussitSt en Yi = 0

dans

~i

=0

r3iUr4i (3.1)

k

N~n

r. i

-~n ~

= ui

= (-I)i- k k

~pk = yk

Yid

dans f~i

1 i

?

pk

i (3.2)

I

= 0

i r3i U r4i

?pi[k "~n

k --~n ~ F

F. = O

= (-l)i

k k k (~) ui+Pi)(vi-ui)d r i >. o,

(3.3)

Ilk

vviE

i Na d •

l

Les relations (3.1)~ (3°2), (3.3) s'interpr~tent comme les C.N.S. d'optimalit~ du problgme suivant : l'~tat du syst~me est donn~ par (3.1) et le eritgre est donng par (3.4)

jk(uik) =

. ( y k - Yid)2dx + x) i i 7~ i Fi

i

;~ Yi dE "

147

ik+l , ~k+! par les formules suivantes (o~ S est l'application de

On calcule ensuite

dualit~ de H½([ ) +

H~ (I))

(3.5) k+l o~

k p

= ~

k

k k k + 0 S( Pl - P2 )

est une suite de nombres r~els, born~e.

3.2 - LE PROBLEME DE LA CONVERGENCE. On v~rifie tout d'abord la relation suivante Igrad(Yi-y~)12dx i=1,2

.

~ i=1,2

1

-

a

l

/g

I i=1,2

(u.-u~)(y~-y.)dF. z l l l z

.

Igrad(Pi-pk) 12dx .

a

/~ (

~ i=1,2

k

k

Yi-Yi ) (Pi-Pi)dx -

.

i

1

(3.6) - b~

I F (ui-uk)2d Fi + b . i=l ,2

i=! ,2

/F

i

Fi + (Pi-Pi)(ui-ui)d k k

. i

k k k (~/-~)(P] - P2 - P] + P2 )d~

>~ O,

d'o~ encore (avec des notations ~videntes)

i/

1

1

~ lui-u~T~ + ~

k

i

(3.7)

b ~ I%-.~12 + T~b /r

+

.k - Pi 12dFi + IPi

. a g

)2dx +

i 1

a 1

~ i s d'apr~s l'infigalitfi de Poincarg, et la continuitfi de l'application trace, il existe une constante C telle que (3.8)

~.

,grad z,2dx ~

C (

~ z z2dx 2 d F+ i ~ ) . .

i

i

i

de sorte que (3.7) et (3.8) impliquent ;

(3.9)

-

-

z Z~

i 'ui-u~'2(b~ - ~

) + ~

+ a ~

~

0 "

.

~ (yi-Yi) dF i

148

Supposons donc que 0 4y C- > ! °

(3.10) On choisit

¥-~ < 2C, b = r} et e n f i n

b

~] ~+ bce q u i e s t p o s s i b l e ditions,

il

existe

(3.11)

- C(

s i ~) > ~ rl une constante

, ce qui est C > 0

vfrifi6,

telle

grace

~ (3.10).

Darts c e s c o n -

que

~ t l y i - y k [ t 2 + l[pi-pktt2 + [ u i - u i l z

) +

+a

>~0 .

Posons ~k = ik _ l m

k

=]~

k

-~

On a ~k+l

k -

ok ~, k k+ , ~0,

(I o)

i variational

let Ys (v) be the unique

equation:

a s (y¢ (v) ,~)=

L.

V2'rl

-{%'rl o

where we assume

g! E H -I/2 (F I) while

The variational

equation

value problem

of Neumann

pc)~Aya (v)=f~

go and v belong

(I0) is equivalent

to ~

.

to the following

boundary

type:

in

(II)

[ ~YAY~ (vJ +Xro '

(i0) ¥ o y a (v) =ga (V)

(8) We note that:

~

(9) We note that:

for v ~ H i

on

F

~ gs (v) =

go+V,

on F °

¢gl '

on F 1

(u)=roYA~P(U) +}~u.

+[ IroYoVl i2 ] , since off o

(~)~

IIvl i2 -0 has a unique optimal control in the form of (19). Consequently, (20)-(23) has a unique solution {y,p} also. In fact, for any given pair (Ys '~)s i I 2 EHI(~)~H~'~(F x[s-T,sD, the solution y,p~H2'l(~x]s,T[). Moreover, the following property can be readily established.

168 Proposition: Let {y,p} be the solution of (20)-(23) with s=0.

Define ~ , the system s

"state" at time s, by the pair (y(.,s),$s) , where

$,S(, t,) = i #P'O("'~)

f°r t' ~ {s=[ 0

i = 1 .....

C I, i -- I,

Under A s s u m p t i o n

...

4.1,

m}

, m.

if x* in X is P a r e t o - o p t i m a l

if the Kuhn

- Tucker

there

~i• ~ 0 for i = i, "" . ' m and aj >- 0 for j = i,... ' p

exist

aZ > 0 f o r

s o m e ~,

P Z aj j=l and

such

Max y~Yj (x*)

then

Proof

qualification

is s a t i s f i e d

and

at x*,

then

: , y),

h >

~

m Z hi< i=l

(x*) gi

h >

(4 1) "

'

= 0.

if the gi's

(4.1) w i t h

that x*

that

< ~jx(X

~k > 0==~gk(x*)

Furthermore,

(4.2) J

are concave

~i ~ 0 , i = I,~..,

and the ~j s are c o n v e x m and aj > 0, j = i,...,

in x p implies

is P a r e t o - o p t i m a l .

:

Let x* ¢

every x E X

this

constraint

:

implies

X be a P a r e t o - o p t i m a l

either

~ j s.t.?j(x)

or

V J

that

but

that

This means

that

for

j(x) :

jcx*)

:

Vxex (Note

point.

> ~j(x*)

this

Max

J is a n e c e s s a r y

it is a n e c e s s a r y

0 condition

and s u f f i c i e n t

(43)

for P a r e t o - o p t i m a l i t y ,

condition

for w e a k Pareto-

optimality). Let F be the set of v e c t o r s such that

there

a tangent

vector

exist

admissible

an arc issuing

at x equal

to h.

at x, from x,

that and

is the set of h ~ R n lying

in X, w i t h

190

Thus

(4.3)

becomes

:

j Under

the

(4,4)

J

constraint

qualification

F = {h ~ R n : < gi(x*), where

I = {i : gi(x*)

Let

Wj ~= ~ x ( X * , Max WEW.

h > _> 0,

one

i E

has

:

I}

: 0}.

Yj(x*))

< w,

Max j = I.-, p

condition,

, then (4 .3 )becomes

h > _> 0

~h

£ F

< w, h > _> 0

~h

E F

:

]

or

Max ~$~UW~

and,

if W is the c o n v e x

hull

of

U

W.

j:l . . . . . p Max wEW Consider

the cone

following Let ~ £

Bram~s

F*N

W

,

J

< w, h > _> 0

~h

F* ~ {z ~ R n

: < z, h > ~ 0

proof

~

it can be s h o w n

, t h e n there

exist

~ r

~h

that F * ~

Ii ~ 0 , i ~ I

~ F}

then

W is not

such

that

?

=

Z iEI

ki gi (x*)

and there

exist wj ~ Wj,

such that

: P

j:l therefore, ~h

]

aj ~ 0 , j : 1 .... , p

,

one has

:

]

setting

Xi = 0

P Z ~j Max j =i wj~Wj

~ Rn

if

i ~

< w

I h >

J'

m

_>

that

is

(4.1) o

Z j=l

i i < gi(x*),

h >

P Z ~. = i j=l ]

:

empty.

191 Let us remark that if each set Wj reduces each ~j is differentiable Kuhn - Tucker result

m

X mj VJ'.x(X*, Y j ( x * ) )

j--i

classical

then

:

p

Finally,

to a single element,

at x* and (4.1) yields the generalized

=

J

X

i=l

t i g~Cx*).

the proof of the sufficient case.

condition

is the same as in the

•

5.

CONCLUSION

The notion of Pareto-optimality The scalarization

process

which have been obtained

has been extended

to perturbed

and the extended Lagrange multiplier can be used to characterize

systems. rule

and compute opti-

mal decisions. A promising

field of application

theory without boundary

side payments

of the Auman's

corresponds

of these results

[16]

characteristic

game

function for a given coalition

to the set of all Pareto-optimal

defined perturbed

is "n-player"

; the reader could verify that the outcomes

in an adequatly

system. REFERENCES

[i]

A.W. STARR et Y.C. HO : Nonzero-Sum

Differential

Games, JOTA,

3 (1969),

184-206.

[2] Further Properties (1969),

[3]

[4]

of Nonzero-Sum

Games, JOTA

207-219.

T.L. VINCENT

& G. LEITMANN

Control

Space Properties

(1970),

91-113.

A. BLAQUIERE

Differential

: of cooperative

games, JOTA,

4

:

Sur la g~om~trie

des surfaces

de Pareto d'un jeu diff~ren-

tiel ~ N joueurs, 744-747.

C.R. Acad.

Sc. Paris S6r. A, 271 (1970),

192

[5]

A~ BLAQUIERE,

Lo JURICEK &

K.E. WIESE :

Sur la g~om~trie des surfaces de Pareto d'un jeu diff~rentiel ~ N joueurs; th~or~me du maximum, C.R. Acad. Sc. Paris

A, 271 (1970), i030-I032 [6]

A. HAURIE

:

Jeux quantitatifs

~ M joueurs, doctoral dissertation, Paris

1970. [7]

M.C. DELFOUR

& S.K. MITTER :

Reachability of Perturbed Linear Systems and Min Sup Problems, SIAM J. On control, [8]

D.P. BERTSEKAS &

7 (1969), 521-533

I.B. RHODES :

On the Minimax Reachability of Targets and Target Tubes, Automatica, [9]

J.D. GLOVER &

7 (1971), 233-247.

F.C. SCHWEPPE

:

Control of Linear Dynamic Systems with Set Constrained Disturbances, [I0]

A. HAURIE

IEEE Trans. on Control, AC-16

(1971), 411-423.

:

On Pareto Optimal Decisions for a Coalition of a Subset of Players, [11]

H.W.

IEEE Trans. on Automatic Control, avril 1973.

KUHN & A.W.

TUCKER :

Non-Linear Programming,

2nd Berkeley Symposium of Mathema-

tical Statistics and Probability,

Univ. Calif. Press,

Berkeley 1951. [12]

J. DANSKIN : On the Theory of Min-Max, J.SIAM Appl. Math., Vol. 14 (1966), pp. 641-664.

[13]

V.F. DEM'YANOV & A.M. RUBINOV : Minimization of functiona!s

in normed spaces, SIAM J. Con-

trol, Vol. 6 (1968), pp. 73-88. [14]

B. LEMAIRE : Probl&mes min-max et applications au contrSle optimal de syst~mes gouvern~s par des ~quations aux d~riv6es partielles lin~aires, Th~se de doctorat, facult6 des sciences, Universit6 de Paris, 1970.

[15]

J.

B~M

:

The Lagrange Multiplier Theorem for Max-Min with several Constraints,

J. SIAM App. Math. Vol 14 (1966), pp 665-667.

193

[161

R.J. AUMANN

:

A Survey of Cooperative Games without side Payments, in Essays in Mathematical Economics, ed. M. Shubik, Princeton 1969.

A UNIFIED THEORY OF DETERMINISTIC TWO-PLAYERS ZERO-SUM DIFFERENTIAL GAMES Christian Marehal Office National d'Etudes et de Recherches Atrospatiales (ONERA) 92320 - Chhtillon (France)

Abstract This paper is a shorter presentation of "Generalization of the optimality theory of Pontryagin to deterministic two-players zero-sum differential games~ [MARCHAL, 1973] presented at the fifth 1FIP conference on optimization techniques. The very notions of zero-sum game and deterministic game are discussed in the first sections. The only interesting case is the case when there is "complete and infinitely rapid information". When the minimax assumption is not satisfied it is necessary to define 3 types of games according to ratios between time-constant of a chattering between two or several controls and delays necessary to measure adverse control and to react to that control ; it thus emphasizes the meaning of the "complete and infinitely rapid information" concept. In the last sections the optimality theory of Pontryagin is generalized to deterministic two-players zero-sum differential games ; it leads to the notion of extremal pencil (or bundle) of trajectories. When some eanonieity conditions generalizing that of Pontryagin are satisfied the equations describing the extremal pencils are ~ery simple but lead to many kinds of singularities already found empirically in some simple examples and called barrier, universal surfaces, dispersal surfaces, focal lines, equivocal lines etc...

lntroduction Many authors have tried to extand to differential game problems the beautiful Pontryagin's theory used in optimization problems, but there is so many singularities in differential game problems, even in the deterministic twoplayers zero-sum case, that a general expression is difficult to find and to express. A new notion is used here : the notion of "extremal pencil (or bundle) of trajectories". This notion allows to present the generalization of Pontryagin's theory in a simple way.

t. Two-players zero-sum differential games Usually two-players zero-sum differential games are presented as follow : A) There is a parameter of description t that we shall call the time. B) The system of interest used n other parameters xt, x2. . . . xn and we shall put : (1)

X =

(~IzXtA./. . . . )Xn)

= state vector.

We shall assume that t, the performance index of interest (called also cost function or pay off) is a only function of the final values--~¢, t~ ; if necessary, if for instance I is related to an integral taken along the described trajectory X(t), we must add into X a component related to that integral. C) Ther~_~ two p i e r s

that we shall call the maximisor M and the minlmisor m, each of them chooses a measurable

control M(t) and re(t) (respectively in the control d o m a ~ , g~)M(t) and ~)m(t) Borelian functions of t) and the velocity vector V = dX/dt is a given Borelian function of X,t and the two controls :

195

D) There is a "playing space" ~ subset of the Rn+l ~,t space and a "terminal surface" ~ , "terminal subset" ~ along the boundaries of ~ .

or more generally a

We shall assume that the set ~ is open.

E) The control equation (2) is defined everywhere in ~

and the performance index I(Xf, tf) is defined everywhere

in ~ ; the game starts in at a given initial p o i n t ~o, t o ; themaximisar tries to maximises I at the first arrival at and the minimisor tries to minimizes it. 2. Zero-sum games Since there is only one performance index I(Xf, tf) it seems that the above defined game is zero-sum, however it is possible that both players have interest to avoid the termination of the game (e.g. the cat, the mouse and the hole around a circular take, when the cat blocks the hole) and in order to avoid diffieutties of non zero-sam games the value of the performance index must also be defined in non-finite cases. 3. Deterministic cases of two-players zero-sum differential games

A first condition of determinism is that both players have complete informations on the control function (~,M, m, t), the control domains ~f)M(t) and

re(t), the performance index

I(Xf, tf),

the playing space ~ , the

terminal subset ~ and the initial eonditions-Xo, t o. It is possible to imagine some particular eases of detem~inistie games such as : A) One of the two players, for instance M, has more or less complete informations on the present and past state v e c t o r ~ t ) and choose a pure strategy based on these various informatinns :

B) He must indicate his choice to the other player. C) The second player choose then its own control function m'~t). Hence : When (3) is given the problem of m is an ordinary'problem of minimization and then M chooses its strategy (3) in order that this minimum be as large as possible. However, if the informations of the first player are incomplete, the eouditions A and B are generally unrealistic : the choice of a good mixed strategy improves very often the possibilities of the first player and the real problems is thus not deterministic. The only realistic and deterministic cases arc the following : A) Both players can measure the present value of-~at an infinite rate ; we shall call T M and T m the infinitely small delays necessary to obtain this measure and to react to it. B) In some eases the optimal control requires a chattering between two or several controls, we shall assume that these chatterings can be made at an infinite rate and we shall call ~"M and

~m the corresponding infinitely small

intervals of time. C) There is then 3 deterministic cases : CI) Case when "~m + Tin absolutely continuous trajectories Xi(t) belonging entirely to :~ , each of them being associated to an adjoint function'~i(t) defined on the same interval of time and sum of an absolutely continuous function of t and a jump function of t (with a bounded total variation). We shall call extremal pencil or extremal bundle the union of the trajectories Xi(t) ; this extremal pencil satisfy the following generalized conditions : A) The pencil begins at the point (~o' to) of interest with at least one trajectory. B) Each trajectory Xi-'~t) is defined on a closed interval of time (tio, tif) and ends at the terminal subset ~ (and not only at ~ + as written erroneously in MARCHAL 1973). ¢>

C) h point ( ~ , t) of the extremal pencil can belong to one or to several trajectories Xq(t) and there is always at least one corresponding adjoint vector Pi(t) different from zero. D) Wish H* (t) = H*(Pi(t), Xi(t), t), the equations (11) become :

-_ (13)

H

J J

200

with :

(14) E) In the same way the generalized equations (12) becomes : For any given i we have for almost all t :

(~)~

--~

-9, ~

~V

ae k F) The functions Pi(t) and H~ (t) can also have jumps in the directions given by the infinite values of the positive factors )~ij" G) As usual when there is forbidden zones, if a point (~,t) of the pencil belong to the terminal zone ~ one can add to the derivatives of the vector ( ~ , -H*) given in (13) and (15) a component normal to ~ and directed outward (if ( ~ , t)t~'~-) or toward the playing space (if ('~, t)~ ~e+), one can even add a jump provided that exist connecting absolutely continuous fnnctions P i ( ~ ) , Hi (tp) leading from P(t-), tt*(t-) to "~t+), H*(t+), verifying for any t.~ the relation (6)(or (7) or (8)) and having their derivatives with respect to ~o in the directions given by these outer or inner normal components. H) Finally for each trajectory Xi(t) of the extremal pencil the final values [Pi(tif), H~(tif)l ,must satisfy the ordinary final conditions of Pontryagin. (also called *transversality conditions").

A simple way to obta;n the directions normal to ~ is to use a Lipsehitzias penalty function f(X, t) equal to zero on ~ and negative in the playing space ~ ; the local gradient of f ( ~ , t) with re~peet so (~,t) gives the outer normal direction (or directions, for instance at a corner of ~ ). On the same way, for the condition H. the final vector [Pi'(tif) ; -I~* (tif)l,. with (n + i) components, must b'e parallel to and in the direction of the local gradient of a Lipsehitzian function f+(X, t) equal to zero on ~ + and negative anywhere else (or antisymmetrically wdth respect t o " ~ - if (Xif, tif)~-~-). Let us note that around points (~,, t) belonging to ~'+ but not to ~e-~_ it is useless to consider the function

f+(x~ t) out of ~ + ~ ( ~ d conversely for L(~, t) if (~,, t)e ~-). On the other hand if the direction of grad f+(X, t) (or grad f ( X , t)), it is not continuous at the final point (~i{' tif) of interest, the vector ~ ,

-H'ill may be into an), direction of the corresponding conic convex hull. Conclusion

The generalization of the optimization theory of Pontryagin to deterministic two-players zero-sum differential games leads to the notion of extremal pencil and to the above equations and rules which are sometimes sufficient to determine these pencils (see for instance the two examples of MARCHAL 1973). The main remaining question is to improve the conditions of backward construction of extremal pencils outlined in that reference.

201

References

ATHANS, M .

-

The status of optimal control theory and applications for deterministic systems, A, 8 differential

games. IEEE trans, on automatic control, (April 1966). BEHN, R.D. and HO, Y.C. - On a class of linear stochastic differential games. IEEE trans, on auto-control, (June 1968). CttYUNG, D.H. - On a class of pursuit evasion games. IEEE trans, on auto-control, (August 1970). HO, Y.C. and BARON, S. - Minimal time intercept problem. IEEE trans, on auto-control, (April 1965). HO, Y.C. , BRYSON, A.E. and BARON, S. - Differential games and optimal pursuit-evaslan strategics. IEEE trans, on auto-control, (October 1965). tSAACS, R. - Differential games. -John Wiley and Sons, (1965). JACOB, J.P. and POLAK, E. -On a class of pursuit-evasion problems. IEEE trans, on -auto-contro|, (December t967). MARCHAL, C. - Thearetlcal research in deterministic optimization. ONERA publication n° 139, (1971). MARCHAL, C. - The hi-canonical systems. Techniques of optimization. A.V. Balakrishnan Editor, Academic Press, New York and London, (1972). MARCHAL, C. - Generalization of the optimality theory of Pontryagin to deterministic two-players zero-sum differential games. ONERA, tir$ ~ part.n° 1233, (1973). MARCHAL, C. - Theoretical research in deterministic two-players zero-sum differential games. ONERA publication, to appear. MESCttLER, P.A. - Ou a goal-keeplng differential game. IEEE trans, on auto-control, (February 1967). MESCHLER, P.A. - Comments on a linear pursuit-evasion game. IEEE trans, on auto-control, (June 1967). PONTRYAGIN, L.S. , BOLTYANSKII, V.G. , GAMKRELIDZE, R.V. and MISCR~KO, E.F. - The mathematical theory of optimal processes. Iuterscience Publishers, John Wiley and Sons, Inc. New York, (1962). ROCKAFELLAR, R.T. - Generalized Hamiltonian equations for convex problems of Lagrange. Pacific J. of Math. 33, 411-427 (1970). ROCKAFELLAR, R.T. - Dual problems of optimal control. Techniques of optimization. A.V. Balakrishnan editor. Ac. Presse, New York, London, (1972). WARGA, J . 1, (1965).

-

Minimax problems and unilateral curves in the calculus of variations. SIAM Journal on Control A, 3,

ABOUT OPTIMALITY OF TIME OF PURSUIT

M. S.NIKOL 'SKII STEKLOV MATHEMATICAL INSTITUTE, MOSCOW, USSR

I~ll tell about results of me, Dr. P.B.Gus~atnikov and V.I.Uhobotov in the problem optimality of pursuit time. I have studied with Dr. P.B.Gusjat-aikov this problem in 1968. There is the article about this results in Soviet Math. Dokl. (vol. 184, N 3, 1969). After this article was the article of N.N.Krasovskii and A.I.Subbotin about this questioao Their result is more general. I'll not tell about result of N.N.Krasovskii aud A.I.Subbotin (see Soviet Journal of Applied Math. and Mechan., N ~, 1969). Recently Dr. P.B.Gusjatnikov and I have got some results in this field in cooperation with Dr.V.I.Uhobotov. Let the motion of a vector

~

in Euclidean space

~be

descri-

bed by the linear vector differential equation

(1)

Q =

where

~£ 6. ~

, C

E QC~

~. t~ and ~

is a c o n s t a n t

square matrix , i~6. []>C-

are control vectors. The vector

to the pursuer, the vector

I~ to the evader.

compact sets. Let a terminal subspace

~

P

and

~

corresponds Q

are convex

be assigned in

pursuit is assumed to be completed when the point

•

~:

The

reaches

for the first time~ It is in the interest of the pursuer to complete the pursuit. The information of pursuer is the equality (1) and ~(~), V(~)

for all present

~ ~ O

. The functions

are meserable functions. The pursuer don't know ~)

~)

~ V(~)

~(~)

in advance,

can be arbitrary meserable function. P~utrjagin have constructed the method of pursuit from initial

point ~@ and gave estimate

%(~o)

of time of pursuit.

203 I'ii say some words about this method. Let

~

is complemental subspace of ~

of pro~ection of

~

onto ~

their geome~ical difference

~ g~.C~

1~f(~)= l[g

WO:,'-~d~

-W-~I-0

..rfg ~

~ -- l~g

~

and in-

.-_

, w h i c h i s a compact c o ~ v e ~ s e t ~

"~o in

The time of pursuit frnm

is operator

parallely ~ .

Pomtrjagi~ considers the compact sets

te~al

and ~T

the theory of Pontrjagin is the least

root of inclusion-

~C

Let

~(%o)

is such root.

Definition I. The optimal time of pursuit from ~o is the least time within pursuer can complete the pursuit from ~o. The Pontrjagin time tion ~

%(~o)

is optimal if the following Condi-

is fulfilled.

Condition A.

EQ

For all extreme point

such that for all

~E

~ 6 P

exists ~ =

[0,T]

~C

"cC

A

Theorem I. If the Condition A is fulfilled and then

~(~)

~(~o) ~ T ,

is optimal time of pursuit.

We shall give some sufficient conditions for fulfilmemt

the

Condition A. Let us

OE P

subspace and ~ , V

, 0

their support subspaces in Ye

restriction of mapp~g~T ~

~C mapping

q[~

Let us

is interior point of Q

on

~, ~(~)

o~ V . ~[%)

!

can be factored in such wa~

~h

in its support ~(~)

is

is re~triction of

204

where ~

is linear mapping ~

is linear mapping

g:}{1

and homeomorp~c ~or set

Q

i~[~ JV >/~ )

~to

L

~ ~ go,T]

sweep

Definition 2.

into

oo

,

,

L

1{~}

{~1~ ~)~( ~ ~. , ~1~(~) is analytical for ~{£o,T]

with the exception f i n i t e

pletely :he set

for

A convex closed set S

from space

set ]{;

~/

is strictly convex, if each its support plane has

only one common point with S . Definitio~

A convex closed set S

from space ~ ( ~ I )

is regular, if it is strictly convex and each its boundary point has only one support plane. Theorem 2. Let

here

~

~(~}

can be factored in the form

is linear mapping V-

analytical functiono Let

FQ

into

~

,

~(~)

is strictly convex in

-nonnegative ~

. In

these conditions Condition A is fulfilled. Theorem ~,

Le~

~

is regular in V

• In these

conditions t h e

equality (5) is necesssry for fulfilment the Condition A. The another sufficient conditions for fulfilment the Condition A are given by t~he following Theorem ~. Theorem @. If for

~ >I 0

q~

~C and

~

are commutative on

205

, ~

amd

~Q

sweeps completely the set ~ P

, rhea the Corn-

ditiom A is fulfilled.

Example.

The P o m t r ~ a g i n ' s t e s t e x ~ p l e :

"6

•

are positive comstamts,

~,~,~,~ ~ R K , K ~

{al~ ~ , frill , the~ the conditiom A is fulfilled

amd the time

~(~)

is optimal.

ALGEBRAIC AUTOMATA AND OPTIMAL SOLUTIONS IN PATTERN RECOGNITION

E.ASTESIANO Istituto

- G.COSTA

di Matematica

Via L.B. Alberti,4

- Universit~

di Genova -

16132 GENOVA (ITALY)

INTRODUCTION U. Grenander (1969) proposed a formalization of the linguistic approach in pattern recognition (see also Pavel (1969))o Though the main interest in this method is undoubtely for its pratical application to the construction of particular gr~m~nars of patterns,we think the theoretical questions worthwhile further insight. Therefore we devote our atten~on to the abstract formulation of the problem; however, in order to give a detailed model,we restrict ourselves to a definite class of decision rules. In the recognition system we consider here, the objects to be recognized are (represented by) terms on a graded alphabet and the decision rules are (impleme5 ted by) algebraic automata; moreover we assume that sample classes (in some sense the "training sets") and rules of identifications of objects in images are given. In this context we investigate the problems related to the definition, the existence and the effective construction of optimal grmmmars of patterns. This paper is a generalization and improovement of a previous work of one of the authors. The results can also be considered (but the point of wiew is completely diff~ rent) a generalization of well known classical results in algebraic theory of automa ta; these can in fact be obtained as a particular case of our results (when the sample classes are a partition). The first part is devoted to set up substantially well known definitions and results, in a language more apt to treat our problem. In the second the recognition model and a definition of the optimal solution are proposed and ex plaited. In the last section~conditions of existence for the optimal solution are g! vet and the problem of the effective construction is solved. Finally a few examples are presented to show that sQme seemingly incomplete results cannot in fact be substantially improoved. i. PRELIMINARY NOTIONS. We refer to Cohn (1965) and Gr~tzer (1968) concepts

and to Thatcher

cerns algebraic

and Wright

(1968) an~ Arbib and Give'on

for the algebraic

(1968) for what co~

automata°

If X is a non empty set, DF(X) is the set of all families of non ~npty,mutually joint,subsets

of X; we denote its elements b y ~ , ~ , . . . , O

Ao: U~'--~

~,..°

If~=[A

.

dis-

i, i aI} then

.

~/ A. and ~ : = ~ f A ~ . Conslder on DF(X) the relatlon ~-- defined by: i~l i ~ O; iff a (unique)map ~ : ~ - - - ~ e x i s t s s.t-~ A ~ , we also write

A~ f(A);

Propositio n i.I

~-~

is an order relation on DF(X)

and DF 1 (X) : =(DF(X),b--)

is a

complete

lattice.//

Remark.

We indicate by // the end of the prof; the proof is omitted whenever it is

This work was partially

supported by a G.N.A.F.A.

(C.N.R.)

grant.

207

straightforward or substantially known. Denote now by E(X) the complete lattice of equivalences on the set X, ordered by_. ~ as a subset of X ~ X • I f ~ D F ( X ) and ~ ~E(X),then @ i s an~-equivalence iff, A~, A = x~A~x~o For any P g E(X), let DL(X,P) be the set ~ ( ~ , ~ ) /~6DF(X), ~P , ~ is a ~-equivalence

Proposition 1.2.

and ~. be the relation on DL(X,P) defined by :

E_~ is an order relation and DLI(X,P) : = (DL(X,P),~) is acomplete

lattice iff P is a (complete) sublattice of E(X). // A graded (ranked) set is a pair (~,~'),where~-.is a non empty set and ~ a map fnto N

(the set of non negative integers); if n ~ , t h e n

from

~ := ~'-l(n). From now n

on we shall simply w r i t e ~ instead of (~,O'). A ~-algebra (or simply:an algebra) is a pair ~ = ( A , ~ the carrier of ~ , on A. If o J ~ n if n -0,then ~...

and ~ is a map that assigns to each element ~ i n ~ ' ~is

%is

an n-ary operator, that is : if

n~l, then

Given ~ =

then we denote free 5--algebra of~'-terms on X ( or

and its carrier by F~(X); if X = ~

(A, ~), we denote by rp~ ~is

connected iff rp~

denoted by C (~); C( ~ ) i s

the

unique homomorphism from ~ i n t o

is the set of

;we

DLI(A,C(~)) is

all ~-eongruences on ~ • C(~),

A graded (ranked) alphabet is a finite graded set ~

, s.t. ~

o will be a graded alphabet that we consider as fixed and given. is a pair M = ( ~ , ~

D L I ( ~ ,P). ~ ~. From now on

),where : ~ - - ( Q , ~ ) is a ~" -algebra and ~

DF(Q). The response function of M is just r p ~

of M is ~ M

~

then an ~-congruence is simply an ~-equivalence

We write : C,C(~), DLI(P), instead of C ( ~ ) ,

M is connected iff ~

and F~.

is onto. The set of all congruences on ~ will be

which is a congruence on ~; C ( ~ , ~ )

~-automaton

we write ~ .

a (complete) sublattice of E(A), hence

a complete lattice. If o ~ D F ( A ) ,

A

~ : An--P A ;

to indicate ~ - a l g e b r a s .

simply :terms) by ~ _ ( X )

on A

an operator

an element of A. We use capital German letters,~p~,...#~,...~

If X is a set disjoint from ~ ,

say that

),where A is a non empty set,

; we shall denote it also by rPM

•

is connected~and M is finite iff Q is finite. The behaviour

.= IB/B = rPMl(F), F e ~J; the equiresponse congruence of M

the canonical congruence on ~

ER(M), is

associated with rPM ; eventually ,~(M):----(ER(M),~M).

Lemma 1.3. For any ~- -automaton M, ~A.(M)e DLI(C).// If ( ~ , ~ )

~ DLI(C), then " ~ ( ( ~ , ~ ) )

is the ~-automaton ( ~ / ~

, ~/~),

where

- =

Lemma 1.4. If = (@,03).I1

(~,~)

e DLI(C), then q ~ ( ( e , ~ ) )

is connected and ~ ( ~ ((~,0~)))--

208

Let M

= (~[) ~ ) be a ~-automaton, i =1,2 ; an homomorphism from M into M is a i ....... I 2 pair ( ? , ~ ) , w h e r e ~ : ~ , - - ~ ~ Z is an algebras homomorphism, 9 : ~I--~ ~2 is a map and, ~

F @ ~i' ~ (F) ~ ( F ) "

(~,~)

is an isomorphism, and we write M I~M2, iff :

is an algebras isomorphism, ~ is one to one and onto and ~(F) = ~(F). If Mland M 2 are connected and there is an homomorphism ( ~ , ~ )

from M I into M2, then ( ~ , ~ )

is uniquely determined by the properties : rpM = ~ o r P M a n d ~ ( F ) - ~ (F) ~ F F - ~ , too2 1 reover ~ is onto, we indicate this by writing Ml--@~M2.These definitions and properties allow Lermna 1.5.

us to state the following lermna.

If M and M' are connected automata, then : i) ~ (]k(M))=M ; ii) M--~M'

iff ~ ( M ) 4.~(M~).// We denote by ~ .

the class of connected ~ -

lance, by [M]~ the class of ~ _

automata mod. the isomorphism equivac corresponding to M and by ~ the relation on ~ d e -

fined by : E M I ~ [ M ~ - iff M 2 ~

M I. By the above lermna, ~ is correctly defined and

it is order relation. Theorem i°6.

(~,~4)

is a poset (i.e. partially ordered set) anti-isomorphic to

DLl(C),therefore ( 9 Q ' ~ )

is a complete lattice anti-isomorphic to DLI(C).//

We recall that similar results~ for monadic algebra automata without final states~ can be found in B~chi (1966). Given

~=

(A, ~ ), a symbol x not in A IJE. and S~--A, then for each "Itin F~(SU{x~)

we can define the unary operator o n ~ i) if • = s @ S,

then

i~(a)=s;

iii) if ~ = ~i++. ~nOO ,then if~ =O~e~o Remarks.

,then

I~I=H~

, as follows : ~ a

ii) if ~ = x , then

e A,

ll~ll~(a) = a ;

~I'~I~(a) = ~o~( II~--iII~ (a), .... ~l~nll~ (a)); clearly

ll~II~(a) = ~

•

i) the above operators correspond to the "polynomials" in Gr~tzer (1968);

ii) One can verify that if ~ = I ~l~li~, ~: e F~ ~x~ )

;

is connected, then, ~ S ~ A ,

iii)

the ~ - t e r m on Y obtained from ~

if ~ =

~(Y)

[ II~:|I~,~eF~(SU~x}~

, for any set Y , then

l l ~ ( a ) is

by replacing each occurrence of x in ~: with the

term a+ Consider

~

e DF(A) and ~ connected.

Definition i+I. N ~ i s eA.a~Fz

,

I[~;~(a)

the relation on A Sot., if a, beA,

@ A~ i f f

llz'l$(h)

(a,b) e N ~

iff~'6~(Ix)),

e A i.

Theorem 1.7.

i) N~

iii) C ( ~ , ~ )

is a (complete) sublattice of the complete,lattice C(~).

Proof. of N ~ ,

Hint :

is the maximnm of C ( ~ , ~ )

; ii) G(~,~)----I~'C(~)/e_~N~}

use a modified, but equivalent (see above remark),definition

considering F~ ( A ~ x ~ )

instead of F~( ~x~ )°//

209

For any

~

@DF(F~[ ), set C ( ~

): = C ( ~ Z , ~ ) ;

minimal 5"-automata for ~(i.e.

2. THE RECOGNITION MODEL.

having ~

by theorems 1.6 and 1.7 a class of

as their behaviour) exists: the class

We need a few other definitions before we can give our

recognition model.Consider on DF(X), X non empty set,the relation M-M-- ~

iff

~ ~

~

defined by :

and the map ~ is a bijection. It is soon verified that

W-- is an order relation.

If ~ =

(A, c()

and

~C(~)

then ~

is an O~-separa-

ring congruence iff each congruence class intersects at most one element of ~ . denote by SC ( ~ )

the set of all d-separating

Consider now the free algebra i = I,...,N~ ; we denote by

congruences on ~[. FZ

__~ and a set H = [(ti,t'i)I (ti,t')_ ~(H)

We

the congruence on ~ g e n e r a t e d

X

by H , seeGr~tzer

(1968). One can verify that ~(H) coincides with the reflexive~ symmetric and transitive closure of the relation R(H), defined by :(t,t')~ R(H) iff there is a pair (ti,t')i in H s.t. t' is obtained from t replacing in t t i by t'i " We can now give in detail our recognition model; see Grenander (1969) and Pavel (1969) for the motivations,

for part of the terminology and a wider discussion on the subject.

- The "objects" to be recognized are coded on a graded alphabet - W h a t we actually recognize are (structural)descriptions of the "objects"(analogous to the "configurations" in Grenander (1969)) i.e.

-terms. One "object" may corre-

spond to mauy different descriptions. - We have some information about the corrispondence descriptions - "objects" ,i.e. we are given a finite set H

F

x F

: (t,t')eH means that t and t' correspond to

the same "object" and can thus be identified. If appears quite natural that we identify also all the pairs in R(H) and that we extend the process by reflexivity, symmetry and transitivity. This eventually amounts

to consider on F

the identifica-

tions given by the congruence ~(H). We can restate all this, by saying that we are given a finitely generated congruence (mod I ~ )

and the images now become,

- We are given

~DF(F~),

h~- ~ -

and

An admissible,

for I ~ I~

on ~ Z " we call imases the classes

for us, the objects to be recognized.

the family of examples , i.e. a family of sets ofalrea

dy classified descriptions, o ~ a n d - An admissible,

I~

I~

must be such that I ~

is -~-separating.

and O~ , family of patterns is a family

~ 6 D F ( F ~ ) s.t.

is a ~-congruence.

for I ~

and ~ ,

decision rule is a map

r : F~.

~

~

, such

that : ~r: = -l~r'i(A)' A~)--~ is an admissible family of patterns and a (connected) -automaton M e~ists such that ~r----~ M

(we say that r is implemented by M ).

210

Usually a decision rule can be implemented by several (even non isomorphi¢)~'-aut. Definition 2.1.

A solution of the recosnition problem,with I ~

is a E-automaton implementing an admissible, for I ~ Consider

~=(A,c~), ~EDF(A) and P _ ~ S C ( ~ A ) ,

and

~

~given,

and o~,decision rule.

then : EDL ( ~ , P):= [ ( ~ , ~ )

(~,~)

DL( A ,P), Remark • The order ~ (~,~)~(~,~)

induced on EDL(~,P) by the order < we have on DL(A,P) is sot.

iff ~

and ~ H - - ~ °

We call quasi-complete lower semilattice (q.c.l.s.-lattice~ any ordered set in which all non ~ ={0~DF(F~.

subsets have a g.l.b. ) I~H-~}

Thus~ if we consider the set EDF(~): =

, the set of extensions of ~

,ordered byH--

; it is ea-

sy to see that (EDF(~),~--) is a q.c.l.s.-lattice but not a lattice. From this we have also that,if P is a q.c.l.s.-lattice, then E D L ( ~ P )

is a q.c.l.s.-lattice, but,

even if P is a complete lattice, EDL ( ~ P ) is not in general a lattice. This fact I is of great importance as+we shall see now. Set SC(~): = S C ( ~ K , ~ )

and, if P ~_ SC(~), Ip 1 = ~ ~ ; ~ 6 P

/~2-I~

then from

theorem 1.6 and the remark about ~Lk

: g(P)

= P

with

~ D(x,Aj) to

the

= L

part with

for

j¢i

},

of

the

smallest

index.

245

A i = {~he

n i elements

n. w i l l d e p e n d i In [9J we t o o k Remark The

: If R

dynamic

function from

upon as

the v a r i a n t

clusters

is n o t shall

our

the

choice

a)

For

by

which

R

one

if f u r t h e r m o r e

R(x,i,P)

ter

(~)

WATANABE b)

A

A

and

thorough

zation

of

L k must

be

chosen.

in a p p l y i n g the

all

the

p F

for

P subdominant

the

characterize

form.

partitions w h i c h are less thin than

the

impose

and

is a w e a k

defined

connected

(cf A p p e n d i x

Remark

of

the

the

are

each

thinner

generally, set

:

properties

Q*

the g r a p h

the

forms

Q ~ of E for w h i c h

p1 t 2)

of w e a k

parts

of

} and r p = (E,Fp),

p = O,l,2,...,n ultra-metric

constitutes

of a c e r t a i n

a

dis-

3).

:

It f o l l o w s

from

these

definitions

that

pt

is a thinner

partition

than

Qe. Definition They

are

of

the

over)apping

characterized

to a single

point.

by

They

the

a~E

is i s o l a t e d

a point

aGE

is o v e r l a p p i n g

5.2.2 The

they

a)

of " f u z z y

permit

intersection, To

profile

by

are

strong

points forms

the f o l l o w i n g

: 0 O, a n d

m(t,x(t),u)

n(t, x(t))

with the same conditions as in Problem

i0

~(t, x(t), u) < 0

( Qb(t, x(t), u)

~b(t,x(t),u) ~ 0

= {

=

o

,(t,x(t)) < o

¢ (t,x(t))

,(t,x(t)) ~ o

l

P.

The following t h e o r e m gives the existence of, and necessary conditions for, solutions to P r o b l e m P •

Theorem

i

Under the above conditions, there exists a solution pair Xs(. ), u

for p r o b l e m P ¢ .

I. I)

This pair satisfies the " e - m a x i m u m

principle":

Let

~'(e,t,x(t),u)

--

[ z ( , , t ) , f ( t , ~ ( t ) , u ) ] - [L(e,t),~(t,x(t),u)]

-[M(c,t), ~(t,x(t),u)]

- [ N ( e , t ) , ~ ( t , x ( t ) , u)] - g(t, x ( t ) , u)

where

x L(s,t) = ¼~(t, xe(t),u¢)

M(S,t)

= lm(t,

1

Xs(t),ue)

.T

N(e,t) - Z--e J t n(s'xe(s))ds ~V(t,x(t),u) = ~(t,x(t))~t + ~x (t'x(t))f(t'x(t)'u)

,01

262 Then,

Je(,, t, x (t),

1.2)

--

m a x JC(¢, t, x e (t), u) ueU g

If w e write Y ( % t ) = i (x ° (t) - f(t,x¢(t),u )) then w e have

: -Vf*Y +V~P>i'lL +V(~*M + V g * ( ~ n ) +Vg*

Y(%T)

a. e.

= 0

evaluated along (% x (t), u £ ). i. 3)

T h e multipliers Ni(e,t ) are monotonic non-increasing and constant on

intervals along which ~i(t,x e (t)) < 0.

Comments

The proof is omitted here and m a y

be obtained f r o m l~eference 3.

T h e basic idea is to observe first that T

[n(t, x(t)),* (t, x(t))]dt = 0

ol

t

I-

t

n(s,x(s))as,,(t,x(t))

IT 0

T h e n if r(a,t,~:,X) is used to denote the s u m of the integrands in the definition of h(%t,x(t),u)

as a function of × ~ c(t,x)

~ ~-~ ! f ( t , x , u ) , g ( t , x , u ) , ~ ( t , x , u ) , ~ ( t , x , u )

~ u

u I

then

d@dr-(e't':k ,X

+O(X-×e)) i

> 0 @=0

263 T h i s g i v e s I. l).

T o o b t a i n i . 2), l e t d(t) b e an e l e m e n t of t h e S c h w a r z s p a c e of

infinitely smooth functions with compact support, and Xd(t ) = xe(t) + @ d(t). Then

dh(e'Xd('d@ ) , u ¢ )

[

=0

0=0

gives I. 2).

Condition I. 3) is immediate.

We m a y p r o c e e d now to t h e l i m i t i n g f o r m of T h e o r e m

n e w existence theorem and m a x i m u m

Theorem

2

1 w h i c h g i v e s us a

principle for P r o b l e m P.

A s ¢ c o n v e r g e s to z e r o , x (.) c o n v e r g e s u n i f o r m l y to x (-) and u o P . If,

c o n v e r g e s w e a k * to u ° w i t h Xo(. ), u ° b e i n g a s o l u t i o n p a i r to P r o b l e m furthermore,

the matrix

~u

3u

has full rank along (t,Xo(t), Uo) then the following limits exist:

~(t) :

~r~z(~,t)

X (t) = l i r a L(~, t) ~0 ~(t) : l i m M ( e , t )

~(t) : l i m N ( ~ , t )

and w e have the m a x i m u m

2. t )

principle:

Let

~ ( t , x ( t ) , u) = [~ (t), f(t, x ( t ) , u)] - [x (t), ~o(t, x(t), u)]

264

[~(t),@(t,x(t),u)]- [~(t),,(t,x(t),u)] - g(t, x(t), u)

Then

Jd(t'x°(t)'u°) = um a¢x U g ~yf(t,x o (t),u)

z. z)

[ = -Vf*~ +V~*X + V @ * ~

+ V~;"'~ + Vg*

a.e.

~(T) = 0

evaluated along {t,Xo{t), Uo).

Z. 3)

The multipliers ~i(t) are non negative and ~i(t) = 0 w h e n ~i(t, Xo{t),Uo) < 0;

the multipliers ~i(t) are monotonic non increasing functions of t which are constant along intervals along which %i(t,Xo(t)) < 0 with v.l(T) = 0.

Comments

Again a detailed proof m a y be found in Reference 3.

The m a i n idea

here is that the matrix above, having full rank, has an inverse which allows us to write u

s

-u

o

as a function of the constraint t e r m s ~(t,x (t),u¢), etc. so that the

convergence arguments proceed in a straight-forward manner.

l~efe rence s

i.

Balakrishnan, A. V.,"The Epsilon Technique - A Constructive A p p r o a c h to Optimal Control" in Control Theory and the Calculus of Variations, A. V. Balakrishnan (ed), A c a d e m i c Press, N e w York, 1969

Z.

~vlcShane, E. J., "Optimal Controls, Relaxed and Ordinary, " in M a t h e m a t ical T h e o r y of Control, A. V. Balakrishnan and L. W. Neustadt (eds), A c a d e m i c Press, N e w York, 1967

3.

Mersky, $. ~V. ,An Application of the Epsilon Technique to Control P r o b l e m s with Inequali_~ Con____~straints,Dissertation, University of California, Los Angeles, 1973

4.

Young, L. C. ,Lectures on the Calculus of Variations and Optimal Control Theory, W. B. Saunders Co., Philadelphia, 1969

OPTIMAL CONTROL OF SYSTEMS GOVERNED BY VARIATIONAL INEQUALITIES J.P. YVON (IRIA 78 - ROCQUENCOURT - FRANCE)

SUMMARY In many physical situations, systems are not represented by equations but by variationnal inequalities : a typical case is systems involving semi-porous mediums but there are many other examples (cf. e.g. Duvaut-Lions [4]). This paper (1)is devoted to the study of optimal control problems for such systems. As in the case of partial differential equations we are led to consider the analogous separation between elliptic and parabolic systems ; this is studied first and then we give two algorithms with application to a biochemical-example. I - ELLIPTIC INEQUALITIES Let us define - V Hilbert space, K closed convex subset of V, - a(y,z) bilinear form on V, continuous and positive definite, - j(z) convex %.s.c. functional on V, and -

U Hilbert space, N ad

-

B E

~(~;

V')

a closed convex subset of

.

Then we consider the following problem : Problem E O

For each

v EU

(I.|)

find

y E K

a(y,~-y)

where

f

solution of

+ j(~)-j(y) >i (f+Bv,@-y)

V ~ E K

is given in V'.

Theorem 1. I Under the following hypothesis Ii [1.2)

a(" , ")

is c°ercive : a(~,~) > - ~

f

~>

0

vuEV

or j(.)

is strictly convex

there is a unique solution y(v) to Problem E . O

For the proof of this theorem cf. Lions-Stampaeehia -

~ Hilbert space and

-

z d given in

C

[6I. We introduce now :

E ~(V;~)

and we consider Problem E I Find (1.3)

u E

~ad

solution of J(u) ,.< J(v)

(I) More details about definitions proofs etc.., will be given in Yvon E8] •

266 where

Theorem

1.2

If we assume (i)

Nad

li) If

(or v > 0

m --~m weakly

--

(1.5)

bounded vn

lim

v

in

in (I.4)) a n d V

and

v ---~ v

......

(B Vn,~n)

n

~ (Bv,~),

then nhere is at least one solution For the proof lows to take

one uses a minimizing the limit in (1.1).

Remark I The assumption case

(1.6)

ii) of (1.5)

weakly in 4, then . . . . . . .

sequence

to (1.3).

of J(v) and the hypothesis

is a property

of eompacity

(l.5)-ii)

of B. For instance

H ~__.V ~-~V'

(each space dense

in the next with continuousinjeetion) B v = ~ v

we may take

B E~(U;~)

so that

(B If the injection

v,~)vv,

=

(B v,~) H

from V into H is compact

then we obtain property

II - PARABOLIC We suppose now that we have - V,H Hilbert

spaces,

V ~ H

(|.5)-ii).

SYSTEMS

(as in (1.6)) dense with continuous

injection

so that

V~H = H ~ c_~V ~ - a(y,z) bilinear form on V, symmetric and coercive, - f given in L2(O,T;H), - j(z) a convex £.s.c. functional on V with domain D(j) = {~E V lj(~) < + ~ } - Yo

given in the closure

of D(j)

in H.

Then we have Theorem

2.1

With the previous

data, there exists a unique function

y E C (~,T]

(2.1)

;V) ,

y

such that

~"~ E L2(O,T; H)

and satisfying (2.2)

Idy z-y) + a(y,z-y) "dt ~

+ j(z) - j(y) ~ V z E D(j).

(2.3)

y(O) = Yo

Demonstration

in Brezis [2]

Now let us define - ~ H i l b e r t space, -

B E ~(~;L2(O,T;H))

~ad

closed convex

subset of

(f,z-y)

a.e.

in (O,T),

al-

in the

267

and Problem P

o For each

(2.4)

vE

Ua d find

y

satisfying (2.1) and

(~t,z-y) + a(y,z-y) + j(z) - j ( y ) ~

There exists a unique

(f+Bv, z-y) P O . Now let us introduce

y(v) solution of Problem

- ~ Hilbert space and C E ~(L2(O,T;V); ~) - z d given in and Problem P1 Find

u 6 Uad

(2.5)

such that J(u) 10

Theorem 2.2 w-T{h the following hypothesis I i) The injection from (2.7)

ii) ~ d

is bounded

there exists at least one solution u

V

into H is compact,

(or v >0)

to Problem

P1 "

An example Let Q an open set of ~ n F its boundary and consider the system ~t

-f~y = v

O and (2.9)

= Yo

in Q

in

Q x ]"O,T [

Yo

given in L2(Q)

jO

if

r < h

kr

if

r >/ h

h,k > 0 .

¢(r)

In order to set properly the inequality associated with relations (2.8) le~ H=L2(Q) V = HI(Q) U = L2(Q) (2.10)

a(y,z) = JQI

i~i. ~Y(x) 8z--~-(x) dx •= ~ x i ~ xi ~0

(2.11) so that

j(z) =/F

F[z(y)]d Y

with

F(r) =

if

ri

h

Ik(r2_h2)

if

r >z h

y(v) is the unique solution of the variationnal inequality :

268 ~dd-~tv ,z-y(v)) + a(y(v)~z-y(v))

(2.

+ j(z) - j(y(v))

~ (v,z-y(v)) 2 e

•

12" I Y(V)It=o

= Yo

The cost functional (2. !3)

(~)

is J(v) =

- zdl 2 m~ dt + v

]

Then if ~ ; is bounded or v > 0 lution of ~ 5 ) with (2.13).

[[ V[l~

V ~0

there exists at least one optimal control

U

so-

Remark 2.1 As in the elliptic ease the main difficulty of the problem (theoretically and numerically) is the non differentiability of the mapping (2.14)

v ~y(v)

solution of

Problem

Po

(or

Eo).

So that the question of necessary optimal conditions from u is, as far as we know, yet opened. For some results towards this direction el. F. Mignot [ 7 ] III-

DUALITY APPROACH

Using the ideas submitted in a paper from Cea-Glowinski-Nedelec ~ ] one can obtain a dual formulation of the variationnal inequality. For reason of simplicity we suppose that we are in the elliptic case and that the variationnal inequality comes from the minimization problem : (3. 1)

Inf ½ a ( % 9 ) ~E V

+ j (9) - (f + Bv~9)

Then the fundamental assumptions are : There exists a Banach space L, a closed convex bounded set A o f and an operator G (non necessarily linear) from V into L such that (3.2)

j(~) = S ~ A

L' with 0 E A'

(I)

Now we can re,trite ~he problem (3.1) in the form (3.3)

!nf ~p EV

Sup ~ EA

~(~,~;v)

with (3.4)

1

~(~,~9

v) = ~ a(~,~) + < ~ ,G(~) > -

(f+Bv,~).

The dual formulation of (3.3) is (3.5)

Sup

Inf

~E A

~EV

~(~,~;v)

Example 3 We take the analogue of example 2. The problem is in the general form of (3.1) with a(.,,) and j(.) given by (2.10) (2.11). So that we have L =

LI(F)

L' = L~(F)

!l = {~ 6 e~(r) I 0 ~ ~(~) 4 I

a.e. on

F} .

and ~(?)

= k~

(2(y)

_ h 2)

which is a non linear operator from V = H I( ~

into

L~(F).

(]) Here denotes the duality product between L T

and

L.

269

Theorem 3.1 Under the following hyp0thesis IFor ea__ch (3.6)

k E A

the mapping

-+

L

is convex i.s.e.,

there exists a saddle point for ~(.,.;v) The proof is an application of the theorem of KY Fan-Sion. Theorem 3.2 If

G(~)

is continuous from

and if assumption (3.6) holds,

V- weak into L'-weake

then M(k) =;~(y(k),k;v) = inf ~(~0,k;v) ~6V is G~teaux diffenriatiable with derivative given by (3.7)

(3.8)

M'(k). ~ = < ~,G(y(k))>

Corollary 3. l A necessary and sufficient condition for (3.9)

< ~-k,G(y(k~))

> >~0

k ~ E A solvin$ the dual problem (3.5) is V

k E A

Corollary 3.2 If kW solve the dual (3.5) then y(k ~) solve the primal (3.3). Now we can state the problem corresponding to the paragraph ] : Optimal control problem A. (3.10)

I

B.

For each of

v E Uad

Sup ~EA Find

compute

Inf ~ EV

u E Uad

k(v)

and y(v) = y(k(v)) solution

;£ (~0,~;v)

such that

J(u) ~< J(v)

with

J

given in (1.4)

Then using the optimality condition (3.9), we can associate to the previous problem the Suboptimal control problem I A.

B. (3.11)

For k fixed in A compute

Inf i

l]Cy(k;v)- Zall2

v 6 ~ad this gives C.

y(k;v) solution of

Inf ~(~,k;v) ~EV Solve the optimal control problem

u(h)

+ v~l ~

and yO~) = y(k;u(k))

Then finally find ~ E A satisfying < k~-k

, G(y(k*))> ~ 0

V k 6 A

Remark 3.1 The previous technique which consists in permuting the determination of u and is due to Begis-Glowinski [i] . Notice that problem (3. ]I) is not equivalent to problem (3.10) this can be shown on very simple counter-examples (cf. e.g. Yvon [8] ). Theorem 3.3 Under assumptions of ~$| and theorem 3.2 there exists at least one solution k'to

270 problem (3.1~)~ IV - REGULARIZATION An other way to avoid the non differentiability of the mapping (2.14) is to approach Problem P! (for instance) by a sequence of problem more regular wich ensure the differentiabillty of cost functions~ We will expose the method in the parabolic case (§2). Fundamental hypothesis° (4.1)

There exists a family of functionnal js (.) of convex functionals on V twice continuously differentiable such that

(4.2)

j (~) + a(~,~) ~

(4,3)

V

lira j ~ ) e~O if

v

--~ r

5

(4.4)

~ (4.5)

y

~E V

= j(~)

~

V@

independant of g ~V

(I)

weakly in L2(O,T;V) as c -~O, then r

J 0 j(y(t))dt

4 lim

There exists a sequence

0 JE(Ye(t))dt z

bounded in

V

such that

j~(z s) = O

Then we define Problem

P

Find

y

(4.6)

oe g

solution of

i ( ~t

' z-Ye) + a(Y~'z-YE)

Ye(O) = Yo

+

Je (z)

- Je(Ys ) ~ (f+Bv,z-y~)

V z EV

Theorem 4.1 For each vE Nad

there is a unique solution

ye(v) to (4.6) such that

y (v) E C( [O,T] ;V). c Furthermore y (v) ~ y(v) in G where y(v) is the solution of Problem P . o With notation of §2 we introduce (4.7)

L2(O,T;V)

J~(v) = llCye(v) - Zdl]~ + V

as

s

~

O

Ilvll~

and the

PIE

Problem Find

ueE~ad

(4.8)

such that Je(ua) ~< Ja(v)

Theorem 4.2 There exists at least one u~ sequence ~E, } of {us} such that

where

(I)

u

solution of (4.8) and as

u , -~ u g is a solution of Problem PI"

For simplicity we assume that

V v ~ Ua d . g -+O

there exists a sub-

in I~

D(j) = D(j~) = V.

(Cf. notations of Th. 2.1)

271 Remark 4 As

je(.)

is in class

C2

the Problem Pos may be rewritten as

dY e ( ~ ,z) + a(ye,z) + (j~(ye),z) = (f+Bv,z)

V

z E V

and Problem PI~ is then an ordinary optimal control problem for parabolic systems. V - APPLICATION TO A BIOCHEMICAL-EXAMPLE The system represents an enzymatic reaction in a membrane with semi-porous boundary. The problem is unidimensional in space and the functions a(x,t), s(x,t), p(x,t) represent.respectively the concentration of activator, substrate and product in the membrane ~j#. In dimension-less variables the problem may be stated as Ida

(5.1)

~2a

la(o,t)

= Vo(t)

La(x,o)

= O

a(l,t) = Vl(t)

0s _ 02__s +o a s t Ox 2 l+a " l+s = O

~ (5.2)

]s(o,t) = So

0 > 0

s(1,t) = ~I

~o,~l E~

|

~

s (x,o)

t

= 0

0 x2

l+a " l+s

1

+ ~(p(o,t)) = 0

(5.3)

I ~x (l,t) + +(p(l,t))

0

p(x,o) = o where

~(r)

is real function given in (2.9).

Control variables are

vo

and

oo

v! :

co

U = L (O,T) x L (O,T) and O ~< vi(t ) ~< M

~ad = {v E

a.e. on (O,T),

i=1,2 }

The cost function is

(5.4)

J(v) =

J

(o,t)-

Zo(t)12dt+

z! (t) 1 2dt

0

Theorem 5.1 The system ( 5 . 1 ) . . . ( 5 . 3 )

a d m i t s a unique s o l u t i o n

a(v),s(v),p(v).

(I) For more details about enzymatic systems cf. Kernevez

[5] .

272

Theorem 5.2 There exist at least one $,iven bi

uE~ d

satisfying

J(u~

J(v)

V v E l~d

with

J(v)

(5.4). VI - NUMERICAL RESULTS

Example

I To give comparative numerical results on the two types of algorithm we have

considered first the example of § ll.Computation have been performed with = )O,I[ and

zd

so that

(61)

J(v) = 2

f~ l~x(l,t) - Zd(t) I2dt +

(solution is sy~netric by changing

Represents method

r = { O } U { I}

only function of time so that the cost function is

x

in

2 ~ !I~Iu

l-x).

the state corresponding to an "optimal control" computed by duality

(~III), The threshold is given by h=0.5.

Fisure 2 Gives comparison between regularization

and duality on the same example. The

suboptimality of duality is clear on this picture, Actually the "optimal" values of cost are : duality : 4. regularization

: O,36

10

-2

!O-2

Remark 6.1 In the previous examples ~ in (6.1) has been taken near zero so that the opti~ mal state may fit z d

as well as possible.

Example 2 (Bio-chemical example of ~V). As an example 1 the problem has been considered completely symmetric with a unique control

v(t) so that boundary conditions a(o,t)

Figure 3 and F i ~

= a(1,t)

in (5,1) are

= v(t)~

4

give optimal control and corresponding optimal value of the state computed by regularization,

Figure 3 represents also values of optimal control computed for two

values of the regularization this example.

parameter g . The only active constraint is

v ~ O

in

273

Example 1

desired state

0.5

I I

"optimal state"(duality)

I f

0.0

!

0.5

0.25 Fisure |

0.75

1.

Time

Optimal state

Example 1

desired state 0.5

!

! ! I

•

I 0,0

"

O.0

!

.i

i

0.25

regularization

:~ualit~ I I

7,

'

0.5 Figure 2

Optimal state

I

0.75

I.

•Time

274

IIv(t)

A /\\

O.03

Example 2

",\,{ :

s=

10 - 5

!'\

0.02

~ O

~ S

O"

#|

it"

iI |

0.01

:11

/.

i!t

i

10 -1

// i 0.75

0.5

0.25

Figure 3

.Time

t

Optimal control

Example 2

s

=

I0-5

0.5

0.3

J O. 0

i

. ~

U--

_

'Optimal state"

....

/.,,,!i ............................ ~'~

o!~

! Fi.$ure 4

Optimal sta~.

o'~

~ime

275

Vll - REFERENCES

(i)

D. Begis H. Glowinski

(2)

H. Brezis

(3)

J

"Dual num. meth. for some variational problem..." in Techniques of optimization. Academic Press (1972). "Probl~mes unilat~raux") Journal of Math. pures et appliqu~es 51, (]972).

tea

R. Glowinski

"Minimisation de fonctionnelles non diff~rentiables", Proceedings of the Dundee Num. Anal. Symp. (1972).

J.C. Nedelec (4)

G. Duvaut

"Les in~quations en m~canique et en physique", Dunod Paris (1972)

J.L. Lions (5)

J.P. Kernevez

"Evolution et contr$1e des syst~mes bio-math~matiques" Thgse, Paris (1972).

(6)

J.L. Lions

"Variational Inequalities", Comm. on pure and app. math.

G. Stampacchia vol XX, pp. 439-519 (1967). (7)

F. Mignot

S~minaire Lions-Brezis

(8)

J.P. Yvon

Th~se Paris 1973.

Paris 1972-1973.

ON

DETERMINING

THE

OPTI~L

SUBMANIFOLDS

VALUE

SURFACE

OF

HAS

Harold

AN

L.

STATE

SPACE

INFINITE

WHERE

THE

DERIVATIVE

Stalford

Radar Analysis Stsff Radar Division Naval Resesrch Laboratory Washington, D.C. 20375

ABSTRACT The

problem

control

process

surface

often

out of

of

which

the

solving the

is

investigated.

the

first

one

state

the is

dimension

examples

are

the

an

In

infinite

of entire

in

less

than

provided

An

set.

cost

produces

optimal

general,

the

classes.

a

Second,

there remain

are

from

consists

cannot Our

be

which is

of

We

is

to

In

submanifolds for

of

the

establishing

shall

points

determine

state

with-

necessity

submsnifolds state

space.

of

the

condition.

infinite

optimal at

approaching

at

is

least

the

optimal the

paper of

such

the

value every

surface.

point.

In

distinct

surface tangents

not

state

smooth.

is to The

approaching

smooth. the third

tangent

class.

first

This

calculate terminal

three

the

one

latter

derivative

equstions

the

to

to the above

smooth belonging

this

to

values

all

where

space.

cost

surface

where

is

state

where

the

solving

the

certain derived

The

the

points

where

investigate

an

is

for

problems

call

points of

where

without

practice~

set

points

those

cost of

established

utility

initial

necessarily

of

the

but

of

optimal

we

not

consists

derivative

problem.

dition

surface

those

only

the

control any

the

surface

bounded.

desire

infinite

plotting

bounded

be

optimal

INTRODUCTION optimal

have

optimal

problem.

dimension

an

points

can

but

illustrate

of

condition

control

the

to

transfer

we

necessary

theorem,

solving

surface

First~

surface class

a

value

A

in

and

the at

submanifolds

of

Calculating

space An

objective

optimal

surface

practice,

optimal

proved

value

derivative

such

I.

the

optimal

space.

equations

condition

having Three

obtaining

possesses

submanifolds with

of

value entire will

presents

surface optimal

occur

has

along

a necessary

subm~nifolds.

an

control smooth con-

277 We

shall

which

the

now

define

ensuing

II. The their

family

that

in

are

have

needed

Q.

elements

These

U,

optimal

by

where

f: E n x E TM ~ E n is a c o n t i n u o u s

state

is d e s c r i b e d

u(t)),

Constraints

the set valued

u(t)

motion

are

four

a function

space

dynamical by

of

elements

behavior

means

of

the

E Em

function.

The e v o l u t i o n

in the state

systems

(that

is,

in the

f an explicit

t itself. with

the two elements

of all L e b e s g u e whose

functions

of

space X, an open

set c o n t a i n e d

is e q u ip p e d

intervals

on the control

the basic

values

have range

in ~ are given

U

: X ~ set of all compact

where

U is a c o n t i n u o u s

in

implicitly

is p r e c i s e l y

subsets

control

A

set value

function.

the set of control

~

entirely

in

val

tf).

~(tf)

of the d i f f e r e n t i a l

function

trajectory

[to, is

terminating

and given

: [to,

the

state An

tf] space

initial

~ E n is X

admissible

contained or

by

of E m,

For each state x,

values

available

the set

to the controller

at the state x. A solution

Q

measurable

function

(2)

U(x)

The

have

equation

space ~ is the space

of time t on bounded

and

is modeled

of ~ is time

of the process

by

seven

®)

set ® is a closed

For n o n - a u t o n o m o u s

The f u n c t i o n

functions

state

by a point m o v i n g

The c o n t r o l l e r

for

differential

processes

(X and

r e ( t ) E En,

of t), one c o m p o n e n t

and U.

E m.

the

The terminal

of X.

control

hereafter,

f in

The

subsequently.

process,

ordinary

described

E n.

sets

~(t)

closure

processes

investigation

of

state

optimal

described

under

systems

of

(1)

funct i o n

PROCESSES

space

go ) , two

function

of E n.

CONTROL

evolution

velocity

subset

control

processes

state

= f(m(t),

optimal

Euclidean such

and

are

control

OPTIN[AL

control

define

fo'

of

governed

their

to

(f,

an

optimal

n-dimensional

functions

of

OF

behavior

and

a point

family

holds.

A FAMILY

of

dynamical

equations

the

theory

final

in

the time

to

all

times

trajectory

is

for

(i) for some m e a s u r a b l e

conditions

said

terminal for

equation

set

0.

a terminating

be

is called

admissible t contained

said

to

The

time

be

admissible

tf

a trajectory.

if

it

in

the

lies

terminating is

called

trajectory.

interif the

278

The

time

have

to

it

is

tf

belongs

be

the

constrained

A control has

at

such

to

same to

be

function

least

that

the

one

fixed

by

U(~(t)) $ corresponds

~);

for

the

tf]

corresponding

of

[to,

time

u:[to,

u(t)E

trajectory

interval

terminating

terminal

~ Em

is

all

the

not

set

9.

to

be

in

control

necessarily

trajectories

unless

admissible

trajectory

t contained

to

does

said

admissible

for

tf

distinct

~:[to,

[to,

tf).

function

u

if tf)

it

~ X

Here,

the

if

t

~(t)

= ~(co)

f(~(T),

+ f

u(~)) dr

4o for

all

only

t contained

continuous,

necessarily Let sible ing

unique x ° be

control

each

function The

set

(3)

J(Xo,

tf]

~ E m having

C(Xo)

emanating

, let

T(Xo;U)

satisfying

to

be

to

the

be

u(t)

transferred

initial

time

specified.

~

u)

the

domain

function ~

denotes

the

In

is

space

f

o the

by

continuous of

is

from

set

the

to

are

of

be

not

of

one

the

set

corresponding for

all

admis-

terminat-

control

Xo,

all all

Lebesgue

the

of

of

function

terminating to

the

con-

t contained

in

the

of

Septuple

functions, measurable

go

the

final

the

ter-

time

tf

is

criterion

u(T)) dr

go

is

a real

valued

a neighborhood

valued

bounded

of

The

family

of

(f,

U,

go'

fo'

optimal X,

X

9,

J(xo,

the

and

open

in

with

the

~,

tra-

u)

where

processes f,

differentiable, is

set

transfer.

control ~)

continuously terminal

function

C(x o)

number with

continuously

controls,

to

real

associated

the

the

continuous

u belongs

u).

is

in X to

o

function [(Xo;

while

fo(~CT),

on

performance

a member

fixed,

function

a real

x ° contained

performance

+ftf

defined

control

a member value

summary,

represented are

where

function

E n x E m,

jectory

(I)

least

For

C U(~(t))

t o is The

= go(~(tf))

minimized

differentiable Q,

from

the at

x o.

denote

~ emanating

and

denote

from

required

u.

u:[to,

t is

function

functions

is

9;

necessarily

control

f is

equation

u.

state

not

since

C(x o)

u, of

that,

differential

Let

trajectories

domain

minal

for

Note

the

in X.

in

admissible

tf]. to

trajectory

u contained

the

[to,

contained

admissible

trol

in

solutions

E n,

U, ~

and

is

and is

3 is

fo the

a

279

closed

set

optimal

sontained

control

in

the

III. Let tion

be contained o be contained in

in T(xo; all

u*).

The

control in

If is

the

pair

for

function

for

from

x to

the

space

X.

the

Some placed

x,

on

the

F denote

this

family

of

V

: X~

of

the

optimal

The

Xo,

func-

contained

optimal

at

for

trajectories

is

then

all

x ° if,

for

satisfied:

the

If an

optimal

state

space

denotes

the

function V

V

is well

value

needed

value

disjoint

be

value

J(xo,

pair

(u*,

X then

we

~*,

u*)

~*)

have

a

is

optimal

transfer

called

defined

function

on

above

cost

the

optimal

the

entire

the

state

state space

surface. in

order

function

V.

A decomposition of

at

V(x)

optimal

are

be and

inequality

the

that

value

to

C(x o)

control

~*

E1

set. suppose

the

numbers:

value

We

Let

trajectory

u)

in

real

optimal

i.

~,

X.

the

said

in

V(Xo).

the

terminal

collection

is

optimal

be

the

space

following

is to

definitions

Definition able

~*)

into

A plot

called

Let

FUNCTION

let

~*)

x o contained

a state

function.

is

(u*,

X

value

state and

~ J(x o,

defined

from

Thus,

the

u*)

every

the

(u*,

u),

~*,

arbitrarily

exists

X.

VALUE

u contained

T(Xo;

J(x o,

in

C(x o)

pair

functions

contained

of

OPTIMAL

x

u*

closure

processes.

D of

to

the

subsets

describe

state

whose

an

space

X

is

X.

union

assumption

is

a denumer-

This

is

usually

Y

written

as

D = .~Xo,

Xj

: j E Jl

where

J is

a denumerable

index

set

for

l

the

members

Definition

of

D other

2.

decomposition

than

A regular

D

X o.

decomposition

o,.

Xj

: j

D of

such

the

that

state

is

space

open

and

X is dense

a in

I

X and

such

submanifold

that of

for

each

X ° is o p e n submanifold Let

to b e c o n t i n u o u s l y

is

a continuously

differentiable

3

Since

3.

X.

E n.

ferential Definition

j E J,

in X,

it

follows

of d i m e n s i o n

B be

a subset

differentisble

that

X ° is a c o n t i n u o u s l y

dif-

n of E n. of

E n.

on B

A mapping if

there

F

: B -

is s n o p e n

E 1 is s a i d set

W

280

containing

3

tinuously

such

We

are

now

unresolved optimal

in

control

physical

I.

X such

ferentiable

in

examples

There that

exists

value

in nature.

control m o d e l

is s h o w n

surface

submanifo!d

tion can fail its place.

from

contained

type suing

an

to have

an of

satisfied

by

control

models

D of the state

V is c o n t i n u o u s l y

control

processes

Vincent

dif-

space. we

introduce

it is readily

that

[5] p r e s e n t s

crops.

Since

is c o n t i n u -

problems

problem where

a tear or split

is

theory tears

subset

and

Therein,

extending

the o p t i m a l

along

the c o n t i n u i t y

another

satisfied

an

the o b j e c t i v e

a

assump-

assumption

to take

if the optimal

value

S

to

$

a

function

S

to

C

if

neighborhood

: C is

closed

~

~

of X whose closure o V when restricted set

C

of

differentiable

V 1 V1

let X. be a m e m b e r of the r e g u l a r J on the s u b m a n i f o l d X.. 3

open

function

from

E1

is

on

to C

in

the

topo~

S has

a

such

continu-

contains

e

and

~.

be

and

~

contains to

that

on

said

continuous

X

of

a continuous Vl(X)

=

extension

V(x)

for

911

S. an

optimal I.

in

the

satisfies

value

Take

of

Then

manner.

along

problems smooth

which

It in

continuous

and the

resulting

2.

is

scissors deform

The

Assumption

encompasses running

surface

a pair

surface.

differentiable that

an

continuously

Assumption cuts

exists

open

a

in

! is met

value V!

V1

Consider

smooth

is

is

family

optimal

in some control

eat or destroy

Let ~ be a point

There

X. and j optimal

Here,

have

D.

2.

that

ously

function

of m o s t

of the state

Assumption

extension

fies

con-

is continuous.

Assumption

V

value

to be satisfied,

decomposition

of

as

It

the

decomposition

For example,

that

Incidentally~

Suppose

such

for It

well

of an a g r i c u l t u r a l

value

ous

is

of D.

function

insects

the

which

assumption.

herein.

discontinuous

is to control

of

function

theory

as

a regular

the o p t i m a l

on the m e m b e r s

processes

that

a

the

control

considered

model

logy

to

describe

processes

It is, however~

function

to

optimal

constructed

The o p t i m a l

smooth

extended

W.

a position

ous.

optimal

be

on

processes.

Assumption space

F may

conjecture

hypothetically of

that

differentiable

make

surface surface

is

introduced

which

the

submanifolds

the

and

satis-

number

in is so

optimal of

a

a of

continuthe

that

general the

value state

of

en-

surfaces

space.

x

281 IV.

THE

FUNDAMENTAL

EQUATION Let such

(f,

that

D =

U,

its

{Xo, .

Xj

fo'

go'

X,

optimal : j C

OF ®,

value

Jl

be

PARTIAL DYNAMIC ~)

DIFFERENTIAL

PROGRAMMING

be

an

function

optimal

control

V satisfies

a regular

process

in

Assumption

decomposition

with

I.

which

F Let

V

satis-

!

lies

Assumption

partial the

I.

It

differential

open

equation

(4)

is

shown

equation

and

dense

member

is

written

as

holds

for

This where

all

x ~ X

equation

the

will

optimal

D.

For

convenience,

manifold

be

some

a unit

X.. Let 3 row vector

denote

the

function

Definition at

~

4.

in

n-i

the

that

is of

The

must D

of

be

X.

met

on

This

in

determining

points

smooth.

STATEMENT

the

of

the

continuously a point

to

regular

M

at

differentiable

on

~.

decomposition

M

and

Finally,

sub-

let

N(~)

denote

let

N(~) T

N(~).

value

direction

Grad

fundamental

• f(x,v)}

not

~ denote normal

the

programming

member

denote

optimal

normal

limit

M

state

that

subsequently

dimensional let

[4]

decomposition

is

PROBLEM

the

transpose

dynamic the

+ G r a d V(x)

V. Xj

Stalford

. o be utilized

value

Let

of

X o of

0 = MINIMUM { f o ( X , V ) vcv(~

and

in

V(~

function

N(~)

+ h

if

. N(~))

V has

the

an

infinite

derivative

limit

- N(~) T

h~o + cannot

be

positive

bounded.

Suppose an

Recall

tive

that

infinite

at of

Problem.

the

notation

optimal

derivative

that

tions

The

h~o + denotes

that

h

takes

on

each

point

only

values.

an

each the

n-i of

in

at

value

function

least

one

dimensional its

points.

submanifold Vectorially,

of

V has the of one

at

normal E n has is

of

directions two

normal

course

of

M

to

M.

direc-

the

nega-

other.

Determine

the

equation

o f the

submanifold

M without

solving

282

first

the

optimal

control

problem

for

optimal

control

feedback

policies.

VI.

a.

ORTHOGONAL

Let

T(~)

denote

We

desire

to

nates

such

vector

by

(5)

y :

where

K(~)

The chosen

the

new

the

tangential

matrix

K(~) is

the

normal

orthogonal

vectors

linearly

system

vectors

COORDINATES

into

coincides

T(~).

Such

with

to

new the

M at

coordi-

normal

a transformation

is

equation

matrix

vector the

(7)

K(~)

holds

where

K(~) T

is

gonal

transformation

(8)

tangential x coordinates

coordinate

T(~),

that

, K(~) T =

K(~) T

equal

Equation

OF

, x

vector

such

of the

and

the

tangential

a matrix

transform

that

N(a)

given

TRANSFORMATION

to

(4)

is the

can

0 = MINIMUM

composed that

N(~)

of

the

normal

vector

N(~)

and

the

is,

and

the

tangential

vectors

T(ff)

can

be

Equation

(7)

implies

Equation

(5)

is

equation

Identity

the

Matrix

transpose

inverse

of

of

coordinates.

be

rewritten

of

K(~).

K(~).

Thus

an

that ortho-

as

i fo(X'V) + Grad V(x).K(e)T.K(~).f(x,v)}

v C U(x) where ing (9)

x E Xo .

zero

terms

Substituting

0 = MINI~T~ ~ l f o ( X ~ v) v C U(x) + [Grad

for all x C Xo~

Equation

(6)

into

Equation

(8)

and delet-

we o b t a i n + [Grad

V(x).N(~)T]-[N(~).f(x,

V(x).T(~)T].[T(~).f(x,

v)]}

v)]

283

VII.

Let

I Xkl

The

following

and

2.

be

I.

[Grad

This face

in

vation

In

the

is

8.2.1

case

not

to

the

invoking

x k converges

the

to

to

M

slopes

at

Stalford

the

case,

by

~,

state

~.

Assumptions

the

(i x

1

n-l)

bounded.

of

that

the

converges

verified

that

direction

Lemma

is

as

states

tangent

for

T]

X O that

be

limit

V(x k).T(~)

the

this

in can

the

observation

approached.

When

sequence

observation

Observation matrix

any

THEOREM

the

~ remain [3,

optimal

of

p.

finite

84]

value

Assumption

optimal as

&

asserts

function

2 can

be

value

used

sur-

is

this

obser-

is

continuous.

to

amend

the

lemma.

Let

C(~)

be

{N ( ~ ) . f ( c ~ , Note

that

since when

we

number

is

speak

1.

value

is

closure

of

the

set

: v ~ U(~)}.

composed n)

of

a

(i x

of

the

zero

is

a point

If

~

function

N(~),

then

dary

v)

convex

scalars

vector

and

vector

or f(~,

in

one v)

C(~)

dimensional is

a

we,

(n x

in

vectors i)

vector.

essence,

Belo~

mean

the

real

zero.

Theorem

of

Proof. the

C(~)

N(~)

the

has

it

is

an

of

infinite

necessary

the

submanifold

derivative

that

the

in

zero

M where the

vector

the

normal

optimal

direction

belongs

to

the

boun-

C(~).

We

zero

prove

vector

the

theorem

belongs

by

either

showing to

the

that

a contradiction

interior

or

the

arises

exterior

if

of

c(~). Suppose 5

be

some

interior

(I0)

that positive of

C(~).

the

zero

vector

number Let

xk = ~

such

I Xkl

+ hk.N(~

be

)

belongs that

5 and

the

sequence

to -8

the

interior

are defined

contained by

of

C(~). in

the

Let

284 where

the

sequence

to

infinity.

an

integer

~hk~

Since K such

contained

in

in

if

convex

In particular~

and

k ~ K then

v)

of

k

the

z K there

exist such

N(~)~f(xk~

Vl(Xk))