Numerical solution to a simple maximization problem disagrees with analytic solution

[Cuicui Chen]

Hi!

I'm solving a very simple maximization problem in AMPL using SNOPT (as a building block for a dynamic programming problem I'm interested in), and am confused why the numerical solution is very different from the analytic solution. The .mod and .dat files are attached (the run commands are inside the .mod file). 

For example, the optimal choice of target_W[1,1] in the analytic solution is 1414 (with the objective function value, static_payoff[1,1], being 0.2499), but the numerical solution is 0 (with the objective function value being 0.2286). 

Incidentally, I also found that the difference between static_payoff[:,:] and v[:,:], under the numerical solution, is not a zero matrix. However, the difference should only be beta*v_plus[:,:], and v_plus[:,:] is zero because coefs[:,:] is zero.

Maybe I am just missing a silly bug in the code, but could anyone help point it out? I haven't been able to figure it out. Much appreciated!

Best,

Cuicui

[Robert Fourer]

The result that I see is copied below. It has target_W[1,1] = 1464 and static_payoff[1,1] = 0.25, with static_payoff[i,j] - v[i,j] = 0 for all i and j. Do your runs show the latest version "SNOPT 7.5-1.2"? If so then please give the AMPL command

shell "snopt -v";

and report the message that appears; that will give details of the build that you are running.

Bob Fourer
am...@googlegroups.com


SNOPT 7.5-1.2 : Optimal solution found.
86 iterations, objective 58.84635069

static_payoff[i,j] - v[i,j] [*,*]
: 1 2 3 4 5 6 7 8 9 10 :=
1 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0
;

target_W[1,1] = 1464
static_payoff[1,1] = 0.25

=======

[Cuicui Chen]

Perplexed why I did not get that answer. Below is what I have. Any clue? Thank you for your time and support!

Ruizes-MacBook-Air-4:structural_script Cuicui$ ampl

ampl: shell "snopt -v";

SNOPT 7.5-1.2 (Jun 2015) (Darwin 10.8.0 x86_64), driver(20151025), ASL(20160325)

Licensed to Harvard University, Cuicui Chen <cuicu...@fas.harvard.edu> (Ruizes-MacBook-Air-4.local).

Maintenance expires with version 20180531.

Using license file "/Users/Cuicui/Tools/Ziena/ampl-z-10/ampl.lic".

ampl: include test.mod;

SNOPT 7.5-1.2 : outlev=2

 

 SNMEMB EXIT 100 -- finished successfully

 SNMEMB INFO 104 -- memory requirements estimated

 

 Nonlinear constraints       0     Linear constraints       1

 Nonlinear variables       100     Linear variables         0

 Jacobian  variables         0     Objective variables    100

 Total constraints           1     Total variables        100

 

 Itn      0: Feasible linear constraints

 

 SQOPT  EXIT   0 -- finished successfully

 SQOPT  INFO   1 -- optimality conditions satisfied

 Problem name                 at4917

 No. of iterations                  25   Objective           -6.4707677452E+01

 No. of Hessian products            51   Linear    objective -5.4057777357E+01

                                         Quadratic objective -1.0649900095E+01

 No. of superbasics                 25   No. of basic nonlinears             0

 No. of degenerate steps             0   Percentage                        .00

 Max x       (scaled)       91 1.1E+04   Max pi      (scaled)        1 4.7E-04

 Max x                      91 1.1E+04   Max pi                      1 1.0E+00

 Max Prim inf(scaled)        0 0.0E+00   Max Dual inf(scaled)        0 0.0E+00

 Max Primal infeas           0 0.0E+00   Max Dual infeas             0 0.0E+00

 Solution not printed

 

 Time for MPS input                              .00 seconds

 Time for solving problem                        .00 seconds

 Time for solution output                        .00 seconds

 Time for constraint functions                   .00 seconds

 Time for objective function                     .00 seconds

SNOPT 7.5-1.2 : Optimal solution found.

25 iterations, objective -64.70767745

static_payoff[i,j] - v[i,j] [*,*]

:       1          2          3          4          5          6        :=

1    0          0          0          0          0          0

2    0          0          0          0          0          0

3    0          0          0          0          0          0

4    0          0          0          0          0          0

5    0          0          0          0          0          0

6    0.304784   0.242693   0.104754   0          0          0

7    0.60605    0.558703   0.44881    0.255034   0          0

8    0.862321   0.827518   0.741482   0.580544   0.328362   0

9    1.04851    1.02282    0.954121   0.81704    0.592905   0.28382

10   1.1464     1.1255     1.06591    0.941374   0.731984   0.438402

:        7       8   9  10    :=

1    0           0   0   0

2    0           0   0   0

3    0           0   0   0

4    0           0   0   0

5    0           0   0   0

6    0           0   0   0

7    0           0   0   0

8    0           0   0   0

9    0           0   0   0

10   0.0893677   0   0   0

;

[Cuicui Chen]

I just tried it out with knitroampl instead of SNOPT, and the problem is the same. So I guess this is a problem with the AMPL on my computer, not with the solvers? My AMPL version is AMPL Version 20170616 (Darwin 10.8.0 x86_64).

ampl: include test.mod;

Knitro 10.0.1: Knitro: Number of threads = 1

=======================================

           Academic License

       (NOT FOR COMMERCIAL USE)

         Artelys Knitro 10.0.1

=======================================

No start point provided -- Knitro computing one.

Knitro presolve eliminated 0 variables and 0 constraints.

datacheck:            0

hessian_no_f:         1

par_concurrent_evals: 0

The problem is identified as bound constrained only.

Knitro changing algorithm from AUTO to 1.

Knitro changing bar_initpt from AUTO to 3.

Knitro changing bar_murule from AUTO to 4.

Knitro changing bar_penaltycons from AUTO to 1.

Knitro changing bar_penaltyrule from AUTO to 2.

Knitro changing bar_switchrule from AUTO to 1.

Knitro changing linsolver from AUTO to 2.

Problem Characteristics                    ( Presolved)

-----------------------

Objective goal:  Maximize

Number of variables:                   100 (       100)

    bounded below:                       0 (         0)

    bounded above:                       0 (         0)

    bounded below and above:           100 (       100)

    fixed:                               0 (         0)

    free:                                0 (         0)

Number of constraints:                   0 (         0)

    linear equalities:                   0 (         0)

    nonlinear equalities:                0 (         0)

    linear inequalities:                 0 (         0)

    nonlinear inequalities:              0 (         0)

    range:                               0 (         0)

Number of nonzeros in Jacobian:          0 (         0)

Number of nonzeros in Hessian:         100 (       100)

  Iter      Objective      FeasError   OptError    ||Step||    CGits 

--------  --------------  ----------  ----------  ----------  -------

       0   -7.537625e+01   0.000e+00

      10   -6.470772e+01   0.000e+00   2.517e-06   8.408e+01        0

      12   -6.470768e+01   0.000e+00   2.816e-10   7.822e-01        0

EXIT: Locally optimal solution found.

Final Statistics

----------------

Final objective value               =  -6.47076774520038e+01

Final feasibility error (abs / rel) =   0.00e+00 / 0.00e+00

Final optimality error  (abs / rel) =   2.82e-10 / 2.82e-10

# of iterations                     =         12 

# of CG iterations                  =          0 

# of function evaluations           =         16

# of gradient evaluations           =         14

# of Hessian evaluations            =         12

Total program time (secs)           =       0.01871 (     0.005 CPU time)

Time spent in evaluations (secs)    =       0.00060

===============================================================================

Locally optimal or satisfactory solution.

objective -64.70767745; feasibility error 0

12 iterations; 16 function evaluations

static_payoff[i,j] - v[i,j] [*,*]

:         1             2             3             4             5         :=

1    4.08007e-15   3.94129e-15   3.71925e-15   3.4972e-15    3.33067e-15

2    4.60743e-15   4.41314e-15   4.10783e-15   3.83027e-15   3.55271e-15

3    6.1201e-15    5.68989e-15   5.07927e-15   4.55191e-15   4.10783e-15

4    1.113e-14     9.46465e-15   7.57033e-15   6.16174e-15   5.27356e-15

5    2.53408e-12   4.28546e-14   1.76525e-14   1.06026e-14   7.70217e-15

6    0.304784      0.242693      0.104754      4.40759e-14   1.52101e-14

7    0.60605       0.558703      0.44881       0.255034      1.97176e-13

8    0.862321      0.827518      0.741482      0.580544      0.328362

9    1.04851       1.02282       0.954121      0.81704       0.592905

10   1.1464        1.1255        1.06591       0.941374      0.731984

:         6             7             8             9            10         :=

1    3.21965e-15   3.10862e-15   2.9976e-15    2.9976e-15    2.9976e-15

2    3.44169e-15   3.21965e-15   3.21965e-15   3.10862e-15   3.10862e-15

3    3.77476e-15   3.66374e-15   3.44169e-15   3.44169e-15   3.33067e-15

4    4.66294e-15   4.32987e-15   3.9968e-15    3.88578e-15   3.88578e-15

5    6.245e-15     5.44009e-15   4.996e-15     4.77396e-15   4.66294e-15

6    9.76996e-15   7.63278e-15   6.60583e-15   6.05072e-15   5.82867e-15

7    2.08722e-14   1.23235e-14   9.54792e-15   8.27116e-15   7.79932e-15

8    3.43853e-08   2.59792e-14   1.53211e-14   1.21014e-14   1.09912e-14

9    0.28382       1.30562e-13   2.70894e-14   1.79856e-14   1.55431e-14

10   0.438402      0.0893677     4.61853e-14   2.42029e-14   1.9762e-14

;

[Cuicui Chen]

HI Bob again,

I think I know where the error is coming from. I currently use the version of AMPL with the recent segfault bug fix (see my previous thread at https://groups.google.com/forum/#!starred/ampl/6w9VjpAKhyw). That is where the problem comes from; I just tried the version of the AMPL BEFORE the bug fix was incorporated, and it worked fine. Could you please look into why that bug fix has anything to do with the solver stopping prematurely? 

Best,

Cuicui 

[Robert Fourer]

Try the most current build of AMPL, dated 20170630. We're seeing this output when running that on your test model:

SNOPT 7.5-1.2 : Optimal solution found.
86 iterations, objective 58.84635069
static_payoff[i,j] - v[i,j] [*,*]
: 1 2 3 4 5 6 7 8 9 10 :=
1 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0
;

target_W[1,1] = 1464
static_payoff[1,1] = 0.25

Bob Fourer
am...@googlegroups.com