Preface

Constrained optimization is a critical and contemporary subject across many disciplines. For example, many principles in classical economical theory are developed based on optimization theory to allocate scarce resources optimally. More recently, theory in optimization has been developed rapidly to catch up with the recent trend of Artificial Intelligence and Machine Learning. The increasing demand for knowledge in optimization led the Department of Mathematics at National Taiwan University to offer an 32-hour elective course on constrained optimization (titled ‘Calculus 4 – Applications in Economics and Management’) in the spring of 2019. The course is intended for students who have just finished courses in classical multivariable (differential) calculus.

The aforementioned course aims to extend and refine the elementary forms of the second derivative test for functions of two variables and the method of Lagrange multipliers for problems with equality constraints, as introduced in students’ earlier courses. To give a little more detail, these ideas were further developed to handle optimization problems involving both equality and inequality constraints, to identify degenerate points arising from such constraints, to derive Envelope Theorems that capture the sensitivity of the optimal value with respect to variations in the constraints and to formulate second-order conditions for constrained optimization problems in spaces of arbitrary dimension. The course has been well-received by both students and faculty members.

To achieve this goal, we will require a substantial background from linear algebra which is the formal language and theory of vectors and matrices. These concepts will be introduced in the beginning. Indeed, optimization theory is one of the many instances in mathematics where (linear) algebra and calculus intersect and enrich each other. The tools of both disciplines work in harmony to deepen our understanding of constrained optimization problems.

Although much literature and textbooks already exist on the subject, most are either too advanced or, at the other extreme, lack sufficient mathematical rigor. This book aims to introduce the basics of optimization theory in an intuitive manner that is accessible to undergraduate students who have acquired a standard course in multivariable differential calculus while maintaining some level of mathematical rigor. The authors believe that understanding both applications and mathematical foundations of optimization theory is crucial for preparing students of this generation, correctly, for more advanced courses and future challenges.

Preface

Constrained optimization is a critical and contemporary subject across many disciplines. For example, many principles in classical economical theory are developed based on optimization theory to allocate scarce resources optimally. More recently, theory in optimization has been developed rapidly to catch up with the recent trend of Artificial Intelligence and Machine Learning. The increasing demand for knowledge in optimization led the Department of Mathematics at National Taiwan Univ...

Preface
Acknowledgment
Introduction
1Linear Algebra (I): Vocabulary
1.1Vector space Rn and its properties
1.2Subspaces of Rn
1.3Linear independence
1.4Basis and dimension
1.5Inner product of Rn
1.6Gram-Schmidt process
1.7Exercises for Chapter 1
2Linear Algebra (II): Ranks
2.1Review on matrices
2.2Solving equations by Gaussian eliminations
2.3Applications of Gaussian eliminations
2.4Rank
2.5Determinant
2.6Inverse
2.7Exercises for Chapter 2
3Linear Algebra (III): Definiteness
3.1Some special matrices
3.2Motivation: Complete the squares
3.3Eigenvalues and eigenvectors
3.4Diagonalization of symmetric matrices
3.5Definiteness
3.6Sylvester's criterion
3.7Connection with quadratic forms
3.8Second derivative test and generalization
3.9Proof of Sylvester's criterion
3.10Exercises for Chapter 3
4Constrained Optimization (I)
4.1Optimization: Equality constraints
4.2Non-degenerate constraint qualifications (NDCQ)
4.3Worked example: Equality constraints
4.4Optimization: Inequality constraints
4.5NDCQ for inequality constrained problems
4.6Proof of complementary slackness
4.7Proof of non-negativity of multipliers
4.8Worked example: Inequality constraints
4.9Worked examples: Linear programming on R2
4.10Exercises for Chapter 4
5Constrained Optimization (II)
5.1Optimization: Mixed constraints
5.2Worked examples: Mixed constraints
5.3Optimization: Minimization problems
5.4Worked example: Minimization problems
5.5Optimization: Kuhn-Tucker's formulation
5.6Proof of Kuhn-Tucker's FOC
5.7NDCQ in Kuhn-Tucker's formulation
5.8Worked examples : Kuhn-Tucker's formulation
5.9Exercises for Chapter 5
6Envelope Theorems
6.1Motivation: Linear budget constraint problem
6.2Envelope Theorem for equality constraints
6.3Worked example: Envelope Theorem
6.4Applications: Shadow prices
6.5Envelope Theorem for unconstrained problems
6.6Envelope Theorem for inequality constraints
6.7Applications in Economics
6.8Proofs of Envelope Theorems
6.9Exercises for Chapter 6
7Second Order Conditions
7.1Motivation : Bordered Hessian matrices
7.2Bordered Hessian matrices
7.3Second order conditions: Statement
7.4Worked examples: Second order conditions
7.5Second derivative test for unconstrained problems
7.6Sketch of the proofs of SOC
7.7Exercises for Chapter 7
Appendix. Di!erential Calculus
A. Partial derivatives
B. Chain rule for multivariable functions
C. Elementary results of optimization in multivariables
Answers to Selected Exercises
Bibliography
Index

Preface
Acknowledgment
Introduction
1Linear Algebra (I): Vocabulary
1.1Vector space Rn and its properties
1.2Subspaces of Rn
1.3Linear independence
1.4Basis and dimension
1.5Inner product of Rn
1.6Gram-Schmidt process
1.7Exercises for Chapter 1
2Linear Algebra (II): Ranks
2.1Review on matrices
2.2Solving equations by Gaussian eliminations
2.3Applications of Gaussian eliminations
2.4Rank
2.5Determinant
2.6Inverse
2.7Exercises for Chapter 2
3Linear Algebra (III): Definiteness
...