version 1.0.0.0 (2.37 KB) by
Eduard Polityko

Function is intended for detecting Pareto points.

A point X* is said to be Pareto optimal one if there is no X such that Fi(X)<=Fi(X*) for all i=1...n, with at least one strict inequality.

These points are also known as non-dominated, non-inferior, or efficient points.

Eduard Polityko (2020). Calculation of Pareto points (https://www.mathworks.com/matlabcentral/fileexchange/22507-calculation-of-pareto-points), MATLAB Central File Exchange. Retrieved .

Created with
R2007b

Compatible with any release

**Inspired by:**
Spot Border Detection, Path Tracing, Measuarement, Fragmentation, Path Tracing, Measurements, Fragmentation for Doubly-Connected Spot, Calculation of distance between strings

**Inspired:**
Calculation of Pareto points 2, Spot Border Detection, Path Tracing, Measuarement, Fragmentation, Path Tracing, Measurements, Fragmentation for Doubly-Connected Spot, Calculation of distance between strings

Create scripts with code, output, and formatted text in a single executable document.

Bhargav KinnalPerfect and simple! Kudos

alli sitaEduard PolitykoHi, just change the sign of the function. For example, if you want to define a maximum of G (x), then define a minimum of -G (x). In other words, argmax (G (x)) = argmin (-G (x)), max (G (x)) = - min (-G (x)). Therefore, change the signs of the rows of the matrix corresponding to the maximum.

Regards,

Eduard

Goutam BeheraHi Eduard,

Can you comment how to proceed if we want the minimum of some functions and maximum of other?

Regards,

Goutam

Eduard PolitykoHi Reza,

Please, email how the task is set. You have a matrix of probabilities

etc? And I will try to help with the ideas.

Regards,

Eduard

Reza TeimooriHi Eduard,

Thanks for sharing the code!

Do you have any idea as to how I can develop the algorithm if data has uncertainty?

Cheers,

Reza

alwittevAliSimon EtterAnas Al RawiHi Eduard,

Both works fine for me.

Many thanks,

Anas

Eduard PolitykoHi Anas,

Thanks for your question. You are absolutely right. You should only replace inequality sign. But for my opinion, will be better to replace F (goal function) by -F (minus F). It is a common practice for changing minimization on maximization and vice versa.

Best regards,

Eduard

Anas Al RawiHi Eduard,

Thanks a lot for sharing. I tested the code accordaing to an example in a recent published book http://www.engr.colostate.edu/~echong/book3/ & the results were identical.

In the case of maximisation, would you only swap ''<'' in line 41 with ''>'' ?

Cheers,

Anas

Petr PosikHi, Eduard,

1] Regarding the "Pareto optimal" and "non-dominated" distinction... I think I understand you. But there are two situations that should be distinguished:

a] We have very large (possibly infinite) space of candidate solutions, X, and their fitness values, F. This set X cantains the set of Pareto-optimal solutions, X*, X* \in X, which may be finite, but very often is infinite. The set X* is Pareto-optimal and of course it is also a set of non-dominated solutions.

b] On the other hand, in multiobjective optimization, you usually do not get the (whole theorethically possible) Pareto-optimal solutions; what you get is a finite set Xnd of solutions which are not dominated by any of solutions you came across during the optimization. The solutions in Xs are only approximation of the whole set X* of Pareto-optimal solutions. Sets X* and Xnd might be (and often are) different and IMHO this distinction is important.

If you consider the matrix of scores that is given to your function as the whole universe of possible solution evaluations, then you are right - the Pareto-optimal and non-dominated solutions are the same.

It is also true, that for many practical applications this distinction is quite subtle and not very important. I prefer to call the output of your function the non-dominated set.

2] Regarding the fact if two solutions which have the same fitness value can be part of the non-dominated (Pareto-optimal) set: on the page you pointed to, there is the following definition:

"A point x* is said to be (glob ally) Pareto optimal or a (globally) efficient solution or a non-dominated or a non-inferior point for (MOP) if and only if there is no x such that fi(x)<=fi(x*) for all i, with at least one strict inequality."

This definition is correct, but your interpretation is wrong. You say "The definition of Pareto points demands at least one strict inequality". But I would rather say "The definition of Pareto points demands NONEXISTENCE of other points with at least one strict inequality." Example:

Let's have a set of 2 points x1 and x2, and both points have the same evaluation, i.e. fi(x1)=fi(x2). Then the points do not dominate each other, right? Since, all their fitness scores are equal, there is no score in which the inequality is strict, right?

Consider the question if x1 is Pareto-optimal: The definition says that x1 is Pareto-optimal if there is no other point that would dominate x1. SInce there is only one other point x2 and since x2 does not dominate x1, then x1 is non-dominated and Pareto-optimal.

The similar holds for x2. So that both points are Pareto-optimal.

I hope we now understand each other.

Cheers, Petr.

Eduard PolitykoHi,

see http://www-new.mcs.anl.gov/otc/Guide/OptWeb/multiobj/. They say that non-dominated and Pareto are synonyms.

It was supposed (but not emphasized because of evidence), that result is Pareto set of matrix rows. And we have no points except of matrix rows and must do our choice among them only. Thus there is no distinction between non-dominated and Pareto in any case.

The definition of Pareto points demands at least one strict inequality. Therefore the only answer is that P and R are not Pareto points.

Regards, Eduard

Petr PosikEduard,

two comments:

1] Your function does not compute pareto optimal points, but non-dominated points. These two words IMHO are not synonyms. The distinction is small, but important. Pareto front is the set of "best" points which are theoretically possible. A non-dominated front is only an approximation of Pareto front, which hopefully gets closer and closer to the Pareto front.

2] You are not right if you say that "if P=R then they are not Pareto because there are no strict inequalities". If they are equal, then none of them is dominated by the other, so that both of them can be part of the non-dominated front. Of course, if one of them is in the nondominated front, then the other is as well and if one of them is NOT it the nondom. front, then the other isn't either.

Regards,

Petr

Harry BroedersI agree. Your function correctly calculates the Pareto optimal points. Thanks for your answer.

Eduard PolitykoAccordingly to definition of Pareto points these points are unique. And if P has Pareto properties and R has Pareto properties and P = R then they are not Pareto because there are no strict inequalities.

But I think now that it is useful to get information about such points. And I try in the next future to add an option to the function to find points mentioned above.

Harry BroedersThe above mentioned problem can be fixed by replacing the line:

if i~=k

by

if any(B(i,:)~=B(k,:))

Harry BroedersThe function misses some pareto points when the input matrix has a duplicated row.

Here is a simple example demonstrating the problem when the first row is duplicated at the end.

>> B=[0 1 2; 1 2 3; 3 2 1; 4 0 2; 2 2 1; 1 1 2; 2 1 1; 0 2 2; 0 1 2];

>> [A b]=prtp(B)

A =

4 0 2

2 1 1

b =

4 7

The pareto point 0 1 2 is missing.