Practical Bilevel Optimization.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：18.17M 资料格式：pdf 举报版权申诉

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第1页.png

第1页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第2页.png

第2页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第3页.png

第3页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第4页.png

第4页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第5页.png

第5页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第6页.png

第6页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第7页.png

第7页 / 共483页

f4d297fb-1f2e-489e-9bcc-bca78ae3fff7.pdf-第8页.png

第8页 / 共483页

文本预览

Practical Bilevel Optimization: Algorithms and Applications

Nonconvex Optimization and lts Applications Volume 30 Managing Editors: Panos Pardalos University of Florida, U.S.A. Reiner Horst University ofTrier, Germany Advisory Board: Ding-Zhu Du University of Minnesota, U.S.A. C. A. Floudas Princeton University, U.S.A. J.Mockus Stanford University, U.S.A. H. D. Sherali Virginia Polyrechnie Institute and State University, U.S.A. The titles published in this series are listed at the end ofthis volume.

Practical Bilevel Optimization Algorithms and Applications by Jonathan F. Bard Graduate Program in Operations Research, Department of Mechanical Engineering, The University ofTexas, Austin, Texas, U.S.A. SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.

A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-1-4419-4807-6 DOI 10.1007/978-1-4757-2836-1 ISBN 978-1-4757-2836-1 (eBook) Printed on acid-free paper All Rights Reserved © 1998 Springer Science+ Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998 No part of the material protected by this copyright notice may be reproduced or 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

CONTENTS PREFACE Part I MATHEMATICAL PROGRAMMING 1 2 INTRODUCTION 1.1 Model Development 1.2 Early Work and Applications 1.3 Structural Considerations 1.3.1 Indifference Points and Nonexistence of Solutions 1.3.2 Significance of Order of Play 1.4 Scope and Outline LINEAR PROGRAMMING 2.1 Introduction 2.1.1 Basic Solutions 2.1.2 Fundamental Theorem 2.1.3 Convex Properties 2.2 Simplex Method 2.2.1 Pivoting 2.2.2 Determining the Leaving Variable 2.2.3 Moving toward Optimality 2.2.4 Degeneracy and Cycling 2.3 Geometry of Simplex Method 2.3.1 Finiteness of Algorithm 2.3.2 Adjacency and Bounded Edges 2.3.3 Unboundedness 2.3.4 Finding Adjacent Extreme Points 2.3.5 Main Geometrie Argument 2.3.6 Alternative Optima and Uniqueness V Xl 1 3 5 8 10 11 12 14 17 17 22 23 25 29 30 32 33 37 41 42 42 44 47 47 48

Vl PRACTICAL BILEVEL ÜPTIMIZATION 2.3.7 Ranking Extreme Points 2.4 Additional Features 2.4.1 Phase 1 and Artificial Variables 2.4.2 Bounded Variables 2.4.3 Kuhn-Tucker Conditions and the Linear Complementarity Problem 2.5 Duality 2.5.1 Primal-Dual Relationship 2.5.2 Dual Theorems 2.5.3 Economic Interpretation 2.5.4 Sensitivity Analysis 2.5.5 Dual Simplex Method 3 INTEGER PROGRAMMING 3.1 lntroduction 3.1.1 Models with Integer Variables 3.1.2 Solving Integer Programs 3.2 Enumerative Methods 3.2.1 Definitions and Concepts 3.2.2 Generic Branch and Bound Algorithm 3.2.3 Branch and Bound Using LP Relaxation 3.2.4 Implementation Issues 3.2.5 Zero-One lmplicit Enumeration 3.2.6 General Brauehing and Data Structures 3.3 Cutting Planes 3.3.1 Method of Integer Forms 3.3.2 Prima! AU-Integer Cuts 3.3.3 Cuts with Unit Coefficients 3.3.4 Valid Inequalities 3.4 Benders Decomposition for Mixed-Integer Linear Programming 3.4.1 Reformulation of MILP 3.4.2 Algorithm 3.5 U nimod ulari ty 4 NONLINEAR PROGRAMMING 4.1 Introduction 4.1.1 Classification of Problems 4.1.2 Difficulties Resulting from Nonlinearities 4.1.3 Notation 49 51 51 54 57 59 61 61 66 66 72 76 76 78 83 87 89 91 92 96 102 106 109 110 114 118 121 127 127 130 133 137 137 140 142 143

Contents 4.2 Optimality Conditions 4.2.1 Unconstrained Problems 4.2.2 Nonnegative Variables 4.2.3 Equality Constraints 4.2.4 lnequality Constraints 4.2.5 Convex Optimization 4.3 Search Techniques for Unconstrained Problems 4.3.1 One-Dimensional Linear Search Techniques 4.3.2 Multidimensional Search Techniques 4.4 Algorithms For Constrained Optimization 4.4.1 Primal Methods 4.4.2 Penalty Methods 4.4.3 Sequential Quadratic Programming Part II BILEVEL PROGRAMMING 5 Introduction LINEAR BLP: CONTINUOUS VARIABLES 5.1 5.2 Theoretical Properties 5.3 Algorithms for the Linear Bilevel Programming Problem 5.3.1 Kth-Best Algorithm 5.3.2 Kuhn-Tucker Approach 5.3.3 Complementarity Approach 5.3.4 Variable Elimination Algorithm 5.3.5 Penalty Function Approach 5.4 Computational Comparisons 6 LINEARBLP: DISCRETE VARIABLES 6.1 6.2 Properties of the Zero-One Linear BLPP lntroduction 6.2.1 Reductions to Linear Three-Level Programs 6.2.2 Algorithmic lmplications 6.3 Properties of the Mixed-Integer Linear BLPP 6.4 Moore-Bard Algorithm for the Mixed-Integer Linear BLPP 6.4.1 Branch and Bound Notation 6.4.2 Bounding Theorems 6.4.3 Algorithm 6.4.4 Computational Experience 6.4.5 Assessment Vll 155 156 157 159 164 167 169 170 175 181 181 185 188 193 195 195 198 202 203 204 209 213 218 222 232 232 233 237 244 245 247 248 249 250 254 257

Vlll PRACTICAL BILEVEL ÜPTIMIZATION 6.5 Algorithm for the Discrete Linear BLPP 6.5.1 Algorithm 6.5.2 Computational Experience 6.5.3 Assessment 7 CONVEX BILEVEL PROGRAMMING Introduction 7.1 7.2 Descent Approaches for the Quadratic BLPP 7.2.1 An EIR Point Descent Algorithm 7.2.2 A Modified Steepest Descent Approach 7.2.3 Hybrid Approach and Concave Minimization 7.3 Branch and Bound Algorithm 7.4 Variable Elimination Algorithm 7.4.1 Convex-Quadratic BLPP 7.4.2 Computational Experience 8 GENERAL BILEVEL PROGRAMMING lndependence of Irrelevant Constraints 8.1 Introduction 8.1.1 8.1.2 Preview of Algorithms 8.2 Branch and Bound Algorithm 8.3 Double Penalty Function Method 8.4 Reetangular Partitioning 8.5 Steepest Descent Direction 8.5.1 Necessary Optimality Conditions 8.5.2 Overview of Descent Method 8.6 Subgradient Descent - Bundle Method 8.6.1 Preliminaries 8.6.2 Optimality Conditions and Stability of Local Salutions 8.6.3 Leader Predominate Algorithm 8.7 Transformation to Concave Program 8.8 Assessment of Algorithms 9 HEURISTICS lntroduction 9.1 9.2 Artificial Intelligence-Based Approaches 9.2.1 Overview of Genetic Algorithms 9.2.2 GABBA 9.2.3 Grid Search Technique 258 259 266 267 269 269 272 274 276 283 284 290 291 296 301 301 305 309 311 320 327 332 333 335 339 341 344 347 352 359 361 361 362 363 364 369

分享到：

赞收藏

资料库

Practical Bilevel Optimization.pdf

相关推荐

课程资源

热门标签

最新资料