. 1
( 59 .)



>>

CONVEXITY AND
OPTIMIZATION IN R L
CONVEXITY AND
OPTIMIZATION IN RL


LEONARD D. BERKOVITZ
Purdue University




A Wiley-Interscience Publication
JOHN WILEY & SONS, INC.
*
-.
This book is printed on acid-free paper.
Copyright 2002 by John Wiley & Sons, Inc., New York, NY. 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  WILEY.COM.
For ordering and customer service, call 1-800-CALL-WILEY.

Library of Congress Cataloging-in-Publication Data:
Berkovitz, Leonard David, 1924”
Convexity and optimization in R [superscript n] / Leonard D. Berkovitz.
p. cm.--(Pure and applied mathematics)
˜˜A Wiley-Interscience publication.™™
Includes bibliographical references and index.
ISBN 0-471-35281-0 (cloth : alk. paper)
1. Convex sets. 2. Mathematical optimization. I. Title. II. Pure and applied
mathematics (John Wiley & Sons : Unnumbered)
QA640 .B46 2001
516.08--dc21
2001045391
Printed in the United States of America.
10 9 8 7 6 5 4 3 2 1
To my wife, Anna
CONTENTS


Preface ix

I Topics in Real Analysis 1
1. Introduction 1
Vectors in R L
2. 1
3. Algebra of Sets 4
Metric Topology of R L
4. 5
5. Limits and Continuity 8
6. Basic Property of Real Numbers 11
7. Compactness 14
8. Equivalent Norms and Cartesian Products 16
9. Fundamental Existence Theorem 18
10. Linear Transformations 21
Differentiation in R L
11. 22


II Convex Sets in Rn 30
Lines and Hyperplanes in R L
1. 30
2. Properties of Convex Sets 35
3. Separation Theorems 45
4. Supporting Hyperplanes: Extreme Points 56
5. Systems of Linear Inequalities: Theorems of the Alternative 61
6. Af¬ne Geometry 69
7. More on Separation and Support 80


III Convex Functions 87
1. De¬nition and Elementary Properties 87
2. Subgradients 102
3. Differentiable Convex Functions 106
4. Alternative Theorems for Convex Functions 113
5. Application to Game Theory 117
vii
viii CONTENTS


IV Optimization Problems 128
1. Introduction 128
2. Differentiable Unconstrained Problems 129
3. Optimization of Convex Functions 137
4. Linear Programming Problems 139
5. First-Order Conditions for Differentiable Nonlinear
Programming Problems 145
6. Second-Order Conditions 163

V Convex Programming and Duality 179
1. Problem Statement 179
2. Necessary Conditions and Suf¬cient Conditions 181
3. Perturbation Theory 188
4. Lagrangian Duality 200
5. Geometric Interpretation 207
6. Quadratic Programming 210
7. Duality in Linear Programming 215

VI Simplex Method 222
1. Introduction 222
2. Extreme Points of Feasible Set 225
3. Preliminaries to Simplex Method 230
4. Phase II of Simplex Method 234
5. Termination and Cycling 245
6. Phase I of Simplex Method 251
7. Revised Simplex Method 255

Bibliography 261

Index 263
PREFACE


This book presents the mathematics of ¬nite-dimensional optimization, featur-
ing those aspects of convexity that are useful in this context. It provides a basis
for the further study of convexity, of more general optimization problems, and
of numerical algorithms for the solution of ¬nite-dimensional optimization
problems. The intended audience consists of beginning graduate students in
engineering, economics, operations research, and mathematics and strong
undergraduates in mathematics. This was the audience in a one-semester
course at Purdue, MA 521, from which this book evolved.
Ideally, the prerequisites for reading this book are good introductory
courses in real analysis and linear algebra. In teaching MA 521, I found that
while the mathematics students had the real analysis prerequisites, many of the
other students who took the course because of their interest in optimization
did not have this prerequisite. Chapter I is for those students and readers who
do not have the real analysis prerequisite; in it I present those concepts and
results from real analysis that are needed. Except for the Weierstrass theorem
on the existence of a minimum, the ˜˜heavy™™ or ˜˜deep™™ theorems are stated
without proof. Students without the real variables prerequisite found the
material dif¬cult at ¬rst, but most managed to assimilate it at a satisfactory
level. The advice to readers for whom this is the ¬rst encounter with the
material in Chapter I is to make a serious effort to master it and to return to
it as it is used in the sequel.
To address as wide an audience as possible, I have not always presented the
most general result or argument. Thus, in Chapter II I chose the ˜˜closest point™™
approach to separation theorems, rather than more generally valid arguments,
because I believe it to be more intuitive and straightforward for the intended
audience. Readers who wish to get the best possible separation theorem in
¬nite dimensions should read Sections 6 and 7 of Chapter II. In proving the
Fritz John Theorem, I used a penalty function argument due to McShane
rather than more technical arguments involving linearizations. I limited the
discussion of duality to Lagrangian duality and did not consider Fenchel
duality, since the latter would require the development of more mathematical
machinery.

ix
x PREFACE


The numbering system and reference system for theorems, lemmas, remarks,
and corollaries is the following. Within a given chapter, theorems, lemmas, and
remarks are numbered consecutively in each section, preceded by the section
number. Thus, the ¬rst theorem of Section 1 is Theorem 1.1, the second,
Theorem 1.2, and so on. The same applies to lemmas and remarks. Corollaries
are numbered consecutively within each section without a reference to the
section number. Reference to a theorem in the same chapter is given by the
theorem number. Reference to a theorem in a chapter different from the current
one is given by the theorem number preceded by the chapter number in Roman
numerals. Thus, a reference in Chapter IV to Theorem 4.1 in Chapter II would
be Theorem II.4.1. References to lemmas and remarks are similar. References
to corollaries within the same section are given by the number of the corollary.
References to corollaries in a different section of the same chapter are given by
pre¬xing the section number to the corollary number; references in a different
chapter are given by pre¬xing the chapter number in Roman numerals to the
preceding.
I thank Rita Saerens and John Gregory for reading the course notes version
of this book and for their corrections and suggestions for improvement. I thank
Terry Combs for preparing the ¬gures. I also thank Betty Gick for typing
seemingly innumerable versions and revisions of the notes for MA 521. Her
skill and cooperation contributed greatly to the success of this project.

L®¤ D. B«©
West Lafayette, Indiana
Convexity and Optimization in n . Leonard D. Berkovitz
Copyright 2002 John Wiley & Sons, Inc.
ISBN: 0-471-35281-0




I
TOPICS IN REAL ANALYSIS


1. INTRODUCTION

The serious study of convexity and optimization problems in RL requires some
background in real analysis and in linear algebra. In teaching a course based
on notes from which this text evolved, the author and his colleagues assumed
that the students had an undergraduate course in linear algebra but did not
necessarily have a background in real analysis. The purpose of this chapter is
to provide the reader with most of the necessary background in analysis. Not
all statements will be proved. The reader, however, is expected to understand
the de¬nitions and the theorems and is expected to follow the proofs of
statements whenever the proofs are given. The bad news is that many readers
will ¬nd this chapter to be the most dif¬cult one in the text. The good news is
that careful study of this material will provide background for many other
courses and that subsequent chapters should be easier. If necessary, the reader
should return to this chapter when encountering this material later on.

2. VECTORS IN RL
By euclidean n-space, or RL, we mean the set of all n-tuples x : (x , . . . , x ),
 L
where the x , i : 1, . . . , n are real numbers. Thus, RL is a generalization of the
G
familiar two- and three-dimensional spaces R and R. The elements x of RL
are called vectors or points. We will often identify the vector x : (x , . . . , x )
 L
with the n ; 1 matrix
x

$
x
L
and abuse the use of the equal sign to write

x

x: $ .
x
L
1
2 TOPICS IN REAL ANALYSIS


In this case we shall call x a column vector. We shall also identify x with the
1 ; n matrix (x , . . . , x ) and write x : (x , . . . , x ). In this case we shall call x
 L  L
a row vector. It will usually be clear from the context whether we consider x
to be a row vector or a column vector. When there is danger of confusion, we
will identify x with the column vector and use the transpose symbol, which is
a superscript t, to denote the row vector. Thus xR : (x , . . . , x ).
 L
We de¬ne two operations, vector addition and multiplication by a scalar. If
x : (x , . . . , x ) and y : (y , . . . , y ) are two vectors, we de¬ne their sum x ; y
 L  L
to be

x ; y : (x ; y , . . . , x ; y ).
  L L
For any scalar, or real number, we de¬ne x to be

x : ( x , . . . , x ).
 L
We assume that the reader is familiar with the properties of these operations
and knows that under these operations RL is a vector space over the reals.
Another important operation is the inner product, or dot product, of two
vectors, denoted by 1x, y2 or xRy and de¬ned by

L
1x, y2 :  x y .
GG
G
Again, we assume that the reader is familiar with the properties of the inner
product. We use the inner product to de¬ne the norm #·# or length of a vector
x as follows:

L 
#x# : 1x, x2 :  x .
G

. 1
( 59 .)



>>