ON THE COMPLEXITY OF LINEAR-QUADRATIC CONTROL

Authors
Citation
Al. Norman, ON THE COMPLEXITY OF LINEAR-QUADRATIC CONTROL, European journal of operational research, 73(2), 1994, pp. 319-330
Citations number
20
Categorie Soggetti
Management,"Operatione Research & Management Science
ISSN journal
03772217
Volume
73
Issue
2
Year of publication
1994
Pages
319 - 330
Database
ISI
SICI code
0377-2217(1994)73:2<319:OTCOLC>2.0.ZU;2-1
Abstract
This paper presents an analysis of the computational complexity of the linear quadratic control models commonly used in Economics. These mod els differ in the statistical assumptions concerning the coefficients. The most common assumptions are fixed unknown, fixed known and indepe ndent random. A fourth model to be considered is the MacRae approximat ion. These four models have a nested structure. The computational comp lexity of the first is transfinite. The computational complexity of th e second is linear in the time horizon, T and has the same computation al complexity in the number of states, n as that for matrix multiplica tion of (n X n)-matrices. The computational complexity of the third is n4T. The computational complexity of each iteration of the MacRae app roximation is n4T.