Problems with a nonlinear optimization problems with inequality constraints

[Dat]

Hi,

I am currently working on my master thesis about Dutch auctions.

So far I have summarized my main paper and implemented this model for a very example.

My problem is when I want to solve the problem I get the following error message:

ampl: model test.mod;

ampl: solve;

MINOS 5.51: Error evaluating objective z: can't compute 1/0.

MINOS 5.51: solution aborted.

1 iterations

Nonlin evals: obj = 6, grad = 6.

Error executing "solve" command:

        Error differentiating z: division by 0

ampl:

Here is my model:

reset;

option randseed 3;

param M:= 20; # iterations

param n:= 1; # bidders

param X{i in 1..n}:= Uniform(700,1000); # valuation of bidder i

param Y:= max{i in 1..n} X[i]; # maximum valuations of the bidders

param a:= 800; # c_min = c_M+1

param b:= 1000; # c_0

param T:= 0; #non-negative time discounting increment

var c{k in 0..M+1} <= Y; # at least one user will make a bid and end the auction

maximize z: 1/(c[0]-c[M+1]) * sum{k in 1..M}(c[k] - k*T)*(c[k-1] - c[k]);

subject to g1{i in 1..M}: c[i] - c[i-1] <= 0;

subject to g2: c[M+1] - c[M] <= 0;

# Constraint from the Example that c_0 <= b and a <= c_min

subject to g3: c[0] - b <= 0;

subject to g4: a - c[M+1] <= 0;

# initial values

let c[0]:= 1000;

let c[21]:= 800;

If I change my objective function to: 

maximize z: 1/(b-a) * sum{k in 1..M}(c[k] - k*T)*(c[k-1] - c[k]); 

which should be equivalent to 

maximize z: 1/(c[0]-c[M+1]) * sum{k in 1..M}(c[k] - k*T)*(c[k-1] - c[k]); 

I get a result but basically both should work as c[0] is bigger than c[M+1] and they are starting points.

Enclosed is also the summary of the main paper. Maybe if someone has the time to look over it and see if I made a mistake in the implementation.

Thanks in advance.

[Michael Saunders]

Dat,

Some of the solvers satisfy linear constraints (and bounds)

before evaluating the nonlinear functions.  This means that

even if you specify certain initial values, all variables could

change arbitrarily before the first function evaluation.

The change needed does depend on the initial values.

You have initialized c[0] and c[21] to 1000 and 800.

The other c[i] may end up being 800 at the first evaluation.

Perhaps it would help to distribute them uniformly between 800 and 1000.

Michael

--
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+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Dat]

Thx Michael but what do you mean that the c[i] may end up being 800 at the first evaluation? If I don't type in solve, all the other c[i] are zero so there is no value at all.

My problem is why 1/(c[0]-c[M+1]) does not work since the divisor/denominator is clearly not zero as the error message suggested. Could it be that the objective function does not recognize the let assignment before it solves it and if yes how can I solve it? Any idea?

[Michael Saunders]

Dat, I'm trying to say that MINOS and SNOPT (and possibly other solvers)

do some simplex-type iterations to satisfy linear constraints and bounds

before they evaluate the nonlinear functions.

Even if you initialize c[0] and c[21] to 1000 and 800, they're unlikely

to have these values by the time the solver satisfies the linear constraints.

They will have changed arbitrarily (within the region defined by the

linear constraints and bounds).

Your g1 and g2 constraints say that the c[i] are monotonically decreasing.

Why are you not initializing all of them to plausible values?

These will help c[0] and c[21] stay near where you put them.

Do you need to add lower bounds to all c[i]?

I don't think the default bound is zero -- it's probably negative infinity.

I always tell people to use CONOPT3 to debug their models.

It is especially good at finding feasible points for highly nonlinear problems.

Michael

[Dat]

Hi Michael,

Thanks again for your reply. I understand your point and looking at my model again. I got what you said so somehow during the first evaluation AMPL set c[0] to be 800 which then causes the division by zero. Your question if I have to add lower bounds to all c[i] is that I don't need to just for c[0] and c[M+1] which are my starting price and reserve price. This can be different to the random variable Y which is the valuation of the bidder. My solution is to stick to the original formulation with

maximize z: 1/(b-a) * sum{k in 1..M}(c[k] - k*T)*(c[k-1] - c[k]);

I think this won't change the original problem as in the constraint g3 and g4, I ensure the boundary condition. What do you think?

[Michael Saunders]

Dat, I see that you don't truly need lower bounds on all c[i]

because they are implied by the bounds on c[0] and c[21]

and by linear constraints g1 and g2.

However, to help the solver get started near where you have in mind,

there's every reason to give *all* c[i] sensible initial values.

In AMPL you can write a loop to do that, but any method will do.

Again, why are you not initializing c[1] ... c[20]?

Please try it!

Michael

[Dat]

Hmm do you know how I can get sensible initial values? Maybe do you have an example which I can used? I went through the CONOPT description but so far I haven't found anything which I can use!

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

A perhaps naive input. Your objective 

maximize z: 1/(b-a) * sum{k in 1..M}(c[k] - k*T)*(c[k-1] - c[k]);

seems to be quadratic function in this formulation? And your constraints seems linear.

Unfortunately I do not think the objective is concave so your problem is nonconvex. If it were concave, then it could easily be solved using for instance MOSEK or similar code.