Conversation
Generic optimization package for openCV project, will be developed between the June and September of 2013. This work is funded by Google Summer of Code 2013 project. This project is about implementing several algorithms, that will find global maxima/minima of a given function on a given domain subject to a given constraints. All comments/suggestions are warmly appreciated and to be sent to alozz1991@gmail.com (please, mention the word "openCV" in topic of message, for I'm using the spam-filters)
At this point we have a skeleton of a new module (optim) which can barely compile properly (unlike previous commit). Besides, there is a first draft of solver and lpsolver (linear optimization solver) in this commit.
Added LPSolver class together with two nested classes: LPFunction and LPConstraints. These represent function to be maximized and constraints imposed respectively. They are implementations of interfaces Function and Constraints respectively (latter ones are nested classes of Solver interface, which is generic interface for all optimization algorithms to be implemented within this project). The next step is to implement the simplex algorithm! First, we shall implement it for the case of constraints of the form Ax<=b and x>=0. Then, we shall extend the sets of problems that can be handled by the conversion to the one we've handled already. Finally, we shale concentrate on numerical stability and efficiency.
What we have now corresponds to "formal simplex algorithm", described in Cormen's "Intro to Algorithms". It will work *only* if the initial problem has (0,0,0,...,0) as feasible solution (consequently, it will work unpredictably if problem was unfeasible or did not have zero-vector as feasible solution). Moreover, it might cycle. TODO (first priority) 1. Implement initialize_simplex() procedure, that shall check for feasibility and generate initial feasible solution. (in particular, code should pass all 4 tests implemented at the moment) 2. Implement Bland's rule to avoid cycling. 3. Make the code more clear. 4. Implement several non-trivial tests (??) and check algorithm against them. Debug if necessary. TODO (second priority) 1. Concentrate on stability and speed (make difficult tests)
This version is supposed to work on all problems (please, let me know if this is not so), but is not optimized yet in terms of numerical stability and performance. Bland's rule is implemented as well, so algorithm is supposed to allow no cycling. Additional check for multiple solutions is added (in case of multiple solutions algorithm returns an appropriate return code of 1 and returns arbitrary optimal solution). Finally, now we have 5 tests. Before Thursday we have 4 directions that can be tackled in parallel: *) Prepare the pull request! *) Make the code more clear and readable (refactoring) *) Wrap the core solveLP() procedure in OOP-style interface *) Test solveLP on non-trivial tests (possibly test against http://www.coin-or.org/Clp/)
In particular, the following things are done: *) Consistent tabulation of 4 spaces is ensured *) New function dprintf() is introduced, so now printing of the debug information can be turned on/off via the ALEX_DEBUG macro *) Removed solveLP_aux namespace *) All auxiliary functions are declared as static *) The return codes of solveLP() are encapsulated in enum.
Additional cleaning for simplex method, removing the parts that are currently unused. Removing developer's notes. Trying to reach production level.
Change qualifiers on auxiliary functions (for solveLP() procedure) from const (that does not have much sense) to static (that makes them invisible for outside world and hopefully exacerbates optimization).
Fixed the code so to eliminate warnings related to shadowing and unused parameters. In some settings, these warnings may be treated as an errors and lead to failed build. Suggested by Nikita Manovich.
|
Dear Nikita! Thank You for prompt response. I've made a modifications that will Best Regards, 2013/7/11 Nikita Manovich notifications@github.com
|
|
Hi, The problem exists. You can find more information here http://pullrequest.opencv.org/. |
Fixed all of the warnings.
|
Dear Nikita! Try this one, please. Best Regards, 2013/7/11 Nikita Manovich notifications@github.com
|
|
Vadim, Could you please look at the pull request? |
There was a problem hiding this comment.
mat.hpp is big header with inline implementations of Mat ops. It should not be included in the external headers since it's not required there.
There was a problem hiding this comment.
but I use cv::Mat as arguments to solveLP() how should I use them without
including mat.hpp?
2013/7/11 Vadim Pisarevsky notifications@github.com
In modules/optim/include/opencv2/optim.hpp:
+// In no event shall the Intel Corporation or contributors be liable for any direct,
+// indirect, incidental, special, exemplary, or consequential damages
+// (including, but not limited to, procurement of substitute goods or services;
+// loss of use, data, or profits; or business interruption) however caused
+// and on any theory of liability, whether in contract, strict liability,
+// or tort (including negligence or otherwise) arising in any way out of
+// the use of this software, even if advised of the possibility of such damage.
+//
+//M*/
+
+#ifndef OPENCV_OPTIM_HPP
+#define OPENCV_OPTIM_HPP
+
+#include
+#include "opencv2/core.hpp"
+#include "opencv2/core/mat.hpp"mat.hpp is big header with inline implementations of Mat ops. It should
not be included in the external headers since it's not required there.—
Reply to this email directly or view it on GitHubhttps://github.com//pull/1108/files#r5140743
.
There was a problem hiding this comment.
you use references to cv::Mat, not cv::Mat itself. Just try to move this include to precomp.hpp and build it
Attempting to fix issues pointed out by Vadim Pisarevsky during the pull request review. In particular, the following things are done: *) The mechanism of debug info printing is changed and made more procedure-style than the previous macro-style *) z in solveLP() is now returned as a column-vector *) Func parameter of solveLP() is now allowed to be column-vector, in which case it is understood to be the transpose of what we need *) Func and Constr now can contain floats, not only doubles (in the former case the conversion is done via convertTo()) *)different constructor to allocate space for z in solveLP() is used, making the size of z more explicit (this is just a notation change, not functional, both constructors are achieving the same goal) *) (big) mat.hpp and iostream headers are moved to precomp-headers from optim.hpp
There was a problem hiding this comment.
this and the next line should be removed from the file. #define should be moved to .cpp file.
#include "opencv2/core.hpp" should be added
I'm working on generic numerical optimization module for openCV within the Google Summer of Code 2013 initiative (mentor: Vadim Pisarevsky). I propose the implementation of the first algorithm in the series: the simplex algorithm. This version is not optimized so far, but is supposed to work on all the problems correctly and without cycling. Please, let me know if any problems encountered.