Lecture

Descent Methods and Newton Method with Line Search

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the comparison between descent methods and Newton's method, including modifications for positive definite cases, line search algorithm application, and iterations analysis showing convergence towards the minimum point.

In MOOC

Optimization: principles and algorithms - Unconstrained nonlinear optimization

What you'll learn Formulation: you will learn from simple examples how to formulate, transform and characterize an optimization problem. Objective function: you will review the mathematical properties of the objective function that are important in optimization. Optimality conditions: you will learn sufficient and necessary conditions for an optimal solution. Solving equations, Newton: this is a reminder about Newton's method to solve nonlinear equations. Newton's local method: you will see how to interpret

Official source

Related concepts (13)

Newton's method

In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valued function. The most basic version starts with a single-variable function f defined for a real variable x, the function's derivative f′, and an initial guess x0 for a root of f. If the function satisfies sufficient assumptions and the initial guess is close, then is a better approximation of the root than x0.

Gradient descent

In mathematics, gradient descent (also often called steepest descent) is a iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent. Conversely, stepping in the direction of the gradient will lead to a local maximum of that function; the procedure is then known as gradient ascent.

Newton's method in optimization

In calculus, Newton's method (also called Newton–Raphson) is an iterative method for finding the roots of a differentiable function F, which are solutions to the equation F (x) = 0. As such, Newton's method can be applied to the derivative f ′ of a twice-differentiable function f to find the roots of the derivative (solutions to f ′(x) = 0), also known as the critical points of f. These solutions may be minima, maxima, or saddle points; see section "Several variables" in Critical point (mathematics) and also section "Geometric interpretation" in this article.

Stochastic gradient descent

Stochastic gradient descent (often abbreviated SGD) is an iterative method for optimizing an objective function with suitable smoothness properties (e.g. differentiable or subdifferentiable). It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient (calculated from the entire data set) by an estimate thereof (calculated from a randomly selected subset of the data).

Conjugate gradient method

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems.

Related lectures (64)

Coordinate Descent: Efficient Optimization Techniques

Covers coordinate descent, a method for optimizing functions by updating one coordinate at a time.

Gradient Descent

Covers the concept of gradient descent in scalar cases, focusing on finding the minimum of a function by iteratively moving in the direction of the negative gradient.

Newton Method: Convergence and Quadratic Care

Covers the Newton method and its convergence properties near the optimal point.

Linear Systems: Convergence and Methods

Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.

Optimality of Convergence Rates: Accelerated Gradient Descent