QQ客服 官方微博 反馈留言

	ON DOUBLY POSITIVE SEMIDEFINITE PROGRAMMING RELAXATIONS
	Fu, Taoran1; Ge, Dongdong2; Ye, Yinyu3
	2018
关键词	Doubly nonnegative matrix Semidefinite programming Relaxation quartic optimization
卷号	36
期号	3
DOI	10.4208/jcm.1708-m2017-0130
页码	391-403
英文摘要	Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n(2)) constraints, which makes the SDP solution complexity substantially higher than that for the basic model with O(n) constraints. In this paper, we prove that the doubly-positive SDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQP is symmetric and homogeneous (which represents many classical combinatorial and non-convex optimization problems), the doubly-positive SDP model is equivalent to the basic SDP even without any valid cut. On the other hand, the doubly-positive SDP model could help to tighten the bound up to 36%, but no more. Finally, we manage to extend some of the previous results to quartic models.
会议录出版者	GLOBAL SCIENCE PRESS
会议录出版地	ROOM 3208, CENTRAL PLAZA, 18 HARBOUR RD, WANCHAI, HONG KONG 00000, PEOPLES R CHINA
语种	英语
WOS研究方向	Mathematics
WOS记录号	WOS:000455995700005
内容类型	会议论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/3343]
专题	上海财经大学
作者单位	1.Shanghai Jiao Tong Univ, Sch Math Sci, Shanghai, Peoples R China; 2.Shanghai Univ Finance & Econ, Sch Informat Management & Engn, Shanghai, Peoples R China; 3.Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA
推荐引用方式 GB/T 7714	Fu, Taoran,Ge, Dongdong,Ye, Yinyu. ON DOUBLY POSITIVE SEMIDEFINITE PROGRAMMING RELAXATIONS[C]. 见:.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。