Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một phương pháp phân tích với quy trình cập nhật cho ma trận KKT phát sinh trong điều khiển tối ưu trực tiếp
Tóm tắt
Các bài toán chương trình bậc hai thu được cho các vấn đề điều khiển tối ưu của quy trình động hoặc theo thời gian rời rạc thường liên quan đến ma trận Hessian và ma trận ràng buộc có cấu trúc khối cao, cần được tận dụng bởi các phương pháp số hiệu quả. Trong các phương pháp điểm trong, điều này được thực hiện một cách thanh lịch nhờ vào sự phổ biến của các mã phân tích không xác định đối xứng thưa tiến bộ. Tuy nhiên, với các phương pháp tập hợp tích cực, các kỹ thuật ma trận dày thông thường gặp khó khăn do cần phải cập nhật các ma trận cơ sở trong mỗi lần lặp tập hợp tích cực, do đó làm mất đi cấu trúc thưa sau một vài lần cập nhật. Bài viết này trình bày một phương pháp phân tích mới cho một ma trận KKT phát sinh trong các phương pháp tập hợp tích cực cho điều khiển tối ưu. Nó hoàn toàn tôn trọng cấu trúc khối mà không có bất kỳ sự lấp đầy nào. Đối với phương pháp phân tích này, các cập nhật ma trận được suy ra cho tất cả các trường hợp thay đổi tập hợp tích cực. Điều này cho phép thiết kế một phương pháp tập hợp tích cực có cấu trúc khối rất hiệu quả cho các vấn đề điều khiển tối ưu và điều khiển dự đoán mô hình với các chân trời dài hoặc nhiều tham số điều khiển.
Từ khóa
#Điều khiển tối ưu #phân tích ma trận KKT #phương pháp tập hợp tích cực #phương pháp điểm trong #cơ sở cấu trúc khối.Tài liệu tham khảo
Albersmeyer, J., Bock, H.: Efficient sensitivity generation for large scale dynamic systems. Technical report, SPP 1253 Preprints, University of Erlangen (2009)
Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999)
Bartlett R., Biegler L.: QPSchur: a dual, active set, Schur complement method for large-scale and structured convex quadratic programming algorithm. Optim. Eng. 7, 5–32 (2006)
Bartlett, R., Wächter, A., Biegler, L.: Active set vs. interior point strategies for model predictive control. In: Proceedings of the American Control Conference, Chicago, IL, pp. 4229–4233 (2000)
Benzi M., Golub G., Liesen J.: Numerical solution of saddle-point problems. Acta Numerica 14, 1–137 (2005)
Best M.: An algorithm for the solution of the parametric quadratic programming problem. In: Fischer, H., Riedmüller, B., Schäffler, S. (eds.) Applied Mathematics and Parallel Computing—Festschrift for Klaus Ritter, Chap. 3, pp. 57–76. Physica-Verlag, Heidelberg (1996)
Bock, H., Plitt, K.: A multiple shooting algorithm for direct solution of optimal control problems. In: Proceedings of the 9th IFAC World Congress, pp. 242–247. Pergamon Press, Budapest (1984)
Bock H., Diehl M., Kostina E., Schlöder J.: Constrained optimal feedback control for DAE. In: Biegler, L., Ghattas, O., Heinkenschloss, M., Keyes, D., van Bloemen Waanders, B. (eds.) Real-Time PDE-Constrained Optimization, Chap. 1, pp. 3–24. SIAM, Philadelphia (2007)
Davis T.: Algorithm 832: UMFPACK—an unsymmetric-pattern multifrontal method with a column pre-ordering strategy. ACM Trans. Math. Softw. 30, 196–199 (2004)
Davis T., Hager W.: Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22(4), 997–1013 (2000)
Diehl M., Bock H., Schlöder J., Findeisen R., Nagy Z., Allgöwer F.: Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations. J. Proc. Contr. 12(4), 577–585 (2002)
Diehl M., Kuehl P., Bock H., Schlöder J.: Schnelle Algorithmen für die Zustands- und Parameterschätzung auf bewegten Horizonten. Automatisierungstechnik 54(12), 602–613 (2006)
Duff I.: MA57—a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118–144 (2004)
Duff I., Reid J.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9(3), 302–325 (1983)
Eldersveld S., Saunders M.: A block-LU update for large scale linear programming. SIAM J. Matrix Anal. Appl. 13, 191–201 (1992)
Ferreau H., Bock H., Diehl M.: An online active set strategy to overcome the limitations of explicit MPC. Int. J. Robust Nonlinear Control 18(8), 816–830 (2008)
Fletcher R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987)
Fletcher, R.: Resolving degeneracy in quadratic programming. Numerical Analysis Report NA/135, University of Dundee, Dundee, Scotland (1991)
Fletcher, R.: Approximation Theory and Optimization. Dense Factors of Sparse Matrices, pp. 145–166. Tributes to M.J.D. Powell. Cambridge University Press (1997)
Fletcher, R.: Numerical Analysis 1997. Block Triangular Orderings and Factors for Sparse Matrices in LP, pp. 91–110. Pitman Research Notes in Mathematics, vol. 380. Longman, Harlow (1998)
Gerdts M.: Solving mixed-integer optimal control problems by Branch&Bound: a case study from automobile test-driving with gear shift. Optimal Control Appl. Methods 26, 1–18 (2005)
Gertz E., Wright S.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29, 58–81 (2003)
Gill P., Golub G., Murray W., Saunders M.A.: Methods for modifying matrix factorizations. Math. Comput. 28(126), 505–535 (1974)
Gill P., Murray W., Saunders M., Wright M.: Sparse matrix methods in optimization. SIAM J. Sci. Stat. Comput. 5(3), 562–589 (1984)
Gill P., Murray W., Saunders M., Wright M.: A practical anti-cycling procedure for linearly constrained optimization. Math. Program. 45(1–3), 437–474 (1989)
Gill P., Murray W., Saunders M., Wright M.: Inertia-controlling methods for general quadratic programming. SIAM Rev. 33(1), 1–36 (1991)
Gill, P., Murray, W., Saunders, M.: User’s Guide For QPOPT 1.0: A Fortran Package for Quadratic Programming (1995)
Golub G., van Loan C.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Hall J., McKinnon K.: The simplest examples where the simplex method cycles and conditions where the EXPAND method fails to prevent cycling. Math. Program. Ser. A & B 100(1), 133–150 (2004)
Han S.: Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program. 11, 263–282 (1976)
Haseltine E., Rawlings J.: Critical evaluation of extended Kalman filtering and moving-horizon estimation. Ind. Eng. Chem. Res. 44, 2451–2460 (2005)
Huynh, H.: A large-scale quadratic programming solver based on block-LU updates of the KKT system. PhD thesis, Stanford University (2008)
Kirches C., Sager S., Bock H., Schlöder J.: Time-optimal control of automobile test drives with gear shifts. Optimal Control Appl. Methods 31(2), 137–153 (2010)
Kirches C., Bock H., Schlöder J., Sager S.: Block structured quadratic programming for the direct multiple shooting method for optimal control. Optim. Methods Softw. 26(2), 239–257 (2011)
Leineweber D., Bauer I., Schäfer A., Bock H., Schlöder J.: An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization (Parts I and II). Comput. Chem. Eng. 27, 157–174 (2003)
Nocedal J., Wright S.: Numerical Optimization, 2nd edn. Springer, Berlin, Heidelberg, New York (2006)
Powell M.: Algorithms for nonlinear constraints that use Lagrangian functions. Math. Program. 14(3), 224–248 (1978)
Powell, M.: ZQPCVX: a Fortran subroutine for convex quadratic programming. Technical report, Department of Applied Mathematics and Theoretical Physics, Cambridge University (1983)
Schmid C., Biegler L.: Quadratic programming methods for tailored reduced Hessian SQP. Comput. Chem. Eng. 18(9), 817–832 (1994)
Steinbach, M.: Fast recursive SQP methods for large-scale optimal control problems. PhD thesis, Ruprecht-Karls-Universität Heidelberg (1995)
Vanderbei R.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 11(1–4), 451–484 (1999)
Wächter A., Biegler L.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)
Wirsching, L., Albersmeyer, J., Kühl, P., Diehl, M., Bock, H.: An adjoint-based numerical method for fast nonlinear model predictive control. In: Chung, M., Misra, P. (eds.) Proceedings of the 17th IFAC World Congress, Seoul, Korea, July 6–11, 2008. IFAC-PapersOnLine, vol. 17, pp. 1934–1939 (2008)
Wright, S.: Applying new optimization algorithms to model predictive control. In: Fifth International Conference on Chemical Process Control—CPC V, pp. 147–155. CACHE Publications (1997)