what are feaserror and opterror?

[dominik...@googlemail.com]

Hi
how exactly are the numbers  FeasError and OptError calculated, which are reported for each iteration while knitro is running ?
FeaseError = sum of deviations for each equation? mean of deviations? mean of deviations relative to the starting point deviation?...
Furthermore,  if I use Knitro to solve a system of linear and nonlinear equations and complementaity conditions, by setting the tagretfunction to 0 - what is the optimality error?
Thanks
Dominik

[Richard Waltz]

Dominik,

Please see the section of the User's Manual entitled "Termination criteria", which can be found here:

  http://www.artelys.com/tools/knitro_doc/2_userGuide/termination.html

Richard Waltz

Ziena Optimization LLC

[dominik...@googlemail.com]

I had overlooked that. Thanks!

I was asking because i was surprised about the FeasError I got for the initalvalues, given I had supplied feasible initial values (unless i made a coding error). Now I noticed that knitro says:

KNITRO shifted start point to satisfy presolved bounds
Is there a way i can see which variables were shifted and what the presolved bounds are that are violated, so i can find what's wrong?
I found the newpoint option but i wonder whether there is a more staightforward way to do that. (im using AMPL)

Thanks!
Dominik

[dominik...@googlemail.com]

some more details:
i wanna solve an MPEC with AMPL (ampl's option presolve 0). I provide a solution as a starting guess. I check this guess by calculating all deviations before i solve, they are all below 1e-10. Then knitro shifts the starting guess and never converges. I would like to see which variables exactly knitro shifts so i can try to understand why.

[dominik...@googlemail.com]

my problem is of the following structure, just with more than 2 variables and constraints:

max 0
s.t. 
x_i>=0 complements y_i>=0   for i=1...N
f(x_i,y_i)=0      for i=1...N

where x_i, y_i are scalars.

i got the solution from solving the matrix complementarity system element by element. now i want to get the solution without iterating in one step (because finally i want to solve a collocation problem so ill have  f(x_i,y_i)=F(x_1,...x_N) for i=1...N)

if i drop the complementarity constraints the solution is immediatly accepted. as soon as I add one set of complementarity constraints them a FeasError of 1e0 is initially shown. the algorithm takes a long time to arrive to a solution. if i add all sets of complementarity constraints (3) the algorithm does not ever arrive.

[Richard Waltz]

There is no immediate way to see what variables are shifted (other than using newpoint).  You may want to set honorbnds=0 to prevent it from shifting initial points inside the bounds:

http://www.artelys.com/tools/knitro_doc/3_referenceManual/callableLibrary/userOptions.html?highlight=honorbnds#KTR_PARAM_HONORBNDS

-Richard

[Richard Waltz]

It's hard to say much without looking into it in detail.  If you want to share your AMPL model, I can take a look at it next week and see try to see what is happening.

Best,

-Richard

[dominik...@googlemail.com]

Hi Richard,

thanks for your help. attached the model file.

up to line 509 i just generate the true solution element by element, you can disregard that part.
from line 509 i declare the model i want to solve.
from line 608 i supply the initial guess (which i got from the first 500 lines) as starting point.
from line 635 i validate that it is indeed a solution.
in line 659      i set ptions that should avoid shifting of the starting value according to this forum.
in line 662      i solve. the initial iteration yields a high FeasError  despite providing the answer as starting point. the solver fails.

[dominik...@googlemail.com]

Hi Richard,
please let me know if you figured out what's going on. Many thanks,
Dominik

[Richard Waltz]

Hi Dominik,

I was looking into your problem today, but I was unable to run it.  It seems I need "probmat.dat".  If you can send me this data file, I'll try to take a look.

Thanks,

-Richard

[dominik...@googlemail.com]

Sorry, i forgot attaching that file as well..
Thanks!

[Richard Waltz]

Dominik,

A couple comments.  

1) I see throughout "Untitled.m" that you use (upper-case) "KNITRO_OPTIONS".  Perhaps this is fine on Windows, but, at least to run it on my Linux machine, I needed to change this to lower-case "knitro_options" throughout the file.  I suggest changing to lower-case for portability.

2) When I ran it on my Linux machine I got the error:

Untitled3.m, line 625 (offset 31316):

c2_noneg_con needs 3 subscripts, not 2

context:  let  {iw in NW, iE in NE, iEY in NEY}  >>> c2_noneg_con[iE,iEY] <<<  := c2_noneg_conmat[iww,iE,iEY];

This is the section where you assign starting values and perhaps, indicates, that these starting values are not being assigned correctly.  In my case, it then did not even invoke the final solve command because of this error.  

-Richard

[dominik...@googlemail.com]

Dear Richard,

im very sorry for twice sending you code that doesnt work. I had always just copy pasted the code into the comand promt and overlooked the error you report since this way ampl continues despite errors. Anyway, since the dual value whose assignment faild is always zero, this error didnt influence the results further down the code.

I corrected the problem and checked runing the model file and i hope now it should work. Also i wasnt aware of the KNITRO_OPTIONS compatability problem (i use windows). I hope I finally dot it all right and you can now reproduce what I observe.

Thanks  for your patience,
Dominik


This is what i get displayed: First the check if all equations hold (yes), then the solver run.


Nonsquare complementarity system:
        1450 complementarities including 1015 equations
        1739 variables
max{iE in NE, iEY in NEY} abs(dev1[iE,iEY]) = 1.21037e-12
max{iE in NE, iEY in NEY} abs(dev2[iE,iEY]) = 6.73062e-12
max{iE in NE, iEY in NEY} abs(dev3[iE,iEY]) = 3.34967e-10
max{iE in NE, iEY in NEY} abs(dev4[iE,iEY]) = 3.34967e-10
max{iE in NE, iEY in NEY} abs(dev5[iE,iEY]) = 3.52769e-10
max{iE in NE, iEY in NEY} abs(dev6[iE,iEY]) = 2.22182e-11

max{iE in NE, iEY in NEY}  min(exc11[iE,iEY],exc12[iE,iEY]) = 3.25706e-11
max{iE in NE, iEY in NEY}  min(exc21[iE,iEY],exc22[iE,iEY]) = 1.25842e-10
max{iE in NE, iEY in NEY}  min(exc31[iE,iEY],exc32[iE,iEY]) = 9.9504e-11

min{iE in NE, iEY in NEY} exc5[iE,iEY] = 0.168881
min{iE in NE, iEY in NEY} l1[iE,iEY] = 1.71286e-19
min{iE in NE, iEY in NEY} l2[iE,iEY] = 3.0967e-17
min{iE in NE, iEY in NEY} l5[iE,iEY] = 1.31304e-20

KNITRO 9.0.0: opttol= 1e-7
feastol=1e-6
feastol_abs=1e-6
xtol=0
outlev=4
bar_initpt=2
scale=0
honorbnds=0
alg=3
KNITRO: Number of threads = 1

======================================
       Commercial Ziena License
             KNITRO 9.0.0
          Ziena Optimization
======================================

KNITRO presolve eliminated 0 variables and 0 constraints.

algorithm:            3
bar_initpt:           2
feastol_abs:          1e-006
hessian_no_f:         1
honorbnds:            0
opttol:               1e-007
outlev:               4
par_concurrent_evals: 0
scale:                0
xtol:                 0
The problem is identified as an MPEC.
KNITRO changing linsolver from AUTO to 4.

Problem Characteristics
-----------------------
Objective goal:  Maximize
Number of variables:                  2016
    bounded below:                    1152
    bounded above:                     144
    bounded below and above:           720
    fixed:                               0
    free:                                0
Number of constraints:                2736
    linear equalities:                 576
    nonlinear equalities:             1008
    linear inequalities:                 0
    nonlinear inequalities:           1152
    range:                               0
Number of complementarities:           432
Number of nonzeros in Jacobian:      11088
Number of nonzeros in Hessian:        3600

  Iter     fCount     Objective      FeasError   OptError    ||Step||    CGits
--------  --------  --------------  ----------  ----------  ----------  -------
       0         1   0.000000e+000  1.851e+000
       1         4   0.000000e+000  1.000e+000  1.363e+001  9.805e+000        3
       2         7   0.000000e+000  1.013e+000  9.418e+001  4.600e+000        2
       3         8   0.000000e+000  3.514e+000  1.368e+002  4.667e+000        1
       4         9   0.000000e+000  1.193e+000  4.355e+002  4.304e+000        1
       5        10   0.000000e+000  9.950e-001  3.536e+003  4.208e+000        1
       6        11   0.000000e+000  6.843e-001  2.942e+004  4.787e+000        1
       7        12   0.000000e+000  3.986e-001  2.524e+005  4.378e+000        1
       8        13   0.000000e+000  3.619e-001  9.229e+005  4.526e+000        4
       9        14   0.000000e+000  3.484e-001  1.121e+006  3.158e+000        2
      10        15   0.000000e+000  1.380e+000  6.585e+005  5.925e+000        1
      11        16   0.000000e+000  6.770e-001  5.294e+006  4.898e+000        1
      12        17   0.000000e+000  3.411e-001  1.397e+005  8.891e-001        1
      13        18   0.000000e+000  2.106e-001  9.974e+005  5.607e-001        0
      14        23   0.000000e+000  2.876e-001  3.928e+005  4.141e-001        3
      15        26   0.000000e+000  2.259e-001  1.770e+005  3.102e-001        2
      16        27   0.000000e+000  1.429e-001  9.278e+005  4.949e-001        1
      17        34   0.000000e+000  1.180e-001  4.485e+005  1.237e-001        4
      18        37   0.000000e+000  1.326e-001  7.812e+005  6.186e-002        2
      19        42   0.000000e+000  1.209e-001  3.733e+005  3.093e-002        3
      20        43   0.000000e+000  1.218e-001  1.824e+004  3.093e-002        1
      21        44   0.000000e+000  1.227e-001  2.297e+005  1.620e-001        1
      22        45   0.000000e+000  1.486e-002  1.763e+005  2.402e-001        1
      23        46   0.000000e+000  4.433e-003  1.513e-009  2.886e-002        0
      24        47   0.000000e+000  4.433e-003  9.313e-010  6.163e-005        1
      25        48   0.000000e+000  4.433e-003  6.985e-010  5.099e-010        1

EXIT: Convergence to an infeasible point. Problem appears to be locally
      infeasible. If problem is believed to be feasible, try multistart
      to search for feasible points.

Final Statistics
----------------
Final objective value               =  0.00000000000000e+000
Final feasibility error (abs / rel) =   4.43e-003 / 2.40e-003
Final optimality error  (abs / rel) =   3.73e-009 / 3.73e-009
# of iterations                     =         25
# of CG iterations                  =         39
# of function evaluations           =         50
# of gradient evaluations           =         26
# of Hessian evaluations            =         37
Total program time (secs)           =       4.705 (     4.688 CPU time)
Time spent in evaluations (secs)    =       3.068

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

ampl:

[Richard Waltz]

Dominik,

I've had a chance to look at this and I think I know what is going on.

Let's say you have a complementarity constraint:

  0 <= x complements c(x) >= 0

and it's initialized to be feasible (suppose x=0 and c(x) is some positive number initially).

The AMPL modeling language will automatically introduce auxiliary variables "y" and re-write this complementarity constraint as:

   c(x) = y

  0 <= x complements y >= 0

before passing the model on to KNITRO.  It seems the auxiliary variable "y" is initialized to 0 automatically by AMPL.  Therefore, in the model that KNITRO receives from AMPL, the constraint "c(x)=y" is initially violated (y=0 and c(x) is some positive value).

I don't know of any way to prevent AMPL from reformulating these complementarity constraints and adding auxiliary variables.  I will look into this more and see if there is a way for KNITRO to detect the auxiliary variables "y" introduced by AMPL and initialize them to the initial value for c(x), which would solve the problem.  I will let you know what I discover.

Best,

-Richard

[dominik...@googlemail.com]

Hi Richard,

thanks for your effort and this explanation.

I am surprised that AMPL is not "smart" enough to initialize y at the value implied by c(x) instead of at zero. And even given that, given all other guesses are good and given that element by element AMPL delivers the results (line 350 to 500), i would have expected the algorithm should converge.

I thought maybe it would help to explicitly make that substitution in the AMPL model so ampl doesnt have to create an auxiliary variable. so i replaced c(x) by auxiliary in the constraints and defined var auxiliary = c(x). But the behavior didnt change.

Best
Dominik

[Richard Waltz]

Dominik,

Complementarities add non-convexity to a model, and non-convexity can lead to multiple local minima and locally infeasible points (which are called infeasible stationary points).  KNITRO converges to an infeasible stationary point, which is something a local NLP solver can do.  To avoid these points is, unfortunately, a global optimization problem.

Unfortunately, adding the auxiliary variable yourself will not help because then AMPL will just add another auxiliary variable for your auxiliary variable.  If you define:

   c(x) = y
  0 <= x complements y >= 0,

then AMPL will convert this to:

  c(x) = y

   y = z

  0 <= x complements z >= 0

I believe.  I have to do some more investigations about how one can initialize these auxiliary variables introduced by AMPL.

Best,

-Richard

[sebastian...@gmail.com]

Hi Dominik and Richard,

I think I am having a similar problem to Dominik's. I have a large scale problem with many complementarity constraints. When I feed what I know to be the solution to AMPL-KNITRO I get the behavior described by Dominik (lack of convergence, etc.) I was wondering if there had been any developments on how to supply initial conditions to AMPL-KNITRO when using complementarity constraints, as to avoid the auxiliary variable being set initially to 0.

Thanks for your help.

Best,

Sebastian

[Richard Waltz]

Sebastian,

Unfortunately, I have not come up with a good solution for this yet.  I will talk with the AMPL team and see if I can come up with a solution soon to this.  I will notify you when this issue gets resolved.

-Richard

[Sebastian Sotelo]

Hi Richard,

Thank you for looking into this. Please let me know what you find out

Best,

sebastian

--
You received this message because you are subscribed to "KNITRO Nonlinear Optimization Solver" google group.
To post to this group, send email to KNI...@googlegroups.com
To unsubscribe from this group, send email to KNITRO-un...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/KNITRO?hl=en
Thank You,
Ziena Optimization, Inc.
www.ZIENA.com
---
You received this message because you are subscribed to a topic in the Google Groups "KNITRO Nonlinear Optimization Solver" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/knitro/rWoxKKXuWO0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to knitro+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.