Maximization of a PSD Quadratic Form and Factorization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00531777" target="_blank" >RIV/67985807:_____/21:00531777 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/21:10437016

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s11590-020-01624-w" target="_blank" >http://dx.doi.org/10.1007/s11590-020-01624-w</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11590-020-01624-w" target="_blank" >10.1007/s11590-020-01624-w</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Maximization of a PSD Quadratic Form and Factorization

Popis výsledku v původním jazyce

We consider the problem of maximization of a convex quadratic form on a convex polyhedral set, which is known to be NP-hard. In particular, we focus on upper bounds on the maximum value. We investigate utilization of different vector norms (estimating the Euclidean one) and different objective matrix factorizations. We arrive at some kind of duality with positive duality gap in general, but with possibly tight bounds. We discuss theoretical properties of these bounds and also extensions to generally preconditioned factors. We employ mainly the maximum vector norm since it yields efficiently computable bounds, however, we study other norms, too. Eventually, we leave many challenging open problems that arose during the research.

Název v anglickém jazyce

Maximization of a PSD Quadratic Form and Factorization

Popis výsledku anglicky

We consider the problem of maximization of a convex quadratic form on a convex polyhedral set, which is known to be NP-hard. In particular, we focus on upper bounds on the maximum value. We investigate utilization of different vector norms (estimating the Euclidean one) and different objective matrix factorizations. We arrive at some kind of duality with positive duality gap in general, but with possibly tight bounds. We discuss theoretical properties of these bounds and also extensions to generally preconditioned factors. We employ mainly the maximum vector norm since it yields efficiently computable bounds, however, we study other norms, too. Eventually, we leave many challenging open problems that arose during the research.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA18-04735S" target="_blank" >GA18-04735S: Nové přístupy pro relaxační a aproximační techniky v deterministické globální optimalizaci</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Optimization Letters

ISSN

1862-4472

e-ISSN

1862-4480

Svazek periodika

15

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

14

Strana od-do

2515-2528

Kód UT WoS článku

000555354000001

EID výsledku v databázi Scopus

2-s2.0-85088993896