Global Optimization

My colleague Didier Henrion from LAAS and I, have developed a software called GloptiPoly for the global minimization of a multivariate polynomial on a semi-algebraic set. In fact it also solves the  Generalized Moment Problem with polynomial data. This software was among 30 softwares selected (out of 160) as finalists of the EASA software competition in Switzerland (September 2004). The underlying method makes extensive use of recent results from real algebraic geometry on the representation of polynomials, positive on a compact semi-algebraic set. For more details, see: 

  • J.B. Lasserre. Global optimization with polynomials and the problem of moments  SIAM J. Optimization 11 (2001), pp 796--817. 
  • D. Henrion and J.B. Lasserre. GloptiPoly : Global optimization over polynomials with Matlab and SeDuMi, ACM Trans. Math. Soft. 29 (2003), pp. 165--194. 
  • D. Henrion, J.B. Lasserre and Y. Lofberg. GloptiPoly 3: Moments, Optimization and Semidfinite Programming,  Optimization, Methods and Softwares 24 (2009), pp. 761--779 

GloptiPoly has been used in several areas and more recently for solving certain optimization problems in "Quantum Computing", e.g. in: 

  • Complete hierarchies of efficient approximations to problems in entanglement theory  J Eisert, P Hyllus, O Guhne, M Curty - Physical Review A, 2004 
  • Detecting two-party quantum correlations in quantum-key-distribution protocols  M Curty, O Guhne, M Lewenstein, N Lutkenhaus - Physical Review A, 2005. 
  • Upper bound on the secret key rate distillable from effective quantum correlations with imperfect detectors T Moroder, M Curty, N Lutkenhaus - Physical Review A, 2006 
  • Intercept-resend attacks in the Bennett-Brassard 1984 quantum-key-distribution protocol with weak coherent pulse  M Curty, N Lutkenhaus - Physical Review A, 2005 
  • Quantifying entanglement with witness operators Fernando G.S.L. Brandao. Physical Review A 72, 2005. 
  • Deterministic computational complexity of the quantum separability problem L. Ioannou. Quantum Information and Computation, 2006. 
  • Quantum separability and entanglement detection via entanglement-witness search and global optimization L. Ioannou, B.C. Travaglione. Physical Review A 73, 2006. 
  • Better Bell-inequality violation by collective measurements Yeong-Cherng Liang, A.C. Doherty. Physical Review A 73, 2006. 
  • Estimation of the parameters of a bilinear model with applications to submarine detection and system identification R. Abrahamson, S.M. Kay, P. Stoica. Digital Signal Processing 17 (2007), 756--773. 
  • Gain bandwith optimization in two-pump fiber optical parametric amplifiers under bounded zero-dispersion wavelength fluctuations. N. Wong, K.K.-Y. Wong. Optics Communications 272 (2007), 514--520. 
  • Bounds on quantum correlations in Bell-inequality experiments. Yeong-Cherng Liang, A. Doherty. Physical Review A 75, 2007. 
  • A paradox in bosonic energy computations via semidefinite programming relaxations. M. Navascues, A. Garcia-Saez, A. Acin, S. Pironio, M.B. Plenio. New Journal of Physics 15, 2013, 023026.. 

It is also used: 

  • in Strutural Biology: See e.g. the paper: Y. Khoo, A. Singer, D. Cowburn, Integrating NOE and RDC using sum-of-squares relaxation for protein structure determination, J. Biomolecular NMR 68, pp. 163--185, 2017.
  • for Motion Planning in Robotics: See e.g. the algorithm NUROA (Numerical Roadmap Algorithm) and the associated paper: NUROA: A Numerical Roadmap Algorithm, Reza Iraji, Hamidreza Chitsaz, Proceedings IEEE CDC Conference, Los Angeles, December 2014. arXiv:1403.5384
  • For solving the Optimal Power Flow Problem, an important problem for the optimal management of energy networks. See e.g. the recent papers: 

Advanced optimization methods for power systems, P. Panciatici, M.C. Campi, S. Garratti, S.H. Low, D.K. Molzhan, A.X. Sun and L. Wehenkel. Proceedings 18th Power Systems Computation Conference, Wroclaw, Poland, August 2014. 

Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem, D.K. Molzahn and I.A. Hiskens, IEEE Transactions on Power Systems, 2015. arXiv:1404.5071

Global Optimization for power dispatch problems based on theory of moments, J. Tian, H. Wei and J. Tan, Electrical Power and Energy Systems 71, 2015, pp. 184--194. 

  • For solving some Robust Design Optimization problems. See e.g. 

Stochastic simulation and robust design optimization of integrated photonic filters, Tsui-Wei Weng, D. Melati, A. Melloni and L. Daniel. Nanophotonics, July 2016 

Finally, concerning the impact of this methodology in Optimization, see for instance:

  • Optimization over polynomials: Selected Topics, M. Laurent, Proceedings of ICM conference, Seoul, 2014.
  • The Moment-SOS Hierarchy, J.B. Lasserre, Proceedings of ICM conference, Rio de Janeiro, 2014.
and especially for its impact in Combinatorial Optimization and Theoretical Computer Science,
  • Sum-of-Squares proofs and the quest toward optimal algorithms, B. Barak and D. Steurer, Proceedings of ICM conference, Seoul, 2014.
  • High dimensional estimation via Sum-of-Squares proofs, P. Raghavendra, T. Schramm and D. Steurer, Proceedings of ICM conference, Rio de Janeiro, 2018.