Case Study: Minimization of Kantorovich-Rubinstein distance between two distributions (kantor, ksm_avg, cardn, linear)

Back to main page
Case study background and formulation of problems

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R.

PROBLEM1: problem_Kantorovich_minimize
Minimize Kantor (minimize Kantorovich-Rubinstein distance)
subject to
Linear = 1 (sum of probabilities constraint)
Box constraints (lower bounds on probabilities)
——————————————————————–——————
Kantor = Kantorovich- Rubinstein distance
Linear = linear function
Box constraints = constraints on individual decision variables
——————————————————————–——————
Problem statement without initial point.

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 80 N/A 4.706041e-03 0.02
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data

Problem statement with initial point 0.

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 80 N/A 3.342386e-03 0.29
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
PROBLEM2: problem_KSMavg_with_Cardinality
Minimize KSM_avg (minimize Average Kolmogorov-Smirnov distance)
subject to
Cardn ≤ Const (constraint on cardinality)
Linear = 1 (sum of probabilities constraint)
Box constraints (lower bounds on probabilities)
——————————————————————–——————
KSM_avg = Average Kolmogorov-Smirnov distance
Cardn = Cardinality
Linear = linear function
Box constraints = constraints on individual decision variables
——————————————————————–——————
Problem statement with LINEARIZE=1 option.

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 40 80 3.908609e-03 144.8
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data

Problem statement with MIP=1 for constraint on cardinality function.

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 40 80 3.023553e-03 3600.3
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
CASE STUDY SUMMARY
This case study demonstrates how approximate fixed distribution by variable distribution minimizing Kantorovich-Rubinstein distance or Average Kolmogorov-Smirnov distance between distributions and obtain the same rezult.
The case study provides two Problem statements for minimization Kantorovich-Rubinstein distance and two Problem statements for minimization Average Kolmogorov-Smirnov distance.
For case of Kantorovich-Rubinstein distance one Problem statement contains initial point, other does not. When initial point is present in minimization Kantorovich-Rubinstein distance then optimization begins from this point. If initial point is not present then PSG uses a heuristic to find initial point with small value of Kantorovich-Rubinstein distance.
For case of Average Kolmogorov-Smirnov distance one Problem statement contains “linearize=1” option, other one contains “mip=1” option for constraint on cardinality function. These options provide different approaches for working with cardinality function.
In any case solved problem is multi-extremal and optimization may give local minima instead of global.

References

  • Kantorovich, L.V., and Rubinstein, G.Sh., On a space of totally additive functions, Vestn. Lening. Univ., Vol. 13, No. 7, pp. 52-59, 1958.