DC decomposition of nonconvex polynomials with algebraic techniques

被引：23

作者：

Ahmadi, Amir Ali ^{[1
]}

Hall, Georgina ^{[1
]}

机构：

[1] Princeton Univ, ORFE, Sherrerd Hall, Princeton, NJ 08540 USA

来源：

MATHEMATICAL PROGRAMMING | 2018年 / 169卷 / 01期

关键词：

Difference of convex programming; Conic relaxations; Polynomial optimization; Algebraic decomposition of polynomials; OPTIMIZATION; CONVEXITY; MINIMIZATION;

D O I：

10.1007/s10107-017-1144-5

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure. We prove, however, that optimizing over the entire set of dcds is NP-hard.

引用

页码：69 / 94

页数：26

共 47 条

[11]

[Anonymous], P 44 IEEE C DEC CONT

[12]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[13]

[Anonymous], 1959, Pacific Journal of Mathematics, DOI 10.2140/pjm.1959.9.707

[14]

Argyriou A., 2006, International Conference on Machine Learning, P41

[15] Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches [J].

Bomze, IM ;

Locatelli, M .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2004, 28 (02) :227-245

[16]

Chapelle O., 2009, Advances in Neural Information Processing Systems, P281

[17]

de Klerk E., 2010, On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems

[18] A parametric characterization of local optimality [J].

Mirjam Dür .

Mathematical Methods of Operations Research, 2003, 57 (1) :101-109

[19]

Floudas C.A., 2013, Optimization in computational chemistry and molecular biology: local and global approaches, V40

[20] How to integrate a polynomial over a sphere [J].

Folland, GB .

AMERICAN MATHEMATICAL MONTHLY, 2001, 108 (05) :446-448

← 1 2 3 4 5 →