Claude Lemaréchal
Encyclopedia
Claude Lemaréchal is a French
applied mathematician.
In mathematical optimization, Claude Lemaréchal is known for his work in numerical methods
for nonlinear optimization, especially for problems with nondifferentiable kinks. Lemaréchal and Phil. Wolfe pioneered bundle methods of descent
for convex minimization.
Claude Lemaréchal is a senior researcher (directeur de recherche) at INRIA near Grenoble
, France
.
(SIAM) and the Mathematical Programming Society (MPS).
, a problem whose first formulation required minimizing
a non-convex function
. For this non-convex minimization problem, Lemaréchal applied the theory of Lagrangian duality that was described in Lasdon's Optimization Theory for Large Systems. Because the primal problem was non-convex, there was no guarantee that a solution to the dual problem would provide useful information about the primal. Nonetheless, the dual problem did furnish useful information. Lemaréchal's success with Lagrangian dual methods
on nonlinear programming
problems with nonconvexities
interested Ivar Ekeland and Jean–Pierre Aubin, who applied the Shapley–Folkman lemma
to explain the Lemaréchal's success. The Aubin–Ekeland analysis of duality gaps considered the convexclosure of a nonconvex minimization problem — that is, the problem defined by the closed
convex
hull
of the epigraph
of the original problem. Following Ekeland and Aubin, similar applications of the Shapley–Folkman lemma
are described in optimization monographs and textbooks. These developments were catalyzed by Lemaréchal's demonstration that Lagrangian-dual methods were useful on some optimization problem
s that lacked convexity
.
) subgradient method
s and on bundle methods of descent
for convex minimization problems.
}||unused_data=}}
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
applied mathematician.
In mathematical optimization, Claude Lemaréchal is known for his work in numerical methods
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
for nonlinear optimization, especially for problems with nondifferentiable kinks. Lemaréchal and Phil. Wolfe pioneered bundle methods of descent
Subgradient method
Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function...
for convex minimization.
Claude Lemaréchal is a senior researcher (directeur de recherche) at INRIA near Grenoble
Grenoble
Grenoble is a city in southeastern France, at the foot of the French Alps where the river Drac joins the Isère. Located in the Rhône-Alpes region, Grenoble is the capital of the department of Isère...
, France
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
.
Awards
In 1994, Claude Lemaréchal and Roger J-B Wets were each awarded the George B. Dantzig Prize. Recognizing "original research that has had a major impact on the field of mathematical programming", the Dantzig Prize is awarded by the Society for Industrial and Applied MathematicsSociety for Industrial and Applied Mathematics
The Society for Industrial and Applied Mathematics was founded by a small group of mathematicians from academia and industry who met in Philadelphia in 1951 to start an organization whose members would meet periodically to exchange ideas about the uses of mathematics in industry. This meeting led...
(SIAM) and the Mathematical Programming Society (MPS).
Lagrangian duality and nonconvex primal problems
Soon after joining INRIA (then named "IRIA"), Lemaréchal had the assignment of helping a glass-manufacturer with a problem of scheduling its productionScheduling (production processes)
Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...
, a problem whose first formulation required minimizing
Optimization
Optimization or optimality may refer to:* Mathematical optimization, the theory and computation of extrema or stationary points of functionsEconomics and business* Optimality, in economics; see utility and economic efficiency...
a non-convex function
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
. For this non-convex minimization problem, Lemaréchal applied the theory of Lagrangian duality that was described in Lasdon's Optimization Theory for Large Systems. Because the primal problem was non-convex, there was no guarantee that a solution to the dual problem would provide useful information about the primal. Nonetheless, the dual problem did furnish useful information. Lemaréchal's success with Lagrangian dual methods
Subgradient method
Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function...
on nonlinear programming
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
problems with nonconvexities
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
interested Ivar Ekeland and Jean–Pierre Aubin, who applied the Shapley–Folkman lemma
Shapley–Folkman lemma
In geometry and economics, the Shapley–Folkman lemma describes the Minkowski addition of sets in a vector space. Minkowski addition is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of...
to explain the Lemaréchal's success. The Aubin–Ekeland analysis of duality gaps considered the convexclosure of a nonconvex minimization problem — that is, the problem defined by the closed
Kuratowski closure axioms
In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms which can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition...
convex
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
hull
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
of the epigraph
Epigraph (mathematics)
In mathematics, the epigraph of a function f : Rn→R is the set of points lying on or above its graph:and the strict epigraph of the function is:The set is empty if f \equiv \infty ....
of the original problem. Following Ekeland and Aubin, similar applications of the Shapley–Folkman lemma
Shapley–Folkman lemma
In geometry and economics, the Shapley–Folkman lemma describes the Minkowski addition of sets in a vector space. Minkowski addition is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of...
are described in optimization monographs and textbooks. These developments were catalyzed by Lemaréchal's demonstration that Lagrangian-dual methods were useful on some optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s that lacked convexity
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
.
Bundle methods of descent
Lemaréchal's research also led to his work on (conjugateNonlinear conjugate gradient method
In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function \displaystyle f:The minimum of f is obtained when the gradient is 0:...
) subgradient method
Subgradient method
Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function...
s and on bundle methods of descent
Gradient descent
Gradient descent is a first-order optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient of the function at the current point...
for convex minimization problems.
Biographical
- Citation of Claude Lemaréchal for the George DantzigGeorge DantzigGeorge Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
Prize in 1994 in Optima, Issue 44 (1994) pages 4–5.
Scientific publications
}||unused_data=}}