×

zbMATH — the first resource for mathematics

Some applications of polynomial optimization in operations research and real-time decision making. (English) Zbl 1345.90085
Summary: We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (1) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (2) computing real-time certificates of collision avoidance for a simple model of an unmanned vehicle (UV) navigating through a cluttered environment, and (3) designing a nonlinear hovering controller for a quadrotor UV, which has recently been used for load transportation. On our smaller-scale applications, we apply the sum of squares (SOS) relaxation and solve the underlying problems with semidefinite programming. On the larger-scale or real-time applications, we use our recently introduced “SDSOS Optimization” techniques which result in second order cone programs. To the best of our knowledge, this is the first study of real-time applications of sum of squares techniques in optimization and control. No knowledge in dynamics and control is assumed from the reader.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C22 Semidefinite programming
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Gurobi optimizer reference manual (2012). http://www.gurobi.com · Zbl 0637.90078
[2] MOSEK reference manual, 2013. Version 7. Latest version available at http://www.mosek.com/
[3] Ahmadi, A.A.: Algebraic relaxations and hardness results in polynomial optimization and Lyapunov analysis. PhD thesis, Massachusetts Institute of Technology (2011). http://aaa.princeton.edu/publications · Zbl 1149.90124
[4] Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. In: Proceedings of the 48th Annual Conference on Information Sciences and Systems. Princeton University (2014) · Zbl 1098.15014
[5] Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to SOS optimization (2014, in preparation). http://aaa.princeton.edu/publications · Zbl 07067257
[6] Alizadeh, F; Goldfarb, D, Second-order cone programming, Math. Program., 95, 3-51, (2003) · Zbl 1153.90522
[7] Anderson, B.D.O., Moore, J.B.: Optimal Control: Linear Quadratic Methods. Prentice-Hall Inc, Upper Saddle River (1990) · Zbl 0751.49013
[8] Barry, A.J., Majumdar, A., Tedrake, R.: Safety verification of reactive controllers for UAV flight in cluttered environments using barrier certificates. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 484-490. IEEE (2012) · Zbl 1366.93711
[9] Berman, O., Jaillet, P., Simchi-Levi, D.: Location-routing problems with uncertainty. Facility location: a survey of applications and methods, vol. 106, pp. 427-452 (1995) · Zbl 1149.90124
[10] Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. 1. Athena Scientific Belmont, MA (1995) · Zbl 0904.90170
[11] Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization (1997)
[12] Blackmore, L., Acikmese, B., Scharf, D.P.: Minimum landing error powered descent guidance for Mars landing using convex optimization. AIAA J. Guid. Control Dyn. 33, (2010)
[13] Boman, EG; Chen, D; Parekh, O; Toledo, S, On factor width and symmetric H-matrices, Linear Algebra Appl., 405, 239-248, (2005) · Zbl 1098.15014
[14] Commander, C.W.: Optimization problems in telecommunications with military applications. PhD thesis, University of Florida (2007) · Zbl 0637.90078
[15] Commander, CW; Pardalos, PM; Ryabchenko, V; Shylo, O; Uryasev, S; Zrazhevsky, G, Jamming communication networks under complete uncertainty, Optim. Lett., 2, 53-70, (2008) · Zbl 1145.94008
[16] Commander, CW; Pardalos, PM; Ryabchenko, V; Uryasev, S; Zrazhevsky, G, The wireless network jamming problem, J. Combin. Optim., 14, 481-498, (2007) · Zbl 1149.90124
[17] Domahidi, A., Chu, E., Boyd, S.: ECOS: An SOCP solver for embedded systems. In: European Control Conference (ECC), pp. 3071-3076. IEEE (2013) · Zbl 0253.14001
[18] Dubins, L, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, Am. J. Math., 79, 497-516, (1957) · Zbl 0098.35401
[19] Hilbert, D.: Über die Darstellung Definiter Formen als Summe von Formenquadraten. Math. Ann. 32 (1888) · JFM 20.0198.02
[20] Hoffmann, G.M., Huang, H., Waslander, S.L., Tomlin, C.J.: Quadrotor helicopter flight dynamics and control: theory and experiment. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference, pp. 1-20 (2007) · Zbl 1366.93711
[21] Jarvis-Wloszek, Z., Feeley, R., Tan, W., Sun, K., Packard, A.: Some controls applications of sum of squares programming. In: 42nd IEEE Conference on Decision and Control, vol. 5, pp. 4676-4681 (2003)
[22] Karlof, J.K.: Integer Programming: Theory and Practice. CRC Press, Boca Raton (2005) · Zbl 1073.90002
[23] Khalil, H.: Nonlinear Systems, 3rd edn. Prentice Hall, Englewood Cliffs (2002) · Zbl 1003.34002
[24] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157-270. Springer, Berlin (2009) · Zbl 1163.13021
[25] Majumdar, A., Ahmadi, A.A., Tedrake, R.: Control design along trajectories with sums of squares programming. In: Proceedings of the 2013 IEEE International Conference on Robotics and Automation (ICRA) (2013)
[26] Majumdar, A., Ahmadi, A.A., Tedrake, R.: Control and verification of high-dimensional systems via DSOS and SDSOS optimization. In: Proceedings of the 53rd IEEE Conference on Decision and Control (2014)
[27] Majumdar, A., Tedrake, R.: Robust online motion planning with regions of finite time invariance. In: Algorithmic Foundations of Robotics X, pp. 543-558. Springer, Berlin (2013) · Zbl 0845.65023
[28] Mattingley, J; Boyd, S, Real-time convex optimization in signal processing, IEEE Signal Process. Mag., 27, 50-61, (2010) · Zbl 1211.90170
[29] Mattingley, J; Boyd, S, CVXGEN: a code generator for embedded convex optimization, Optim. Eng., 13, 1-27, (2012) · Zbl 1293.65095
[30] Mellinger, D., Michael, N., Kumar, V.: Trajectory generation and control for precise aggressive maneuvers with quadrotors. In: Proceedings of the 12th International Symposium on Experimental Robotics (ISER 2010) (2010)
[31] Mellinger, D., Michael, N., Shomin, M., Kumar, V.: Recent advances in quadrotor capabilities. 2011 IEEE International Conference on Robotics and Automation (2011)
[32] Mellinger, D., Shomin, M., Michael, N., Kumar, V.: Cooperative grasping and transport using multiple quadrotors. In: Proceedings of the International Symposium on Distributed Autonomous Robotic Systems (2010) · Zbl 0845.65023
[33] Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 117-129, (1987) · Zbl 0637.90078
[34] Nie, J; Schweighofer, M, On the complexity of putinar’s positivstellensatz, J. Complex., 23, 135-150, (2007) · Zbl 1143.13028
[35] Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology (2000)
[36] Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2 Ser. B), 293-320 (2003) · Zbl 1043.14018
[37] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[38] Prajna, S., Jadbabaie, A.: Safety verification of hybrid systems using barrier certificates. In: Hybrid Systems: Computation and Control, pp. 477-492. Springer, Berlin (2004) · Zbl 1135.93317
[39] Prajna, S; Jadbabaie, A; Pappas, GJ, A framework for worst-case and stochastic safety verification using barrier certificates, IEEE Trans. Autom. Control, 52, 1415-1428, (2007) · Zbl 1366.93711
[40] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[41] Stengle, G, A nullstellensatz and a positivstellensatz in semialgebraic geometry, Math. Ann., 207, 87-97, (1974) · Zbl 0253.14001
[42] Sturm, J.: SeDuMi version 1.05 (2001). Latest version available at http://sedumi.ie.lehigh.edu/ · Zbl 1293.65095
[43] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
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.