Solving polynomial least squares problems via semidefinite programming relaxations

被引：0
作者：
Sunyoung Kim
Masakazu Kojima
机构：
[1] Ewha W. University,Department of Mathematics
[2] Tokyo Institute of Technology,Department of Mathematical and Computing Sciences
来源：
Journal of Global Optimization | 2010年 / 46卷
关键词：
Nonconvex optimization problems; Polynomial least squares problems; Polynomial semidefinite programs; Polynomial second-order cone programs; Sparsity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.
引用
收藏
页码：1 / 23
页数：22
相关论文
共 47 条
  • [1] Borchers B.(1999)SDPLIB 1.2, a library of semidefinite programming test problems Optim. Methods Softw. 11&12 683-690
  • [2] Coleman T.F.(1994)On the convergence of reflective Newton methods for large-scale nonlinear minimization subject to bounds Math. Progr. 67 189-224
  • [3] Li Y.(1996)An interior, trust region approach for nonlinear minimization subject to bounds SIAM J. Optim. 6 418-445
  • [4] Coleman T.F.(1988)Testing a class of methods for solving minimization problems with simple bounds on the variables Math. Comp. 50 399-430
  • [5] Li Y.(2003)Cuter, a constrained and unconstrained testing environment, revisited TOMS 29 373-394
  • [6] Conn A.R.(2006)Convergent relaxations of polynomial matrix inequalities and static output feedback IEEE Trans. Autom. Control 51 192-202
  • [7] Gould N.I.M.(2005)Semidefinite approximation for global unconstrained polynomial optimization SIAM J. Optim. 16 490-514
  • [8] Toint P.L.(2005)Generalized Lagrangian duals and sums of squares relaxations of sparse polynomial optimization problems SIAM J. Optim. 15 697-719
  • [9] Gould N.I.M.(2008)Correlative sparsity in primal-dual interior point methods for LP, SOCP and SDP Appl. Math. Optim. 58 69-88
  • [10] Orban D.(2008)Sparse second order cone programming approaches for convex opimitization problems J. Oper. Res. Soc. Japan 51 241-264
12345