An Introduction
to Optimization
WILEY-INTERSCIENCE
SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION
ADVISORY EDITORS
RONALD L. GRAHAM
University of California at San Diego, U.S.A.
JAN KAREL LENSTRA
Department of Mathematics and Computer Science,
Eindhoven University of Technology, Eindhoven, The Netherlands
JOEL H. SPENCER
+
A complete list of titles in this series appears at the end of this volume.
Institute, New York, New York, U.S.A.
An Introduction
to Optimization
Second Edition
EDWIN K. P. CHONG
STANISLAW H. ZAK
A Wiley-lnterscience Publication
INC.
New York / Chichester / Weinheim / Brisbane / Singapore / Toronto
JOHN WILEY & SONS,
This text is printed on acid-free paper. @
Copyright © 2001 by John Wiley & Sons, Inc. All rights reserved.
Published simultaneously in Canada.
No part of this publication may be reproduced, stored in a retrieval system or transmitted in any
form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise,
except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without
either the prior written permission of the Publisher, or authorization through payment of the
appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA
01923, (978) 750-8400, fax (978) 750-4744. Requests to the Publisher for permission should be
addressed to the Permissions Department, John Wiley & Sons, Inc., 605 Third Avenue, New York,
NY 10158-0012, (212) 850-6011, fax (212) 850-6008, E-Mail: PERMREQ @ W1LEY.COM.
For ordering and customer service, call 1-800-CALL-W1LEY.
Library of Congress Cataloging in Publication Data is available.
ISBN: 0-471-39126-3
Printed in the United States of America
1 0 9 8 7 6 5 4 3
To my wife, Yat-Yee, and my parents, Paul and Julienne Chong.
Edwin K. P. Chong
To JMJ, my wife, Mary Ann, and my parents, Janina and Konstanty Zak.
Stanislaw H. Zak
This page intentionally left blank
Contents
xiii
1
1
3
4
5
5
10
14
16
19
21
21
22
vii
Preface
Part I Mathematical Review
1 Methods of Proof and Some Notation
1.1 Methods of Proof
1.2 Notation
Exercises
2 Vector Spaces and Matrices
2.1 Real Vector Spaces
2.2 Rank of a Matrix
2.3 Linear Equations
2.4
Inner Products and Norms
Exercises
3 Transformations
3.1 Linear Transformations
3.2 Eigenvalues and Eigenvectors