检索结果-南通市图书馆

Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces

Frontiers of Mathematics in China 2012年第2期7卷 321-346页

作者： Jiawang NIE Department of Mathematics University of California San DiegoLa Jolla CA 92093 USA

Abstract This paper studies the problem of minimizing a homogeneous polynomial （form） f（x） over the unit sphere Sn-1 = {x ∈ R^n：｜｜X｜｜2 = 1}. The problem is NP-hard when f（x） has degree 3 or higher. Denote by fmin （resp. fmax） the minimum （resp. maximum） value of f（x） on S^n-1. First, when f（x） is an even form of degree 2d, we study the standard sum of squares （SOS） relaxation for finding a lower bound of the minimum .fmin ：max γ s.t.f（x）-γ.｜｜x｜｜2^2d is *** fos be be the above optimal value. Then we show that for all n ≥ 2d,Here, the constant C（d） is independent of n. Second, when f（x） is a multi-form and ^-1 becomes a muilti-unit sphere, we generalize the above SOS relaxation and prove a similar bound. Third, when f（x） is sparse, we prove an improved bound depending on its sparsity pattern; when f（x） is odd, we formulate the problem equivalently as minimizing a certain even form, and prove a similar bound. Last, for minimizing f（x） over a hypersurface H（g） = {x E lRn： g（x） = 1} defined by a positive definite form g（x）, we generalize the above SOS relaxation and prove a similar bound.

关键词： Approximation bound form hypersurface L2-norm g-norm,multi-form polynomial semidefinite programming sum of squ^res

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：