Verification of semidefinite optimization problems with application to variational electronic structure calculation [Elektronische Ressource] / von Denis Chaykin

Denis Chaykin

Sujets

• Naturwissenschaften

Informations

• Publié par: technische_universitat_hamburg-harburg
• Publié le: 01 janvier 2009
• Nombre de lectures: 6
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Verification of Semidefinite Optimization
Problems with Application to Variational
Electronic Structure Calculation
Vom Promotionsausschuss der
Technischen Universita¨t Hamburg-Harburg
zur Erlangung des akademischen Grades
Doktor-Ingenieur
genehmigte Dissertation
von
Denis Chaykin
aus
Krasnogorsk
20091. Gutachter: Prof. Dr. Dr. h.c. Frerich J. Keil
2. Gutachter: PD Dr. Christian Jansson
Tag der mu¨ndlichen Pru¨fung: 19.06.2009Acknowledgements
Naturally, my greatest appreciation goes to my advisors Christian Jansson and Frerich
Keil. Christian Jansson’s dedicated involvement has actually made this thesis possi-
ble. His knowledge, experience and insight are directly and indirectly reflected in this
work. He was always the first person to consult with and to get advise from whenever
I had to face any difficulties. I will be forever grateful for the given chance.
I want to thank Prof. Frerich Keil for the provided opportunity to continue my
research, for his inspiring supervision, patience and understanding. Without his en-
couragement, it would be difficult to bring this thesis to its successful completion.
To all my colleagues, both in the Institute for Reliable Computing and in the Insti-
tute of Chemical Reaction Engineering, thank you for your help, support and for just
making it a nice time.
Finally, on a more personal note, I would like to express my deepest gratitude and
appreciation to my family for their understanding and encouragement. Especially I
thank my wife Pei-Chi for many years of unconditional support and love. Without her
by my side, this thesis could never be brought out.Abstract
In this thesis we develop ideas of rigorous verification in optimization. Semidefinite
programming (SDP) is reviewed as one of the fundamental types of convex optimiza-
tion with a variety of applications in control theory, quantum chemistry, combinatorial
optimization as well as many others. We show, how rigorous error bounds for the
optimal value can be computed by carefully postprocessing the output of a semidef-
inite programming solver. All the errors due to the floating point arithmetic or ill-
conditioning of the problems are considered. We also use interval arithmetic as a
powerful tool to model uncertainties in the input data.
In the context of this thesis a software package implementing the verification al-
gorithms was developed. We provide detailed explanations and show how efficient
routines can be designed to manage real life problems. Criteria for detecting infeasible
semidefinite programs and issuing certificates of infeasibility are formulated. Exam-
ples and results for benchmark problems are included.
Another important contribution is the verification of the electronic structure prob-
lems. There large semidefinite programs represent a reduced density matrix variational
method. Our algorithms allow the calculation of a rigorous lower bound for the ground
state energy. The obtained results and modified algorithms are also of importance
because they show how much we can benefit in terms of problem complexity from
exploiting the specific problem structure.Contents
Contents vii
List of Tables ix
1 Introduction 1
1.1 Overview and motivation . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Theory and algorithms 6
2.1 Semidefinite programming . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Interval arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Rigorous error bounds in semidefinite programming . . . . . . . . . . 13
2.4.1 Rigorous lower bound . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Rigorous upper bound . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Verification of ill-posed problems . . . . . . . . . . . . . . . 23
2.5 Certificates of infeasibility . . . . . . . . . . . . . . . . . . . . . . . 24
3 Rigorous error bounds for RDM variational problems 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Reduced density matrices . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 N-representability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Eigenvalue bounds of the problem structures . . . . . . . . . . . . . . 34
3.4.1 Maximal eigenvalues of 1-RDMs and 2-RDMs . . . . . . . . 35
3.4.2 Maximal eigenvalues of other matrices . . . . . . . . . . . . 38
3.4.3 Considerations . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 SDP implementations . . . . . . . . . . . . . . . . . . . . . . . . . . 43
vii3.5.1 Rigorous error bounds for the RDM method in “dual” SDP
formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5.2 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Rigorous error bounds with verifiedSDP 59
4.1 Implementation of algorithms computing rigorous results . . . . . . . 60
4.1.1 Calculating a lower eigenvalue bound of an interval matrix . . 60
4.1.2 Solving linear systems rigorously . . . . . . . . . . . . . . . 62
4.1.3 Checking SDP infeasibility . . . . . . . . . . . . . . . . . . . 62
4.2 Numerical results for the SDPLIB . . . . . . . . . . . . . . . . . . . 63
5 Conclusions 70
A Phase I methods in semidefinite programming 72
A.1 Dual feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
A.2 Primal feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
B verifiedSDP quick reference 77
B.1 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
B.2 Examples of use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
B.2.1 Stand-alone executable binary . . . . . . . . . . . . . . . . . 79
B.2.2 Using verifiedSDP library . . . . . . . . . . . . . . . . . . . 79
Bibliography 81List of Tables
3.1 Rigorous bounds for the electronic structure benchmark problems. . . 51
3.2 Accuracy of the rigorous bounds for the electronic structure problems. 53
3.3 Computational efforts for the electronic structure benchmark problems. 54
3.4 Ratios of maximal eigenvalues and upper bounds. . . . . . . . . . . . 57
4.1 Approximate optimal values and rigorous bounds for the SDPLIB prob-
lems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Accuracy and computational effort for the SDPLIB problems. . . . . 66
ix