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)