0
$\begingroup$

I work in signal processing field. I have a system that has input c as a 1-D vector (b is the index of c), and P as a system response matrix. Σ is the covariance matrix. Both P and Σ could be measured to a reasonable accuracy. With the input c, I measure a signal m which is a function of time (t). I know that m is also affected by a noise term n:

enter image description here

I believe the noise can be reasonably described by a multi-variate Gaussian model so I am trying to use MLE approach to estimate c. Below is (I believe) the slightly simplified probability equation (based on this):

enter image description here

The vector c has about 1000 elements. It has an equality constraint and an inequality constraint.

![enter image description here

I was able to get a reasonable result using MATLAB fmincon function but the speed is very slow. My model function was written in vectors/matrices, which evaluates very fast.

However I am hoping to apply the same model to at least 1E5 problems repeatedly (the stretch goal is to apply it to every signal we detect). The current speed seems too slow for that. These problems do not have similar answers, however for each problem, I know that physically the answer (optimal c) would have a somewhat 'continuous' region (with regard to b) that are non-zero values, while the rest should all be zeros. In addition, I could use a brute method to 'guess' an initial start point (such as a 1-D discrete delta function), and I know that the 'weighted' centroid of the optimal c and the guessed initial values are close to each other.

I am wondering: if I switch to another language such as C++ (with some open source libraries), is the speed going to be improved significantly? The languages I am currently considering include Python/Julia/C++.

I also have another option which is renting some high-performance computer cores but that would be my last choice.

BTW, with fmincon I had to use 'sqp' algorithm to get the best convergence (if that helps).

$\endgroup$
5
  • $\begingroup$ The effort needed to solve nonlinear optimization problems depends very much on all the details of the problem. Your question is therefore too general to be answerable. $\endgroup$ – whuber Apr 27 '18 at 14:54
  • $\begingroup$ Thank you for the comments. I read some articles and I realized my problem is probably a linear optimization. I added more details in the question. $\endgroup$ – Will Apr 27 '18 at 15:24
  • $\begingroup$ It's not a linear optimization (programming) problem if the objective function is nonlinear. Anyhow, among many other things, the performance of fmincon can be strongly affected by the starting values. Are the 1e5 problems you want to solve closely related to each other, for instance by being minor perturbation from the previous problem? If so, you might be able to use optimum from previous problem as starting value for new problem. And various other possibilities, depending on the nature of the differences between problems. Can you show us the objective function, and how 1e5 problems differ? $\endgroup$ – Mark L. Stone Apr 27 '18 at 15:45
  • $\begingroup$ I have edited my question to make it more clear. Thanks for your suggestions, I am new to this field. $\endgroup$ – Will Apr 27 '18 at 17:03
  • 1
    $\begingroup$ After taking the log of the objective function, this looks like a convex Quadratic Programming (QP) problem, for which specialized solvers exist, which should be faster than fmincon. E.g., quadprog in MATLAB's optimization toolbox, but other QP solvers, such as cplex, gurobi, mosek are likely faster. They can be called from MATLAB or via many other programming interfaces and APIs. 1000 elements is not very big for a convex QP - I'm guessing you can get a huge speedup vs. 20 sec for fmincon. I;d vote to reopen, if I could figure out how (maybe I am not able to?). $\endgroup$ – Mark L. Stone Apr 27 '18 at 17:20
1
$\begingroup$

After taking the log of the objective function, this looks like a convex Quadratic Programming (QP) problem, for which specialized solvers exist, which should be much faster than fmincon.

E.g., quadprog in MATLAB's optimization toolbox is a QP solver (though not specialized to convex QPs). Other QP solvers, such as CPLEX, GUROBI, ands MOSEK (which has its own version of QUADPROG) are likely faster, and have multiple algorithm options (interior point and active set). They can be called from MATLAB or via many other programming interfaces and APIs, including PYTHON and C. There are also convex QP solvers callable from Julia.

1000 elements is not very big for a convex QP. I'm guessing you can get a huge speedup vs. 20 sec for fmincon (I suspect you are using a Quasi-Newton version of fmincon, which right off the bat gives up a lot vs. using the exact Hessian as QP solvers do). There might be various tricks (warms starts, among others) which you can use to get even further speedups.

$\endgroup$
2
  • $\begingroup$ As for the here and now with fmincon, get rid of the exp, if you haven't already done so, and provide the Hessian, $P^T \Sigma P$ $\endgroup$ – Mark L. Stone Apr 27 '18 at 17:57
  • $\begingroup$ Thanks. I did not know getting rid of exp also helps speeding up the computation. I will look into the QP solvers. $\endgroup$ – Will Apr 27 '18 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.