polynomial optimization

Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization

  • Masakazu Muramatsu
  • Hayato Waki
  • Maho Nakata
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , ,

    We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal’ values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial … Read more

    Lower bounds for approximate factorizations via semidefinite programming

  • Erich Kaltofen
  • Kartik Krishnan Sivaramakrishnan
  • Bin Li
  • Zhengfeng Yang
  • Lihong Zhi
    • Categories Semi-definite Programming Tags , ,

    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 … Read more

    Recognizing Underlying Sparsity in Optimization

  • Sunyoung Kim
  • Masakazu Kojima
  • Philippe L. Toint
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more

    Semidefinite Approximations for Global Unconstrained Polynomial Optimization

  • Dorina Jibetean
  • Monique Laurent
    • Categories Global Optimization Theory, Semi-definite Programming, Unconstrained Optimization Tags ,

    We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more

    LMI approximations for cones of positive semidefinite forms

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization Tags , ,

    An interesting recent trend in optimization is the application of semidefinite programming techniques to new classes of optimization problems. In particular, this trend has been successful in showing that under suitable circumstances, polynomial optimization problems can be approximated via a sequence of semidefinite programs. Similar ideas apply to conic optimization over the cone of copositive … Read more