I am solving an optimization problem using fmincon with the interior-point method. The problem has about 5000 variables and 5000 nonlinear constraints. By a very large margin, most of the computational time is spent in the routine 'factorKKTmatrix', which I guess does what its name suggests. As the trust-region version of the interior-point method does not appear to be more efficient, an idea that comes to mind to speed things up is to provide sparsity patterns for the Jacobian of the constraints and the Hessian of the Lagrangian (both are very sparse). To my knowledge, however, this is not possible using fmincon. My question is thus whether I can expect to see significant gains in terms of CPU-time from providing said sparsity patterns, making it worthwhile to try other solvers (eg. knitro) as well?
There would definitely be significant gains in taking advantage of Hessian sparsity, but I don't know why you think that means abandoning FMINCON. This link talks a lot about options in FMINCON to customize Hessian calculations
The trust-region method offers HessPattern (to specify the sparsity pattern as you mentioned) and HessMult. In HessMult, you can customize multiplication with the Hessian in any way you want, including using a sparse matrix to represent the Hessian.
In the interior-point method, you have both HessMult and HessFcn, which allows similar customizations.