English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the general polynomial optimization problem $P: f^*=\min\{f(x)\,:\,x\in K\}$ where $K$ is a compact basic semi-algebraic set. We firstshow that the standard Lagrangian relaxation yields a lower bound as close asdesired to the global optimum $f^*$, provided that it is applied to a problem$\tilde{P}$ equivalent to $P$, in which sufficiently many redundant constraints(products of the initial ones) are added to the initial description of $P$.Next we show that the standard hierarchy of LP-relaxations of $P$ (in thespirit of Sherali-Adams' RLT) can be interpreted as a brute forcesimplification of the above Lagrangian relaxation in which a nonnegativepolynomial (with coefficients to be determined) is replaced with a constantpolynomial equal to zero. Inspired by this interpretation, we provide asystematic improvement of the LP-hierarchy by doing a much less brutalsimplification which results into a parametrized hierarchy of semidefiniteprograms (and not linear programs any more). For each semidefinite program inthe parametrized hierarchy, the semidefinite constraint has a fixed size$O(n^k)$, independently of the rank in the hierarchy, in contrast with thestandard hierarchy of semidefinite relaxations. The parameter $k$ is to bedecided by the user. When applied to a non trivial class of convex problems,the first relaxation of the parametrized hierarchy is exact, in contrast withthe LP-hierarchy where convergence cannot be finite. When applied to 0/1programs it is at least as good as the first one in the hierarchy ofsemidefinite relaxations. However obstructions to exactness still exist and arebriefly analyzed. Finally, the standard semidefinite hierarchy can also beviewed as a simplification of an extended Lagrangian relaxation, but differentin spirit as sums of squares (and not scalars) multipliers are allowed.

A Lagrangian relaxation view of linear and semidefinite hierarchies