# 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**