Approximation of discrete cumulative distribution function

[cap...@hotmail.it]

Hello everyone.

I'm having many issues trying to solve an assignment I've been given. I am a programmer and trying to learn this language is getting very hard. My assignment is the following :

On a set {1,….,N} is defined a discrete cumulative distribution function :

F(i)=yi, i=1,...,N, 

With

F(i) ≥ F(i − 1) ∀i = 2,...,N.

Define an other discrete cumulative distribution function G, which approximates F.

G shall assume n<N values (distinct possibles values of G(i) r n), and shall be defined in a way in which the absolute error (the sum of the differences |F(i) - G(i)|) is as low as possible. 

 

 Formulate the AMPL model for this problem and solve it with some random data.

I tried to solve it without success, but I'll show you my code (full of mistakes).

Here is the .dat file

### SET

set N :=  1..8 ;

set n :=  1..5 ;

### PARAMETERS

param ncount := 5;

param Ncount := 16;

param val :=

1 0.2

2 0.3

3 0.5

4 0.6

5 0.7

6 0.8

7 0.8

8 1 ;

 And here is the .mod file:

### SETS

set N ;

set n ;

### PARAMS

param val{N} <= 1, >= 0;

param ncount;

param Ncount;

param mult := Ncount/ncount integer;

param k default 1;

param x2 {i in 1..ncount} = floor (i*mult);

### VARS

var x{n} <= 1, >= 0 ;

### CONSTR

subject to range1{l in N : l>1} : val[l] >= val[l-1];

subject to range2{j in n : j <= mult*k } : x[j] = x[j+1];

subject to max_val1 : x[ncount] = 1 ;

subject to max_val2 : val[Ncount] = 1 ;

### OBJ

minimize  total_cost  :  sum{i in N , j in n}

abs(val[i] - x[j]);

Could someone please give me the solution?

Thanks in advice.

[Paras Tiwari]

Declare the set N and n as follows in model file

set N :=  1..8 ;

set n :=  1..5 ;

and remove the declaration of set from data file

You have defined mult param as an integer but your division operation produces the floating point value. You need to either 

remove the integer restriction or make sure the data is always integer.

In your constraint max_val2, you are accessing val over Ncount but you have defind val over N. You can define index over N

to access val.

Finally, the absolute operation makes your objective function nonlinear. You need to either linearize the objective function 

or use the quadratic function.

You could write 

minimize  total_cost  :  sum{i in N , j in n}(val[i] - x[j])^2 instead of absolute function if you want to use quadratic formulation.

Thanks,

Paras

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--

Dr. Paras B. Tiwari

Software Engineer/Customer Support Specialist

AMPL Optimization Inc.

[cap...@hotmail.it]

Thanks. It works now, but I have another question.
You wrote me I have to use the quadratic function (sum{i in N , j in n}(val[i] - x[j])^2) instead of the absolute function because it makes the objective function nonlinear, but also the quadratic function is a nonlinear function; so why should I use the quadratic function?

Thanks in advance

[e.d.an...@mosek.com]

Well, the version using absolute value is nonsmooth. Hence, objective function is not differentiable and that might cause problems. Using the quadratic version makes the problem easier.

You could do

minimize sum_{i,j} t[i,j]

st.     val[i]-x[j] <= t[i,j]

        -(val[i]-x[j])  <= t[i,j]

.....

[cap...@hotmail.it]

Hello,

I modified to code, and got it to work but I still have one issue to solve. Here's the updated version :

    ### SETS

    param n;
    param N;
    set Nset:=1..N;
    set nset:=1..(n-1);

    ### PARAMS

    param F{Nset} <= 1, >= 0;
    param mult := (N-1)/(n-1);
    param z := N;

    ### VARS

    var G{Nset} <= 1, >= 0;
    var t{Nset} <= 1 >= 0;

    ### CONSTR

    ###subject to range{d in nset}: G[ceil(mult*d)] <= F[ceil(mult*d)];
    subject to range2{e in nset: e > 1}: G[ceil(mult*(e))] >= F[ceil(mult*(e-1))];
    subject to range3{f in nset} : G[ceil(mult*f)] - G[ceil(mult*(f-1)) + 1] = 0;
    subject to range4{g in Nset: g < z} : G[g] <= G[g+1];
    subject to max_val : G[N] = 1 ;


    subject to l1{h in Nset} : t[h] >= (F[h] - G[h]);
    subject to l2{l in Nset} : t[l] >= -(F[l] - G[l]);

    ### OBJ
    ###minimize  total_cost  :  sum{i in Nset}(F[i] - G[i])^2;                                          quadratic formula
    ###minimize  total_cost  :  sum{i in Nset}(1 + ((0.5)*(((F[i] - G[i])^2) - 1)));                taylor's serie
    minimize  total_cost  :  sum{i in Nset}t[i];

Now, given a dataset as following :

    ### PARAMETERS

    param n := 4;
    param N := 10;

    param F :=
    1 0.1
    2 0.3
    3 0.4
    4 0.45
    5 0.55
    6 0.6
    7 0.8
    8 0.85
    9 0.95
    10 1;

 
Using the quadratic function, or Taylor's expansion, the solver gives me the following output, which is also confirmed to be right from math :

    G [*] :=
     1  0.266667
     2  0.266667
     3  0.266667
     4  0.533333
     5  0.533333
     6  0.533333
     7  0.866667
     8  0.866667
     9  0.866667
    10  1
    ;

However, for my tutor, using quadratic function is not acceptable cause the solver could produce an output different from what I'm expecting, and using Taylor's serie is not good for the learning purpose.
I got asked to linearize the absolute value, and I proceeded as you can see in my ".mod" file (I added 2 constraints "l1" and "l2" and changed the objective function).
I runned the code but the result is bit different from the one obtained with the first 2 methods :

    G [*] :=
     1  0.3
     2  0.3
     3  0.3
     4  0.55
     5  0.55
     6  0.55
     7  0.85
     8  0.85
     9  0.85
    10  1
    ;

 I can't figure out the mismatching in the results since the linearization should be right.

Can you help me? what am I doing wrong?

Thanks in advice

[paras tiwari]

Your formulation looks correct. You might need to look more into how the solver is solving the optimization problem. You could print the detailed message about the each iteration of the algorithm and analyze how the solver is solving your problem. You can go to https://ampl.com/products/solvers/solvers-we-sell/ and select a solver that you are using to solve the problem and look into the different options that you could set to the solver. 

Thanks,

Paras

[Robert Fourer]

You mention "mismatching in the results". Are you concerned that the result that you get by minimizing the sum of squares is different from the result that you get by minimizing the sum of absolute values? It is possible that these results could be the same, but in general they will be different, because they are produced by minimizing two different objective functions.

If you have some other kind of mismatch in mind, then please try to give a more detailed explanation of what seems to be wrong.

Bob Fourer
mailto:am...@googlegroups.com

=======