Optimization

In mathematics, finding the maximum and minimum values of a given function $f: X \to \mathbb{R}$ is referred to as optimization. When the objective function is directly related to real-world problems, it receives significant attention from the perspective of applied mathematics, and the importance of optimization theory in solving these problems is unquestionable.

• Optimization Techniques in Mathematics
  • Optimal Values: Maximum and Minimum $\max$, $\min$
  • Optimal Solutions: Arguments of Maxima and Minima $\text{argmax}$, $\text{argmin}$
  • First Order Necessary Conditions
  • Second Order Necessary/Sufficient Conditions
• Alternating Optimization

Linear Programming

• Linear Programming Problems

Standard Form

• Equation Form
  • Existence of Optimal Solutions
• Basic Feasible Solutions
  • Uniqueness of Basic Feasible Solutions
  • If an Optimal Solution Exists, One of Them is a Basic Feasible Solution
• Proof of the Fundamental Theorem of Linear Programming

Simplex Method

• Dictionary and Tableau
• Simplex Method
  • Initialization and Auxiliary Problems
  • Unbounded Objective Function
  • Cycling in Simplex Method
• Bland’s Rule in Simplex Method

Duality

• Primal and Dual Problems
• Proof of Weak Duality Theorem
• Proof of Strong Duality Theorem

Practice

• Solving Linear Programming Problems with Excel
• Solving Linear Programming Problems with Julia JuMP.jl
• Solving Linear Programming Problems with Python scipy
• Solving Linear Programming Problems with MATLAB Optimization Toolbox
• Solving Linear Programming Problems with R lpSolve

Nonlinear Programming

• Lagrange Multipliers

Gradient Descent

• Gradient Descent
• Stochastic Gradient Descent
• Newton’s Method
• Subgradient
• Subgradient Method

Proximal Algorithms

• Proximal Operator $\operatorname{prox}_{\lambda f} (\mathbf{x})$
• Proximal Minimization Algorithm $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda f}(\mathbf{x}^{(k)})$
• Proximal Gradient Method $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)}))$
• PALM (Proximal Alternating Linearized Minimization)

Evolutionary Programming

Heuristics

Particle Swarm

References

• Luenberger. (2021). Linear and Nonlinear Programming (5th Edition)
• Matousek. (2007). Understanding and Using Linear Programming
• Vanderbei. (2020). Linear Programming(5th Edition)