Interior Point Approach to Linear, Quadratic and Convex Programming Mathematics and Its Applications Managing Editor: M. HAZEWINKEL Centre for Mathematics and Computer Science, Amsterdam, The Netherlands Volume 277 Interior Point Approach to Linear, Quadratic and Convex Programming Algorithms and Complexity by D. den Hertog Centre for Quantative Methods, Eindhoven, The Netherlands SPRINGER SCIENCE+BUSINESS MEDIA, B.V. A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-94-010-4496-7 ISBN 978-94-011-1134-8 (eBook) DOI 10.1007/978-94-011-1134-8 02-0197 -100 ts Reprinted 1997. Printed on acid-free paper AII Rights Reserved © 1994 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1994 Softcover reprint of the hardcover 1s t edition 1994 No part of the material protected by this copyright notice may be reproduced Of utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. Aan mijn ouders Voor Annemieke en Geert-Jan Contents Glossary of symbols and notations Xl 1 Introduction of IPMs 1 1.1 Prelude ........... . 1 1.2 Intermezzo: Complexity issues 3 1.3 Classifying the IPMs 4 1.4 Scope of the book ...... . 7 2 The logarithmic barrier method 9 2.1 General framework ...... . 9 2.2 Central paths for some examples. 14 2.3 Linear programming ...... -. 19 2.3.1 Properties on and near the central path. 19 2.3.2 Complexity analysis ....... 26 2.3.3 Illustration of the Newton process. . . . 32 2.4 Convex quadratic programming . . . . . . . . . 35 2.4.1 Properties on and near the central path. 35 2.4.2 Complexity analysis ........... 43 2.5 Smooth convex programming .......... 49 2.5.1 On the monotonicity of the primal and dual objectives along the central path . . . . . . . . . 49 2.5.2 The self-concordance condition 51 2.5.3 Properties near the central path 53 2.5.4 Complexity analysis 59 2.6 Miscellaneous remarks 66 3 The center method 73 3.1 General framework 73 3.2 Centers for some examples 78 3.3 Linear programming . . . 83 3.3.1 Properties at and near the centers. 83 3.3.2 Complexity analysis ........ 89 3.4 Smooth convex programming ....... 95 3.4.1 On the monotonicity of the primal and dual objectives along the path of centers . . . . . . . . . . . . . . . . . . . .. 95 vii viii CONTENTS 3.4.2 Properties near the centers . 98 3.4.3 Complexity analysis 101 3.5 Miscellaneous remarks ..... 107 4 Reducing the complexity for LP 111 4.1 Approximate solutions and rank-one updates 111 4.1.1 The revised logarithmic barrier algorithm. 111 4.1.2 Complexity analysis 115 4.1.3 An illustrative example. 120 4.2 Adding and deleting constraints 122 4.2.1 General remarks 122 4.2.2 The effects of shifting, adding and deleting constraints 124 4.2.3 The build-up and down algorithm. 133 4.204 Complexity analysis 135 4.2.5 Concluding remarks. 139 5 Discussion of other IPMs 145 5.1 Path-following methods ........ 145 5.2 Affine scaling methods . . . . . . . . . 148 5.3 Projective potential reduction methods 152 504 Affine potential reduction methods 156 5.5 Comparison of IPMs . . . . . . . . . . 160 6 Summary, conclusions and recommendations 169 Appendices 175 A Self-concordance proofs 175 A.1 Some general composition rules . . . . . . . . 175 A.2 The dual geometric programming problem . . 178 A.3 The extended entropy programming problem . 180 AA The primallp-programming problem 180 A.5 The duallp-programming problem 182 A.6 Other smoothness conditions. 184 B General technical lemmas 187 Bibliography 191 Index 205 Acknowledgements This book was written when the author was working at the Delft University of Technology. During this period I have had the benefit of advice and help from many people. First I want to thank Dr. ir. C. Roos for his stimulating and enthusiastic collabora tion. During the past several years, I had the good fortune to work in his research group dedicated to the study of interior point methods. He always gave freely of his time, whether at his office during our daily meetings or occasionally by telephone late into the evening. I also wish to acknowledge Dr. T. Tedaky, a veteran of the interior point group, for our abundant collaboration which I always found to be helpful and fruitful. His broad view of the mathematical programming area was of great value for me. Thanks also go to Prof. dr. F.A. Lootsma who urged me to rearrange my work into a book. Also the contact with the KSLA (Koninklijke/Shell-Laboratorium, Amsterdam) group in Amsterdam, which was formalized in an official research agreement, was essential. I gratefully acknowledge KSLA for the financial support during the past two years. In particular I want to thank Drs. J.F. Ballintijn for the discussions we had. I also learned a lot from several guests who visited Delft: Prof. dr. K.M. Anstreicher, Dr. O. Giiler, Dr. F. Jarre, Dr. J. Kaliski, and my second promotor Prof. dr. J.-Ph. Vial. Many of these visits resulted in joint publications. I also have to mention my officemates Jan van Noortwijk and Benjamin Jansen. The discussions with Jan on the role of the Operations Research in practice and the relationship between theory and practice influenced my choice of careers. Benjamin, also a member of the interior point group, read the first version of this book very carefully. The task he had set for himself was to find at least one error on each page. I have to admit that he succeeded. Nevertheless, I take full responsibility for all remaining mistakes in this book. Furthermore, I thank all other persons in the university who made my stay in Delft pleasant, especially Wim Penninx for his 'IEX assistance. I want to thank my parents for all that they have done for me, which is too much to write down. Finally, I sincerely thank my wife Annemieke for all of her love and compassion. She understood the many times I was physically or mentally absent from her. For this, I am in her debt. ix Glossary of symbols and notations Xi i-th coordinate of the vector x. xT transpose of the vector x. X diagonal matrix with the components of X on the diagonal. e vector of alll's of appropriate length, i.e. eT = (1,···, If. ei i-th unit vector of appropriate length. I identity matrix of appropriate dimension. lRn n-dimensional Euclidean space. Ilxll 2-norm of the vector x. v( n) = O(w ( n)) means that there exists a constant c > 0 such that, for large enough n, v(n) :::; cw(n). v( n) = 8( w( n)) means that there exist constants Cl > 0 and C2 > 0 such that, for large enough n, clw(n) :::; v(n) :::; c2w(n). F-jG means that G - F is positive semi-definite. L binary input length of the linear (or quadratic) programming prob lem. (CP) primal linear programming problem. (CD) dual linear programming problem. (QP) primal quadratic programming problem. (QD) dual quadratic programming problem. (CP) primal convex programming problem. (CD) (Wolfe) dual of the convex programming problem. z* optimal value. z or z/ a lower bound for the optimal value. zu an upper bound for the optimal value. /-I barrier parameter. /-10 initial barrier parameter. ZO initial lower bound for the optimal value. IjJB logarithmic barrier function. IjJD distance function of Huard. IjJK Karmarkar's potential function. IjJTY primal-dual potential function of Todd and Yeo IjJM multiplicative potential function. IjJSM symmetric multiplicative potential function. x(/-I), Y(/-I) minimizing point for IjJB (primal, dual). x(z), y(z) minimizing point for cPD (primal, dual). o(y,/-I) distance measure to Y(/-I). Xl Xli GLOSSARY 8(x,jl) distance measure to x(jl). (J(Y,z) distance measure to y(z). P orthogonal projection onto the null-space of the matrix B. B 10 objective function of (CP). Ii, i = 1,"', n constraint functions of (CP). p search direction. g gradient of cPB or cPo. Hi Hessian of Ii(Y). H Hessian of cPB or cPo. self-concordance constant. feasible region of problem (CP). interior of F. intersection of F and the level set Io(y) ~ z. interior of Fz• desired accuracy for the final solution. updating factor for J1. or z. steplength.