  


A new approximation hierarchy for polynomial conic optimization
Peter J.C. Dickinson (peter.dickinsoncantab.net) Abstract: In this paper we consider polynomial conic optimization problems, where the feasible set is defined by constraints in the form of given polynomial vectors belonging to given nonempty closed convex cones, and we assume that all the feasible solutions are nonnegative. This family of problems captures in particular polynomial optimization problems, polynomial semidefinite polynomial optimization problems and polynomial second order cone optimization problems. We propose a general hierarchy of linear conic optimization relaxations inspired by an extension of Pólya's Positivstellensatz for homogeneous polynomials being positive over a basic semialgebraic cone contained in the nonnegative orthant. Under some classical assumptions these relaxations converge monotonically to the optimal value of the original problem. The members of this hierarchy provide strong bounds for the optimum value, especially for polynomial semidefinite problems and polynomial second order cone optimization problems, where these bounds are comparable or even outperform the existing bounds based on sumofsquares. Adding a redundant polynomial positive semidefinite constraint to the original problem improves the bounds drastically. We provide an extensive list of numerical examples which clearly indicate the advantages and disadvantages of our hierarchy. Keywords: real algebraic geometry; copositive optimization; approximation hierarchy; conic optimization; nonnegative polynomials; polynomial optimization Category 1: Linear, Cone and Semidefinite Programming Citation: Submitted Download: [PDF] Entry Submitted: 06/16/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  