SONC optimization and exact nonnegativity certificates via second-order cone programming

doi:10.1016/j.jsc.2022.08.002

CSpace

	SONC optimization and exact nonnegativity certificates via second-order cone programming
	Magron, Victor 1,2; Wang, Jie 3
	2023-03-01
发表期刊	JOURNAL OF SYMBOLIC COMPUTATION
ISSN	0747-7171
卷号	115 页码:346-370
摘要	The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a roundingprojection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables.(c) 2022 Elsevier Ltd. All rights reserved.
关键词	Sum of nonnegative circuit polynomials Second -order cone programming Polynomial optimization Sum of binomial squares Rounding -projection algorithm Exact nonnegativity certificate
DOI	10.1016/j.jsc.2022.08.002
收录类别	SCI
语种	英语
资助项目	Tremplin ERC Stg Grant[ANR-18-ERC2-0004-01] ; FMJH Program PGMO ; EDF ; Thales ; Orange et Criteo ; European Union[813211] ; AI Interdisciplinary Institute ANITI[ANR-19-PI3A-0004]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000860188200016
出版者	ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/60969
专题	中国科学院数学与系统科学研究院
通讯作者	Magron, Victor
作者单位	1.CNRS LAAS, 7 Ave colonel Roche, F-31400 Toulouse, France 2.Inst Math, F-31400 Toulouse, France 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Magron, Victor,Wang, Jie. SONC optimization and exact nonnegativity certificates via second-order cone programming[J]. JOURNAL OF SYMBOLIC COMPUTATION,2023,115:346-370.
APA	Magron, Victor,&Wang, Jie.(2023).SONC optimization and exact nonnegativity certificates via second-order cone programming.JOURNAL OF SYMBOLIC COMPUTATION,115,346-370.
MLA	Magron, Victor,et al."SONC optimization and exact nonnegativity certificates via second-order cone programming".JOURNAL OF SYMBOLIC COMPUTATION 115(2023):346-370.