Lower bounds for approximate factorizations via semidefinite programming

Erich Kaltofen(kaltofenmath.ncsu.edu)
Bin Li(blimmrc.iss.ac.cn)
Kartik Krishnan Sivaramakrishnan(kksivarancsu.edu)
Zhengfeng Yang(zyang4math.ncsu.edu)
Lihong Zhi(lzhimmrc.iss.ac.cn)

Abstract: The problem of approximately factoring a real or complex multivariate polynomial $f$ seeks minimal perturbations $\Delta f$ to the coefficients of the input polynomial $f$ so that the deformed polynomial $f + \Delta f$ has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomials that has non-trivial factors. (see [3] and [6] and the literature cited there). Here we consider the solution of the arising optimization problems using polynomial optimization (POP) via semidefinite programming. We restrict to real coefficients in the input and output polynomials.

Keywords: Approximate factorization of polynomials, polynomial optimization, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Proceedings of SNC 07, London, Ontario, Canada, July 25-27, 2007, pp. 203-204

Download: [PDF]

Entry Submitted: 06/06/2008
Entry Accepted: 06/09/2008
Entry Last Modified: 06/06/2008

Modify/Update this entry