Nondifferentiable Optimization and Polynomial Problems
Polynomial extremal problems (PEP) constitute one of the most important subclasses of nonlinear programming models. Their distinctive feature is that an objective function and constraints can be expressed by polynomial functions in one or several variable
- PDF / 27,080,480 Bytes
- 407 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 230 Views
Nonconvex Optimization and Its Applications Volume 24
Managing Editors: Panos Pardalos University of Florida, U.S.A.
Reiner Horst University of Trier, Germany
Advisory Board: Ding-Zhu Do University of Minnesota, U.S.A.
C.A. Floudas Princeton University, U.S.A.
G.lnfanger Stanford University, U.S.A.
1. Mockus Lithuanian Academy of Sciences, Lithuania
P.D. Panagiotopoulos Aristotle University, Greece
H.D. Sherali Virginia Polytechnic Institute and State University, U.S.A.
The titles published in this series are listed at the end of this volume.
Nondifferentiable Optimization and Polynomial Problems by NaumZ. Shor Y.M. Glushkov Institute o/Cybernetics, Ukrainian National Academy 0/ Sciences, Kiev
r...
"
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-4792-5 ISBN 978-1-4757-6015-6 (eBook) DOI 10.1007/978-1-4757-6015-6
Printed on acid-free paper
AII Rights Reserved © 1998 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998 Softcover reprint ofthe hardcover Ist edition 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 1
IX
ELEMENTS OF CONVEX ANALYSIS, LINEAR ALGEBRA, AND GRAPH THEORY 1.1 Convex sets and convex functions 1.2 Properties of sub gradient and c-subgradient sets 1.3 Kuhn-Tucker theorem and dual bounds 1.4 Nonsmooth penalty functions 1.5 Polyhedral sets, matrices and quadratic functions 1.6 Elements of graph theory
2
3
SUB GRADIENT AND c:-SUBGRADIENT METHODS
1 1 8 19 22 25 30
2.1 The sub gradient method 2.2 Fejer-type sub gradient methods 2.3 c-subgradient and bundle methods 2.4 The stochastic sub gradient method
35 37 51 57 68
SUBGRADIENT-TYPE METHODS WITH SPACE DILATION
71
3.1 Heuristics of methods with space dilation 3.2 The Subgradient Method with Space Dilation in the Direc3.3 3.4
tion of Subgradient The ellipsoid method and its generalizations Methods with space dilation in direction of the difference of two successive subgradients in transformed space
v
71
74 88
100
Nondifferentiable optimization and polynomial problems
Vl
4
ELEMENTS OF INFORMATION AND NUMERICAL COMPLEXITY OF POLYNOMIAL EXTREMAL PROBLEMS 4.1 4.2 4.3 4.4
5
DECOMPOSITION METHODS BASED ON NONSMOOTH OPTIMIZATION 5.1 5.2 5.3
6
Introduction to the complexity theory of optimization problems Polynomial-time algorithms for linear programming Interior point algorithms for linear programming and special convex programming problems Review of main results on complexity theory of polynomial programs
Coordinate problems arising in decomposition on constraints Nonsmooth problems linking with decomposition on variables Examples of solving large-scale problems by using decomposition schemes in combination with r-algorithm
