Algorithm details for preprocessing of initial starting point in lincoa about prima HOT 7 CLOSED

I have C++ bindings to lincoa but not pre-processing step in native code. Hence, this request.

Out of curiosity, are you using the Fortran 77 code or the modernized Fortran 2008+ code? The PRIMA project (of this repository) is for the latter. Thanks.

Modern code that you folks wrote. I started with classic code from Powell but then have switched to the modernized code. I plan to use bobyqa, newoa and lincoa.

I had to make a few changes for Cpp bindings. One was to change type of calfun in main subroutines from a procedure to a derived type of two things: a function pointer that has callback function (cache it by calling c_f_procpointer) and a c_ptr that is passed back to callback function like this - that c_ptr argument contains pointer to whatever data C/C++ internally manage (the callbackfn will use it to locate objective function, save exceptions in case of exception since Fortran doesn't handle it etc.)
extern "C" void callbackfn(<some internal type>* data, CFI_xdesc_t*, double*)

The above changes required updating evaluatef to pass the c_ptr.

From Cpp, we pass pointer to struct containingcallbackfn pointer and the first argument it expects. Rest are simplyx and f from Fortran subroutine.

bobyqa and newua work fine with Cpp code. Now, for lincoa I will try to figure out how to pre-solve in Cpp in a lightweight manner to find the closest point subject to linear inequality constraints.

from prima.

Hello @sanketr , thank you for your message.

Mathematically speaking, the preprocessing is to project the starting point onto the feasible reason.

More precisely, assume that the starting point is $x_0$, and the linear constraints are $A x \ge b$. Then the preprocessing solves the problem

$$ \min_{x} ||x-x_0|| \quad \text{s.t.}\quad A x \ge b. $$

There may be other types of linear constraints, but the mathematics is the same.

This is a well-studied problem, and you may choose your favorite algorithm to solve it.

See Section 4.3 of the PDFO paper for more information.

I hope this answers your question. Thanks.

from prima.

@zaikunzhang , thanks for pointers. I am familiar with solving linear equality constraints of the form $Ax=b$ but not a norm with inequality constraints. So, I don't yet have any favorite algorithm in this area.

I see that section 4.3 of PDFO paper mentions QR factorization. So I looked around for minimizing $L_1$ norm with QR factorization, and found a paper Solving Linear Inequalities in Least Squares Sense. I am not sure if this is indeed the kind of "well-studied problem" you referred to.

If you have any references (such as classic paper or book chapter or lecture) or pointers to share, they will be very much appreciated. Anything that helps with a simple, fast enough and reliable initial projection. Meanwhile I will try to figure out what kind of solutions exist for the problem formulation you shared.

from prima.

I see that section 4.3 of PDFO paper mentions QR factorization. So I looked around for minimizing L1 norm with QR factorization, and found a paper Solving Linear Inequalities in Least Squares Sense. I am not sure if this is indeed the kind of "well-studied problem" you referred to.

Note really. The third paragraph of Sec 4.3 talks about another preprocessing (note the words "Another noticeable preprocessing"). According to what you have mentioned, I suggest you ignore it for the moment (that's why I did not mention it in my previous response at all). It is not ideal but will not hurt to ignore this part.

If you have any references (such as classic paper or book chapter or lecture) or pointers to share, they will be very much appreciated. Anything that helps with a simple, fast enough and reliable initial projection. Meanwhile I will try to figure out what kind of solutions exist for the problem formulation you shared.

You may search for "projection onto polyhedron" for references.

Another remark is that the problem

$$ \min_{x} ||x-x_0|| \quad \text{s.t.}\quad A x \ge b $$

is a "convex quadratic programming" problem (note that we can replace its objective with $||x-x_0||^2 = (x-x_0)^T(x-x0)$). You can use any solver available for this kind of problems. It will not likely be the best choice, but it will work.

Thank you.

from prima.

I have C++ bindings to lincoa but not pre-processing step in native code. Hence, this request.

Out of curiosity, are you using the Fortran 77 code or the modernized Fortran 2008+ code? The PRIMA project (of this repository) is for the latter. Thanks.

from prima.

Modern code that you folks wrote. I started with classic code from Powell but then have switched to the modernized code. I plan to use bobyqa, newoa and lincoa.

bobyqa and newua work fine with Cpp code.

Great! The Fortran 77 code contains many bugs (due to the language itself, not due to the algorithms), and it is not maintained anymore. So the modernized version should be used unless we want to be bitten by bugs from time to time, including crashing our computers.

Even worse, it is frustrating and even depressing (if possible at all) to debug when bugs occur, since we need to decode a maze of 244 GOTOs in 7939 lines of Fortran 77 code --- I have been doing this for three years and I do not want anyone else to do it again.

In addition, the performance of the modernized code is much better than the Fortran 77 code in terms of the number of function evaluations, which normally represent the major computational cost for the problems handled by these solvers.

find the closest point subject to linear inequality constraints.

Right. This is exactly what is needed.

from prima.

Since the preprocessing is not part of the algorithms, the PRIMA project will not include it in the Fortran code for the time being. Nevertheless, as you have pointed out, it is already included in the MATLAB interface. That said, I would like to close this issue for the moment. Feel free to reopen it if you would like. Thanks.

from prima.