Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

Simple item page
dc.contributor.authorFreund, Robert M.
dc.contributor.authorVera, Jorge R.
dc.date.accessioned2024-01-10T12:38:45Z
dc.date.available2024-01-10T12:38:45Z
dc.date.issued2009
dc.description.abstractConsider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e. g., no domain ball containing or intersecting the set, etc.). The authors' interest in this problem stems from fundamental issues involving the interplay of (i) the computational complexity of computing a point in the set, (ii) the geometry of the set, and (iii) the stability or conditioning of the set under perturbation. Under suitable definitions of these terms, the authors show herein that problem instances with favorable geometry have favorable computational complexity, validating conventional wisdom. The authors also show a converse of this implication by showing that there exist problem instances that require more computational effort to solve in certain families characterized by unfavorable geometry. This in turn leads, under certain assumptions, to a form of equivalence among computational complexity, geometry, and the conditioning of the set. The authors' measures of the geometry, relative to a given reference point, are based on the radius of a certain domain ball whose intersection with the set contains a certain inscribed ball.
dc.description.abstractThe geometry of the set is then measured by the radius of the domain ball, the radius of the inscribed ball, and the ratio between these two radii, the latter of which is called the aspect ratio. The aspect ratio arises in the analysis of many algorithms for convex problems, and its importance in convex algorithm analysis has been well-known for several decades. However, the presence in our bound of terms involving only the radius of the domain ball and only the radius of the inscribed ball are a bit counterintuitive; nevertheless, we show that the computational complexity must involve these terms in addition to the aspect ratio, even when the aspect ratio itself is small. This lower-bound complexity analysis relies on simple features of the separation oracle model; if we instead assume that the set is conveyed by a self-concordant barrier function, then it is an open challenge to prove such a complexity lower-bound.
dc.description.funderSingapore-MIT Alliance
dc.description.funderAFOSR
dc.fechaingreso.objetodigital2024-05-06
dc.format.extent11 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1287/moor.1090.0408
dc.identifier.eissn1526-5471
dc.identifier.issn0364-765X
dc.identifier.urihttps://doi.org/10.1287/moor.1090.0408
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/77093
dc.identifier.wosidWOS:000271911100006
dc.information.autorucIngeniería;Vera JR;S/I;100240
dc.issue.numero4
dc.language.isoen
dc.nota.accesoSin adjunto
dc.pagina.final879
dc.pagina.inicio869
dc.publisherINFORMS
dc.revistaMATHEMATICS OF OPERATIONS RESEARCH
dc.rightsregistro bibliográfico
dc.subjectconvex optimization
dc.subjectellipsoid algorithm
dc.subjectcomputational complexity
dc.subjectOPTIMIZATION
dc.titleEquivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
dc.typeartículo
dc.volumen34
sipa.codpersvinculados100240
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model.pdf
Size:
98.86 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas