Linear / Nonlinear Solvers, ver. 1.7.1

735 views
Skip to first unread message

Evgeny Lazutkin

unread,
Jan 23, 2014, 6:14:36 AM1/23/14
to casadi...@googlegroups.com
Dear all,

first of all about linear solvers. I have to solve such a system: A*X=B, where shape(A) = 6x6, shape(B) = 6x2 --- > shape(X) = 6x2.

For example I want to use CSparse solver.

from casadi import *

A = DMatrix([[4.93649,  0,  1.0328,  0,  -0.145497,  0],
 [-5.08199,  0,  2.2746,  0,  0.645497,  0],
 [9.01848,  0,  -8.13118,  0,  4.93649,  0],
 [-0.333333,  4.43649,  0,  1.0328,  0,  -0.145497],
 [0,  -5.08199,  -0.333333,  1.7746,  0,  0.645497],
 [0,  9.01848,  0,  -8.13118,  -0.333333,  4.43649]])

B = DMatrix([[-5.32379001  ,0.],
 [ 2.661895   , 0.          ],
 [-5.32379001 , 0.          ],
 [ 0.         ,-5.32379001  ],
 [ 0.         , 2.661895    ],
 [ 0.         ,-5.32379001  ]])

s = CSparse(A.sparsity(), 2)
#s = LapackLUDense(A.sparsity())
#s = LapackQRDense(A.sparsity())
s.init()
s.setInput(A,"A")
s.prepare()
s.setInput(B.T,"B")
s.setInput(1.0,"T")
s.solve()
x_ = s.getOutput("X")
print x_

I get the solution
Matrix<double>(rows = 2, cols = 6):
[[-0.938497,  -0.0410019,  -0.754419,  -0.16372,  -0.606563,  -0.26229 ]
 [0,  0,  0,  -5.32379,  2.66189,  -5.32379 ]]

which is not correct. Second row is exactly the same as second column in B. Is that means, that CSparse does not accept B in Matrix form?

If I reconstruct the system into the form of:

AA = DMatrix(scipy.linalg.block_diag(A,A))

B = DMatrix(12,1)
B[0,0] = -5.32379001
B[1,0] = 2.661895
B[2,0] = -5.32379001
B[3,0] = 0.0
B[4,0] = 0.0
B[5,0] = 0.0

B[6,0] = 0.0
B[7,0] = 0.0
B[8,0] = 0.0
B[9,0] = -5.32379001
B[10,0] = 2.661895
B[11,0] = -5.32379001

The output will be correct
Matrix<double>(rows = 1, cols = 12):
[[-0.938497,  -0.0410019,  -0.754419,  -0.16372,  -0.606563,  -0.26229,  0,  -1,  0,  -0.999998,  0,  -0.999998 ]]

Also in API docs I found following function: casadi.solve(A,B)

s_A = sparse.csr_matrix(A)
s_B = sparse.csr_matrix(B) # from the first example 6x2

x__ = casadi.solve(s_A,s_B)
print x__
print "Check the solution"
print mul(A,x__)

I get:

Matrix<double>(rows = 6, cols = 2):
[[-0.938497,  -1.41142e-18 ]
 [-0.0410019,  -1 ]
 [-0.754419,  5.65351e-18 ]
 [-0.16372,  -0.999998 ]
 [-0.606563,  0 ]
 [-0.26229,  -0.999998 ]]

which is correct! Which linear solver is used in this function?? How to supply them?


The second question is about KinsolSolver. The problem is that. If in the nonlinear equation system I have 18 equations -- then everything is just fine. If I have 30, I have a error message:

RuntimeError:  on line 670 of file "/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/interfaces/sundials/kinsol_internal.cpp"
Module "KINSol" returned flag "KIN_MXNEWT_5X_EXCEEDED".
The description of this flag is:
"Five consecutive steps have been taken that satisfy the inequality  || D_u p ||_L2 > 0.99 mxnewtstep, where p denotes the current step and mxnewtstep is a scalar upper bound on the scaled step length. Such a failure may mean that || D_F F(u)||_L2 asymptotes from above to a positive value, or the real scalar mxnewtstep is too small."

How we can interpret and handle this problem?

Thank you very much for your help!!!!!!

Best regards,
Evgeny



Joel Andersson

unread,
Jan 23, 2014, 7:57:56 AM1/23/14
to casadi...@googlegroups.com
Hello Evgeny!

Next time, if you have two different questions, please make two separate posts.

Anyway, for the first question about linear solvers. I am the first time to admit that the current syntax is confusing to say the least. The reason why it looks so strange is that we are preparing a shift from "row-major" to "column-major" storage in CasADi. This change will turn this syntax into something more intuitive.

That said, I cannot really reproduce your error with the latest development build, so it is probably something that has gotten solved since 1.7.1. I get the correct answer when I use the current syntax, which you get by replacing the last part with:

s = CSparse(A.T.sparsity(), 2) # transpose is no longer an input of a linear solver!
s.init()
s.setInput(A.T,"A")
s.prepare()
s.setInput(B.T,"B")

s.solve()
x_ = s.getOutput("X")
print x_

For me, this gives:
Matrix<double>(rows = 2, cols = 6):
[[-0.938497,  -0.0410019,  -0.754419,  -0.16372,  -0.606563,  -0.26229 ]
 [-6.90094e-17,  -1,  4.52639e-16,  -0.999998,  8.71641e-16,  -0.999998 ]]

So, updating CasADi (and the syntax) will probably solve your problem.

The "solve" operation is basically an algorithm I wrote myself that would work for matrices of symbolic variables (where you cannot do things like partial pivoting). The algorithm reorders the rows and columns according to a Dulmage-Mendelsohn decomposition and then uses a QR factorization without partial pivoting to solve the system of equations. It's a very crude implementation but it has proven to work reasonably well. The linear solver SymbolicQR uses the same algorithm.

I'll answer the second question separately.

Best regards!
Joel

Joel Andersson

unread,
Jan 23, 2014, 8:12:26 AM1/23/14
to casadi...@googlegroups.com
Hello again!

Now for the second question.

I interpret the error as if KINSOL fails to solve the nonlinear system of equations. But if you want detail, you need to check the KINSOL documentation directly. Maybe you need a better initial guess? Be aware that the syntax for "implicit functions" in CasADi has also changed. The implicit solver now also take an initial solution guess as an input and has been improved and generalized.

Note that you can also use an NLP solver such as IPOPT to solve a root-finding problem. If you don't have a good guess and solution time is not an issue, this can be an attractive alternative.

Best regards!
Joel

Evgeny Lazutkin

unread,
Jan 23, 2014, 12:53:00 PM1/23/14
to casadi...@googlegroups.com
Dear Joel,

thank you very much for your answers!

Could you please tell me your CasADi version and give a link to download it for Linux? Thank you!


I am using 1.7.1 -  so that the code modification for Linear Solver doen not help. I still have a wrong solution.

Grettings,
Evgeny

Evgeny Lazutkin

unread,
Jan 23, 2014, 1:00:06 PM1/23/14
to casadi...@googlegroups.com
First of all - thank you!!

Hm.....I will play with initial guess....and check a manual.

Actually I asked about it, because i.e. Implicit NewtonSolver solves the problem very fast ans correct! But, if I am right, it is not a globalized Newton method. Correct? KinsolSover probably can give a more faster solution, since it uses "strategy".

Can I see already this changes in API for Python? I want to compare, what I wrote with what I should write =)

Grettings,
Evgeny

Joel Andersson

unread,
Jan 23, 2014, 6:19:07 PM1/23/14
to casadi...@googlegroups.com
Hello Evgeny!

You can find nightly builds for Windows and Linux in the tested directory at files.casadi.org.

The "NewtonImplicitSolver" was written by Joris, and as far as I know, it's a conventional Newton method, without any globalization strategy such as line-search or trust region. If it converges, it should be very fast, but a globalization strategy should enlarge the region of convergence. KINSOL implements line-search globalization, which can improve convergence if you start far from the optimal solution. But I think that an NLP solver such as IPOPT (which implements a filter line-search globalization) might have an even larger region of convergence.

Best regards!
Joel

Evgeny Lazutkin

unread,
Jan 24, 2014, 3:01:55 AM1/24/14
to casadi...@googlegroups.com
Dear Joel,

many thanks for your help and answers! So now, I will install the CasADi 1.7.0 from "tested" directory for LInux and write here ASAP.

Also I will try to check KINSOL docs....to fix the problem with this error.

Best regards,
Evgeny  

Evgeny Lazutkin

unread,
Jan 24, 2014, 7:03:16 AM1/24/14
to casadi...@googlegroups.com
Dear Joel,

the precompiled casadi version from here http://sourceforge.net/projects/casadi/files/CasADi/tested/
is not working on my ubuntu x86 system.
my steps
# python ./setup.py install
installation is running normal. Casadi is now in python.

the precompiled version brings me the following error when i try to use casadi in python:
root@sop-ubuntu-virtual:/# python
Python 2.7.4 (default, Apr 18 2013, 14:18:39)
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import casadi
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python2.7/site-packages/casadi/__init__.py", line 24, in <module>
    from casadi import *
  File "/usr/local/lib/python2.7/site-packages/casadi/casadi.py", line 28, in <module>
    _casadi = swig_import_helper()
  File "/usr/local/lib/python2.7/site-packages/casadi/casadi.py", line 24, in swig_import_helper
    _mod = imp.load_module('_casadi', fp, pathname, description)
ImportError: /usr/local/lib/python2.7/site-packages/casadi/_casadi.so: wrong ELF class: ELFCLASS64
>>>

This is with every precompiled version. Everytime I have to transfer the source of casadi and compile it by myself:

---------------------------

the following version i transferred and compile it successfully.
git clone https://github.com/casadi/casadi.git casadi && cd casadi && git checkout 1.7.0

root@sop-ubuntu-virtual:/# /usr/jmodelica_install/bin/jm_python.sh
Python 2.7.4 (default, Apr 18 2013, 14:18:39)
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import casadi
>>> casadi.__version__
'1.7.0+'
>>>

This version is also not working with my example. I get wrong results.

s = CSparse(A.T.sparsity(), 2)
s
.init()
s
.setInput(A.T,"A")
s
.prepare()
s
.setInput(B.T,"B")

s
.solve()

x_
= s.getOutput("X")
print x_



For me, this gives:

Matrix<double>(rows = 2, cols = 6):
[[-0.938497,  -0.0410019,  -0.754419,  -0.16372,  -0.606563,  -0.26229 ]
 
[0,  0,  0,  -5.32379,  2.66189,  -5.32379 ]



---------------------------

After that I have tested the tested source code from git

git clone https://github.com/casadi/casadi.git -b tested casadi
with this source i have the problem that i can not compile it:
root@sop-ubuntu-virtual:/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build# make install_casadi
cd /usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/ThirdParty/CasADi; \
                make -f Makefile
make[1]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/ThirdParty/CasADi'
make[2]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build'
make[2]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build'
cd /usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/ThirdParty/CasADi/../../casadi_build && make  python
make[2]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
-- Flag needed for enabling C++11 features: -std=gnu++0x
-- A library with BLAS API found.
-- A library with LAPACK API found.
-- Detected an IPOPT configuration without sIPOPT headers. Build will proceed, but without sIPOPT functionality.
-- Could not find KNITRO include dir
-- Could not find KNITRO library
-- Could not find CPLEX include dir
-- Could not find CPLEX libraries
-- Could not find MA57
-- MA57 libraries not found. Falling back to MA27
-- Could not find MA27
-- Could not find OOQP include dir
-- Could not find SNOPT include dir
-- Could not find Snopt libs
-- Could not find MATLAB include dir
-- Could not find Matlab libs
-- Could not find SNOPT include dir
-- Could not find Snopt libs
-- Could not find MATLAB include dir
-- Could not find Matlab libs
-- Python executable is /usr/local/bin/python
-- numpy.get_include() is /usr/local/lib/python2.7/site-packages/numpy/core/include
-- Numpy path found: /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy
-- Python libs: /usr/local/lib/libpython2.7.a
-- Numpy includes: /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy;/usr/include
-- Numpy libs: /usr/local/lib/python2.7/site-packages/numpy/core/multiarray.so
--
-- The following features have been enabled:

* dynamic-loading , Compile with support for dynamic loading of generated functions (needed for ExternalFunction)
* using-c++11 , Using C++11 features (improves efficiency and is required for some examples).
* sundials-interface , Interface to the ODE/DAE integrator suite SUNDIALS.
* csparse-interface , Interface to the sparse direct linear solver CSparse.
* lapack-interface , Interface to LAPACK.
* ipopt-interface , Interface to the NLP solver Ipopt.
* qpoases-interface , Interface to the active-set QP solver qpOASES.
* dsdp-interface , Interface to the interior point SDP solver DSDP (requires BLAS and LAPACK).

-- The following OPTIONAL packages have been found:

* LibXml2
* BLAS
* Threads
* LAPACK
* PkgConfig
* IPOPT
* SWIG
* NUMPY
* PythonInterp

-- The following features have been disabled:

* opencl-support , Enable just-in-time compiliation to CPUs and GPUs with OpenCL.
* get-ipopt , Download and build Ipopt.
* knitro-interface , Interface to the NLP solver KNITRO.
* cplex-interface , Interface to the QP solver CPLEX.
* ooqp-interface , Interface to the QP solver OOQP (requires BLAS).
* sqic-interface , Interface to the QP solver SQIC.
* slicot-interface , Interface to the controls library SLICOT.
* worhp-inteface , Interface to the NLP solver Worhp (requires LibXml2 headers).

-- The following OPTIONAL packages have not been found:

* KNITRO
* CPLEX
* MA57
* MA27
* OOQP
* MATLAB
* OCTAVE

-- Configuring done
-- Generating done
-- Build files have been written to: /usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build
make[3]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[4]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
Scanning dependencies of target casadi_control
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
[  0%] Building CXX object control/CMakeFiles/casadi_control.dir/dple_solver.cpp.o
[  0%] Building CXX object control/CMakeFiles/casadi_control.dir/dple_internal.cpp.o
[  1%] Building CXX object control/CMakeFiles/casadi_control.dir/simple_indef_dple_solver.cpp.o
[  1%] Building CXX object control/CMakeFiles/casadi_control.dir/simple_indef_dple_internal.cpp.o
Linking CXX static library ../lib/libcasadi_control.a
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
[  1%] Built target casadi_control
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
[  1%] Generating runtime_embedded.hpp
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
[  1%] Built target casadi_runtime_embedded
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
Scanning dependencies of target casadi
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[5]: Betrete Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
[  2%] Building CXX object symbolic/CMakeFiles/casadi.dir/casadi_options.cpp.o
[  2%] Building CXX object symbolic/CMakeFiles/casadi.dir/casadi_meta.cpp.o
[  2%] Building CXX object symbolic/CMakeFiles/casadi.dir/printable_object.cpp.o
[  2%] Building CXX object symbolic/CMakeFiles/casadi.dir/shared_object.cpp.o
[  3%] Building CXX object symbolic/CMakeFiles/casadi.dir/weak_ref.cpp.o
[  3%] Building CXX object symbolic/CMakeFiles/casadi.dir/generic_type.cpp.o
[  3%] Building CXX object symbolic/CMakeFiles/casadi.dir/options_functionality.cpp.o
[  3%] Building CXX object symbolic/CMakeFiles/casadi.dir/stl_vector_tools.cpp.o
[  4%] Building CXX object symbolic/CMakeFiles/casadi.dir/profiling.cpp.o
[  4%] Building CXX object symbolic/CMakeFiles/casadi.dir/functor.cpp.o
[  4%] Building CXX object symbolic/CMakeFiles/casadi.dir/functor_internal.cpp.o
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp: In constructor ‘CasADi::CustomEvaluateCInternal::CustomEvaluateCInternal(void (*)(CasADi::CustomFunction&, void*))’:
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp:35: error: class ‘CasADi::CustomEvaluateCInternal’ does not have any field named ‘FunctorCInternal’
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp:35: error: no matching function for call to ‘CasADi::FunctorCInternal<void (*)(CasADi::CustomFunction&, void*)>::FunctorCInternal()’
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.hpp:43: note: candidates are: CasADi::FunctorCInternal<P>::FunctorCInternal(P) [with P = void (*)(CasADi::CustomFunction&, void*)]
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.hpp:41: note:                 CasADi::FunctorCInternal<void (*)(CasADi::CustomFunction&, void*)>::FunctorCInternal(const CasADi::FunctorCInternal<void (*)(CasADi::CustomFunction&, void*)>&)
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp: In constructor ‘CasADi::CallbackCInternal::CallbackCInternal(int (*)(CasADi::FX&, void*))’:
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp:47: error: class ‘CasADi::CallbackCInternal’ does not have any field named ‘FunctorCInternal’
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.cpp:47: error: no matching function for call to ‘CasADi::FunctorCInternal<int (*)(CasADi::FX&, void*)>::FunctorCInternal()’
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.hpp:43: note: candidates are: CasADi::FunctorCInternal<P>::FunctorCInternal(P) [with P = int (*)(CasADi::FX&, void*)]
/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/ThirdParty/CasADi/CasADi/symbolic/functor_internal.hpp:41: note:                 CasADi::FunctorCInternal<int (*)(CasADi::FX&, void*)>::FunctorCInternal(const CasADi::FunctorCInternal<int (*)(CasADi::FX&, void*)>&)
make[5]: *** [symbolic/CMakeFiles/casadi.dir/functor_internal.cpp.o] Fehler 1
make[5]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[4]: *** [symbolic/CMakeFiles/casadi.dir/all] Fehler 2
make[4]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[3]: *** [CMakeFiles/python.dir/rule] Fehler 2
make[3]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[2]: *** [python] Fehler 2
make[2]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/casadi_build'
make[1]: *** [all-local] Fehler 2
make[1]: Verlasse Verzeichnis '/usr/install/jmodelica_2014_install/jmodelica_sourcee/JModelica/build/ThirdParty/CasADi'
make: *** [casadi] Fehler 2


---------------------------

Can you please give the source of your precompiled 1.7.0 tested version? Or which version do you use??

Best regards,
Evgeny

Evgeny Lazutkin

unread,
Jan 28, 2014, 4:26:16 AM1/28/14
to casadi...@googlegroups.com
Dear Joel and other CasADi-users!

Please help me with my problem! Does somebody have the same problem under using 1.7.1 or 1.7.0? (Linux, Python)

It is very important to me!

Thank you very much!

Best regards,
Evgeny

Joel Andersson

unread,
Jan 28, 2014, 5:00:53 AM1/28/14
to casadi...@googlegroups.com
Hello Evgeny!

Sorry for slow answer. I don't know why the precompiled libraries are not working for you. Maybe it could be an issue of conflicting versions? Anyway, compiling from sources should be easy enough, especially on Ubuntu. Your problem during compilation is definitely due to conflicting versions. Try compiling in a new clean directory.

Best regards!
Joel

Evgeny Lazutkin

unread,
Jan 29, 2014, 10:39:41 AM1/29/14
to casadi...@googlegroups.com
Dear Joel,

I trying to solve this problem with respect to your comments and instructions. I will post here the information. I want to check all...

Thank you very much for your help. I will write asap.

Best regards,
Evgeny

Evgeny Lazutkin

unread,
Jan 30, 2014, 9:06:21 AM1/30/14
to casadi...@googlegroups.com
Dear Joel,

after updating CasADi to the "Tested"-Version this example with linear solver works well. There are no errors!

This post is connected to the story here
https://groups.google.com/forum/#!topic/casadi-users/or-Yk6WDLEA

And I almost forgot to tell you about the Nonlinear solver - you were rigth. This error was caused by inappropriate initial guess for KinsolSolver! By now, works everything fine!

My biggest thanks for you and your team!

Best regards,
Evgeny
Reply all
Reply to author
Forward
0 new messages