On the Complexity of Using Handelman Relaxation for Solving Polynomial Optimization Problems

被引：0
作者：
Tamba, Tua A. [1 ]
Nazaruddin, Yul Y. [1 ]
机构：
[1] Inst Teknol Bandung, Instrumentat & Control Res Grp, Bandung, Indonesia
来源：
PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON INSTRUMENTATION, CONTROL, AND AUTOMATION (ICA) | 2016年
关键词：
Polynomial optimization; Handelman representation; computational complexity; linear programming; semidefinite programming;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper investigates the computational complexity involved when using Handelman relaxation method for solving multivariable polynomial optimization problems. In particular, the relationship between the degree of the Handelman representation of nonnegative polynomial function over convex polytopic set and the number of decision variables required to prove its existence through linear programming method is characterized. A simulation result to help illustrate the computational complexity and rate of convergence of Handelman relaxation method for solving multivariable polynomial optimization problem is also presented.
引用
收藏
页码：143 / 147
页数：5
相关论文
共 50 条
  • [41] Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems
    P. M. Kleniati
    P. Parpas
    B. Rustem
    Journal of Optimization Theory and Applications, 2010, 145 : 289 - 310
  • [42] On solving a class of fractional semi-infinite polynomial programming problems
    Guo, Feng
    Jiao, Liguo
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2021, 80 (02) : 439 - 481
  • [43] Convex generalized Nash equilibrium problems and polynomial optimization
    Jiawang Nie
    Xindong Tang
    Mathematical Programming, 2023, 198 : 1485 - 1518
  • [44] CONVERGENT RELAXATIONS OF POLYNOMIAL OPTIMIZATION PROBLEMS WITH NONCOMMUTING VARIABLES
    Pironio, S.
    Navascues, M.
    Acin, A.
    SIAM JOURNAL ON OPTIMIZATION, 2010, 20 (05) : 2157 - 2180
  • [45] Convex generalized Nash equilibrium problems and polynomial optimization
    Nie, Jiawang
    Tang, Xindong
    MATHEMATICAL PROGRAMMING, 2023, 198 (02) : 1485 - 1518
  • [46] Efficient linear reformulations for binary polynomial optimization problems
    Elloumi, Sourour
    Verchere, Zoe
    COMPUTERS & OPERATIONS RESEARCH, 2023, 155
  • [47] WELL-POSEDNESS IN UNCONSTRAINED POLYNOMIAL OPTIMIZATION PROBLEMS
    Van Doat Dang
    Huy Vui Ha
    Tien-So'n Pham
    SIAM JOURNAL ON OPTIMIZATION, 2016, 26 (03) : 1411 - 1428
  • [48] Real Radicals and Finite Convergence of Polynomial Optimization Problems
    Sekiguchi, Yoshiyuki
    ADVANCES IN MATHEMATICAL ECONOMICS, VOL 20, 2016, 20 : 89 - 99
  • [49] A POLYNOMIAL OPTIMIZATION APPROACH TO PRINCIPAL-AGENT PROBLEMS
    Renner, Philipp
    Schmedders, Karl
    ECONOMETRICA, 2015, 83 (02) : 729 - 769
  • [50] Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum-Classical Algorithms
    Wurtz, Jonathan
    Sack, Stefan H.
    Wang, Sheng-Tao
    IEEE TRANSACTIONS ON QUANTUM ENGINEERING, 2024, 5
12345