Case Study: Approximation of a Discrete Distribution by Some Other Discrete Distribution in Euclidean Space by Minimizing Kantorovich-Rubinstein Distance (linear, sqrt_quadratic)

Back to main page

Case study background and problem formulations

Instructions for optimization with PSG MATLAB Subroutines.


Minimize Kantorovich-Rubinstein distance
subject to
Linearmulti = vector_of_fixed_probabilities (constraint on linking atoms between distributions)
Box constraints (lower bounds on probabilities)
Linearmulti = set of linear functions specified by a matrix of scenarios
Box constraints = constraints on individual decision variables
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 30 N/A 0.1406680967 14.3
Matlab Subroutines Matlab Code Data

PROBLEM 1: Minimize Sum of
Euclidean Distances
Minimize Sum of Sqrt_Quadratic
Sqrt_Quadratic = square root of quadratic function
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 20 N/A 0.1406681 0.03
Run-File Problem Statement Data Solution
R R Code Data

Numerical algorithm in MATLAB environment for approximation of a discrete distribution in 2-dimensional space by some other discrete distribution with a smaller number of atoms. The approximation is done my minimizing the Kantorovich-Rubinstein distance between distributions. Positions and probabilities of atoms of the approximating distribution are variables of the optimization problem. The algorithm solves a sequence of optimization problems reducing the distance between distributions. Optimization problems are solved by calling PSG solver in MATLAB environment. One instance of Problem 1 (changing the positions of atoms) is presented in PSG Run-file environment. Problem statement and algorithm are described in Kuzmenko and Uryasev [1].


[1] V. Kuzmenko and S. Uryasev. KANTOROVICH-RUBINSTEIN DISTANCE MINIMIZATION: APPLICATION TO LOCATION PROBLEMS. In  Large Scale Optimization Applied to Supply Chain & Smart Manufacturing: Theory & Real Applications. Springer Optimization and Its Applications. 2019