Geometric algorithm for multiparametric linear programming

被引：147

作者：

Borrelli, F ^{[1
]}

Bemporad, A

Morari, M

机构：

[1] ETH, Swiss Fed Inst Technol, Automat Control Lab, Zurich, Switzerland

[2] Univ Siena, Dipartimento Ingn Informaz, I-53100 Siena, Italy

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 2003年 / 118卷 / 03期

关键词：

multiparametric programming; sensitivity analysis; post-optimality analysis; linear programming; optimal control;

D O I：

10.1023/B:JOTA.0000004869.66331.5c

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems.

引用

页码：515 / 540

页数：26

共 22 条

[1] A GEOMETRIC VIEW OF PARAMETRIC LINEAR-PROGRAMMING
ADLER, I
MONTEIRO, RDC
[J]. ALGORITHMICA, 1992, 8 (02) : 161 - 176
[2] The explicit linear quadratic regulator for constrained systems
Bemporad, A
Morari, M
Dua, V
Pistikopoulos, EN
[J]. AUTOMATICA, 2002, 38 (01) : 3 - 20
[3] Model predictive control based on linear programming - The explicit solution
Bemporad, A
Borrelli, F
Morari, M
[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2002, 47 (12) : 1974 - 1985
[4] Convexity recognition of the union of polyhedra
Bemporad, A
Fukuda, K
Torrisi, FD
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2001, 18 (03): : 141 - 154
[5] BERKELAAR A, 1997, INT SERIES OPERATION, V6
[6] Borrelli F., 2001, Hybrid Systems: Computation and Control. 4th International Workshop, HSCC 2001. Proceedings (Lecture Notes in Computer Science Vol.2034), P162
[7] Borrelli F., 2002, THESIS ETH ZURICH
[8] An algorithm for the solution of multiparametric mixed integer linear programming problems
Dua, V
Pistikopoulos, EN
[J]. ANNALS OF OPERATIONS RESEARCH, 2000, 99 (1-4) : 123 - 139
[9] Fiacco A.V., 1983, INTRO SENSITIVITY ST
[10] FILIPPI C, 1997, 12 U PAD DEP PUR APP

← 1 2 3 →