Leonid Kantorovich

How to use this course

Leonid Kantorovich is the only person to have received the Nobel Memorial Prize in Economic Sciences for work that began as pure mathematics. Economists know him for linear programming and for the idea that an optimal plan carries its own prices. Analysts know him for Kantorovich spaces, the Newton–Kantorovich theorem and the Kantorovich inequality. Probabilists and geometers know the Kantorovich duality and the Kantorovich–Rubinstein distance, which sit at the centre of modern optimal transport. This course presents all three, alongside a career shaped by the Soviet system: early fame, two decades of official suspicion of his economics, then late honours.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. Lessons 07 to 10 can be read independently of 04 to 06 by a reader mainly interested in optimization and transport.

Timeline

A Petrograd childhood, 1912–1926

Leonid Vitalyevich Kantorovich was born in St Petersburg on 19 January 1912 into a Jewish family. His father, Vitaly Moiseevich Kantorovich, was a doctor; his mother was Paulina Grigoryevna Zaks. He was the youngest of five children. Two of his elder brothers became physicians.

His childhood coincided with war, revolution and civil war. In his Nobel autobiography he recalled the February and October Revolutions of 1917 and a year spent in Belorussia during the Civil War. His father died in 1922, and his mother brought him up. His interest in science appeared around 1920, and it developed quickly enough that in 1926, at the age of fourteen, he entered the mathematics department of Leningrad State University.

Professor at twenty-two, 1926–1937

At the university his teachers included Vladimir Smirnov, Grigorii Fichtenholz and Boris Delaunay. Among his friends were Sergei Sobolev, Solomon Mikhlin, Isidor Natanson and the Faddeevs. He also attended the history lectures of Evgeny Tarle, which first drew him to political economy. He began research in his second year in Fichtenholz’s seminar, on the descriptive set theory then being created in Moscow by Nikolai Luzin. In 1929–30 he solved several of Luzin’s problems on analytic and projective sets and reported them at the First All-Union Mathematical Congress in Kharkov in 1930, where he met Sergei Bernstein, Pavel Alexandrov, Andrey Kolmogorov and Aleksandr Gelfond, and foreign guests including Jacques Hadamard and Paul Montel.

He graduated in 1930, aged eighteen. The Soviet Union had abolished academic degrees, so he began teaching at once: at the Naval Engineering School, at the Leningrad Institute of Industrial Construction Engineering and at the university. His applied work of these years produced new methods for conformal mapping and for variational problems, collected in Approximate Methods of Higher Analysis (1936) with Vladimir Krylov. He became a full professor in 1934. When degrees were restored in 1935 he received the doctorate of science.

From 1935 he developed a theory of partially ordered function spaces (Lesson 05). At the Moscow Topological Conference that year he met John von Neumann, Garrett Birkhoff, Albert Tucker and Maurice Fréchet. Torsten Carleman invited a memoir on functional equations for Acta Mathematica. In 1937 he won first prize in a Leningrad competition for young researchers.

The plywood trust and the war, 1938–1944

In 1938 the laboratory of the Leningrad Plywood Trust asked the young professor for help. Several machines could each process several kinds of raw material at different rates, and the trust wanted to distribute the work so as to maximize output in a fixed assortment. Mathematically this meant maximizing a linear function over a convex polytope with an enormous number of vertices. Kantorovich found a general method, which he called the method of resolving multipliers, and saw at once that the same structure appeared in many planning problems: allocating crops to fields, cutting sheets with least waste, routing freight. In July 1939 Leningrad University published his booklet Mathematical Methods of Organizing and Planning Production. It contained the essential ideas of linear programming, eight years before George Dantzig’s simplex method.

The booklet was hardly noticed outside Leningrad, and inside the Soviet Union its implications were unwelcome. The resolving multipliers behaved like prices, and the claim that an optimal plan determines prices sounded too close to marginalist economics, which Soviet ideology rejected. Official criticism followed, and his economic writing stalled for most of two decades.

The road of life

In June 1941 Germany invaded the Soviet Union, and by September Leningrad was besieged. Kantorovich, now a professor at the Higher Engineering-Technical School of the Navy, was given the rank of major. The only supply route into the city in winter ran across the ice of Lake Ladoga. He calculated the safe distance between vehicles as a function of ice thickness and air temperature, and in December 1941 and January 1942 he walked the ice between the lorries to check that the spacing held. He received the Order of the Patriotic War and the medal for the Defence of Leningrad. His school was later evacuated to Yaroslavl, where he wrote a probability textbook for military engineers.

In 1942 two of his most lasting works appeared or were written. The Academy’s Doklady published the four-page note On the translocation of masses (Lesson 08), and he completed the manuscript of The Best Use of Economic Resources, which would wait seventeen years for publication.

Approximation and variational methods

For the general reader. Many problems of engineering ask for a function that makes some energy as small as possible. Exact solutions are rare. In the early 1930s Kantorovich found ways to reduce such problems in two variables to ordinary differential equations in one, and to approximate rough functions by smooth polynomials while keeping control of averages.

Kantorovich polynomials (1930)

Sergei Bernstein’s polynomials \(B_nf(x)=\sum_{k=0}^n f(k/n)\,p_{n,k}(x)\), with \(p_{n,k}(x)=\binom nk x^k(1-x)^{n-k}\), converge uniformly to any continuous \(f\) on \([0,1]\). They use point values and so make no sense for an integrable function. Kantorovich replaced the values by local averages:

The operators are positive, preserve constants, and satisfy \(\|K_n f\|_1\le\|f\|_1\) because \(\int_0^1p_{n,k}=\frac{1}{n+1}\). Uniform convergence for continuous \(f\) follows from the Korovkin-type argument used for Bernstein polynomials. Mean convergence then follows by density of continuous functions and the uniform bound on \(\|K_n\|\).

The Kantorovich method

Consider a functional \(J[u]=\iint_\Omega F(x,y,u,u_x,u_y)\,dx\,dy\) on a region \(a\le x\le b\), \(\varphi_1(x)\le y\le\varphi_2(x)\). The Ritz method fixes all coordinate functions and varies only numerical coefficients. Kantorovich fixed functions of \(y\) only and let the coefficients be unknown functions of \(x\):

where each \(g_k\) already satisfies the boundary condition in \(y\). Integrating out \(y\) turns \(J\) into a one-dimensional functional of \(f_1,\dots,f_N\), whose Euler–Lagrange equations are ordinary differential equations. The method keeps more of the solution exact than Ritz does, since the \(x\)-dependence is found, not guessed.

Example: torsion of a rectangular bar

The Prandtl stress function solves \(\Delta u=-2\) in \(|x|\le a,\ |y|\le b\) with \(u=0\) on the boundary; equivalently it minimizes \(J[u]=\iint(u_x^2+u_y^2-4u)\). Take \(u=(b^2-y^2)f(x)\). Integrating in \(y\),

With \(f(\pm a)=0\), the solution is \(f(x)=1-\dfrac{\cosh kx}{\cosh ka}\).

Ordered vector spaces

For the general reader. Most spaces of functions have a natural order: one function is below another if it is smaller at every point. Kantorovich made this order a structural axiom and showed that much of analysis, including limits, extensions of linear maps and even parts of numerical methods, can be done using the order alone. The spaces he singled out are now called Kantorovich spaces.

A vector lattice (or Riesz space) is a real vector space \(E\) with a partial order compatible with addition and positive scaling, in which every pair \(x,y\) has a supremum \(x\vee y\). Then \(x^+=x\vee0\), \(x^-=(-x)\vee0\) and \(|x|=x^++x^-\) are defined. \(E\) is Dedekind complete, a K-space in Kantorovich’s terminology, if every non-empty subset that is bounded above has a supremum. Examples are \(\mathbb R^n\) with the coordinatewise order, \(L^p(\mu)\) for \(1\le p\le\infty\) with the almost-everywhere order, and \(\ell^\infty\). The space \(C[0,1]\) is a vector lattice but not Dedekind complete. Kantorovich introduced the notion in 1935, at the same time as related work by Garrett Birkhoff in the United States, Hans Freudenthal in the Netherlands and Hidegorô Nakano in Japan, following an earlier lecture of Frigyes Riesz (1928).

Proof sketch. As in the scalar case, extend one dimension at a time. To extend from \(X_0\) to \(X_0+\mathbb Rz\) one needs \(c\in E\) with \(T_0y-p(y-z)\le c\le p(y'+z)-T_0y'\) for all \(y,y'\in X_0\). Sublinearity shows every left-hand element is below every right-hand element, and Dedekind completeness supplies \(c=\sup_y(T_0y-p(y-z))\). Zorn’s lemma finishes the argument. Conversely, it was later shown that the extension property for all such \(X,p\) forces \(E\) to be Dedekind complete, so Kantorovich’s condition is exactly the right one.

Functional analysis and numerical mathematics

For the general reader. In 1948 Kantorovich published a long paper arguing that the abstract language of Banach spaces was the right setting for computation. An iterative method is an operator; its convergence is a statement about norms. Two results from this program are used every day in scientific computing: a guarantee that Newton’s method converges, checkable at the starting point, and a sharp bound for the speed of steepest descent.

Proof idea. Compare the iterates with Newton’s method for the scalar quadratic \(\phi(t)=\tfrac{\beta K}{2}t^2-t+\eta\), whose smaller root is \(t^*\). Starting at \(t_0=0\), its Newton iterates \(t_n\) increase to \(t^*\). Induction using the Lipschitz bound on \(F'\) and the Banach lemma on perturbed inverses gives \(\|x_{n+1}-x_n\|\le t_{n+1}-t_n\). So \((x_n)\) is Cauchy, and the quadratic \(\phi\) is a majorant. This method of majorants is Kantorovich’s main idea.

Proof. Diagonalize, so with \(w_i=x_i^2/\|x\|^2\) the left side is \(\big(\sum w_i\lambda_i\big)\big(\sum w_i\lambda_i^{-1}\big)\). On \([m,M]\) the convex function \(1/\lambda\) lies below its chord: \(\lambda^{-1}\le\frac{m+M-\lambda}{mM}\). Hence \(\sum w_i\lambda_i^{-1}\le\frac{m+M-\bar\lambda}{mM}\) with \(\bar\lambda=\sum w_i\lambda_i\), and \(\bar\lambda(m+M-\bar\lambda)\le\frac{(m+M)^2}{4}\).

Consequence. For \(f(x)=\tfrac12x^{\mathsf T}Ax-b^{\mathsf T}x\), steepest descent with exact line search satisfies

Linear programming, 1939

For the general reader. A factory has machines, materials and orders, and it wants the best plan. When every constraint and the goal are linear, the possible plans form a polyhedron, and the best one sits at a corner. Kantorovich showed in 1939 how to find it, and how to certify that a plan is optimal by attaching a number, a multiplier, to every constraint.

The basic problem of 1939

In modern notation, the central problem of the booklet reads: machines \(i=1,\dots,n\) can each produce parts \(k=1,\dots,m\); machine \(i\) working a full day on part \(k\) makes \(\alpha_{ik}\) units. Parts are needed in proportions \(p_1:\dots:p_m\) to assemble finished products. Choose fractions of time \(h_{ik}\ge0\) with \(\sum_k h_{ik}=1\) for each machine to maximize the number \(z\) of complete sets:

Kantorovich’s criterion: a plan is optimal if and only if there are multipliers \(\lambda_k\ge0\), one per part, such that each machine works only on parts where \(\lambda_k\alpha_{ik}\) is maximal over \(k\). The \(\lambda_k\) value the parts; each machine then does what is most valuable for it. This is the complementary slackness condition of linear programming duality.

Proof sketch. Weak duality is one line: \(c^{\mathsf T}x\le(A^{\mathsf T}y)^{\mathsf T}x=y^{\mathsf T}Ax\le y^{\mathsf T}b\). Equality is the hard part. It follows from Farkas’s lemma, a separating-hyperplane statement for the closed convex cone generated by the columns of \(A\). The general duality theorem was stated by John von Neumann in 1947 and proved by David Gale, Harold Kuhn and Albert Tucker in 1951. Kantorovich had the optimality criterion for his class of problems in 1939 and developed the method further in a 1940 note in the Doklady.

The translocation of masses

For the general reader. In 1781 Gaspard Monge asked how to move a pile of earth into a hole of the same volume with least total effort. His problem resisted solution for more than a century because each grain had to go to a single destination. Kantorovich, in a four-page note of 1942, let mass be split. The problem then became linear, had a dual problem, and acquired a simple optimality test. Modern optimal transport grows from this note.

Let \(\mu,\nu\) be Borel probability measures on spaces \(X,Y\) and \(c:X\times Y\to[0,\infty)\) a cost. Monge’s problem: minimize \(\int c(x,T(x))\,d\mu(x)\) over maps \(T\) with \(T_\#\mu=\nu\). Kantorovich’s problem: minimize over couplings

\(\Pi(\mu,\nu)\) is convex and never empty (it contains \(\mu\otimes\nu\)), the objective is linear, and when \(X,Y\) are compact and \(c\) continuous the set is weakly compact, so a minimizer exists. Kantorovich worked on a compact metric space in exactly this setting.

Why the criterion works. If such \(U\) exists, then for any coupling \(\pi'\), \(\int d\,d\pi'\ge\int(U(y)-U(x))\,d\pi'=\int U\,d\nu-\int U\,d\mu\), and this lower bound is achieved by \(\pi\). So \(\pi\) is optimal. The converse, building \(U\) from an optimal plan, is the substance of the 1942 note. Kantorovich read \(U\) as a price: moving a unit of mass from \(x\) to \(y\) raises its value by exactly the transport cost along used routes, and never by more.

One dimension

On \(\mathbb R\) with \(c(x,y)=h(x-y)\), \(h\) convex, the monotone rearrangement \(T=F_\nu^{-1}\circ F_\mu\) is optimal, where \(F\) are distribution functions. For \(c=|x-y|\), the optimal cost is \(\int_{\mathbb R}|F_\mu(t)-F_\nu(t)|\,dt\).

The Kantorovich–Rubinstein metric

For the general reader. How far apart are two probability distributions? Kantorovich proposed in 1942 to answer with the least work needed to move one into the other. With Gennady Rubinstein in 1958 he turned this into a norm on spaces of measures. The same distance, under the names earth mover’s distance and Wasserstein distance, now compares images, trains generative neural networks and measures curvature of metric spaces.

For a metric space \((X,d)\) and probability measures with finite first moment, define

From the general duality. When \(c=d\), any admissible pair \((\varphi,\psi)\) can be improved to one of the form \((f,-f)\) with \(f\) 1-Lipschitz. Set \(f(x)=\inf_y\big(d(x,y)-\psi(y)\big)\). Then \(f\ge\varphi\), \(f\) is 1-Lipschitz as an infimum of 1-Lipschitz functions, and taking \(x=y\) gives \(f(y)\le-\psi(y)\), so \(\psi\le-f\). Hence \(\int\varphi\,d\mu+\int\psi\,d\nu\le\int f\,d\mu-\int f\,d\nu\). The two families of constraints collapse into one Lipschitz condition. The triangle inequality for \(W_1\) follows from the dual formula at once, since a supremum of seminorms is a seminorm; or from the primal formula by gluing couplings. Rubinstein and Kantorovich used the dual to extend \(W_1\) to a norm on all signed measures of total mass zero.

Prices from optimal plans

For the general reader. Kantorovich’s most controversial idea was economic. An optimal plan for a whole economy, he argued, automatically produces a set of valuations for every resource: the extra output one more unit would allow. He called them objectively determined valuations. Economists in the West recognized them as shadow prices; Soviet critics heard an echo of market economics. The mathematics is the sensitivity theory of linear programming.

Proof sketch. By duality \(v(b)=\min\{b^{\mathsf T}y: y\in P\}\), where \(P=\{y\ge0: A^{\mathsf T}y\ge c\}\) does not depend on \(b\). A minimum of linear functions of \(b\) is concave and, with finitely many vertices of \(P\), piecewise linear. For any dual-optimal \(y^*\) at \(b\) and any \(b'\), \(v(b')\le b'^{\mathsf T}y^*=v(b)+(b'-b)^{\mathsf T}y^*\): that is the supergradient inequality.

Complementary slackness carries the economic message. A resource not fully used in the optimal plan has valuation 0. An activity that is used breaks even at these valuations, and an activity that would make a loss at them is not used. In The Best Use of Economic Resources (1959) Kantorovich applied this to rent for land and natural resources, to a normative efficiency coefficient for capital investment and to the pricing of transport, each a question on which official Soviet doctrine was sensitive.

Rational cutting

From 1948 to 1950 Kantorovich and the geometer Victor Zalgaller applied these methods at the Leningrad Carriage-Building Works to cut steel sheet with least waste. Given cutting patterns \(j\), each yielding \(a_{ij}\) pieces of type \(i\), and demands \(d_i\), one solves

The dual variables price each piece type, and a new pattern is worth adding exactly when its pieces are worth more than one sheet at those prices. This test is the idea behind column generation, rediscovered for cutting stock by Paul Gilmore and Ralph Gomory in 1961. Their 1951 book also combined linear programming with stage-by-stage optimization, independently of Richard Bellman’s dynamic programming.

Recognition, 1944–1975

Kantorovich returned to Leningrad in 1944 and combined his chair at the university with the leadership of the Department of Approximate Methods at the Academy’s Mathematical Institute in Leningrad. His 1948 paper on functional analysis and applied mathematics won him the Stalin (State) Prize in 1949. In 1948 he was assigned to computations for the Soviet atomic project. With Mark Gavurin and Vera Faddeeva he worked on computer design and programming automation. Functional Analysis in Semi-ordered Spaces (1950, with Boris Vulikh and Aron Pinsker) and Functional Analysis in Normed Spaces (1959, with Gleb Akilov) became standard texts.

His economics remained under a cloud until after Stalin’s death. In 1956, when Tjalling Koopmans asked about his work, the 1939 booklet was sent abroad; it appeared in English in Management Science in 1960, and the 1942 transport note had been reprinted there in 1958. Kantorovich learned only in the mid-1950s that Koopmans, George Dantzig and Frank Hitchcock had reached similar results independently in the West. At home, The Best Use of Economic Resources finally appeared in 1959. A national conference on mathematical methods in economics in 1960 backed the new direction, though attacks from orthodox economists continued.

He was elected a Corresponding Member of the USSR Academy of Sciences in 1958 and moved in 1960 to the new Siberian Branch at Novosibirsk, where he headed a mathematical economics group with Vasily Nemchinov and founded the Department of Computational Mathematics at Novosibirsk State University. He became a full Academician in 1964. In 1965 he shared the Lenin Prize with Nemchinov and Viktor Novozhilov for the application of mathematical methods to economics. Among his doctoral students across these decades were Gleb Akilov, Victor Havin, Mikhail Solomyak, Gennady Rubinstein, Iosif Romanovskii and Valery Makarov.

Last years and legacy, 1971–1986

In 1971 Kantorovich moved to Moscow to lead research at the Institute of National Economic Management and to advise government planning bodies. In 1975 the Royal Swedish Academy of Sciences awarded him and Tjalling Koopmans the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel, for their contributions to the theory of optimum allocation of resources. His Nobel lecture, given on 11 December 1975, was titled Mathematics in Economics: Achievements, Difficulties, Perspectives. He received honorary doctorates from Glasgow, Grenoble, Nice, Helsinki, Paris and Cambridge, among others, and was elected to the Hungarian Academy of Sciences (1967) and the American Academy of Arts and Sciences (1969).

He died of cancer in Moscow on 7 April 1986, aged 74, and is buried at Novodevichy Cemetery. His wife, the physician Natalya Ilyina, and their two children survived him; both children became mathematical economists.

Legacy

• Optimization: linear programming, duality and shadow prices, the cutting-stock problem and the method of majorants are standard in operations research.
• Optimal transport: the Kantorovich formulation and duality underlie the work of Yann Brenier, Robert McCann, Cédric Villani and Alessio Figalli. Villani (2010) and Figalli (2018) received Fields Medals for work in this area.
• Analysis: Kantorovich spaces are a branch of functional analysis, with applications to Boolean-valued analysis and to economics with infinitely many goods.
• Numerical analysis: the Newton–Kantorovich theorem and the Kantorovich inequality are textbook results in scientific computing.
• Probability and data science: the Kantorovich–Rubinstein (Wasserstein) distance is used in limit theorems, statistics, image analysis and machine learning.

Connections

People linked to Leonid Kantorovich across this collection. A name without a link has no page here yet. See Leonid Kantorovich in the network of all 337 lives →

Teachers and advisors

• Grigorii Fichtenholz
• Vladimir Smirnov

Students

• Gennady Rubinstein 1956
• Gleb Akilov 1947
• Iosif Romanovskii 1962
• Mikhail Solomyak 1959
• Svetlozar Rachev 1979
• Valery Makarov 1965
• Victor Havin 1958

Influenced by

• Gaspard Monge
• Nikolai Luzin 1929-1930

Influenced

• Cédric Villani

Colleagues and collaborators

• John von Neumann
• Aron Pinsker
• Boris Vulikh
• George Dantzig
• Mark Gavurin
• Tjalling Koopmans
• Vasily Nemchinov
• Victor Zalgaller 1948-1951
• Viktor Novozhilov
• Vladimir Krylov 1936

Friends

• Sergei Sobolev

Also mentioned in this life

• Pavel Alexandrov
• Stefan Banach
• Augustin-Louis Cauchy
• Richard Dedekind
• Leonhard Euler
• Maurice Fréchet
• Jacques Hadamard
• Andrey Kolmogorov
• Joseph-Louis Lagrange
• Henri Lebesgue
• Isaac Newton
• Ludwig Prandtl
• Frigyes Riesz

Fields

• functional analysis 11 lives
• numerical analysis 6 lives

On CoursesHub

• Functional Analysis · Mathematics for Physics
• Numerical Methods & Computational Physics

Sources and further reading

Biography

1. L. V. Kantorovich, Biographical and Curriculum vitae, NobelPrize.org.
2. J. J. O’Connor and E. F. Robertson, Leonid Vitalyevich Kantorovich, MacTutor History of Mathematics.
3. Leonid Kantorovich, Wikipedia.
4. INFORMS, Leonid V. Kantorovich: biographical profile.
5. A. M. Vershik, L. V. Kantorovich and linear programming, arXiv:0707.0491.
6. Leonid Vitalievich Kantorovich, Mathematics Genealogy Project.

Mathematics

1. L. V. Kantorovich, Mathematical methods of organizing and planning production (1939), English translation in Management Science 6 (1960), 366–422.
2. L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS 37 (1942); reprinted in Management Science 5 (1958), 1–4.
3. L. V. Kantorovich, Functional analysis and applied mathematics, Uspekhi Mat. Nauk 3 (1948).
4. L. V. Kantorovich and G. Sh. Rubinstein, On a space of completely additive functions, Vestnik Leningrad Univ. 13 (1958).
5. L. V. Kantorovich and V. I. Krylov, Approximate Methods of Higher Analysis, 1936; English translation, Interscience/Noordhoff, 1958.
6. L. V. Kantorovich and G. P. Akilov, Functional Analysis, 2nd ed., Pergamon, 1982.
7. L. V. Kantorovich, The Best Use of Economic Resources, Pergamon, 1965.
8. L. V. Kantorovich, Mathematics in economics: achievements, difficulties, perspectives, Nobel lecture, 1975.
9. C. Villani, Optimal Transport, Old and New, Springer, 2009.
10. C. D. Aliprantis and O. Burkinshaw, Positive Operators, Springer, 2006.
11. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.