-
A new approximation hierarchy for polynomial conic optimizationDickinson, Peter J. C., 1985- ; Povh, Janez, 1973-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 non-negative. This family of problems captures in particular polynomial optimization problems (POPs), polynomial semi-definite polynomial optimization problems (PSDPs) and polynomial second-order cone-optimization problems (PSOCPs). We propose a new general hierarchy of linear conic optimization relaxations inspired by an extension of Pólyaʼs Positivstellensatz for homogeneous polynomials being positive over a basic semi-algebraic cone contained in the non-negative orthant, introduced in Dickinson and Povh (J Glob Optim 61(4):615-625, 2015). We prove that based on some classic assumptions, these relaxations converge monotonically to the optimal value of the original problem. Adding a redundant polynomial positive semi-definite constraint to the original problem drastically improves the bounds produced by our method. We provide an extensive list of numerical examples that clearly indicate the advantages and disadvantages of our hierarchy. In particular, in comparison to the classic approach of sum-of-squares, our new method provides reasonable bounds on the optimal value for POPs, and strong bounds for PSDPs and PSOCPs, even outperforming the sum-of-squares approach in these latter two cases.Source: Computational optimization and applications. - ISSN 0926-6003 (Vol. 73, iss. 1, 2019, str. 37-67)Type of material - article, component part ; adult, seriousPublish date - 2019Language - englishCOBISS.SI-ID - 16466459
Author
Dickinson, Peter J. C., 1985- |
Povh, Janez, 1973-
Topics
polynomial conic optimization |
polynomial semi-definite programming |
polynomial second-order cone programming |
approximation hierarchy |
linear programming |
semi-definite programming |
polinomska stožčna optimizacija |
polinomsko semidefinitno programiranje |
polinomska optimizacija nad stožci drugega reda |
aproksimacijska hierarhija |
linearna optimizacija |
semidefinitna optimizacija
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dickinson, Peter J. C., 1985- | |
Povh, Janez, 1973- | 22649 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.