133 views

Skip to first unread message

Dec 22, 2011, 12:37:26 PM12/22/11

to KNITRO Nonlinear Optimization Solver

Dear All,

I have shown below a particular case where Knitro (in C++ version)

fails to find an optimal solution (even though the kinitro in GAMS

does find an optimal solution from the same starting point).

I am trying to embed Knitro in a stochastic global optimization

routine as the local solver; the lines below shows a particular case

where the C++ Knitro fails to return a solution even though other C++

local solvers do return an optimal solution for the same problem

definition.

Please what options can i change in the knitro.opt file for it to be

able to find optimal solutions at least for this particular test case

(I have tried on my own to no avail)

Many thanks

Regards,

Yemi

C++ file:

void getProblemSizes (int * const n,

int * const m,

int * const nnzJ,

int * const nnzH)

{

*n = 5;

*m = 8;

*nnzJ = 5*8;

*nnzH = 0;

return;

}

void getProblemData (int * const objType,

int * const objGoal,

double * const xLoBnds,

double * const xUpBnds,

double * const xInitial,

int * const cType,

double * const cLoBnds,

double * const cUpBnds,

int * const jacIndexVars,

int * const jacIndexCons,

int * const hessRows,

int * const hessCols,

int * const objFnType,

int * const xType,

int * const cFnType)

{

/*---- DEFINE THE OBJECTIVE FUNCTION AND VARIABLE BOUNDS. */

int iK, iJ, iI;

*objType = KTR_OBJTYPE_GENERAL;

*objGoal = KTR_OBJGOAL_MINIMIZE;

xLoBnds[0] = 0;

xLoBnds[1] = 0;

xLoBnds[2] = 0;

xLoBnds[3] = 0;

xLoBnds[4] = 0;

xUpBnds[0] = 1;

xUpBnds[1] = 1;

xUpBnds[2] = 1;

xUpBnds[3] = 10;

xUpBnds[4] = 10;

xInitial[0] = 0.75;

xInitial[1] = 0.75;

xInitial[2] = 0.55;

xInitial[3] = 8.25;

xInitial[4] = 3.00;

/*---- DEFINE THE CONSTRAINT FUNCTIONS. */

cType[0] = KTR_CONTYPE_GENERAL;

cType[1] = KTR_CONTYPE_GENERAL;

cType[2] = KTR_CONTYPE_GENERAL;

cType[3] = KTR_CONTYPE_GENERAL;

cType[4] = KTR_CONTYPE_GENERAL;

cType[5] = KTR_CONTYPE_GENERAL;

cType[6] = KTR_CONTYPE_GENERAL;

cType[7] = KTR_CONTYPE_GENERAL;

cLoBnds[0] = 1.25;

cLoBnds[1] = 3;

cLoBnds[2] = -1e10;

cLoBnds[3] = -1e10;

cLoBnds[4] = -1e10;

cLoBnds[5] = 0;

cLoBnds[6] = 0;

cLoBnds[7] = 0;

cUpBnds[0] = 1.25;

cUpBnds[1] = 3;

cUpBnds[2] = 1.6;

cUpBnds[3] = 3;

cUpBnds[4] = 0;

cUpBnds[5] = 0;

cUpBnds[6] = 0;

cUpBnds[7] = 0;

/*---- PROVIDE FIRST DERIVATIVE STRUCTURAL INFORMATION. */

iK = 0;

for (iI=0; iI<5; iI++){

for (iJ=0; iJ<8; iJ++){

jacIndexCons[iK] = iJ;

jacIndexVars[iK] = iI;

iK++;

}

}

return;

}

double computeFC (const double * const x,

double * const c)

{

double dObj;

double res;

res = -1.5*x[0];

res += -2*x[1];

res += 0.5*x[2];

res += -2*x[3];

res += -3*x[4];

res /= -1;

dObj = res;

c[0] = pow(x[3],2);

c[0] += x[0];

/* constraint e3 */

c[1] = pow(x[4],1.5);

c[1] += 1.5*x[1];

/* constraint e4 */

c[2] = x[0];

c[2] += x[3];

/* constraint e5 */

c[3] = x[1];

c[3] += 1.333*x[4];

/* constraint e6 */

c[4] = -1*x[0];

c[4] += -1*x[1];

c[4] += x[2];

/* Binary constraints */

c[5] = x[0]*(x[0] - 1);

c[6] = x[1]*(x[1] - 1);

c[7] = x[2]*(x[2] - 1);

return( dObj );

}

int main (int argc, char *argv[])

{

if (KTR_set_int_param_by_name(kc, "gradopt", KTR_GRADOPT_FORWARD) !=

0)

exit( -1 );

if (KTR_set_int_param_by_name(kc, "hessopt", KTR_HESSOPT_BFGS) != 0)

exit( -1 );

if (KTR_set_func_callback (kc, &callbackEvalFC) != 0)

exit( -1 );

}

all other options are same as in callbackExample1.c and problemHS15.c

GAMS file:

$Ontext

The GAMS knitro optimal result

LOWER LEVEL UPPER MARGINAL

---- VAR z -INF 7.667 +INF .

---- VAR y1 . . 1.000 5.8091E+5

---- VAR y2 . 1.000 1.000 -1.702

---- VAR y3 . 1.000 1.000 -0.595

---- VAR x1 . 1.118 10.000 7.8184E-9

---- VAR x2 . 1.310 10.000 6.4806E-9

$Offtext

variables z;

positive variables y1, y2, y3, x1, x2;

equations

obj

c1

c2

c3

c4

c5

c6

c7

c8;

obj.. z =e= 2*x1 + 3*x2 + 1.5*y1 + 2*y2 - 0.5*y3;

c1.. x1**2 + y1 =e= 1.25;

c2.. x2**1.5 + 1.5*y2 =e= 3;

c3.. x1 + y1 =l= 1.6;

c4.. 1.333*x2 + y2 =l= 3;

c5.. -y1 -y2 + y3 =l= 0;

c6.. y1*(y1-1) =e= 0;

c7.. y2*(y2-1) =e= 0;

c8.. y3*(y3-1) =e= 0;

x1.up = 10;

x2.up = 10;

x1.lo = 0;

x2.lo = 0;

y1.up = 1;

y1.lo = 0;

y2.up = 1;

y2.lo = 0;

y3.up = 1;

y3.lo = 0;

y1.l = 0.75;

y2.l = 0.75;

y3.l = 0.55;

x1.l = 8.25;

x2.l = 3.00;

option nlp=knitro;

model sobol /all/;

solve sobol using nlp minimizing z;

I have shown below a particular case where Knitro (in C++ version)

fails to find an optimal solution (even though the kinitro in GAMS

does find an optimal solution from the same starting point).

I am trying to embed Knitro in a stochastic global optimization

routine as the local solver; the lines below shows a particular case

where the C++ Knitro fails to return a solution even though other C++

local solvers do return an optimal solution for the same problem

definition.

Please what options can i change in the knitro.opt file for it to be

able to find optimal solutions at least for this particular test case

(I have tried on my own to no avail)

Many thanks

Regards,

Yemi

C++ file:

void getProblemSizes (int * const n,

int * const m,

int * const nnzJ,

int * const nnzH)

{

*n = 5;

*m = 8;

*nnzJ = 5*8;

*nnzH = 0;

return;

}

void getProblemData (int * const objType,

int * const objGoal,

double * const xLoBnds,

double * const xUpBnds,

double * const xInitial,

int * const cType,

double * const cLoBnds,

double * const cUpBnds,

int * const jacIndexVars,

int * const jacIndexCons,

int * const hessRows,

int * const hessCols,

int * const objFnType,

int * const xType,

int * const cFnType)

{

/*---- DEFINE THE OBJECTIVE FUNCTION AND VARIABLE BOUNDS. */

int iK, iJ, iI;

*objType = KTR_OBJTYPE_GENERAL;

*objGoal = KTR_OBJGOAL_MINIMIZE;

xLoBnds[0] = 0;

xLoBnds[1] = 0;

xLoBnds[2] = 0;

xLoBnds[3] = 0;

xLoBnds[4] = 0;

xUpBnds[0] = 1;

xUpBnds[1] = 1;

xUpBnds[2] = 1;

xUpBnds[3] = 10;

xUpBnds[4] = 10;

xInitial[0] = 0.75;

xInitial[1] = 0.75;

xInitial[2] = 0.55;

xInitial[3] = 8.25;

xInitial[4] = 3.00;

/*---- DEFINE THE CONSTRAINT FUNCTIONS. */

cType[0] = KTR_CONTYPE_GENERAL;

cType[1] = KTR_CONTYPE_GENERAL;

cType[2] = KTR_CONTYPE_GENERAL;

cType[3] = KTR_CONTYPE_GENERAL;

cType[4] = KTR_CONTYPE_GENERAL;

cType[5] = KTR_CONTYPE_GENERAL;

cType[6] = KTR_CONTYPE_GENERAL;

cType[7] = KTR_CONTYPE_GENERAL;

cLoBnds[0] = 1.25;

cLoBnds[1] = 3;

cLoBnds[2] = -1e10;

cLoBnds[3] = -1e10;

cLoBnds[4] = -1e10;

cLoBnds[5] = 0;

cLoBnds[6] = 0;

cLoBnds[7] = 0;

cUpBnds[0] = 1.25;

cUpBnds[1] = 3;

cUpBnds[2] = 1.6;

cUpBnds[3] = 3;

cUpBnds[4] = 0;

cUpBnds[5] = 0;

cUpBnds[6] = 0;

cUpBnds[7] = 0;

/*---- PROVIDE FIRST DERIVATIVE STRUCTURAL INFORMATION. */

iK = 0;

for (iI=0; iI<5; iI++){

for (iJ=0; iJ<8; iJ++){

jacIndexCons[iK] = iJ;

jacIndexVars[iK] = iI;

iK++;

}

}

return;

}

double computeFC (const double * const x,

double * const c)

{

double dObj;

double res;

res = -1.5*x[0];

res += -2*x[1];

res += 0.5*x[2];

res += -2*x[3];

res += -3*x[4];

res /= -1;

dObj = res;

c[0] = pow(x[3],2);

c[0] += x[0];

/* constraint e3 */

c[1] = pow(x[4],1.5);

c[1] += 1.5*x[1];

/* constraint e4 */

c[2] = x[0];

c[2] += x[3];

/* constraint e5 */

c[3] = x[1];

c[3] += 1.333*x[4];

/* constraint e6 */

c[4] = -1*x[0];

c[4] += -1*x[1];

c[4] += x[2];

/* Binary constraints */

c[5] = x[0]*(x[0] - 1);

c[6] = x[1]*(x[1] - 1);

c[7] = x[2]*(x[2] - 1);

return( dObj );

}

int main (int argc, char *argv[])

{

if (KTR_set_int_param_by_name(kc, "gradopt", KTR_GRADOPT_FORWARD) !=

0)

exit( -1 );

if (KTR_set_int_param_by_name(kc, "hessopt", KTR_HESSOPT_BFGS) != 0)

exit( -1 );

if (KTR_set_func_callback (kc, &callbackEvalFC) != 0)

exit( -1 );

}

all other options are same as in callbackExample1.c and problemHS15.c

GAMS file:

$Ontext

The GAMS knitro optimal result

LOWER LEVEL UPPER MARGINAL

---- VAR z -INF 7.667 +INF .

---- VAR y1 . . 1.000 5.8091E+5

---- VAR y2 . 1.000 1.000 -1.702

---- VAR y3 . 1.000 1.000 -0.595

---- VAR x1 . 1.118 10.000 7.8184E-9

---- VAR x2 . 1.310 10.000 6.4806E-9

$Offtext

variables z;

positive variables y1, y2, y3, x1, x2;

equations

obj

c1

c2

c3

c4

c5

c6

c7

c8;

obj.. z =e= 2*x1 + 3*x2 + 1.5*y1 + 2*y2 - 0.5*y3;

c1.. x1**2 + y1 =e= 1.25;

c2.. x2**1.5 + 1.5*y2 =e= 3;

c3.. x1 + y1 =l= 1.6;

c4.. 1.333*x2 + y2 =l= 3;

c5.. -y1 -y2 + y3 =l= 0;

c6.. y1*(y1-1) =e= 0;

c7.. y2*(y2-1) =e= 0;

c8.. y3*(y3-1) =e= 0;

x1.up = 10;

x2.up = 10;

x1.lo = 0;

x2.lo = 0;

y1.up = 1;

y1.lo = 0;

y2.up = 1;

y2.lo = 0;

y3.up = 1;

y3.lo = 0;

y1.l = 0.75;

y2.l = 0.75;

y3.l = 0.55;

x1.l = 8.25;

x2.l = 3.00;

option nlp=knitro;

model sobol /all/;

solve sobol using nlp minimizing z;

Dec 27, 2011, 2:19:56 PM12/27/11

to KNITRO Nonlinear Optimization Solver

Dear Yemi,

When KNITRO is used through GAMS, the GAMS system automatically

computes exact first and second derivatives (gradient/Jacobian,

Hessian) and provides these to KNITRO. In your C++ example you are

using approximations for both the first and second derivatives. This

is a very significant difference. Using exact derivatives as opposed

to approximate derivatives improves KNITRO performance tremendously.

It is not surprising that the performance between GAMS and your C++

example differs. If at all possible, we recommend trying to provide

at least exact first derivatives (gradient and Jacobian).

I will try to look at your C++ problem in more detail when I get a

chance to see why it is not finding an optimal solution with

approximate derivatives. Often, when using finite-difference first

derivatives, it just can't get the accuracy required by the optimality

conditions. You might try "KTR_GRADOPT_CENTRAL" for the first

derivatives and also experiment with other options for the Hessian

approximation.

Richard Waltz

Ziena Optimization LLC

When KNITRO is used through GAMS, the GAMS system automatically

computes exact first and second derivatives (gradient/Jacobian,

Hessian) and provides these to KNITRO. In your C++ example you are

using approximations for both the first and second derivatives. This

is a very significant difference. Using exact derivatives as opposed

to approximate derivatives improves KNITRO performance tremendously.

It is not surprising that the performance between GAMS and your C++

example differs. If at all possible, we recommend trying to provide

at least exact first derivatives (gradient and Jacobian).

I will try to look at your C++ problem in more detail when I get a

chance to see why it is not finding an optimal solution with

approximate derivatives. Often, when using finite-difference first

derivatives, it just can't get the accuracy required by the optimality

conditions. You might try "KTR_GRADOPT_CENTRAL" for the first

derivatives and also experiment with other options for the Hessian

approximation.

Richard Waltz

Ziena Optimization LLC

Dec 27, 2011, 11:57:46 PM12/27/11

to KNITRO Nonlinear Optimization Solver

Yemi,

As a follow-up, I coded your model and although the Interior-Point

algorithms in KNITRO cannot solve it, the Active-Set algorithm

(algorithm=3) solve it pretty easily (8 iterations). The output is at

the end of this message.

In general you should try all the KNITRO algorithms. KNITRO 8.0 has a

new multi-algorithm feature that will run all the KNITRO algorithms

(possibly in parallel) with the ability to terminate as soon as an

optimal solution is found. You can select this by setting

"KTR_PARAM_ALGORITHM=KTR_ALG_MULTI" (or "algorithm=5").

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

*** NO CHECK MADE FOR ZIENA LICENSE ***

KNITRO 8.0.0

Ziena Optimization

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

algorithm: 3

debug: 1

gradopt: 2

hessopt: 2

maxtime_cpu: 1e+08

maxtime_real: 1e+08

outlev: 4

outmode: 2

presolve: 0

KNITRO changing bar_switchrule from AUTO to 2.

KNITRO changing linsolver from AUTO to 4.

KNITRO performing finite-difference gradient computation with 1

thread.

Problem Characteristics

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

Objective goal: Minimize

Number of variables: 5

bounded below: 0

bounded above: 0

bounded below and above: 5

fixed: 0

free: 0

Number of constraints: 8

linear equalities: 0

nonlinear equalities: 5

linear inequalities: 0

nonlinear inequalities: 3

range: 3

Number of nonzeros in Jacobian: 40

Number of nonzeros in Hessian: 15

Iter fCount Objective FeasError OptError ||

Step|| CGits

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

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

0 6 2.785000e+01 6.756e+01

KNITRO performing finite-difference gradient computation with 1

thread.

1 12 2.050506e+01 3.986e+01 1.925e+01 2.236e

+00 1

2 18 1.261872e+01 8.700e+00 2.000e+01 3.289e

+00 1

3 24 9.791015e+00 1.902e+00 6.372e+00 1.379e

+00 1

4 30 8.719649e+00 2.869e-01 6.034e-01

5.356e-01 0

5 36 8.488260e+00 1.339e-02 1.866e-01

1.157e-01 0

6 42 8.476351e+00 3.545e-05 1.059e-02

5.954e-03 0

7 48 8.476319e+00 2.517e-10 2.836e-05

1.586e-05 1

8 54 8.476319e+00 2.220e-16 1.185e-07

1.126e-10 1

EXIT: Locally optimal solution found.

Final Statistics

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

Final objective value = 8.47631944665550e+00

Final feasibility error (abs / rel) = 2.22e-16 / 3.29e-18

Final optimality error (abs / rel) = 1.19e-07 / 3.95e-08

# of iterations = 8

# of CG iterations = 5

# of function evaluations = 54

# of gradient evaluations = 0

Total program time (secs) = 0.00471 ( 0.005 CPU

time)

Time spent in evaluations (secs) = 0.00002

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

-Richard

As a follow-up, I coded your model and although the Interior-Point

algorithms in KNITRO cannot solve it, the Active-Set algorithm

(algorithm=3) solve it pretty easily (8 iterations). The output is at

the end of this message.

In general you should try all the KNITRO algorithms. KNITRO 8.0 has a

new multi-algorithm feature that will run all the KNITRO algorithms

(possibly in parallel) with the ability to terminate as soon as an

optimal solution is found. You can select this by setting

"KTR_PARAM_ALGORITHM=KTR_ALG_MULTI" (or "algorithm=5").

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

*** NO CHECK MADE FOR ZIENA LICENSE ***

KNITRO 8.0.0

Ziena Optimization

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

algorithm: 3

debug: 1

gradopt: 2

hessopt: 2

maxtime_cpu: 1e+08

maxtime_real: 1e+08

outlev: 4

outmode: 2

presolve: 0

KNITRO changing bar_switchrule from AUTO to 2.

KNITRO changing linsolver from AUTO to 4.

KNITRO performing finite-difference gradient computation with 1

thread.

Problem Characteristics

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

Objective goal: Minimize

Number of variables: 5

bounded below: 0

bounded above: 0

bounded below and above: 5

fixed: 0

free: 0

Number of constraints: 8

linear equalities: 0

nonlinear equalities: 5

linear inequalities: 0

nonlinear inequalities: 3

range: 3

Number of nonzeros in Jacobian: 40

Number of nonzeros in Hessian: 15

Iter fCount Objective FeasError OptError ||

Step|| CGits

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

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

0 6 2.785000e+01 6.756e+01

KNITRO performing finite-difference gradient computation with 1

thread.

1 12 2.050506e+01 3.986e+01 1.925e+01 2.236e

+00 1

2 18 1.261872e+01 8.700e+00 2.000e+01 3.289e

+00 1

3 24 9.791015e+00 1.902e+00 6.372e+00 1.379e

+00 1

4 30 8.719649e+00 2.869e-01 6.034e-01

5.356e-01 0

5 36 8.488260e+00 1.339e-02 1.866e-01

1.157e-01 0

6 42 8.476351e+00 3.545e-05 1.059e-02

5.954e-03 0

7 48 8.476319e+00 2.517e-10 2.836e-05

1.586e-05 1

8 54 8.476319e+00 2.220e-16 1.185e-07

1.126e-10 1

EXIT: Locally optimal solution found.

Final Statistics

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

Final objective value = 8.47631944665550e+00

Final feasibility error (abs / rel) = 2.22e-16 / 3.29e-18

Final optimality error (abs / rel) = 1.19e-07 / 3.95e-08

# of iterations = 8

# of CG iterations = 5

# of function evaluations = 54

# of gradient evaluations = 0

Total program time (secs) = 0.00471 ( 0.005 CPU

time)

Time spent in evaluations (secs) = 0.00002

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

-Richard

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu