<<

. 58
( 59 .)



>>

Farkas™s lemma In¬mum, 12”14
differentiable nonlinear programming, Inner product, 2
162”163 Interior points
linear inequalities, 63”64, 67”68 continuity of convex functions, 96”98
linear programming, 142 convex sets
n-dimensional, 76
linear programming duality, 220
Feasible sets relative interior points, 80”86
optimization problems, 129
simplex method Jacobian matrix, 25, 165
auxiliary problem, 251”255 Jensen™s inequality, convex functions, 90”91
extreme points, 225”229
Finite-intersection property, 15 Karush”Kuhn”Tucker theorem, differentiable
First-order conditions, differentiable nonlinear nonlinear programming, 155”163
programming, 145”163 constraint quali¬cations, 154”163
Forward transformation, revised simplex second-order conditions, 168”172
method, 258”260 suf¬cient conditions, 159”160
Frechet differentiable, 24
´ Krein”Milman theorem, 60
Free variables, simplex method, 230 Kuhn”Tucker vectors
Fritz-John theorem, differentiable nonlinear de¬nition, 184
programming, 146”163 examples, 197”200
second-order conditions, 172”174 as multipliers, 184”185
Fundamental existence theorem, 18”20 as subgradients of value function,
194”196
Gale™s theorem, linear inequalities, 68
Game theory, 117”127 Lagrange multipliers
optimal mixed strategies, 126”127 convex programming
optimal pure strategies, 125”126 as Kuhn”Tucker vectors, 184”815
Gauge functions, 101 necessary conditions, 181”184
Gauss elimination, 232”234 saddle point conditions, 187”188
Gauss”Jordan elimination, 233”234 as subgradients of value function,
Geometric interpretation, convex programming 194”196
duality, 207”210 suf¬cient conditions, 186”187
Gordan™s theorem differentiable nonlinear programming, ¬rst-
generalization to convex functions, 215 order conditions, 146”163
linear inequalities, 65”67 Lagrangian duality, convex programming,
quadratic programming, 211”215 200”207
quadratic programming, 211”215
Half-open line segments, 31 Leaving variables
Half spaces, 35”36 revised simplex method, 256”260
intersection theorems, 55”56 simplex method, 239”245
Hessian matrix Left-hand limit, real numbers, 14
266 INDEX

Limit points Mean-square approximation by orthogonal
continuity, 9”11 functions, 135
Metric toplogy, Euclidean n-space (RL), 5”8
metric toplogy, 6
Limits, 9”11 Minimizers
Linear functionals convex function optimization, 137”139
Euclidean n-space (RL), 21”24 convex programming
hyperplane de¬nition, 33”34 necessary and suf¬cient conditions,
Linear inequalities 183”188
convex sets, theorems of the alternative, quadratic programming, 213”215
61”68 differentiable nonlinear programming,
Farkas™s lemma, 63”65, 67 145”163
Gale™s theorem, 68 fundamental existence theorem, 19”20
Gordan™s theorem, 65”67 linear programming, 140”145
Motzkin™s theorem, 66”67 Minkowski distance function, 101
Linear manifolds, 69”71 Mixed strategies, 125”127
dimension, 70”71 Morgan™s law, 4”5
Linear programming. See also Nonlinear Motzkin™s theorem, linear inequalities, 66”67
Multipliers, see Kuhn”Tucker vectors;
programming
canonical linear programming problem, 144 Lagrange multipliers
complementary slackness condition,
141”145 Necessary conditions
duality in, 215”221 convex programming, 181”188
formulation, 139”140 differentiable nonlinear programming
necessary and suf¬cient conditions, ¬rst-order conditions, 145”163
141”145 second-order conditions, 163”178
simplex method linear programming duality, 215”221
auxiliary problem, 251”255 quadratic programming, 211”215
examples, 222”225 Negative half space, convex set properties,
extreme points, feasible set, 225”229 35”36
phase I procedure, 251”255 Nonbasic variables, simplex method, 230
phase II procedure, 234”245 Nonlinear programming, differentiable
preliminaries, 230”234 problems
revised method, 255”260 ¬rst-order conditions, 145”163
termination and cycling, 245”250 second-order conditions, 163”178
standard vs. canonical linear forms, 144”145 Nontrivial supporting hyperplane, 56”57, 85
Linear regression, 134”135 Null set, 4”5
Linear transformation
as derivative, 22”25 Open cover, 14”15
Euclidean n-space (RL), 21 Open line segment, 31
Line segments, 31 Open sets, metric toplogy, 6”8
Lipschitz continuous functions, 98 Optimal solution, simplex method, 231,
Local minimizers 238”245
Optimal strategies, see Game theory
convex functions, 137
differentiable nonlinear programming, Orthogonality, 4
second-order suf¬ciency theorems,
172”178 Parallel hyperplanes, 34
differentiable unconstrained problems, Parallel subspace, 70
129”136 Payoff matrix, 123”127
Logarithmic convexity, 113 ˜˜Penalty function™™ proof, differentiable
Lower bounds, real numbers, 12”13 nonlinear programming, 151”163
Perturbation theory, 188”200
Matrix games, 122”127 Pivot position, simplex method, 244”245
Maximization of convex functions, 137”139 auxiliary problems, 252”255
INDEX 267

Positive de¬nite matrix, 111”112, 135”136 simplex method, phase I, 251”255
Positive half space, 35”36 Smallest index rule, simplex method,
Primal convex programming problem (CPII), termination and cycling, 248”250
180”188 Strict local minimizers
Lagrangian duality, 200”207 de¬ned, 128
Proper separation, convex sets, 46 differentiable nonlinear programming,
second-order suf¬cient conditions,
Quadratic programming, 210”215 172”178
dual quadratic program (DQP), 214”215 differentiable unconstrained problems,
130”136
Real numbers, boundedness properties, Strictly convex function
11”14 de¬ned, 87”88
Relative boundaries, convex sets, support and differential criteria, 109”111
separation theorems, 81”86 Strict separation, convex sets, 46”47
Relative interior, convex sets, support and Strong separation, convex sets, 47”48
separation theorems, 80”86 Subdifferentials, convex functions, 102”106
Revised simplex method, 255”260 Subgradients, convex functions, 102”106
Right-hand limit, 13”14 differentiable functions, 106”109
Submarine-convoy game, 124”127
Saddle points Subsequences, continuity, 9”11
convex programming Suf¬cient conditions
Lagrangian duality, 206”207 convex programming, 181”187
necessary and suf¬cient conditions, for absence of duality gap, 206”207
182”188 quadratic programming, 211
game theory applications, 125”127 differentiable nonlinear programming,
Second derivative test, differentiable 159”160
unconstrained problems, 130”133 second-order conditions, 172”178
Second-order conditions, differentiable linear programming duality, 218”219
nonlinear programming, 163”178 Support function, 101
Second-order test vector, differential nonlinear Supporting hyperplanes, 56”57, 85
programming, 167”178 Supremum, 12”14
Sensitivity vector, convex programming,
perturbation theory, 193 Tableau method, 236
Separation theorems, 45”56 Tangential constraints, differentiable nonlinear
alternative theorems, 61”68 programming, 165”178
best possible in RL, 82”85 second-order suf¬ciency theorems, 172”178
disjoint convex sets, 53”56, 82 Termination, simplex method, 245”250
point and convex set, 49”53 Theorems of the alternative, linear inequalities,
proper separation, 46, 53”54 61”68
strict separation, 46”47 Farkas™s lemma, 63”65, 67”68
strong separation, 47”49, 54 Gale™s theorem, 68
Sequential criterion, Euclidean n-space (RL) Gordan™s theorem, 65”67
limits, 10”11 Motzkin™s theorem, 66”67
Simplex method Three-chord property, convex functions,
examples, 222”225 92”94
extreme points, feasible set, 225”229 Triangle inequality, 3
phase I procedure, 251”255 Two-person zero-sum games, 122”127
phase II procedure, 234”245
preliminaries, 230”234 Unbounded sets
revised method, 255”260 revised simplex method, 259
termination and cycling, 245”250 simplex method, 223, 238”240
Slack variables Unconstrained problems
linear programming, 144 differentiable problems, 129”136
268 INDEX

Unconstrained problems (Continued) Upper bounds, real numbers, 11”14
linear regression, 134”135
orthogonal mean-square approximations, Value function, perturbation theory, 189”200
135”136 Vector-valued convex functions, alternative
second derivative test, 130”133 theorems, 113”117
strict minimizers, 130, 132 Von Neumann minimax theorem, 117”121
Uniform continuity, 117
Convexity and Optimization in n . Leonard D. Berkovitz
Copyright 2002 John Wiley & Sons, Inc.
ISBN: 0-471-35281-0




PURE AND APPLIED MATHEMATICS
A Wiley-Interscience Series of Texts, Monographs, and Tracts
Founded by RICHARD COURANT
Editors: MYRON B. ALLEN III, DAVID A. COX, PETER LAX
Editors Emeriti: PETER HILTON, HARRY HOCHSTADT, JOHN TOLAND
A complete list of the titles in this series appears at the end of this volume.
PURE AND APPLIED MATHEMATICS
A Wiley-Interscience Series of Texts, Monographs, and Tracts



Founded by RICHARD COURANT
Editors: MYRON B. ALLEN III, DAVID A. COX, PETER LAX
Editors Emeriti: PETER HILTON, HARRY HOCHSTADT, JOHN TOLAND




ADÁMEK, HERRLICH, and STRECKER”Abstract and Concrete Catetories
ADAMOWICZ and ZBIERSKI”Logic of Mathematics
AINSWORTH and ODEN”A Posteriori Error Estimation in Finite Element Analysis
AKIVIS and GOLDBERG”Conformal Differential Geometry and Its Generalizations
ALLEN and ISAACSON”Numerical Analysis for Applied Science
*ARTIN”Geometric Algebra
AUBIN”Applied Functional Analysis, Second Edition
AZIZOV and IOKHVIDOV”Linear Operators in Spaces with an Indefinite Metric
BERG”The Fourier-Analytic Proof of Quadratic Reciprocity
BERMAN, NEUMANN, and STERN”Nonnegative Matrices in Dynamic Systems
BERKOVITZ”Convexity and Optimization in n
BOYARINTSEV”Methods of Solving Singular Systems of Ordinary Differential
BOYARINTSEV”Equations
BURK”Lebesgue Measure and Integration: An Introduction
*CARTER”Finite Groups of Lie Type
CASTILLO, COBO, JUBETE, and PRUNEDA”Orthogonal Sets and Polar Methods in
Linear Algebra: Applications to Matrix Calculations, Systems of Equations,
Inequalities, and Linear Programming
CASTILLO, CONEJO, PEDREGAL, GARCIÁ, and ALGUACIL”Building and Solving
Mathematical Programming Models in Engineering and Science
CHATELIN”Eigenvalues of Matrices
CLARK”Mathematical Bioeconomics: The Optimal Management of Renewable
CLARK”Resources, Second Edition
COX”Primes of the Form x2 + ny 2: Fermat, Class Field Theory, and Complex
Multiplication
*CURTIS and REINER”Representation Theory of Finite Groups and Associative Algebras
*CURTIS and REINER”Methods of Representation Theory: With Applications to Finite
*CURTIS and REINER”Groups and Orders, Volume I
CURTIS and REINER”Methods of Representation Theory: With Applications to Finite
*CURTIS and REINER”Groups and Orders, Volume II
DINCULEANU”Vector Integration and Stochastic Integration in Banach Spaces
*DUNFORD and SCHWARTZ”Linear Operators
*DUNFORD and SCHWARTZ” Part 1”General Theory
*DUNFORD and SCHWARTZ” Part 2”Spectral Theory, Self Adjoint Operators in
Hilbert Space
*DUNFORD and SCHWARTZ” Part 3”Spectral Operators
FARINA and RINALDI”Positive Linear Systems: Theory and Applications
FOLLAND”Real Analysis: Modern Techniques and Their Applications
FR–LICHER and KRIEGL”Linear Spaces and Differentiation Theory
GARDINER”Teichmüller Theory and Quadratic Differentials
GREENE and KRANTZ”Function Theory of One Complex Variable
*Now available in a lower priced paperback edition in the Wiley Classics Library.
†Now available in paperback.
*GRIFFITHS and HARRIS”Principles of Algebraic Geometry
GRILLET”Algebra
GROVE”Groups and Characters
GUSTAFSSON, KREISS and OLIGER”Time Dependent Problems and Difference
GUSTAFSSON, KREISS and OLIGER”Methods
HANNA and ROWLAND”Fourier Series, Transforms, and Boundary Value Problems,
HANNA and ROWLAND”Second Edition
*HENRICI”Applied and Computational Complex Analysis
*HENRICI”Volume 1, Power Series”Integration”Conformal Mapping”Location
of Zeros
*HENRICI”Volume 2, Special Functions”Integral Transforms”Asymptotics”
Continued Fractions
*HENRICI”Volume 3, Discrete Fourier Analysis, Cauchy Integrals, Construction
of Conformal Maps, Univalent Functions
*HILTON and WU”A Course in Modern Algebra
*HOCHSTADT”Integral Equations
JOST”Two-Dimensional Geometric Variational Procedures
KHAMSI and KIRK”An Introduction to Metric Spaces and Fixed Point Theory
*KOBAYASHI and NOMIZU”Foundations of Differential Geometry, Volume I
*KOBAYASHI and NOMIZU”Foundations of Differential Geometry, Volume II
KOSHY”Fibonacci and Lucas Numbers with Applications
LAX”Linear Algebra
LOGAN”An Introduction to Nonlinear Partial Differential Equations
McCONNELL and ROBSON”Noncommutative Noetherian Rings
MORRISON”Functional Analysis: An Introduction to Banach Space Theory
NAYFEH”Perturbation Methods
NAYFEH and MOOK”Nonlinear Oscillations
PANDEY”The Hilbert Transform of Schwartz Distributions and Applications
PETKOV”Geometry of Reflecting Rays and Inverse Spectral Problems
*PRENTER”Splines and Variational Methods
RAO”Measure Theory and Integration
RASSIAS and SIMSA”Finite Sums Decompositions in Mathematical Analysis
RENELT”Elliptic Systems and Quasiconformal Mappings
RIVLIN”Chebyshev Polynomials: From Approximation Theory to Algebra and Number
RIVLIN”Theory, Second Edition
ROCKAFELLAR”Network Flows and Monotropic Optimization
ROITMAN”Introduction to Modern Set Theory

<<

. 58
( 59 .)



>>