DC Decomposition of Nonconvex Polynomials with Algebraic Techniques
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 (CCP). We prove, however, that optimizing over the entire set of dcds is NP-hard.
Code (0)
등록된 구현이 없습니다.
Tasks
validMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Geometry of 3D Environments and Sum of Squares Polynomials
Motivated by applications in robotics and computer vision, we study problems related to spatial reasoning of a 3D environment using sublevel sets of polynomials. These include: tightly containing a cloud of points (e.g.,…
Spatial ReasoningSymmetry Breaking in Symmetric Tensor Decomposition
In this note, we consider the highly nonconvex optimization problem associated with computing the rank decomposition of symmetric tensors. We formulate the invariance properties of the loss function and show that critica…
Tensor DecompositionUsing Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubl…
BIG-bench Machine LearningOn the Expressive Power of Deep Polynomial Neural Networks
We study deep neural networks with polynomial activations, particularly their expressive power. For a fixed architecture and activation degree, a polynomial neural network defines an algebraic map from weights to polynom…
Polynomial Neural NetworksFundamental Conditions for Low-CP-Rank Tensor Completion
We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold struct…
Matrix Completion