Introductory Lectures on Convex Optimization A Basic Course
It was in the middle of the 1980s, when the seminal paper by Kar markar opened a new epoch in nonlinear optimization. The importance of this paper, containing a new polynomial-time algorithm for linear op timization problems, was not only in its complex
- PDF / 16,666,131 Bytes
- 253 Pages / 440.698 x 664.659 pts Page_size
- 64 Downloads / 221 Views
A Basic Course
Applied Optimization
Volume 87
Series Editors:
Panos M. Pardalos University ofFlorida, US.A.
Donald W. Heam University ofFlorida, US.A.
INTRODUCTORY LECTURES ON CONVEX OPTIMIZATION
A Basic Course
By
Yurii Nesterov Center of Operations Research and Econometrics, (CORE) Universite Catholique de Louvain (UCL) Louvain-la-Neuve, Belgium
'' ~·
Springer Science+Business Media, LLC
Library of Congress Cataloging-in-PubHcation
Nesterov, Yurri Introductory Lectures on Convex Optimization: A Basic Course ISBN 978-1-4613-4691-3 ISBN 978-1-4419-8853-9 (eBook) DOI 10.1007/978-1-4419-8853-9
Copyright Cl 2004 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 2004 Softcover reprint of the hardcover 1st edition 2004
All rights reserved. No part ofthis publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photo-copying, microfilming, recording, or otherwise, without the prior written perrnission ofthe publisher, with the exception ofany material supplied specifrcally for the purpose ofbeing entered and executed on a computer system, for exclusive use by the purchaser ofthe work. Permissions for books published in the USA: permj ssi ons®wkap com Permissions for books published in Europe: [email protected] Printedon acid-free paper.
Contents
Preface Acknowledgments Introduction 1. NONLINEAR OPTIMIZATION 1.1 World of nonlinear optimization 1.1.1 General formulation of the problern 1.1.2 Performance of numerical methods 1.1.3 Complexity bounds for global optimization 1.1.4 Identity cards of the fields 1.2 Local methods in unconstrained minimization 1.2.1 Relaxation and approximation 1.2.2 Classes of differentiable functions 1.2.3 Gradient method 1.2.4 Newton method
lX
xiii XV
1 1 1 4 7 13 15 15 20 25 32
First-order methods in nonlinear optimization 1.3.1 Gradient method and Newton method: What is different? 1.3.2 Conjugate gradients 1.3.3 Constrained minimization
37 42 46
2. SMOOTH CONVEX OPTIMIZATION 2.1 Minimization of smooth functions 2.1.1 Smooth convex functions 2.1.2 Lower complexity bounds for :FJ:• 1 (Rn) 2.1.3 Strongly convex functions 2.1.4 Lower complexity bounds for s:,J}(Rn)
51 51 51 58 63 66
1.3
37
vi
INTRODUCTORY LEGTURES ON CONVEX OPTIMIZATION
2.1.5
Gradient method 2.2 Optimal Methods 2.2.1 Optimal methods 2.2.2 Convex sets 2.2.3 Gradient mapping 2.2.4 Minimization methods for simple sets 2.3 Minimization problern with smooth components 2.3.1 Minimax problern 2.3.2 Gradient mapping 2.3.3 Minimization methods for minimaxproblern 2.3.4 Optimization with functional constraints 2.3.5 Method for constrained minimization
68 71 71 81 86 87 90 90 93 96 100 105
3. NONSMOOTH CONVEX OPTIMIZATION 3.1 General convex functions 3.1.1 Motivation and definitions 3.1.2 Operations with convex functions 3.1.3 Continuity and differentiability 3.1.4 Separation theorems 3.1.5 Subgradients 3.1.6 Computing subgradients 3.2 Nonsmooth minimization methods 3.2.1 Generallower c
Data Loading...
