Paper Info
Title
The Many Faces of Degeneracy in Conic Optimization
Abstract
AbstractSlater's condition - existence of a "strictly feasible solution" - is acommon assumption in conic optimization. Without strict feasibility,first-order optimality conditions may be meaningless, the dual problemmay yield little information about the primal, and small changesin the data may render the problem infeasible. Hence, failure of strictfeasibility can negatively impact off-the-shelf numerical methods, suchas primal-dual interior point methods, in particular. New optimizationmodeling techniques and convex relaxations for hard nonconvex problemshave shown that the loss of strict feasibility is a more pronouncedphenomenon than has previously been realized. In this text, we describevarious reasons for the loss of strict feasibility, whether due topoor modeling choices or more interestingly rich underlying structure,and discuss ways to cope with it and, in many pronounced cases,how to use it as an advantage. In large part, we emphasize the facialreduction preprocessing technique due to its mathematical elegance,geometric transparency, and computational potential.
Year
DOI
Venue
2017
10.1561/2400000011
Periodicals
Keywords
Field
DocType
Machine Learning,Theoretical Computer Science,Communications and Information Theory,Networking,Optimization,Computational geometry,Computational biology,Operations research,Denoising,Information theory and computer science,Information theory and statistics,Pattern recognition and learning,Modeling and Analysis: Sensor Networks
Transparency (graphic),Mathematical optimization,Regular polygon,Degeneracy (mathematics),Duality (optimization),Preprocessor,Conic optimization,Numerical analysis,Interior point method,Mathematics
Journal
Volume
Issue
ISSN
3
2
2167-3888
Citations 
PageRank 
References 
3
0.40
0
Authors
2
Name
Order
Citations
PageRank
Dmitriy Drusvyatskiy116617.25
Henry Wolkowicz21444260.72