Loading…
A new polynomially solvable class of quadratic optimization problems with box constraints
We consider the quadratic optimization problem max x ∈ C x T Q x + q T x , where C ⊆ R n is a box and r : = rank ( Q ) is assumed to be O ( 1 ) (i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary Q and q . The idea is based on a reduction of the problem to enumera...
Saved in:
| Published in: | Optimization letters 2021-09, Vol.15 (6), p.2331-2341 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | cdi_FETCH-LOGICAL-c242t-3b74d824c48c5fe71b8dabd03bf7b4dd6bfa554b5a888bebcc1d0f9774399c483 |
| container_end_page | 2341 |
| container_issue | 6 |
| container_start_page | 2331 |
| container_title | Optimization letters |
| container_volume | 15 |
| creator | Hladík, Milan Černý, Michal Rada, Miroslav |
| description | We consider the quadratic optimization problem
max
x
∈
C
x
T
Q
x
+
q
T
x
, where
C
⊆
R
n
is a box and
r
:
=
rank
(
Q
)
is assumed to be
O
(
1
)
(i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary
Q
and
q
. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension
O
(
r
)
. This paper generalizes previous results where
Q
had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously. |
| doi_str_mv | 10.1007/s11590-021-01711-6 |
| format | article |
| fullrecord | <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_1007_s11590_021_01711_6</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1007_s11590_021_01711_6</sourcerecordid><originalsourceid>FETCH-LOGICAL-c242t-3b74d824c48c5fe71b8dabd03bf7b4dd6bfa554b5a888bebcc1d0f9774399c483</originalsourceid><addsrcrecordid>eNp9kM1OAyEUhYnRxFp9AVe8AAoMMzDLpvGnSRM3unBFgAGlmYERptb69KI1Ll3dszjfyc0HwCXBVwRjfp0JqVuMMCUIE04Iao7AjIiGIsYEPv7LnJ6Cs5w3GDeEtO0MPC9gsDs4xn4f4uBV3-9hjv270r2Fplc5w-jg21Z1SU3ewDhOfvCfJccAxxRLbchw56dXqOMHNDHkKSkfpnwOTpzqs734vXPwdHvzuLxH64e71XKxRoYyOqFKc9YJygwTpnaWEy06pTtcacc167pGO1XXTNdKCKGtNoZ02LWcs6ptC1TNAT3smhRzTtbJMflBpb0kWH7LkQc5ssiRP3JkU6DqAOVSDi82yU3cplD-_I_6Ar6-ao4</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A new polynomially solvable class of quadratic optimization problems with box constraints</title><source>Springer Nature</source><creator>Hladík, Milan ; Černý, Michal ; Rada, Miroslav</creator><creatorcontrib>Hladík, Milan ; Černý, Michal ; Rada, Miroslav</creatorcontrib><description>We consider the quadratic optimization problem
max
x
∈
C
x
T
Q
x
+
q
T
x
, where
C
⊆
R
n
is a box and
r
:
=
rank
(
Q
)
is assumed to be
O
(
1
)
(i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary
Q
and
q
. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension
O
(
r
)
. This paper generalizes previous results where
Q
had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously.</description><identifier>ISSN: 1862-4472</identifier><identifier>EISSN: 1862-4480</identifier><identifier>DOI: 10.1007/s11590-021-01711-6</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Computational Intelligence ; Mathematics ; Mathematics and Statistics ; Numerical and Computational Physics ; Operations Research/Decision Theory ; Optimization ; Short Communication ; Simulation</subject><ispartof>Optimization letters, 2021-09, Vol.15 (6), p.2331-2341</ispartof><rights>The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature 2021</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c242t-3b74d824c48c5fe71b8dabd03bf7b4dd6bfa554b5a888bebcc1d0f9774399c483</cites><orcidid>0000-0002-3261-9524 ; 0000-0002-1761-897X ; 0000-0002-7340-8491</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Hladík, Milan</creatorcontrib><creatorcontrib>Černý, Michal</creatorcontrib><creatorcontrib>Rada, Miroslav</creatorcontrib><title>A new polynomially solvable class of quadratic optimization problems with box constraints</title><title>Optimization letters</title><addtitle>Optim Lett</addtitle><description>We consider the quadratic optimization problem
max
x
∈
C
x
T
Q
x
+
q
T
x
, where
C
⊆
R
n
is a box and
r
:
=
rank
(
Q
)
is assumed to be
O
(
1
)
(i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary
Q
and
q
. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension
O
(
r
)
. This paper generalizes previous results where
Q
had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously.</description><subject>Computational Intelligence</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Numerical and Computational Physics</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Short Communication</subject><subject>Simulation</subject><issn>1862-4472</issn><issn>1862-4480</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp9kM1OAyEUhYnRxFp9AVe8AAoMMzDLpvGnSRM3unBFgAGlmYERptb69KI1Ll3dszjfyc0HwCXBVwRjfp0JqVuMMCUIE04Iao7AjIiGIsYEPv7LnJ6Cs5w3GDeEtO0MPC9gsDs4xn4f4uBV3-9hjv270r2Fplc5w-jg21Z1SU3ewDhOfvCfJccAxxRLbchw56dXqOMHNDHkKSkfpnwOTpzqs734vXPwdHvzuLxH64e71XKxRoYyOqFKc9YJygwTpnaWEy06pTtcacc167pGO1XXTNdKCKGtNoZ02LWcs6ptC1TNAT3smhRzTtbJMflBpb0kWH7LkQc5ssiRP3JkU6DqAOVSDi82yU3cplD-_I_6Ar6-ao4</recordid><startdate>20210901</startdate><enddate>20210901</enddate><creator>Hladík, Milan</creator><creator>Černý, Michal</creator><creator>Rada, Miroslav</creator><general>Springer Berlin Heidelberg</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0002-3261-9524</orcidid><orcidid>https://orcid.org/0000-0002-1761-897X</orcidid><orcidid>https://orcid.org/0000-0002-7340-8491</orcidid></search><sort><creationdate>20210901</creationdate><title>A new polynomially solvable class of quadratic optimization problems with box constraints</title><author>Hladík, Milan ; Černý, Michal ; Rada, Miroslav</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c242t-3b74d824c48c5fe71b8dabd03bf7b4dd6bfa554b5a888bebcc1d0f9774399c483</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Computational Intelligence</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Numerical and Computational Physics</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Short Communication</topic><topic>Simulation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hladík, Milan</creatorcontrib><creatorcontrib>Černý, Michal</creatorcontrib><creatorcontrib>Rada, Miroslav</creatorcontrib><collection>CrossRef</collection><jtitle>Optimization letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hladík, Milan</au><au>Černý, Michal</au><au>Rada, Miroslav</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A new polynomially solvable class of quadratic optimization problems with box constraints</atitle><jtitle>Optimization letters</jtitle><stitle>Optim Lett</stitle><date>2021-09-01</date><risdate>2021</risdate><volume>15</volume><issue>6</issue><spage>2331</spage><epage>2341</epage><pages>2331-2341</pages><issn>1862-4472</issn><eissn>1862-4480</eissn><abstract>We consider the quadratic optimization problem
max
x
∈
C
x
T
Q
x
+
q
T
x
, where
C
⊆
R
n
is a box and
r
:
=
rank
(
Q
)
is assumed to be
O
(
1
)
(i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary
Q
and
q
. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension
O
(
r
)
. This paper generalizes previous results where
Q
had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s11590-021-01711-6</doi><tpages>11</tpages><orcidid>https://orcid.org/0000-0002-3261-9524</orcidid><orcidid>https://orcid.org/0000-0002-1761-897X</orcidid><orcidid>https://orcid.org/0000-0002-7340-8491</orcidid></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1862-4472 |
| ispartof | Optimization letters, 2021-09, Vol.15 (6), p.2331-2341 |
| issn | 1862-4472 1862-4480 |
| language | eng |
| recordid | cdi_crossref_primary_10_1007_s11590_021_01711_6 |
| source | Springer Nature |
| subjects | Computational Intelligence Mathematics Mathematics and Statistics Numerical and Computational Physics Operations Research/Decision Theory Optimization Short Communication Simulation |
| title | A new polynomially solvable class of quadratic optimization problems with box constraints |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-13T22%3A55%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20new%20polynomially%20solvable%20class%20of%20quadratic%20optimization%20problems%20with%20box%20constraints&rft.jtitle=Optimization%20letters&rft.au=Hlad%C3%ADk,%20Milan&rft.date=2021-09-01&rft.volume=15&rft.issue=6&rft.spage=2331&rft.epage=2341&rft.pages=2331-2341&rft.issn=1862-4472&rft.eissn=1862-4480&rft_id=info:doi/10.1007/s11590-021-01711-6&rft_dat=%3Ccrossref_sprin%3E10_1007_s11590_021_01711_6%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c242t-3b74d824c48c5fe71b8dabd03bf7b4dd6bfa554b5a888bebcc1d0f9774399c483%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true |