Closed sanketr closed 1 year ago
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.
@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.
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.
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.
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.
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.
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.
For lincoa, pre-processing of initial starting point is done in
preprima
function inMatlab
andpython
code. There seems to be a lot going on in the code - I couldn't figure out the method of pre-processing from it. It would be very helpful to have the details of the method that is implemented there (for up to linear constraints - we can leave out non-linear constraints). Perhaps this could be added a PDF or markdown note in this repository so that users know how to implement this.If I have the details of the method, and pseudo-code to implement, I could implement this in c/c++. Alternatively, if this is implemented reliably in c/c++/fortran already, I could re-use that instead if you point me to it.
I have C++ bindings to lincoa but not pre-processing step in native code. Hence, this request.