×

zbMATH — the first resource for mathematics

A penalty method for nonlinear programs with set exclusion constraints. (English) Zbl 1461.49016
Summary: A common requirement in optimal control problems arising in autonomous navigation is that the decision variables are constrained to be outside certain sets. Such set exclusion constraints represent obstacles that must be avoided by the motion system. This paper presents a simple and efficient method for solving optimization problems with general set exclusion and implicit constraints. The method embeds the set exclusion constraints in a quadratic penalty framework and solves the inner optimization problems using a proximal algorithm that deals directly with the implicit constraints. We derive convergence results for this method by transforming the generated iterates to points of a reformulated problem with complementarity constraints. Furthermore, the practical application of the solution method is validated in numerical simulations of a model predictive control approach to path planning for a mobile robot. Finally, a runtime comparison with state-of-the-art solvers applied to the problem with complementarity constraints illustrates the efficiency of the proposed method.
MSC:
49J45 Methods involving semicontinuity and convergence; relaxation
90C30 Nonlinear programming
Software:
Ipopt; CasADi; SNOPT; ALGENCAN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, Joel A. E.; Gillis, Joris; Horn, Greg; Rawlings, James B.; Diehl, Moritz, CasADi - A software framework for nonlinear optimization and optimal control, Mathematical Programming Computation, 11, 1, 1-36 (2019) · Zbl 1411.90004
[2] Anitescu, Mihai, Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints, SIAM Journal on Optimization, 16, 1, 120-145 (2005) · Zbl 1099.65050
[3] Bertsekas, Dimitri P., Constrained optimization and Lagrange multiplier methods (1982), Academic Press · Zbl 0572.90067
[4] Birgin, Ernesto G.; Martınez, Josâ Mario, Practical augmented Lagrangian methods for constrained optimization (vol. 10) (2014), SIAM · Zbl 1339.90312
[5] Clarke, Frank H., A new approach to Lagrange multipliers, Mathematics of Operations Research, 1, 2, 165-174 (1976) · Zbl 0404.90100
[6] Cottle, Richard W.; Dantzig, George B., A generalization of the linear complementarity problem, Journal of Combinatorial Theory, 2, 79-90 (1970) · Zbl 0186.23806
[7] Flegel, Michael L., Constraint qualifications and stationarity concepts for mathematical programs with equilibrium constraints / (2005) · Zbl 1147.90397
[8] Gilbert, Elmer; Johnson, Daniel, Distance functions and their application to robot path planning in the presence of obstacles, IEEE Journal of Robotics and Automation, 1, 1, 21-30 (1985)
[9] Gill, Philip E.; Murray, Walter; Saunders, Michael A., SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Review, 47, 1, 99-131 (2005) · Zbl 1210.90176
[10] Hermans, Ben, Patrinos, Panos, & Pipeleers, Goele (2018). A penalty method based approach for autonomous navigation using nonlinear model predictive control. In 6th IFAC conference on nonlinear model predictive control (pp. 268-274).
[11] Izmailov, Alexey F.; Solodov, Mikhail V.; Uskov, E. I., Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints, SIAM Journal on Optimization, 22, 4, 1579-1606 (2012) · Zbl 1274.90385
[12] Leyffer, Sven, Complementarity constraints as nonlinear equations: Theory and numerical experience, (Optimization with multivalued mappings (2006), Springer), 169-208 · Zbl 1190.90240
[13] Leyffer, Sven; López-Calva, Gabriel; Nocedal, Jorge, Interior methods for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 17, 1, 52-77 (2006) · Zbl 1112.90095
[14] Mercy, Tim; Van Parys, Ruben; Pipeleers, Goele, Spline-based motion planning for autonomous guided vehicles in a dynamic environment, IEEE Transactions on Control Systems Technology (2017)
[15] Patel, Rushen B.; Goulart, Paul J., Trajectory generation for aircraft avoidance maneuvers using online optimization, Journal of Guidance, Control, and Dynamics, 34, 1, 218-230 (2011)
[16] Rajamani, Rajesh, Vehicle dynamics and control (2011), Springer Science & Business Media · Zbl 1097.70001
[17] Sathya, Ajay Suresha, Sopasakis, Pantelis, Van Parys, Ruben, Themelis, Andreas, Pipeleers, Goele, & Patrinos, Panos (2018). Embedded nonlinear model predictive control for obstacle avoidance using PANOC. In Proceedings of the 2018 European control conference.
[18] Scheel, Holger; Scholtes, Stefan, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Mathematics of Operations Research, 25, 1, 1-22 (2000) · Zbl 1073.90557
[19] Scholtes, Stefan; Stöhr, Michael, How stringent is the linear independence assumption for mathematical programs with complementarity constraints?, Mathematics of Operations Research, 26, 4, 851-863 (2001) · Zbl 1082.90580
[20] Stella, Lorenzo, Themelis, Andreas, Sopasakis, Pantelis, & Patrinos, Panagiotis (2017). A simple and efficient algorithm for nonlinear model predictive control. In 56th IEEE conference on decision and control (pp. 1939-1944).
[21] Tyrrell Rockafellar, R.; Wets, Roger J.-B., Variational analysis (vol. 317) (2009), Springer Science & Business Media
[22] Wächter, Andreas; Biegler, Lorenz T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57 (2006) · Zbl 1134.90542
[23] Waltz, Richard A.; Nocedal, Jorge, KNITRO user’s manualTechnical report OTC-2003/5 (2003), Northwestern University: Northwestern University Evanston, Illinois
[24] Wang, Peng; Ding, Baocang, A synthesis approach of distributed model predictive control for homogeneous multi-agent system with collision avoidance, International Journal of Control, 87, 1, 52-63 (2014) · Zbl 1317.93022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.