Optimization Methods: Foundations and Applications (Mini-Textbook Study Notes)

Linear and Nonlinear Optimization

Introduction to Optimization

Optimization is a mathematical discipline focused on finding the best solution from a set of feasible alternatives, often subject to constraints. It is widely used in engineering, economics, and operations research.

• Optimization Problem: Involves maximizing or minimizing an objective function subject to constraints.

• Linear Optimization (LO): The objective function and constraints are linear.

• Nonlinear Optimization: At least one of the objective function or constraints is nonlinear.

General Formulation

• Linear Optimization: $\text{minimize} \quad c^T x$ $\text{subject to} \quad Ax \leq b$ $x \geq 0$

• Nonlinear Optimization: $\text{minimize} \quad f(x)$ $\text{subject to} \quad g_i(x) \leq 0, \; i = 1, \ldots, m$ $h_j(x) = 0, \; j = 1, \ldots, p$

Convex Functions

Convex functions play a central role in optimization, as they guarantee that any local minimum is a global minimum.

• Definition: A function $f(x)$ is convex if for any $x_1, x_2$ and $\lambda \in [0,1]$, $f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2)$

• Example: $f(x) = x^2$ is convex.

Linear Optimization: Applications and Formulations

Transportation Problem

The transportation problem is a classic example of linear optimization, where the goal is to minimize the cost of distributing products from several suppliers to several consumers.

• Formulation: $\text{minimize} \quad \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$ $\text{subject to} \quad \sum_{j=1}^n x_{ij} = a_i, \; i = 1, \ldots, m$ $\sum_{i=1}^m x_{ij} = b_j, \; j = 1, \ldots, n$ $x_{ij} \geq 0$

• Variables: $x_{ij}$ is the amount shipped from supplier $i$ to consumer $j$.

Manufacturing Problem

Manufacturing optimization involves determining the optimal production quantities to maximize profit or minimize cost.

• Formulation: $\text{maximize} \quad \sum_{j=1}^n p_j x_j$ $\text{subject to} \quad \sum_{j=1}^n a_{ij} x_j \leq b_i, \; i = 1, \ldots, m$ $x_j \geq 0$

• Variables: $x_j$ is the amount of product $j$ produced.

Capacity Expansion

Capacity expansion problems determine the optimal timing and amount of capacity to add in order to meet future demand.

• Formulation: $\text{minimize} \quad \sum_{t=1}^T c_t y_t$ $\text{subject to} \quad \sum_{s=1}^t y_s \geq d_t, \; t = 1, \ldots, T$ $y_t \geq 0$

• Variables: $y_t$ is the capacity added in period $t$.

Scheduling Problem

Scheduling problems involve assigning resources to tasks over time to optimize objectives such as minimizing completion time or maximizing resource utilization.

• Formulation: $\text{minimize} \quad \sum_{i=1}^n c_i x_i$ $\text{subject to} \quad \sum_{j=1}^m a_{ij} x_j \leq b_i, \; i = 1, \ldots, n$ $x_j \in \{0,1\}$

• Variables: $x_j$ indicates whether task $j$ is scheduled.

Decision Variables and Formulation

Definition of Decision Variables

Decision variables represent the choices available to the decision maker in an optimization problem.

• Example: In the transportation problem, $x_{ij}$ is the decision variable representing the quantity shipped from $i$ to $j$.

Formulation Steps

1. Define decision variables.

2. Write the objective function.

3. List all constraints.

Investment Problems

Investment under Taxation

Investment problems often involve maximizing returns while considering constraints such as taxation.

• Formulation: $\text{maximize} \quad \sum_{i=1}^n r_i x_i$ $\text{subject to} \quad \sum_{i=1}^n x_i \leq B$ $x_i \geq 0$

• Variables: $x_i$ is the amount invested in asset $i$.

Cash Flow per Dollar Invested

Year	A	B	C	D	E
1996	0.00	0.00	0.00	0.00	0.00
1997	0.00	0.00	0.00	0.00	0.00
1998	0.00	0.00	0.00	0.00	0.00
1999	0.00	0.00	0.00	0.00	0.00

Additional info: Table values are placeholders; actual cash flows would be provided in a full problem statement.

Revenue Management

Industry Applications

Revenue management uses optimization to maximize income from limited resources, such as airline seats or hotel rooms.

• Formulation: $\text{maximize} \quad \sum_{i=1}^n p_i x_i$ $\text{subject to} \quad \sum_{i=1}^n x_i \leq C$ $x_i \geq 0$

• Variables: $x_i$ is the number of units sold at price $p_i$.

Convexity and Power of Linear Optimization

Convex Functions

• Definition: Convex functions ensure tractable optimization problems.

• Example: $f(x) = x^2$ is convex; $f(x) = -x^2$ is not.

Power and Limitations of LO

• Strengths: Efficient algorithms exist for large-scale problems.

• Limitations: Not all real-world problems are linear; nonlinear and integer constraints may require advanced methods.

Summary Table: Optimization Problem Types

Type	Objective Function	Constraints	Example
Linear	Linear	Linear	Transportation, Manufacturing
Nonlinear	Nonlinear	Linear/Nonlinear	Portfolio Optimization
Integer	Linear/Nonlinear	Linear/Nonlinear	Scheduling

Conclusion

Optimization methods are essential tools in mathematics and applied sciences, providing systematic approaches to decision-making in complex environments. Mastery of linear and nonlinear optimization, formulation techniques, and understanding of convexity are foundational for advanced study and practical application. Additional info: These notes are based on lecture slides for an introductory optimization course and cover foundational concepts relevant to calculus and applied mathematics.