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.

CYCLE (PROBLEM 1 + PROBLEM 2): Minimize Kantorovich-Rubinstein distancensubject 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 ——————————————————————–

Dataset	30	N/A	0.1406680967	14.3
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Matlab Subroutines	Matlab Code		Data

PROBLEM 1: Minimize Sum of Euclidean Distances Minimize Sum of Sqrt_Quadratic ——————————————————————– Sqrt_Quadratic = square root of quadratic function ——————————————————————–

Dataset	20	N/A	0.1406681	0.03
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
R	R Code		Data

CASE STUDY SUMMARYn 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].

References [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