izpis_h1_title_alt

A new approximation hierarchy for polynomial conic optimization
Dickinson, Peter J. C. (Avtor), Povh, Janez (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (463,92 KB)
URLURL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007%2Fs10589-019-00066-0 Povezava se odpre v novem oknu

Izvleček
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.

Jezik:Angleški jezik
Ključne besede:Polynomial conic optimization, Polynomial semi-definite programming, Polynomial second-order cone programming, Approximation hierarchy, Linear programming, Semi-definite programming
Vrsta gradiva:Članek v reviji (dk_c)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FS - Fakulteta za strojništvo
Leto izida:2019
Št. strani:str. [1-31]
UDK:519.8(045)
ISSN pri članku:0926-6003
DOI:10.1007/s10589-019-00066-0 Povezava se odpre v novem oknu
COBISS.SI-ID:16466459 Povezava se odpre v novem oknu
Število ogledov:268
Število prenosov:259
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:N1-0057, J1-8132, N1-0071, P1-0383
Naslov:Visoko zmogljiv reševalec za binarne kvadratične probleme, Pozitivne preslikave in realna algebrična geometrija, Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme, Kompleksna omrežja

Sekundarni jezik

Jezik:Slovenski jezik
Izvleček:
V članku obravnavamo polinomske konične optimizacijske probleme, kjer je dopustna množica definirana z omejitvami, da morajo biti dani polinomski vektorji v danih nepraznih zaprtih konveksnih stožcih. Dodatno morajo dopustne rešitve zadoščati pogoju nenegativnosti. Ta družina problemov zajema zlasti klasične probleme polinomske optimizacije (POP), probleme polinomske semidefinitne optimizacije (PSDP) in probleme polinomske optimizacije nad stožci drugega reda (PSOCP). Predlagamo novo splošno hierarhijo linearnih koničnih optimizacijskih poenostavitev, ki naravno sledijo iz razširitve Pólya-jevega izreka o pozitivnosti iz Dickinson in Povh (J Glob Optim 61 (4): 615-625, 2015). Ob nekaterih klasičnih predpostavkah te poenostavitve monotono konvergirajo k optimalni vrednosti izvirnega problema. Kot zanimivost pokažemo, da dodajanje posebne redundantne omejitve k osnovnemu problemu ne spremeni optimalne rešitve tega problema, a bistveno izboljša kvaliteto poenostavitev. V članku tudi predstavimo obsežen seznam številčnih primerov, ki jasno kažejo na prednosti in slabosti naše hierarhije.

Ključne besede:polinomska stožčna optimizacija, polinomsko semidefinitno programiranje, polinomska optimizacija nad stožci drugega reda, aproksimacijska hierarhija, linearna optimizacija, semidefinitna optimizacija

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj