Overview of Nonlinear Optimization: Concepts & Applications

SECTION 01

What is Optimization?

The process of finding the best solution from a set of available alternatives according to some criterion.

Everyday Examples

Finding the shortest route to work
Maximizing profit while minimizing cost
Training a neural network (minimizing loss)
Portfolio optimization in finance

Key Question

What makes a problem nonlinear?

SECTION 02

General Optimization Problem Formulation

General Optimization Problem

Standard Form

\[\begin{aligned} & \underset{x \in \mathbb{R}^n}{\text{minimize}} & & f(x) \\ & \text{subject to} & & g_i(x) \leq 0, \quad i = 1,\ldots,m \\ & & & h_j(x) = 0, \quad j = 1,\ldots,p \\ & & & x \in \mathcal{X} \end{aligned}\]

\(x = (x_1, x_2, \ldots, x_n)^T\): Decision variables
\(f(x): \mathbb{R}^n \to \mathbb{R}\): Objective function
\(g_i(x) \leq 0\): Inequality constraints
\(h_j(x) = 0\): Equality constraints
\(\mathcal{X}\): Feasible region/domain

SECTION 03

Terminology

Key Definitions

Feasible point: \(x\) satisfying all constraints
Feasible set: \(\mathcal{F} = \{x : g_i(x) \leq 0, h_j(x) = 0, x \in \mathcal{X}\}\)
Optimal solution: \(x^* \in \mathcal{F}\) such that \(f(x^*) \leq f(x)\) \(\forall x \in \mathcal{F}\)
Optimal value: \(f^* = f(x^*)\)

Simple Example

\[\begin{aligned} \min_{x \in \mathbb{R}} \quad & x^2 + 2x + 1 \\ \text{s.t.} \quad & x \geq 0 \end{aligned}\]

What is \(x^*\) and \(f^*\)?

SECTION 04

Linear vs. Nonlinear Optimization

Linear Programming (LP)

Linear Program

\[\begin{aligned} & \min_{x} & & c^T x \\ & \text{s.t.} & & Ax \leq b \\ & & & Ex = d \\ & & & x \geq 0 \end{aligned}\]

Objective function is linear
All constraints are linear
Feasible region is a polyhedron
Global optimum always exists (if bounded)
Polynomial-time solvable (Simplex, Interior Point)

SECTION 05

Nonlinear Programming (NLP)

Nonlinear Program

At least one of \(f(x)\), \(g_i(x)\), or \(h_j(x)\) is nonlinear

Aspect	Linear	Nonlinear
Objective	\(c^T x\)	\(x^2 + \sin(x)\)
Constraints	\(Ax \leq b\)	\(x_1^2 + x_2^2 \leq 1\)
Feasible region	Polyhedron	Curved boundaries
Optima	Single global	Multiple local
Complexity	Polynomial	Generally NP-hard
Algorithms	Simplex, IPM	Gradient-based

SECTION 06

Why Nonlinear Optimization is Challenging

Multiple local optima
No polynomial-time guarantee
Sensitivity to starting point
Convergence issues
Constraint qualification

multiple local minima — Multiple local minima

SECTION 07

Types of Nonlinear Problems

Classification of NLP Problems

By Constraints

Unconstrained: \(\min f(x)\)
Equality constrained: \(\min f(x)\) s.t. \(h(x) = 0\)
Inequality constrained: \(\min f(x)\) s.t. \(g(x) \leq 0\)
Mixed: Both equality and inequality constraints

By Function Properties

Smooth: \(f, g, h\) are continuously differentiable
Nonsmooth: Contains non-differentiable points
Convex: Special structure (global optimum guaranteed)
Nonconvex: General case (local optima possible)

SECTION 08

Convexity - A Crucial Concept

Convex Sets and Functions

A set \(S\) is convex if for any \(x, y \in S\) and \(\lambda \in [0,1]\):

\[\lambda x + (1-\lambda)y \in S\]

\(f\) is convex if for any \(x, y \in \text{dom}(f)\) and \(\lambda \in [0,1]\):

\[f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)\]

Golden Rule

Convex problem = Convex objective + Convex feasible set

\(\Rightarrow\) Every local minimum is a global minimum!

SECTION 09

Visual Understanding of Convexity

SECTION 10

Applications of Nonlinear Optimization

Real-World Applications

Engineering & Design

Structural optimization
Control system design
Signal processing
Robotics path planning

Machine Learning & AI

Neural network training
Support vector machines
Reinforcement learning
Computer vision

Economics & Finance

Portfolio optimization
Risk management
Option pricing
Resource allocation

Operations Research

Supply chain optimization
Facility location
Energy systems
Telecommunications

SECTION 11

Case Study: Portfolio Optimization

Markowitz Mean-Variance Model

\[\begin{aligned} & \min_{w} & & \frac{1}{2} w^T \Sigma w \\ & \text{s.t.} & & \mu^T w \geq r_{\min} \\ & & & \mathbf{1}^T w = 1 \\ & & & w \geq 0 \end{aligned}\]

\(w\): Portfolio weights
\(\Sigma\): Covariance matrix (risk)
\(\mu\): Expected returns
\(r_{\min}\): Minimum required return

Why nonlinear? Quadratic objective function!

SECTION 12

Solution Approaches - Preview

Solution Methodologies

Analytical Approaches

Optimality conditions (KKT conditions)
Lagrange multipliers
Convex analysis

Numerical Methods

Gradient-based: Steepest descent, Newton’s method
Constrained: Sequential quadratic programming
Global: Genetic algorithms, simulated annealing
Modern: Interior point methods, trust region

SECTION 13

Historical Perspective

Historical Development

1600s-1700s: Newton, Leibniz, Euler (calculus of variations)
1800s: Lagrange multipliers, method of Lagrange
1939: Karush develops optimality conditions
1947: Dantzig invents Simplex method (Linear Programming)
1951: Kuhn-Tucker extend Karush conditions (KKT)
1960s-1980s: Development of nonlinear programming algorithms
1990s-Present: Interior point methods, convex optimization
2000s-Present: Large-scale optimization, machine learning applications

SECTION 14

Practical Considerations

Key Challenges in Practice

Scaling: How to handle large-scale problems?
Initialization: Where to start the algorithm?
Convergence: When to stop?
Globalization: How to avoid local optima?
Numerical stability: Dealing with ill-conditioning

Success Factors

Understanding problem structure
Choosing appropriate algorithms
Proper implementation and tuning

SECTION 15

Summary

Nonlinear optimization is everywhere in science and engineering
Key difference from linear: local vs global optima
Convexity is a game-changer when present
Multiple solution approaches exist
Rich mathematical theory supports practical algorithms

Next: Mathematical Foundations & Convex Analysis

← Previous: Sensitivity Analysis Next: Mathematical Foundations →