Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.

org/terms-privacy

Nonlinear
Optimization
Introduction to
 MOS-SIAM Series on Optimization
This series is published jointly by the Mathematical Optimization Society and the Society for Industrial and Applied
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Mathematics. It includes research monographs, books on applications, textbooks at all levels, and tutorials.
Besides being of high scientific quality, books in the series must advance the understanding and practice of
optimization. They must also be written clearly and at an appropriate level for the intended audience.
Editor-in-Chief
Jesús De Loera
University of California, Davis

Editorial Board
Gennadiy Averkov, Otto von Guericke University Magdeburg Simge Küçükyavuz, Northwestern University
Amitahn Basu, Johns Hopkins University Andrea Lodi, Polytechnique de Montréal
Maryam Fazel, University of Washington Rekha Thomas, University of Washington
Serge Gratton, INP-ENSEEIHT Stephen J. Wright, University of Wisconsin
Fatima Kilinç-Karzan, Carnegie Mellon University

Series Volumes
Beck, Amir, Introduction to Nonlinear Optimization: Locatelli, Marco and Schoen, Fabio, Global Optimization:
Theory, Algorithms, and Applications with Python and Theory, Algorithms, and Applications
MATLAB, Second Edition De Loera, Jesús A., Hemmecke, Raymond, and Köppe,
Nie, Jiawang, Moment and Polynomial Optimization Matthias, Algebraic and Geometric Ideas in the
Theory of Discrete Optimization
Cartis, Coralia, Gould, Nicholas I. M., and Toint, Philippe
L., Evaluation Complexity of Algorithms for Nonconvex Blekherman, Grigoriy, Parrilo, Pablo A., and Thomas,
Optimization: Theory, Computation, and Perspectives Rekha R., editors, Semidefinite Optimization and
Convex Algebraic Geometry
Cui, Ying and Pang, Jong-Shi, Modern Nonconvex
Nondifferentiable Optimization Delfour, M. C., Introduction to Optimization and
Semidifferential Calculus
Shapiro, Alexander, Dentcheva, Darinka, and
Ruszczyński, Andrzej, Lectures on Stochastic Ulbrich, Michael, Semismooth Newton Methods for
Programming: Modeling and Theory, Third Edition Variational Inequalities and Constrained Optimization
Delfour, Michel C., Introduction to Optimization and Problems in Function Spaces
Hadamard Semidifferential Calculus, Second Edition Biegler, Lorenz T., Nonlinear Programming: Concepts,
Campi, Marco C. and Garatti, Simone, Introduction to the Algorithms, and Applications to Chemical Processes
Scenario Approach Shapiro, Alexander, Dentcheva, Darinka, and
Beck, Amir, First-Order Methods in Optimization Ruszczyński, Andrzej, Lectures on Stochastic
Terlaky, Tamás, Anjos, Miguel F., and Ahmed, Shabbir, Programming: Modeling and Theory
editors, Advances and Trends in Optimization with Conn, Andrew R., Scheinberg, Katya, and Vicente, Luis
Engineering Applications N., Introduction to Derivative-Free Optimization
Todd, Michael J., Minimum-Volume Ellipsoids: Theory Ferris, Michael C., Mangasarian, Olvi L., and Wright,
and Algorithms Stephen J., Linear Programming with MATLAB
Bienstock, Daniel, Electrical Transmission System Attouch, Hedy, Buttazzo, Giuseppe, and Michaille, Gérard,
Cascades and Vulnerability: An Operations Research Variational Analysis in Sobolev and BV Spaces:
Viewpoint Applications to PDEs and Optimization
Koch, Thorsten, Hiller, Benjamin, Pfetsch, Marc E., Wallace, Stein W. and Ziemba, William T., editors,
and Schewe, Lars, editors, Evaluating Gas Network Applications of Stochastic Programming
Capacities Grötschel, Martin, editor, The Sharpest Cut: The Impact
Corberán, Ángel and Laporte, Gilbert, Arc Routing: of Manfred Padberg and His Work
Problems, Methods, and Applications Renegar, James, A Mathematical View of Interior-Point
Toth, Paolo and Vigo, Daniele, Vehicle Routing: Problems, Methods in Convex Optimization
Methods, and Applications, Second Edition Ben-Tal, Aharon and Nemirovski, Arkadi, Lectures on
Beck, Amir, Introduction to Nonlinear Optimization: Modern Convex Optimization: Analysis, Algorithms,
Theory, Algorithms, and Applications with MATLAB and Engineering Applications
Attouch, Hedy, Buttazzo, Giuseppe, and Michaille, Gérard, Conn, Andrew R., Gould, Nicholas I. M., and Toint,
Variational Analysis in Sobolev and BV Spaces: Phillippe L., Trust-Region Methods
Applications to PDEs and Optimization, Second Edition
Shapiro, Alexander, Dentcheva, Darinka, and
Ruszczyński, Andrzej, Lectures on Stochastic
Programming: Modeling and Theory, Second Edition
 Introduction to
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Nonlinear
Optimization
Theory, Algorithms, and
Applications with
Python and MATLAB
Second Edition

Amir Beck
Tel Aviv University
Tel Aviv, Israel

Society for Industrial and Applied Mathematics Mathematical Optimization Society

Philadelphia Philadelphia
 Copyright © 2023 by the Society for Industrial and Applied Mathematics
10 9 8 7 6 5 4 3 2 1
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

All rights reserved. Printed in the United States of America. No part of this book may be
reproduced, stored, or transmitted in any manner without the written permission of the
publisher. For information, write to the Society for Industrial and Applied Mathematics,
3600 Market Street, 6th Floor, Philadelphia, PA 19104-2688 USA.
No warranties, express or implied, are made by the publisher, authors, and their employers
that the programs contained in this volume are free of error. They should not be relied on as
the sole basis to solve a problem whose incorrect solution could result in injury to person or
property. If the programs are employed in such a manner, it is at the user’s own risk and the
publisher, authors, and their employers disclaim all liability for such misuse.
Trademarked names may be used in this book without the inclusion of a trademark symbol.
These names are used in an editorial context only; no infringement of trademark is intended.

Publications Director Kivmars H. Bowling

Executive Editor Elizabeth Greenspan
Acquisitions Editor Paula Callaghan
Developmental Editor Rose Kolassiba
Managing Editor Kelly Thomas
Production Editor Louis R. Primus
Copy Editor Susan Fleshman
Production Manager Donna Witzleben
Production Coordinator Cally A. Shrader
Compositor Cheryl Hufnagle
Graphic Designer Doug Smock

Library of Congress Cataloging-in-Publication Data

Names: Beck, Amir, author.
Title: Introduction to nonlinear optimization : theory, algorithms and
applications with Python and MATLAB / Amir Beck, Tel Aviv University,
Tel Aviv, Israel.
Description: Second edition. | Philadelphia : Society for Industrial and
Applied Mathematics, [2023] | Series: MOS-SIAM series on optimization |
Includes bibliographical references and index. | Summary: "This book is
a modern introduction to the area of optimization. Its objective is to
provide the foundations of theory and algorithms of nonlinear
optimization, as well as to present a variety of applications from
diverse areas of applied sciences"-- Provided by publisher.
Identifiers: LCCN 2023009070 (print) | LCCN 2023009071 (ebook) | ISBN
9781611977615 (paperback) | ISBN 9781611977622 (ebook)
Subjects: LCSH: Mathematical optimization. | Nonlinear theories. | MATLAB.
| AMS: Functional analysis -- Miscellaneous applications of functional
analysis -- Applications in optimization, convex analysis, mathematical
programming, economics. | Calculus of variations and optimal control;
optimization -- Optimality conditions -- None of the above, but in this
section.
Classification: LCC QA402.5 .B4224 2023 (print) | LCC QA402.5 (ebook) |
DDC 515/.642--dc23/eng/20230531
LC record available at https://lccn.loc.gov/2023009070
LC ebook record available at https://lccn.loc.gov/2023009071

is a registered trademark. is a registered trademark.

Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

For

My wife Nili

My parents Nili and Itzhak

My daughters Noy and Vered
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Contents

Preface xi

1 Mathematical Preliminaries 1
1.1 The Space Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Space R m×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Inner Products and Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Basic Topological Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Optimality Conditions for Unconstrained Optimization 13

2.1 Global and Local Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Classification of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Second Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Global Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Quadratic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3 Least Squares 43
3.1 “Solution” of Overdetermined Systems . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Data Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Regularized Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Denoising . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Nonlinear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6 Circle Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4 The Gradient Method 57

4.1 Descent Directions Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 The Gradient Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3 The Condition Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Diagonal Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5 The Gauss–Newton Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.6 The Fermat–Weber Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.7 Convergence Analysis of the Gradient Method . . . . . . . . . . . . . . . . . . 83
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

vii
 viii Contents

5 Newton’s Method 95
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

5.1 Pure Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.2 Damped Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.3 The Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6 Convex Sets 113

6.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2 Algebraic Operations with Convex Sets . . . . . . . . . . . . . . . . . . . . . . . 116
6.3 The Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.4 Convex Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.5 Topological Properties of Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . 124
6.6 Extreme Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

7 Convex Functions 135

7.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.2 First Order Characterization of Convex Functions . . . . . . . . . . . . . . . . 137
7.3 Second Order Characterization of Convex Functions . . . . . . . . . . . . . . 141
7.4 Operations Preserving Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.5 Level Sets of Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.6 Continuity and Differentiability of Convex Functions . . . . . . . . . . . . . 150
7.7 Extended Real-Valued Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.8 Maxima of Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.9 Convexity and Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

8 Convex Optimization 171

8.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.3 The Orthogonal Projection Operator . . . . . . . . . . . . . . . . . . . . . . . . 180
8.4 CVX (MATLAB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
8.5 CVXPY (Python) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

9 Optimization over a Convex Set 207

9.1 Stationarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.2 Stationarity in Convex Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
9.3 The Orthogonal Projection Revisited . . . . . . . . . . . . . . . . . . . . . . . . 211
9.4 The Gradient Projection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
9.5 Sparsity Constrained Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

10 Optimality Conditions for Linearly Constrained Problems 231

10.1 Separation and Alternative Theorems . . . . . . . . . . . . . . . . . . . . . . . . 231
10.2 The KKT conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
 Contents ix

10.3 Orthogonal Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

11 The KKT Conditions 253

11.1 Inequality Constrained Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
11.2 Inequality and Equality Constrained Problems . . . . . . . . . . . . . . . . . . 256
11.3 The Convex Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.4 Constrained Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
11.5 Second Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . 269
11.6 Optimality Conditions for the Trust Region Subproblem . . . . . . . . . . . 273
11.7 Total Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

12 Duality 291
12.1 Motivation and Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
12.2 Strong Duality in the Convex Case . . . . . . . . . . . . . . . . . . . . . . . . . . 295
12.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Answers and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

Bibliographic Notes 343

Bibliography 345

Index 349
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Preface

Preface to the Second Edition: The second edition features two significant
enhancements to the first edition.
1. Python codes were added on top of the existing MATLAB codes to illustrate and demon-
strate different aspects of the algorithmic and applicative nature of nonlinear optimiza-
tion. Since the first edition’s publication, Python has become one of the leading software
languages for scientific computing and is used in many applications, most notably those
arising in data science. Readers interested in implementation may choose to follow ei-
ther the MATLAB or Python codes which appear, sometimes literally, side by side. A
new section on the Python module CVXPY (Section 8.5) describes how to solve convex
optimization problems using Python.
2. The new edition contains more than 90 new exercises. Final answers to many of the
overall 250 exercises were added, as well as more than 70 full and detailed solutions at the
end of the chapters, effectively providing many more examples that illustrate the theory
and techniques of nonlinear optimization. Exercises with final answers are marked by
(◦) and those with full solutions are marked by (•).
I hope the new edition will benefit the readers in their journey into the fascinating world of
nonlinear optimization.

I want to thank Dror Pan for reading the book and for his extremely helpful remarks.

Preface to the First Edition: This book emerged from the idea that optimization
training should include three basic components: a strong theoretical and algorithmic founda-
tion, familiarity with various applications, and the ability to apply the theory and algorithms
on actual “real-life” problems. The book is intended to be the basis of such an extensive train-
ing. The mathematical development of the main concepts in nonlinear optimization is done
rigorously, where a special effort was made to keep the proofs as simple as possible. The results
are presented gradually and accompanied with many illustrative examples. Since the aim is not
to give an encyclopedic overview, the focus is on the most useful and important concepts. The
theory is complemented by numerous discussions on applications from various scientific fields
such as signal processing, economics, and localization. Some basic algorithms are also presented
and studied to provide some flavor of this important aspect of optimization. Many topics are
demonstrated by MATLAB programs, and ideally, the interested reader will find satisfaction in
the ability to actually solve problems on his or her own. The book contains several topics that,
compared to other classical textbooks, are treated differently. The following are some examples
of the less common issues.
• The treatment of stationarity is comprehensive and discusses this important notion in
the presence of sparsity constraints.

xi
 xii Preface

• The concept of “hidden convexity” is discussed and illustrated in the context of the trust
Downloaded 11/18/24 to 5.198.138.118 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

region subproblem.
• The MATLAB toolbox CVX is explored and used.

• The gradient mapping and its properties are studied and used in the analysis of the gradi-
ent projection method.
• Second order necessary optimality conditions are treated using a descent direction ap-
proach.

• Applications such as circle fitting, the Chebyshev center, the Fermat–Weber problem,
denoising, clustering, total least squares, and orthogonal regression are studied both the-
oretically and algorithmically, illustrating concepts such as duality. MATLAB programs
are used to show how the theory can be implemented.
The book is intended for students and researchers with a basic background in advanced calculus
and linear algebra, but no prior knowledge of optimization theory is assumed. The book con-
tains more than 170 exercises, which can be used to deepen the understanding of the material.
The MATLAB functions described throughout the book can be found at
www.siam.org/books/mo19.

The outline of the book is as follows. Chapter 1 recalls some of the important concepts in linear
algebra and calculus that are essential for the understanding of the mathematical developments
in the book. Chapter 2 focuses on local and global optimality conditions for smooth uncon-
strained problems. Quadratic functions are also introduced along with their basic properties.
Linear and nonlinear least squares problems are introduced and studied in Chapter 3. Several
applications such as data fitting, denoising, and circle fitting are discussed. The gradient method
is introduced and studied in Chapter 4. The chapter also contains a discussion on descent di-
rection methods and various stepsize strategies. Extensions such as the scaled gradient method
and damped Gauss–Newton are considered. The connection between the gradient method and
Weiszfeld’s method for solving the Fermat–Weber problem is established. Newton’s method is
discussed in Chapter 5. Convex sets and functions along with their basic properties are the sub-
jects of Chapters 6 and 7. Convex optimization problems are introduced in Chapter 8, which
also includes a variety of applications as well as CVX demonstrations. Chapter 9 focuses on
several important topics related to optimization problems over convex sets: stationarity, gradi-
ent mappings, and the gradient projection method. The chapter ends with results on sparsity
constrained problems, illuminating the different type of results obtained when the underlying
set is not convex. The derivation of the KKT optimality conditions from the separation and
alternative theorems is the subject of Chapter 10, where only linearly constrained problems
are considered. The extension of the KKT conditions to problems with nonlinear constraints
is discussed in Chapter 11, which also considers the second order necessary conditions. Appli-
cations of the conditions to the trust region and total least squares problems are studied. The
book ends with a discussion on duality in Chapter 12. Strong duality under convexity assump-
tions is established. This chapter also includes a large amount of examples, applications, and
MATLAB illustrations.
I would like to thank Dror Pan and Luba Tetruashvili for reading the book and for their
helpful remarks. It has been a pleasure working with the SIAM staff, namely with Bruce Bailey,
Elizabeth Greenspan, Sara Murphy, Gina Rinelli, and Kelly Thomas.