Mathematical Optimisation: Concepts and Types

Core Concepts

• Mathematical optimisation seeks the best solution from available alternatives.
• Achieved through maximising or minimising a real function by selecting input values from an allowed set.
• Applicable across engineering, economics, computer science, and operations research.

Core Components

• Objective Function: The function to maximise or minimise.
• Decision Variables: Adjustable inputs to optimise the objective function.
• Constraints: Limitations or restrictions that decision variables must satisfy.

Types of Optimisation Problems

• Linear Programming: Features linear objective functions and constraints.
• Nonlinear Programming: Involves nonlinear objective functions or constraints.
• Integer Programming: Restricts some or all decision variables to integer values.
• Dynamic Programming: Simplifies complex problems into smaller subproblems.
• Stochastic Programming: Deals with uncertainty in problem parameters.
• Convex Optimisation: Has a convex objective function and a convex feasible region, easing the search for global optima.

Linear Programming

• Optimisation problems with linear objective functions and constraints.
• Standard form: maximising a linear objective function with linear equality and non-negativity constraints.
• The feasible region is a convex polyhedron.
• If an optimal solution exists, it is found at a vertex of the feasible region.
• The Simplex method is a common algorithm for solving these problems.

Nonlinear Programming

• Optimisation problems where either the objective function or a constraint is nonlinear.
• Can be more challenging to solve than linear programs.
• May contain multiple local optima.
• Solution techniques include gradient descent, Newton's method, and heuristic algorithms.
• Convexity is important: a convex objective function with a convex feasible region guarantees that a local optimum is also a global optimum.

Integer Programming

• Mathematical optimisation where some or all variables must be integers.
• Used to model problems with discrete decision variables.
• Types include Pure Integer Programming (all variables are integers), Mixed Integer Programming (some variables are integers), and Binary Integer Programming (variables are 0 or 1).
• Solving these problems is generally NP-hard, making exact solutions computationally expensive for large-scale problems.
• Common solution techniques are branch and bound, cutting plane methods, and heuristic algorithms.

Convex Optimisation

• Minimises a convex objective function subject to convex constraints.
• Convexity ensures any local minimum is a global minimum.
• Easier to solve than general nonlinear programs.
• Applicable in machine learning, finance, and engineering.
• Common algorithms include interior-point methods and gradient-based methods.

Optimality Conditions

• Conditions satisfied at an optimal solution.
• For unconstrained optimisation, the gradient of the objective function must be zero (first-order necessary condition).
• For constrained optimisation, Karush-Kuhn-Tucker (KKT) conditions provide necessary conditions for optimality.
• KKT conditions involve the objective function's gradient, constraint functions' gradients, and Lagrange multipliers.

Duality

• Every optimisation (primal) problem has a dual problem.
• The dual problem gives a lower or upper bound on the primal problem's optimal value.
• Strong duality occurs when the optimal values of primal and dual problems are equal.
• Duality theory offers insights into optimisation problem structures and aids in developing efficient algorithms.

Algorithms

• Gradient Descent: Iteratively moves in the direction of the negative gradient.
• Newton's Method: Employs the Hessian matrix to find the optimal solution.
• Simplex Method: Solves linear programming problems by moving between vertices of the feasible region.
• Interior Point Methods: Solve linear and nonlinear programs by moving through the feasible region's interior.
• Branch and Bound: Solves integer programming problems by systematically exploring the feasible region.
• Dynamic Programming: Simplifies complex problems into recursive subproblems.

Applications

• Engineering Design: Optimises structures, circuits, and control systems.
• Finance: Used for portfolio optimisation, risk management, and algorithmic trading.
• Logistics: Applications include supply chain optimisation, routing, and scheduling.
• Machine Learning: Used for training models, feature selection, and hyperparameter tuning.
• Operations Research: Applications in resource allocation, inventory management, and queuing theory.

Explore the core concepts of mathematical optimisation, including objective functions, decision variables, and constraints. Learn about linear, nonlinear, integer, dynamic, stochastic, and convex optimisation problems. Useful across engineering, economics and computer science.