Introduction to Mathematical Optimization

Mathematical Optimization: Introduction and Foundations

Mathematical Optimization and Its Role

Mathematical optimization is a branch of applied mathematics focused on finding the best solution from a set of feasible alternatives, often subject to constraints. It is foundational in engineering, economics, data science, and operations research.

• Optimization Problem: The process of maximizing or minimizing a function by systematically choosing input values from within an allowed set and computing the value of the function.

• Applications: Includes resource allocation, scheduling, machine learning, and control systems.

• Types of Optimization:

  • Linear Optimization: Objective and constraints are linear.

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

  • Convex Optimization: The objective is convex and the feasible set is a convex set.

  • Combinatorial Optimization: The feasible set is discrete (e.g., integer programming).

Focus and Objectives of the Course

This course introduces the main concepts and methods in mathematical optimization, with a focus on both theory and practical algorithms. The main objectives are:

• Understanding the structure of optimization problems.

• Learning about existence and uniqueness of solutions.

• Studying computational complexity and algorithmic approaches.

Prerequisites

• Basic knowledge of calculus (differentiation, integration).

• Familiarity with linear algebra (vectors, matrices, eigenvalues).

• Some exposure to mathematical proofs and logic.

Optimization Problems: Preliminary Considerations

An optimization problem can be generally formulated as:

$\min_{x \in X} f(x)$

where $X$ is the feasible set and $f(x)$ is the objective function to be minimized (or maximized).

• Feasible Set: The set of all points $x$ that satisfy the problem's constraints.

• Objective Function: The function $f(x)$ whose minimum (or maximum) is sought.

Existence of Solutions: Weierstrass Theorem

The Weierstrass theorem provides conditions under which an optimization problem has a solution:

Theorem (Weierstrass): If $X$ is a non-empty, compact subset of $\mathbb{R}^n$ and $f: X \to \mathbb{R}$ is continuous, then $f$ attains its minimum and maximum on $X$.

$\exists x^* \in X : f(x^*) \leq f(x), \forall x \in X$

• Compactness: A set is compact if it is closed and bounded.

• Continuity: The function $f$ must be continuous on $X$.

Example: Existence of Minima

Consider $f(x) = x^2$ on $X = [-1, 1]$. The minimum is at $x^* = 0$, $f(0) = 0$.

A Note on Boundedness

• If $X$ is not bounded, $f$ may not attain a minimum (e.g., $f(x) = x$ on $X = (0, \infty)$).

• If $X$ is not closed, the minimum may not be attained within $X$ (e.g., $f(x) = x$ on $X = (0, 1)$).

Example: Probability Distributions

Let $X$ be the set of probability distributions on a finite set. The minimum of a continuous function over $X$ is attained due to compactness.

Nonlinear Optimization is Computationally Hard

While linear optimization problems can often be solved efficiently, nonlinear optimization problems are generally much harder and may not have efficient (polynomial-time) algorithms.

• Combinatorial Optimization: Many problems are NP-hard, meaning no known polynomial-time algorithms exist.

• Example: Max-Cut Problem

  • Given a graph $G = (V, E)$, partition $V$ into two sets to maximize the number of edges between the sets.

  • This can be formulated as a quadratic optimization problem:

  $\max_{x \in \{-1, 1\}^n} \frac{1}{4} \sum_{i, j} w_{ij}(1 - x_i x_j)$

Summary Table: Types of Optimization Problems

Type	Objective Function	Feasible Set	Complexity
Linear	Linear	Polyhedron	Polynomial-time
Convex	Convex	Convex	Polynomial-time (for some cases)
Nonlinear	Nonlinear	General	NP-hard (in general)
Combinatorial	Discrete/Quadratic	Discrete	NP-hard

Bibliography

• Bertsekas, D. P. (2016). Nonlinear Programming.

• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization.

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization.

Additional info: These notes provide foundational concepts in optimization, which are essential for advanced calculus and applied mathematics courses, especially those focusing on optimization theory and applications.