Lower bounds for approximate factorizations via semidefinite programming: (extended abstract)

ABSTRACT

The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations ? f to the coefficients of the input polynomial f so that the deformed polynomial f +Δ f has the desired factorization properties. Effcient algorithms exist that compute the nearest real or complex polynomial that has non-trivial factors (see [3,6 ]and the literature cited there). Here we consider the solution of the arising optimization problems polynomial optimization (POP)via semide finite programming (SDP). We restrict to real coe cients in the input and output polynomials.

REFERENCES

• 1: Borchers, B. CSDP,a C library for semide finite programming. Optimization Methods and Software 11 & 12 (1999), 613--623. Available at http://infohost.nmt.edu/~borchers/csdp.html
• 2: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 3: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 4: Markus A. Hitz , Erich Kaltofen , Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.205-212, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309937]
• 5: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 6: Kaltofen, E., May, J., Yang, Z., and Zhi, L. Approximate factorization of multivariate polynomials using singular value decomposition. Manuscript, 22 pages. Submitted, Jan.2006.
• 7: Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145799]
• 8: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 9: Nie, J., Demmel, J., and Gu, M. Global minimization of rational functions and the nearest GCDs. http://arxiv.org/pdf/math/0601110 2006.
• 10: Prajna, S., Papachristodoulou, A., Seiler, P., and Parrilo, P. A. SOSTOOLS: Sum of squares optimization toolbox for MATLAB. Available from http://www.cds.caltech.edu/sostools and http://www.mit.edu/~parrilo/sostools 2004.
• 11: Ruppert, W. M. Reduzibilität ebener Kurven.J. reine angew. Math. 369 (1986),167--191.
• 12: Ruppert, W. M. Reducibility of polynomials f(x,y) modulo p J. Number Theory 77 (1999),62--70.
• 13: Waki, H., Kim, S., Kojima, M., and Muramatsu, M. SparsePOP: A sparse semide nite programming relaxation of polynomial optimization problems. Research Report B-414, Tokyo Institute of Technology, Dept. of Mathematical and Computing Sciences, Oh-Okayama, Meguro 152--8552, Tokyo, Japan, 2005. Available at http://www.is.titech.ac.jp/~kojima/SparsePOP
• 14: M. Yamashita , K. Fujisawa , M. Kojima, SDPARA: semiDefinite programming algorithm paRAllel version, Parallel Computing, v.29 n.8, p.1053-1067, 1 August 2003 [doi>10.1016/S0167-8191(03)00087-5]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Experimentation, Theory

Keywords:
SDP, approximate factorization, hybrid method