Grant: Discovery Grants Program - Individual
University of Waterloo
$38,000.00
Strengthening Relaxations for Efficient Solutions of Hard Numerical Problems
EF 2024-25
Résumé
Current optimization problems arising from areas such as machine learning and data science are generally large scale and often ill-conditioned and even ill-posed. This raises the obvious questions: how to model, handle, and solve large scale problems efficiently, while simultaneously maintaining accuracy. Moreover, these problems generally must be relaxed to tractable convex problems. The main objectives of the proposed research is to strengthen relaxations, while maintaining tractability and robustness. We hope to advance the number and size of classes of problems that can be provably solved to optimality.
The approach we plan on using to solve these problems is divided into three parts. First, we strengthen the convex relaxations often by adding redundant constraints to the original model. Alternatively, one can do second order liftings. For example, empirically we observe that for random problems the second lifting for the max-cut problem provides a zero duality gap, though this fails for instances with special structure.
The second lifting is in general a much larger problem and strict feasibility (regularity) is often lost. However, we can exploit the structure and apply facial reduction (FR) a form of regularization. Moreover, FR provides a natural splitting for first order splitting type methods. In addition, we can add on redundant constraints to the subproblems in the splitting as well as to the dual variables for better speed and accuracy.
Finally, we consider the problem of obtaining good solutions from the relaxations. This involves constructing appropriate duals and using weak duality to obtain good lower bounds to identify optimality of the original hard problem. This, in combination with strong rounding procedures to obtain feasible solutions, reduces the duality gaps for the above problems. The above approach has been successfully used for several classes of problems. For robust solutions for quantum key distribution rate computation, accurate lower bounds are essential. Our approach finds provable lower bounds to machine precision and solves previously intractable instances. For large scale linear programming (LP) we are using a robust algorithm and a warm start procedure that exploits high probability optimal basis information. For nearest low rank matrix approximations in machine learning and in particular to protein side-chain positioning problems we surprisingly solve to optimality many data sets for these NP-hard problems. In summary, the loss of strict feasibility appears to be pervasive in many hard problems.
We have obtained algorithms for FR for special classes of problems including LPs. We plan on improving this preprocessing technique for other general classes of convex problems. This highly qualified personnel who have joined in this have learned the details of the state of the art optimization solvers. These skills are in demand at software firms as well as large companies that develop their own software.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-03825
Name nom
Wolkowicz, Henry
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
38000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Strengthening Relaxations for Efficient Solutions of Hard Numerical Problems
Keywords
large scale optimization; semidefinite programming relaxations; improved algorithms; accuracy of solutions; exploiting structure
Application summary
Current optimization problems arising from areas such as machine learning and data science are generally large scale and often ill-conditioned and even ill-posed. This raises the obvious questions: how to model, handle, and solve large scale problems efficiently, while simultaneously maintaining accuracy. Moreover, these problems generally must be relaxed to tractable convex problems. The main objectives of the proposed research is to strengthen relaxations, while maintaining tractability and robustness. We hope to advance the number and size of classes of problems that can be provably solved to optimality.
The approach we plan on using to solve these problems is divided into three parts. First, we strengthen the convex relaxations often by adding redundant constraints to the original model. Alternatively, one can do second order liftings. For example, empirically we observe that for random problems the second lifting for the max-cut problem provides a zero duality gap, though this fails for instances with special structure.
The second lifting is in general a much larger problem and strict feasibility (regularity) is often lost. However, we can exploit the structure and apply facial reduction (FR) a form of regularization. Moreover, FR provides a natural splitting for first order splitting type methods. In addition, we can add on redundant constraints to the subproblems in the splitting as well as to the dual variables for better speed and accuracy.
Finally, we consider the problem of obtaining good solutions from the relaxations. This involves constructing appropriate duals and using weak duality to obtain good lower bounds to identify optimality of the original hard problem. This, in combination with strong rounding procedures to obtain feasible solutions, reduces the duality gaps for the above problems. The above approach has been successfully used for several classes of problems. For robust solutions for quantum key distribution rate computation, accurate lower bounds are essential. Our approach finds provable lower bounds to machine precision and solves previously intractable instances. For large scale linear programming (LP) we are using a robust algorithm and a warm start procedure that exploits high probability optimal basis information. For nearest low rank matrix approximations in machine learning and in particular to protein side-chain positioning problems we surprisingly solve to optimality many data sets for these NP-hard problems. In summary, the loss of strict feasibility appears to be pervasive in many hard problems.
We have obtained algorithms for FR for special classes of problems including LPs. We plan on improving this preprocessing technique for other general classes of convex problems. This highly qualified personnel who have joined in this have learned the details of the state of the art optimization solvers. These skills are in demand at software firms as well as large companies that develop their own software.