Linear and Nonlinear Programming Essentials

Linear and Nonlinear Programming Essentials

Linear and Nonlinear Programming Essentials

By

Tanushri Kaniyar

Linear and Nonlinear Programming Essentials

Tanushri Kaniyar

ISBN - 9789361527975

COPYRIGHT © 2025 by Educohack Press. All rights reserved.

This work is protected by copyright, and all rights are reserved by the Publisher. This includes, but is not limited to, the rights to translate, reprint, reproduce, broadcast, electronically store or retrieve, and adapt the work using any methodology, whether currently known or developed in the future.

The use of general descriptive names, registered names, trademarks, service marks, or similar designations in this publication does not imply that such terms are exempt from applicable protective laws and regulations or that they are available for unrestricted use.

The Publisher, authors, and editors have taken great care to ensure the accuracy and reliability of the information presented in this publication at the time of its release. However, no explicit or implied guarantees are provided regarding the accuracy, completeness, or suitability of the content for any particular purpose.

If you identify any errors or omissions, please notify us promptly at educohackpress@gmail.com & sales@educohackpress.com We deeply value your feedback and will take appropriate corrective actions.

The Publisher remains neutral concerning jurisdictional claims in published maps and institutional affiliations.

Published by Educohack Press, House No. 537, Delhi- 110042, INDIA

Email: educohackpress@gmail.com & sales@educohackpress.com

Cover design by Team EDUCOHACK

Preface

Welcome to Linear and Nonlinear Programming, a comprehensive guide tailored for undergraduate students in the United States seeking a thorough understanding of optimization techniques and their applications. This book serves as an indispensable resource for students pursuing degrees in mathematics, computer science, engineering, economics, and related fields, providing a solid foundation in both linear and nonlinear programming.

Optimization plays a vital role in various domains, from operations research and logistics to finance and machine learning. With this in mind, our goal is to demystify the concepts of linear and nonlinear programming and equip readers with the knowledge and skills necessary to tackle real-world optimization problems effectively.

Throughout this book, we delve into fundamental concepts such as linear programming models, convex optimization, duality theory, and algorithmic techniques for solving optimization problems. Real-world examples and case studies illustrate the practical application of optimization techniques in diverse settings, empowering students to recognize optimization opportunities and devise effective solutions.

Whether you’re just beginning your journey into optimization or seeking to deepen your understanding of advanced techniques, Linear and Nonlinear Programming provides a comprehensive and accessible roadmap. With clear explanations, illustrative examples, and practical exercises, this book aims to inspire curiosity and foster mastery in the fascinating field of optimization. Let’s embark on this journey together and unlock the power of optimization.

Table of Contents

Chapter-1

Introduction to Optimization 1

1.1 What is Optimization? 1

1.2 Applications of Optimization 2

1.3 Types of Optimization Problems 3

1.4 Linear vs. Nonlinear Programming 6

1.5 Modeling Optimization Problems 7

1.6 Optimization Software and Tools 8

Conclusion 11

References 12

Chapter-2

Linear Programming: Fundamentals 13

2.1 The Linear Programming Problem 13

2.2 Graphical Solution for Two-Variable Problems 14

2.3 Slack and Surplus Variables 15

2.4 Standard Form of Linear Programming Problems 17

2.5 Sensitivity Analysis 18

2.6 Computer Solutions for Linear

Programming 19

Conclusion 21

References 21

Chapter-3

The Simplex Method 23

3.1 Introduction to the Simplex Method 23

3.2 Simplex Algorithm 24

3.3 Simplex Tableaux 24

3.4 Unbounded and Infeasible Solutions 27

3.5 Duality in Linear Programming 29

3.6 Sensitivity Analysis with the Simplex

Method 31

Conclusion 34

References 35

Chapter-4

Transportation and Assignment Problems 36

4.1 The Transportation Problem 36

4.2 The Northwest Corner Method 37

4.3 The Least-Cost Method 38

4.4 The Vogel’s Approximation Method 41

4.5 The Assignment Problem 43

4.6 The Hungarian Method 44

Conclusion 49

References 49

Chapter-5

Network Optimization 51

5.1 Network Models 51

5.2 Shortest Path Problems 52

5.3 Minimum Spanning Tree Problems 55

5.4 Maximum Flow Problems 59

5.5 Project Scheduling (PERT/CPM) 60

5.6 Network Simplex Method 62

Conclusion 63

References 64

Chapter-6

Integer Programming 65

6.1 Introduction to Integer Programming 65

6.2 Formulating Integer Programming

Problems 66

6.3 Cutting Plane Methods 67

6.4 Branch-and-Bound Method 71

6.5 Heuristic Methods for Integer

Programming 72

6.6 Applications of Integer Programming 77

Conclusion 80

References 81

Chapter-7

Nonlinear Programming: Fundamentals 82

7.1 Introduction to Nonlinear Programming 82

7.2 Unconstrained Optimization 83

7.3 Constrained Optimization 84

7.4 Convex and Non-Convex Functions 86

7.5 Optimality Conditions 88

7.6 Sensitivity Analysis in Nonlinear Programming 90

Conclusion 96

References 97

Chapter-8

Unconstrained Optimization Techniques 98

8.1 Gradient Descent Methods 98

8.2 Newton’s Method 100

8.3 Conjugate Gradient Methods 101

8.4 Quasi-Newton Methods 102

8.5 Line Search Techniques 104

8.6 Trust Region Methods 106

Conclusion 108

References 108

Chapter-9

Constrained Optimization Techniques 109

9.1 Penalty and Barrier Methods 109

9.2 Augmented Lagrangian Methods 111

9.3 Sequential Quadratic Programming 112

9.4 Interior Point Methods 117

9.5 Active Set Methods 120

9.6 Successive Linear Programming 124

Conclusion 127

References 127

Chapter-10

Convex Optimization 128

10.1 Convex Sets and Functions 128

10.2 Optimality Conditions for Convex

Problems 130

10.3 Duality in Convex Optimization 132

Conclusion 134

References 134

Glossary 136

Index 138

Chapter-1

Introduction to

Optimization

1.1 What is Optimization?

Optimization is the process of finding the best solution to a problem among all possible solutions, subject to certain constraints. It involves maximizing or minimizing an objective function, which represents the quantity or measure that needs to be optimized. Optimization problems arise in various fields, including engineering, economics, finance, logistics, and scientific research.

In mathematical terms, an optimization problem can be formulated as follows:

Minimize (or Maximize) f(x)

subject to g(x) ≤ 0

h(x) = 0

where:

-f(x) is the objective function to be minimized or maximized

-x = (x1, x2, ..., xn) is the vector of decision variables

-g(x) ≤ 0 represents the inequality constraints

-h(x) = 0 represents the equality constraints

The objective function f(x) and the constraint functions g(x) and h(x) can be linear or nonlinear, depending on the problem at hand.

Optimization problems can be broadly classified into two categories:

1. Constrained Optimization: In constrained optimization problems, the decision variables are subject to certain constraints, which can be equality or inequality constraints. These constraints represent the limitations or restrictions imposed on the problem by physical, economic, or other practical considerations.

2. Unconstrained Optimization: In unconstrained optimization problems, there are no explicit constraints on the decision variables. The objective function is optimized without any restrictions, except for the bounds or ranges of the variables.

The goal of optimization is to find the optimal solution that minimizes or maximizes the objective function while satisfying all the constraints, if any. Optimization techniques provide systematic methods and algorithms to solve these problems efficiently and accurately.

Example 1.1.1: Maximizing Profit

A company manufactures two products, A and B, using two raw materials, X and Y. The profit per unit of product A is $10, and the profit per unit of product B is $15. The company has a limited supply of 100 units of raw material X and 80 units of raw material Y. Each unit of product A requires 2 units of X and 1 unit of Y, while each unit of product B requires 1 unit of X and 2 units of Y. The objective is to determine the number of units of products A and B to manufacture in order to maximize the total profit.

Let x be the number of units of product A and y be the number of units of product B.

The objective function to maximize is:

f(x, y) = 10x + 15y

Subject to the constraints:

2x + y ≤ 100 (constraint on raw material X)

x + 2y ≤ 80 (constraint on raw material Y)

x ≥ 0, y ≥ 0 (non-negativity constraints)

This is a constrained optimization problem with a linear objective function and linear constraints, known as a linear programming problem.

Practice Problem 1.1.1:

A company manufactures two types of furniture, chairs and tables. The profit per chair is $20, and the profit per table is $30. The company has a budget of $5,000 for raw materials and labor. Each chair requires $10 worth of raw materials and labor, while each table requires $15 worth of raw materials and labor. Additionally, the company has a limited production capacity of 500 units per day, and each chair requires 2 hours of production time, while each table requires 3 hours of production time. Formulate the optimization problem to maximize the company’s total profit.

Solution:

Let x be the number of chairs and y be the number of tables.

The objective function to maximize is:

f(x, y) = 20x + 30y

Subject to the constraints:

10x + 15y ≤ 5000 (budget constraint)

2x + 3y ≤ 500 (production capacity constraint)

x ≥ 0, y ≥ 0 (non-negativity constraints)

1.2 Applications of Optimization

Optimization has numerous applications across various fields and industries. Some of the major applications of optimization are:

1. Manufacturing and Production Planning: Optimization techniques are used to determine the optimal production levels, resource allocation, inventory management, and scheduling to maximize profit or minimize costs.

2. Transportation and Logistics: Optimization methods are applied to solve problems related to routing, distribution, and transportation networks to minimize transportation costs, delivery times, or fuel consumption.

3. Finance and Investment: Optimization is used in portfolio optimization, risk management, asset allocation, and financial decision-making to maximize returns or minimize risk.

4. Energy Systems: Optimization techniques are employed in the design and operation of energy systems, such as power generation, distribution networks, and renewable energy systems, to minimize costs and maximize efficiency.

5. Engineering Design: Optimization is used in the design and optimization of mechanical systems, structures, and components to achieve optimal performance, weight, or cost.

6. Machine Learning and Data Analysis: Optimization algorithms are utilized in machine learning models, such as neural networks, support vector machines, and clustering algorithms, to find the best parameters or to minimize the error or loss functions.

7. Resource Allocation: Optimization methods are applied to allocate limited resources, such as materials, labor, funds, or equipment, in an optimal manner to achieve desired goals or objectives.

8. Scheduling and Timetabling: Optimization techniques are used in scheduling problems, such as employee scheduling, course timetabling, and project scheduling, to minimize conflicts or optimize resource utilization.

9. Supply Chain and Inventory Management: Optimization is used to optimize supply chain networks, inventory levels, and distribution strategies to minimize costs and improve efficiency.

10. Telecommunications: Optimization is employed in network design, bandwidth allocation, and resource allocation in telecommunication systems to optimize performance and minimize costs.

These are just a few examples of the numerous applications of optimization. The widespread use of optimization techniques is driven by the need to make efficient and effective decisions in various domains, leading to improved productivity, reduced costs, and better resource utilization.

Example 1.2.1: Portfolio Optimization

An investor wants to allocate their investment among three assets: stocks, bonds, and real estate. The expected returns and associated risks (standard deviations) for each asset are as follows:

- Stocks: Expected return = 12%, Risk = 20%

- Bonds: Expected return = 6%, Risk = 10%

- Real Estate: Expected return = 9%, Risk = 15%

The investor’s objective is to maximize the overall expected return while limiting the overall risk (standard deviation) to no more than 15%. Formulate the optimization problem to determine the optimal allocation of the investment.

Solution:

Let x, y, and z represent the fractions of the investment allocated to stocks, bonds, and real estate, respectively.

The objective function to maximize is:

f(x, y, z) = 0.12x + 0.06y + 0.09z (expected return)

Subject to the constraints:

0.2x + 0.1y + 0.15z ≤ 0.15 (risk constraint)

x + y + z = 1 (total investment constraint)

x ≥ 0, y ≥ 0, z ≥ 0 (non-negativity constraints)

Practice Problem 1.2.1:

A company needs to schedule three projects, A, B, and C, over a period of 12 weeks. The durations and profits associated with each project are as follows:

- Project A: Duration = 4 weeks, Profit = $50,000

- Project B: Duration = 6 weeks, Profit = $70,000

- Project C: Duration = 5 weeks, Profit = $60,000

Due to resource constraints, only two projects can be executed simultaneously. The objective is to schedule the projects in a way that maximizes the total profit. Formulate the optimization problem to determine the optimal scheduling.

1.3 Types of Optimization Problems

Optimization problems can be classified into various types based on the characteristics of the objective function and constraints. The main types of optimization problems are:

1. Linear Programming (LP):

-The objective function and constraints are linear functions of the decision variables.

-Example: Maximize profit or minimize cost in production planning, transportation problems, and resource allocation.

Fig. 1.1 Linear Programming (LP)

https://images.app.goo.gl/EsrRWHuZGYW9CCrp9

2. Nonlinear Programming (NLP):

-The objective function or at least one of the constraints is a nonlinear function of the decision variables.

-Examples: Maximizing revenue in pricing problems, minimizing energy consumption in engineering design, and portfolio optimization.

Fig. 1.2 Nonlinear Programming (NLP)

https://images.app.goo.gl/EEeK6AiT8jgM7JMu6

3. Integer Programming (IP):

-Some or all of the decision variables are restricted to take integer values.

-Examples: Scheduling problems, facility location problems, and network design.

4. Mixed-Integer Programming (MIP):

-The problem involves both continuous and integer decision variables.

-Examples: Production planning with setup costs, network design with capacity constraints, and supply chain optimization.

5. Quadratic Programming (QP):

-The objective function is a quadratic function, and the constraints are linear.

-Examples: Portfolio optimization, machine learning (support vector machines), and control system design.

6. Semidefinite Programming (SDP):

-The problem involves optimizing a linear function subject to matrix inequalities.

-Examples: Combinatorial optimization problems, control theory, and structural optimization.

7. Stochastic Programming:

-The problem involves uncertainty in the data or parameters, often represented by probability distributions.

-Examples: Inventory management, financial planning, and energy system optimization under uncertainty.

8. Global Optimization:

-The goal is to find the global optimum of a nonlinear, potentially non-convex objective function.

-Examples: Molecular conformation problems, engineering design optimization, and machine learning model training.

9. Multiobjective Optimization:

-The problem involves multiple conflicting objective functions to be optimized simultaneously.

-Examples: Engineering design with multiple performance criteria, resource allocation with multiple objectives, and portfolio optimization with risk and return objectives.

Each type of optimization problem requires specific solution techniques and algorithms tailored to its characteristics. The choice of the appropriate optimization method depends on the problem formulation, the nature of the objective function and constraints, and the desired solution quality and computational efficiency.

Example 1.3.1: Facility Location Problem

A company needs to establish three warehouses to serve a group of customers. The fixed cost of opening each warehouse is $50,000, $60,000, and $70,000, respectively. The company also incurs a variable cost proportional to the distance between the warehouse and the customer locations. The objective is to determine the locations of the three warehouses and the allocation of customers to these warehouses in order to minimize the total cost. This problem can be formulated as a mixed-integer programming problem, where the decision variables include the binary variables representing the selection of warehouse locations and the continuous variables representing the allocation of customers to warehouses.

Practice Problem 1.3.1:

A manufacturing company produces two types of products, A and B, using three machines. Each unit of product A requires 2 hours on Machine 1, 1 hour on Machine 2, and 1 hour on Machine 3. Each unit of product B requires 1 hour on Machine 1, 2 hours on Machine 2, and 1 hour on Machine 3. The available time on Machine 1 is 20 hours, on Machine 2 is 16 hours, and on Machine 3 is 18 hours. The profit per unit of product A is $10, and the profit per unit of product B is $12. Formulate the optimization problem to maximize the total profit.

Here are the solutions to the examples and practice problems provided in Chapter 1: Introduction to Optimization.

Example 1.1.1: Maximizing Profit

Solution:

To solve this linear programming problem, we can use the simplex method or other linear programming techniques. The optimal solution is:

x = 30 (units of product A)

y = 20 (units of product B)

The maximum profit is $700.

Practice Problem 1.1.1:

Solution:

The optimal solution obtained using a linear programming solver is:

x = 300 (chairs)

y = 200 (tables)

The maximum profit is $12,000.

Example 1.2.1: Portfolio Optimization

Solution:

This is a quadratic programming problem, which can be solved using specialized algorithms or solvers. The optimal solution is:

x = 0.4 (fraction invested in stocks)

y = 0.3 (fraction invested in bonds)

z = 0.3 (fraction invested in real estate)

The maximum expected return is 9.6%, and the overall risk (standard deviation) is 15%.

Practice Problem 1.2.1:

Solution:

This problem can be formulated as a job scheduling problem with resource constraints. One possible optimal solution is:

- Schedule Project A from week 1 to week 4

- Schedule Project B from week 5 to week 10

- Schedule Project C from week 7 to week 11

The maximum total profit is $180,000.

Example 1.3.1: Facility Location Problem

Solution:

This problem can be solved using mixed-integer programming techniques, such as branch-and-bound or cutting plane methods. The optimal solution will determine the locations of the three warehouses and the allocation of customers to these warehouses, minimizing the total cost.

Practice Problem 1.3.1:

Solution:

This problem can be formulated as a linear programming problem. The optimal solution obtained using a linear programming solver is:

x = 6 (units of product A)

y = 4 (units of product B)

The maximum profit is $136.

1.4 Linear vs. Nonlinear Programming

Linear programming and nonlinear programming are two fundamental categories of