GCS - Reference to equations in code

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
abdullah
Posts: 3501
Joined: Sun May 04, 2014 3:16 pm

GCS - Reference to equations in code

Postby abdullah » Sat Apr 06, 2019 10:02 am

I was going through saso's PVS issues of March, one of them is:
General Analysis GCS.cpp:3582 Medium V547 CWE-571 Expression 'first' is always true.
Going to the code, it is part of the function:

Code: Select all

int System::solve(SubSystem *subsysA, SubSystem *subsysB, bool /*isFine*/, bool isRedundantsolving)
Link to github

PVS is right to note that first is always true no matter what, so this looks like a bug.

The code comments indicate that it is doing a "// line search, Eq. 18.28"

Does anyone know which document this Eq. 18.28 refers to?
abdullah
Posts: 3501
Joined: Sun May 04, 2014 3:16 pm

Re: GCS - Reference to equations in code

Postby abdullah » Sat Apr 06, 2019 11:21 am

I found it. :)

The book is called:
Numerical Optimization - Jorge Nocedal, Stephen J. Wright

Chapter 18 is about SQP, and equation 18.28 is about linear search and matches the if statement.
chrisb
Posts: 25155
Joined: Tue Mar 17, 2015 9:14 am

Re: GCS - Reference to equations in code

Postby chrisb » Sat Apr 06, 2019 12:40 pm

If you found that it should be easy to find any error too :o .
abdullah
Posts: 3501
Joined: Sun May 04, 2014 3:16 pm

Re: GCS - Reference to equations in code

Postby abdullah » Sat Apr 06, 2019 6:58 pm

chrisb wrote:
Sat Apr 06, 2019 12:40 pm
If you found that it should be easy to find any error too :o .
The first to determine is whether it was intended or not.

The thing is that the book indicates that to avoid the Maratos effect (an effect that impedes progression in the minimisation problem), a second order function may be used.

About this second order function, the book says:
The second-order correction step requires evaluation of the constraints c i (x k + p k )
for i ∈ E ∪ I, and therefore it is preferable not to apply it every time the merit function
increases. One strategy is to use it only if the increase in the merit function is accompanied
by an increase in the constraint norm.
It can be shown that when the step p k is generated by the SQP method (18.11) then,
near a solution satisfying second-order sufficient conditions, the algorithm above takes
either the full step p k or the corrected step p k + p̂ k . The merit function does not interfere
with the iteration, so superlinear convergence is attained, as in the local algorithm.
From the code, I understand that logari, at least at the begining, intended to execute the second order step once, the first time.

The book appears to suggest that he won't do it more often because it has to evaluate several constraints, so I understand, because the computational cost is high.

Now, I do not know if logari decided afterwards to execute this step in all the steps, or if he just forgot to make the boolean false after the first iteration.

I have PM-ed logari.

BTW, I like the book. I might buy a hard copy. I do not like to read on the computer almost 700 pages.
abdullah
Posts: 3501
Joined: Sun May 04, 2014 3:16 pm

Re: GCS - Reference to equations in code

Postby abdullah » Fri Apr 12, 2019 5:13 pm

I have created a ticket issue #3929.

Logari suggest to test it with a properly implemented bool flag and without and take the one working best.