algencan going unfeasible!
73 views
Skip to first unread message
Andrea Cassioli
Jun 20, 2012, 12:41:36 PM6/20/12
to TANGO Project - ALGENCAN
Dear all,
I am struggling with this bug for days, so I decided to ask for help!
I am integrating algencan in a C++ application in which I must solve a
sequence of box-constrained problems. In an earlier version it was
working well. Now I am refactoring the code so that in the future I
will be able to include linear constraints also.
Something is going deeply wrong, but I cannot figure out what it is:
algencan backtrace forever in the very first linesearch, going
unfeasible! The setting is:
- the problem is convex;
- function evaluation correct;
- gradient coded and checked;
- no hessian;
- bound on the variables as [0,100], but the upperbound can be
removed;
- no memory leaks;
- other solvers work;
below there is the execution trace for a one-dimensional problem.
====================================================================
This is ALGENCAN 2.3.7.
ALGENCAN, an augmented Lagrangian method for nonlinear programming,
is part of
the TANGO Project: Trustable Algorithms for Nonlinear General
Optimization.
See http://www.ime.usp.br/~egbirgin/tango/ for details.
====================================================================
The optional specification file algencan.dat was not found in the
current
directory (this is not a problem nor an error). The default values
for the
ALGENCAN parameters will be used.
ALGENCAN PARAMETERS:
firstde = T
hptype = HAPPRO
innslvr = TN
sclsys = F
skipacc = T
lsssub = MA57
sclsub = MA57
rmfixv = T
slacks = F
scale = F
epsfeas = 1.0000D-10
epsopt = 1.0000D-07
iprint = 99
ncomp = 0
Number of variables : 1
Number of equality constraints : 0
Number of inequality constraints : 0
Number of bound constraints : 2
Number of removed fixed variables : 0
Entry to GENCAN.
Number of variables: 1
Required optimality tolerance: 1.0D-07
1
GENCAN ITERATION = 0 (Initial
point)
Leaving-face iterations = 0
Inner-to-the-face iterations = 0
Functional evaluations = 1
Conjugate gradient iterations = 0
Newtonian system factorizations = 0
Trust-region iterations = 0
Trust-region matrix factorizations = 0
Functional value =
4.6033865872923689D+03
Sup-norm of the continuous projected gradient = 9.9D+01 2-norm =
9.9D+01
Sup-norm of the internal projection of gp = 9.9D+01 2-norm =
9.9D+01
Sup-norm of x (attained at x_{ 1}) = 1.0D+00 2-norm =
1.0D+00
Sup-norm of x - x_{prev} = 0.0D+00 2-norm =
0.0D+00
Conjugate Gradients (maxit = 1, eps = 1.0D-01, delta = 1.0D
+02)
(Preconditioner: QNCGNA, Hessian-vector product type: HAPPRO)
CG iter = 0 rnorm = 2.9194D+02 dnorm = 0.0000D+00 q =
0.0000D+00
CG iter = 1 rnorm = 0.0000D+00 dnorm = 1.4066D+01 q =
-2.0532D+03
Flag of CG: The maximum step to remain within the box is smaller
than 0.1)
TN Line search (xsupn = 2.9D+04, amax = *******, dsupn = 1.4D+01)
100
Projected point F = 5.2383799874935467D+04 FE = 2
The first trial is at the boundary.
Discarding projected point. We will now consider x + amax d.
100
Alpha = ******* F = 5.2383799874935467D+04 FE = 3
Function value at the boundary is greater than at the current
point.
We will backtrack.
-14447.7
Alpha = ******* F = 9.7920948731507576D+08 FE = 4
-21721.5
Alpha = ******* F = 2.2100985388266091D+09 FE = 5
-25358.4
Alpha = ******* F = 3.0108668258611517D+09 FE = 6
-27176.9
Alpha = ******* F = 3.4575819096981082D+09 FE = 7
-28086.1
Alpha = ******* F = 3.6925221866965175D+09 FE = 8
-28540.7
Alpha = ******* F = 3.8128880089656944D+09 FE = 9
-28768
Alpha = ******* F = 3.8737948410427809D+09 FE = 10
-28881.7
Alpha = ******* F = 3.9044292373169456D+09 FE = 11
-28938.5
Alpha = ******* F = 3.9197916805129271D+09 FE = 12
-28966.9
Alpha = ******* F = 3.9274842133756480D+09 FE = 13
-28981.1
Alpha = ******* F = 3.9313333076232252D+09 FE = 14
-28988.2
The solution is meant to be around 1000.
Any clues??
best,
andrea
I am struggling with this bug for days, so I decided to ask for help!
I am integrating algencan in a C++ application in which I must solve a
sequence of box-constrained problems. In an earlier version it was
working well. Now I am refactoring the code so that in the future I
will be able to include linear constraints also.
Something is going deeply wrong, but I cannot figure out what it is:
algencan backtrace forever in the very first linesearch, going
unfeasible! The setting is:
- the problem is convex;
- function evaluation correct;
- gradient coded and checked;
- no hessian;
- bound on the variables as [0,100], but the upperbound can be
removed;
- no memory leaks;
- other solvers work;
below there is the execution trace for a one-dimensional problem.
====================================================================
This is ALGENCAN 2.3.7.
ALGENCAN, an augmented Lagrangian method for nonlinear programming,
is part of
the TANGO Project: Trustable Algorithms for Nonlinear General
Optimization.
See http://www.ime.usp.br/~egbirgin/tango/ for details.
====================================================================
The optional specification file algencan.dat was not found in the
current
directory (this is not a problem nor an error). The default values
for the
ALGENCAN parameters will be used.
ALGENCAN PARAMETERS:
firstde = T
hptype = HAPPRO
innslvr = TN
sclsys = F
skipacc = T
lsssub = MA57
sclsub = MA57
rmfixv = T
slacks = F
scale = F
epsfeas = 1.0000D-10
epsopt = 1.0000D-07
iprint = 99
ncomp = 0
Number of variables : 1
Number of equality constraints : 0
Number of inequality constraints : 0
Number of bound constraints : 2
Number of removed fixed variables : 0
Entry to GENCAN.
Number of variables: 1
Required optimality tolerance: 1.0D-07
1
GENCAN ITERATION = 0 (Initial
point)
Leaving-face iterations = 0
Inner-to-the-face iterations = 0
Functional evaluations = 1
Conjugate gradient iterations = 0
Newtonian system factorizations = 0
Trust-region iterations = 0
Trust-region matrix factorizations = 0
Functional value =
4.6033865872923689D+03
Sup-norm of the continuous projected gradient = 9.9D+01 2-norm =
9.9D+01
Sup-norm of the internal projection of gp = 9.9D+01 2-norm =
9.9D+01
Sup-norm of x (attained at x_{ 1}) = 1.0D+00 2-norm =
1.0D+00
Sup-norm of x - x_{prev} = 0.0D+00 2-norm =
0.0D+00
Conjugate Gradients (maxit = 1, eps = 1.0D-01, delta = 1.0D
+02)
(Preconditioner: QNCGNA, Hessian-vector product type: HAPPRO)
CG iter = 0 rnorm = 2.9194D+02 dnorm = 0.0000D+00 q =
0.0000D+00
CG iter = 1 rnorm = 0.0000D+00 dnorm = 1.4066D+01 q =
-2.0532D+03
Flag of CG: The maximum step to remain within the box is smaller
than 0.1)
TN Line search (xsupn = 2.9D+04, amax = *******, dsupn = 1.4D+01)
100
Projected point F = 5.2383799874935467D+04 FE = 2
The first trial is at the boundary.
Discarding projected point. We will now consider x + amax d.
100
Alpha = ******* F = 5.2383799874935467D+04 FE = 3
Function value at the boundary is greater than at the current
point.
We will backtrack.
-14447.7
Alpha = ******* F = 9.7920948731507576D+08 FE = 4
-21721.5
Alpha = ******* F = 2.2100985388266091D+09 FE = 5
-25358.4
Alpha = ******* F = 3.0108668258611517D+09 FE = 6
-27176.9
Alpha = ******* F = 3.4575819096981082D+09 FE = 7
-28086.1
Alpha = ******* F = 3.6925221866965175D+09 FE = 8
-28540.7
Alpha = ******* F = 3.8128880089656944D+09 FE = 9
-28768
Alpha = ******* F = 3.8737948410427809D+09 FE = 10
-28881.7
Alpha = ******* F = 3.9044292373169456D+09 FE = 11
-28938.5
Alpha = ******* F = 3.9197916805129271D+09 FE = 12
-28966.9
Alpha = ******* F = 3.9274842133756480D+09 FE = 13
-28981.1
Alpha = ******* F = 3.9313333076232252D+09 FE = 14
-28988.2
The solution is meant to be around 1000.
Any clues??
best,
andrea
Ernesto G. Birgin
Jun 20, 2012, 12:54:44 PM6/20/12
to tango-...@googlegroups.com
Hi Andrea!
As far as i can see, there is something wrong where it is written:
TN Line search (xsupn = 2.9D+04, amax = *******, dsupn = 1.4D+01)
right after computing direction d by conjugate gradients.
On one hand, the value of amax is not being shown. I am guessing this is because it is negative and the 'write' format of amax is not ready to write negative maximum steps along direction d! On the other hand, there is the problem that may be causing the first issue: in the same line it is written that the sup-norm of x is 2.9D+04. Since your problem has n=1 and x must satisfy 0 <= x <= 100, this is not possible.
All iterates generated by Gencan satisfy the box-constraints. The initial guess is projected within the box-constraints in case it is infeasible. Therefore, the reported situation should never occur.
My guess is that your code is overwriting some memory space or something like that, since a few lines before, it is written:
Sup-norm of x (attained at x_{ 1}) = 1.0D+00
and the value of x should not change from one point to the other.
I hope it helps.
Regards,
Ernesto.
As far as i can see, there is something wrong where it is written:
TN Line search (xsupn = 2.9D+04, amax = *******, dsupn = 1.4D+01)
On one hand, the value of amax is not being shown. I am guessing this is because it is negative and the 'write' format of amax is not ready to write negative maximum steps along direction d! On the other hand, there is the problem that may be causing the first issue: in the same line it is written that the sup-norm of x is 2.9D+04. Since your problem has n=1 and x must satisfy 0 <= x <= 100, this is not possible.
All iterates generated by Gencan satisfy the box-constraints. The initial guess is projected within the box-constraints in case it is infeasible. Therefore, the reported situation should never occur.
My guess is that your code is overwriting some memory space or something like that, since a few lines before, it is written:
Sup-norm of x (attained at x_{ 1}) = 1.0D+00
I hope it helps.
Regards,
Ernesto.
Andrea Cassioli
Jun 21, 2012, 11:31:18 AM6/21/12
to TANGO Project - ALGENCAN
Hi Ernesto,
thanks for the reply. Indeed it seems some memory issues....I tried to
go to the basic and remove the MA57 and running Valgrind I got only
these errors:
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x4C2CF23: bcmp (in /usr/lib/valgrind/
vgpreload_memcheck-amd64-linux.so)
==6791== by 0x228BAD56: _gfortran_compare_string (in /usr/lib/
libgfortran.so.3.0.0)
==6791== by 0x5044271: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x228BAD59: _gfortran_compare_string (in /usr/lib/
libgfortran.so.3.0.0)
==6791== by 0x5044271: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x5044274: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
The problem seems to be at line 191 in algencan.f where the code check
for MA57. No other memory issues seem to be detected. I can not
understand...
Andrea
> > Seehttp://www.ime.usp.br/~egbirgin/tango/for details.
thanks for the reply. Indeed it seems some memory issues....I tried to
go to the basic and remove the MA57 and running Valgrind I got only
these errors:
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x4C2CF23: bcmp (in /usr/lib/valgrind/
vgpreload_memcheck-amd64-linux.so)
==6791== by 0x228BAD56: _gfortran_compare_string (in /usr/lib/
libgfortran.so.3.0.0)
==6791== by 0x5044271: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x228BAD59: _gfortran_compare_string (in /usr/lib/
libgfortran.so.3.0.0)
==6791== by 0x5044271: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
==6791== Conditional jump or move depends on uninitialised value(s)
==6791== at 0x5044274: algencan_ (algencan.f:191)
==6791== by 0x505A38A: algencan(double, double, int, int, int,
double*, double*, double*, int, double*, int*, int*, int*, int,
double*, double*, double*, double*, int*) (cwrapper.cpp:163)
==6791== by 0x420512: double algencan_opt<DaoVector, Plan,
std::vector<double, std::allocator<double> > >(DaoVector&, Plan&,
std::vector<double, std::allocator<double> >&, std::vector<double,
std::allocator<double> >&, double) (algencan.hpp:40)
==6791== by 0x4191AC: main (opt4D.cpp:47)
==6791==
The problem seems to be at line 191 in algencan.f where the code check
for MA57. No other memory issues seem to be detected. I can not
understand...
Andrea
Ernesto G. Birgin
Jun 21, 2012, 1:00:32 PM6/21/12
to tango-...@googlegroups.com
As far as I can see there is nothing wrong at line 191 of Algencan. Can you post a minimal code and instructions to reproduce your error here? Ernesto.
On Wednesday, June 20, 2012 1:41:36 PM UTC-3, Andrea Cassioli wrote:
On Wednesday, June 20, 2012 1:41:36 PM UTC-3, Andrea Cassioli wrote:
Andrea Cassioli
Jun 25, 2012, 9:10:50 AM6/25/12
to tango-...@googlegroups.com
Hi Ernesto,
I agree with you. Unfortunately the overall code is far too complex to extract a minimal snippet to post here. Any memory checker I have tried so far say nothing about memory violations. My guess is that, as I have already seen in the past with other codes, it might be a linking issues when interfacing FORTRAN and C++. Somehow memory alignment is screwed up. Being a big code, different parts are linked and compiled in a slightly different way....so I guess this might be the issue.
Is there any ALGENCAN user that you are aware that use it in a big code so that similar issues might have been solved before?
Andrea
Reply all
Reply to author
Forward
0 new messages