Optimisation

前置知识

37 项必需的前置知识（一直追溯到底）

你将学会

• Formulate and solve linear programs with the simplex method, and interpret the dual problem.
• Prove that local minima of convex functions are global, and apply the KKT conditions.
• Implement gradient descent and analyse its convergence for smooth convex functions.

定义

• A set C is convex if it contains the line segment between any two of its points.
• A function f is convex if f(tx + (1 − t)y) ≤ t f(x) + (1 − t) f(y) for all x, y and 0 ≤ t ≤ 1.
• A linear program optimises a linear function subject to finitely many linear inequalities.

定理

• Strong duality for linear programming: if the primal problem has an optimal solution, so does the dual, with the same optimal value.
• Every local minimum of a convex function on a convex set is a global minimum.
• For a convex function with L-Lipschitz gradient, gradient descent with step size 1/L reduces the gap to the optimal value at rate O(1/k).

常见误解

• Assuming every critical point is a minimum.
• Thinking every linear program has an optimal solution; it may be infeasible or unbounded.

可选发现

• Statistical inference Least squares and maximum likelihood estimation are optimisation problems.
• ← Numerical methods

学习路径

• Applied mathematics

延伸阅读

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization (2004)
• Jorge Nocedal and Stephen J. Wright, Numerical Optimization (1999)