forum.alglib.net

ALGLIB forum
It is currently Sun Nov 03, 2024 3:55 pm

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Alglib minnlc returns solution out of constraints
PostPosted: Wed May 06, 2020 1:23 pm 
Offline

Joined: Wed May 06, 2020 1:10 pm
Posts: 1
I am trying to implement a simple minimisation under a quadratic inequality constraint and a linear equality constraint as well as lower and upper bounds. My problem is as follow:

min: x1*(-0.00498) + x2*0.05656

u.c. :

. x1^2 * 0.00001048 + 2*x1*x2*0.001431 + x2^2*0.6737996 <= 0.0084050
. x1 + x2 = 1.0
. 0 < x1 < 0.9
. 0 < x2 < 0.9

Once implemented in F# using Alglib it seems that the constraints are not respected. Neither the sum x1+x2 is equal to 1.0 nor the variance is below 0.0084. Though lower and upper bound are respected, my objective function with x2 is improved (lower) than with x0. I believe I have an issue with my formulation of the constraints, but I can't see which one.



let nsfunc2_jac(x:float[]) (fi:float[])(jac:float[,])=
fi.[0] <- -(x.[0]*-0.00498+x.[1]*0.05656)
fi.[2] <- x.[0]+x.[1]+x.[2]-1.0
fi.[1] <- x.[0]*x.[0]*0.00001048 + 2.0*x.[0]+x.[1]*0.001431 + x.[1]*x.[1]*0.6737996-0.0084050
jac.[0,0] <- -0.00498
jac.[0,1] <- 0.05656
jac.[2,0] <- 1.0
jac.[2,1] <- 1.0
jac.[1,0] <- 2*x.[0]*0.00001048 + 2*x[1]*0.001431
jac.[1,1] <- 2*x.[0]*0.001431 + 2+x[1]*0.6737996

let mutable state2 = new alglib.minnlcstate()
let mutable rep2 = new alglib.minnlcreport()
let mutable nrep = new alglib.ndimesional_rep(func2)
let x0 = [|0.8999, 0.1001|]
alglib.minnlccreate(2,x0, &state2)
alglib.minnlcsetalgoaul(state2, 1000.0, 15.0)
alglib.minnlsetcond(state2, 0.000001,10.0)
alglib.minnlcsetscale(state2, [|1.0,1.0|])
alglib.minnlcsetprecexactlowrank(state2, 5.0)
alglib.minnlcsetnlc(state2, 1,1)
alglib.minnlcsetbc(state2, [|0.0,0.0|], [|0.9,0.9|])

alglib.minnlcoptimize(state2, jac, nrep, None)
let x2, rep = alglib.minnlcresults(state2)
let var = x2.[0]*x2.[0]*0.00001048 + 2.0*x2.[0]+x2.[1]*0.001431 + x2.[1]*x2.[1]*0.6737996
printfn "Variance: %s" var.ToString()
I get Var = 0.53 well above the 0.0084050 target. In fact, after the first iteration both my equality and my inequality constraints are broken and the algorithm never comes back within the range.

More worisome, I receive an answer TerminationType = 1 -> OK


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Mon Apr 15, 2024 2:28 pm 
Offline

Joined: Sun Feb 06, 2022 6:24 pm
Posts: 13
Hello, it looks like that even with the latest version of Alglib the solution can still be outside the boundaries with a positive termination output.
Do you have any idea why it happens?


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Mon Apr 15, 2024 3:47 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 925
Do you have any concrete example, and which exactly solver (AUL2, SQP) do you use?

The original example has a mistake in Jacobian


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Wed May 01, 2024 1:47 am 
Offline

Joined: Sun Feb 06, 2022 6:24 pm
Posts: 13
Hi Sergey,
I can't share my code because it involves many classes, so I have tried to replicate a simpler function that returns more or less the same issue:

Code:

#include <iomanip>
#include <iostream>

#include "optimization.h"

using namespace std;
using namespace alglib;


void  func(const real_1d_array& x, real_1d_array& fi, void* ptr)
{
    fi[0] = 50 * pow(x[0], 3) * x[1] - pow(x[2],2);
   
    fi[1] = x[1] * pow(x[2], 3);

    double g = 100 * sin(x[0]);
    double f = 300 * sin(x[1] * 0.9);

    fi[0] = -x[2];

    fi[1] = f + g - 1e-3 * pow(x[2], 2) - 265.;
    fi[2] = f - 1.5 * g;

}



int main()
{
   
    real_1d_array x0 = "[0, 0, 0]";
    real_1d_array s = "[1, 1, 1]";
    double epsx = 1e-9;
    double diffstep = 1e-6;
    ae_int_t maxits = 100000;
    real_1d_array bndl = "[-inf, -inf, -inf]";
    real_1d_array bndu = "[+inf, +inf, +inf]";
    real_1d_array nlcl = "[0, 0]";
    real_1d_array nlcu = "[0, 0]";

    minnlcstate state;
    minnlccreatef(x0, diffstep, state);
    minnlcsetcond(state, epsx, maxits);
    minnlcsetscale(state, s);

    minnlcsetalgoslp(state);

    minnlcsetbc(state, bndl, bndu);
    minnlcsetnlc2(state, nlcl, nlcu);
    minnlcoptguardsmoothness(state);

    minnlcreport rep;
    minnlcoptimize(state, func);
    minnlcresults(state, x0, rep);

    for (int i = 0; i < x0.length(); i++)
    {
        cout << setprecision(10) << x0[i] << endl;
    }

    cout << endl;
    cout << "nlc\t" << rep.nlcidx << "\t" << rep.nlcerr << endl;
    cout << "bc\t" << rep.bcidx << "\t" << rep.bcerr << endl;
    cout << "Termination Type:\t" << rep.terminationtype << endl;
    optguardreport ogrep;
    minnlcoptguardresults(state, ogrep);
    printf("%s\n", ogrep.badgradsuspected ? "true" : "false"); // EXPECTED: false
    printf("%s\n", ogrep.nonc0suspected ? "true" : "false"); // EXPECTED: false
    printf("%s\n", ogrep.nonc1suspected ? "true" : "false"); // EXPECTED: false
}



This will be the output:

Quote:
1.570793632
0.6214630454
1.006445372

nlc 1 9.182153749
bc -1 0
Termination Type: 2
false
false
false


As you see, the second non linear condition is not respected, but the termination type is 2.
Mine code has similar outputs, except termintation type that is 7.


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Wed May 01, 2024 9:44 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 925
Hi!

1. The problem with constraints, especially nonlinear ones, is that in real life it is impossible to tell whether they are satisfied or not. E.g., equality constraints are ALWAYS violated, the question is how big is the violation. In your case it is obviously a large violation (9.18), but what about 0.002 - is it big enough to trigger the alarm?

Our present approach is that we do not decide whether violation is large or small, we simply return all the information about the solution and let the caller decide whether it is bad or good. It is possible to do differently, but presently we prefer to give no promises... because any such promise will become a part of API.

2. Speaking of your specific demo, targets/constraints involving periodic functions like sin() and cos() are really difficult to handle. You need a good initial point in order to be able to converge to the solution. In your case the solver stuck in a local minimum of feasibility error.

Probably, something like that happens in your 'real' problem.

Sergei


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Thu May 02, 2024 12:33 am 
Offline

Joined: Sun Feb 06, 2022 6:24 pm
Posts: 13
Hi Sergey,

thanks for the explanation!

One more thing: in the manual the termination type 7 is described as

Quote:
stopping conditions are too stringent,
further improvement is impossible,
X contains best point found so far.


Could you give more details on the meaning?


Top
 Profile  
 
 Post subject: Re: Alglib minnlc returns solution out of constraints
PostPosted: Tue May 07, 2024 4:23 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 925
The exact meaning is solver-dependent. The SQP solver typically returns it when the target stagnated (changes really slowly) for too long, or when the stopping tolerances are too tight, i.e. less than sqrt(machineEpsilon). Other solvers have slightly different conditions, but generally it triggers when the stopping tolerances are too tight and progress is too slow.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group