An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems

被引：10
|
作者：
Bertsimas, Dimitris [1 ]
Freund, Robert M. [1 ]
Sun, Xu Andy [2 ]
机构：
[1] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA
[2] IBM Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA
来源：
OPTIMIZATION METHODS & SOFTWARE | 2013年 / 28卷 / 03期
关键词：
polynomial optimization; semidefinite programming relaxation; accelerated first order methods; global optimization; GLOBAL OPTIMIZATION; SEMIDEFINITE; MATLAB;
D O I：
10.1080/10556788.2012.656114
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Our interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.
引用
收藏
页码：424 / 441
页数：18
相关论文
共 50 条
  • [31] Canonical primal-dual algorithm for solving fourth-order polynomial minimization problems
    Zhou, Xiaojun
    Gao, David Yang
    Yang, Chunhua
    APPLIED MATHEMATICS AND COMPUTATION, 2014, 227 : 246 - 255
  • [32] Standard bi-quadratic optimization problems and unconstrained polynomial reformulations
    Immanuel M. Bomze
    Chen Ling
    Liqun Qi
    Xinzhen Zhang
    Journal of Global Optimization, 2012, 52 : 663 - 687
  • [33] Standard bi-quadratic optimization problems and unconstrained polynomial reformulations
    Bomze, Immanuel M.
    Ling, Chen
    Qi, Liqun
    Zhang, Xinzhen
    JOURNAL OF GLOBAL OPTIMIZATION, 2012, 52 (04) : 663 - 687
  • [34] Vector Direction of Filled Function Method on Solving Unconstrained Global Optimization Problem
    Napitupulu, Herlina
    Bin Mohd, Ismail
    PROCEEDINGS OF THE 7TH SEAMS UGM INTERNATIONAL CONFERENCE ON MATHEMATICS AND ITS APPLICATIONS 2015: ENHANCING THE ROLE OF MATHEMATICS IN INTERDISCIPLINARY RESEARCH, 2016, 1707
  • [35] Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems
    Elloumi, Sourour
    Lambert, Amelie
    Lazare, Arnaud
    2019 6TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT 2019), 2019, : 1498 - 1503
  • [36] A fast method for binary programming using first-order derivatives, with application to topology optimization with buckling constraints
    Browne, P. A.
    Budd, C.
    Gould, N. I. M.
    Kim, H. A.
    Scott, J. A.
    INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 2012, 92 (12) : 1026 - 1043
  • [37] Solving polynomial optimization problems via the truncated tangency variety and sums of squares
    Ha, Huy Vui
    Pham, Tien Son
    JOURNAL OF PURE AND APPLIED ALGEBRA, 2009, 213 (11) : 2167 - 2176
  • [38] Convergence of a first-order consensus-based global optimization algorithm
    Ha, Seung-Yeal
    Jin, Shi
    Kim, Doheon
    MATHEMATICAL MODELS & METHODS IN APPLIED SCIENCES, 2020, 30 (12) : 2417 - 2444
  • [39] An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
    Yang, Heng
    Liang, Ling
    Carlone, Luca
    Toh, Kim-Chuan
    MATHEMATICAL PROGRAMMING, 2023, 201 (1-2) : 409 - 472
  • [40] On the Complexity of Using Handelman Relaxation for Solving Polynomial Optimization Problems
    Tamba, Tua A.
    Nazaruddin, Yul Y.
    PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON INSTRUMENTATION, CONTROL, AND AUTOMATION (ICA), 2016, : 143 - 147
12345