How should Feature Selection and Hyperparameter optimization be ordered in the machine learning pipeline? My  objective is to classify sensor signals. 
The concept of my solution so far is :
i) Engineering features from raw signal
ii) Selecting relevant features with ReliefF and a clustering approach
iii) Apply N.N, Random Forest and SVM
However I am trapped in a dilemma. In ii) and iii), there are hyperparameters like k-Nearest Neigbours for ReliefF or the window length, for which the sensor signal is evaluated, or the number of hidden units in each layer of N.N.
There are 3 Problems I see here :
1) Tuning feature selection parameters will influence the classifier performance
2) Optimizing hyperparameters of classifier will influence the choice of features.
3) Evaluating each possible combination of configuration is intractable.
So my questions are :
a) Can I make a simplifying assumption, s.t. tuning feature selection parameters can be decoupled from tuning classifier parameters ?
b) Are there any other possible solutions ?
 A: No one mentioned approaches that make hyper-parameter tuning and feature selection the same so I will talk about it.  For this case you should engineer all the features you want at the beginning and include them all.
Research now in the statistics community have tried to make feature selection a tuning criterion.  Basically you penalize a model in such a way that it is incentivized to choose only a few features that help it make the best prediction.  But you add a tuning parameter to determine how big of a penalty you should incur.  
In other words you allow the model to pick the features for you and you more or less have control of the number of features. This actually reduces computation because you no longer have to decide which features but just how many features and the model does the rest.
So then when you do cross-validation on the parameter then you are effectively doing cross-validation on feature selection as well.
Already there are many ML models that incorporate this feature selection in some way or another.


*

*Doubly-regularized support vector machines which is like normal SVM but with feature selection

*Elastic net which deals with linear regression

*Drop-out regularization in neural networks (don't have reference for this one)

*Random forest normally does random subsets of the features so kind of handles feature selection for you


In short, people have tried to incorporate parameter tuning and feature selection at the same time in order reduce complexity and be able to do cross-validation
A: Like you already observed yourself, your choice of features (feature selection) may have an impact on which hyperparameters for your algorithm are optimal, and which hyperparameters you select for your algorithm may have an impact on which choice of features would be optimal.
So, yes, if you really really care about squeezing every single percent of performance out of your model, and you can afford the required amount of computation, the best solution is probably to do feature selection and hyperparamter tuning "at the same time". That's probably not easy (depending on how you do feature selection) though. The way I imagine it working would be like having different sets of features as candidates, and treating the selection of one set of features out of all those candidate sets as an additional hyperparameter.
In practice that may not really be feasible though. In general, if you cannot afford to evaluate all the possible combinations, I'd recommend:


*

*Very loosely optimize hyperparameters, just to make sure you don't assign extremely bad values to some hyperparameters. This can often just be done by hand if you have a good intuitive understanding of your hyperparameters, or done with a very brief hyperparameter optimization procedure using just a bunch of features that you know to be decently good otherwise.

*Feature selection, with hyperparameters that are maybe not 100% optimized but at least not extremely terrible either. If you have at least a somewhat decently configured machine learning algorithm already, having good features will be significantly more important for your performance than micro-optimizing hyperparameters. Extreme examples: If you have no features, you can't predict anything. If you have a cheating feature that contains the class label, you can perfectly classify everything. 

*Optimize hyperparameters with the features selected in the step above. This should be a good feature set now, where it actually may be worth optimizing hyperparams a bit.

To address the additional question that Nikolas posted in the comments, concering how all these things (feature selection, hyperparameter optimization) interact with k-fold cross validation: I'd say it depends.
Whenever you use data in one of the folds for anything at all, and then evaluate performance on that same fold, you get a biased estimate of your performance (you'll overestimate performance). So, if you use data in all the folds for the feature selection step, and then evaluate performance on each of those folds, you'll get biased estimates of performance for each of them (which is not good). Similarly, if you have data-driven hyperparameter optimization and use data from certain folds (or all folds), and then evaluate on those same folds, you'll again get biased estimates of performance. Possible solutions are:


*

*Repeat the complete pipeline within every fold separately (e.g. within each fold, do feature selection + hyperparameter optimization and training model). Doing this means that k-fold cross validation gives you unbiased estimates of the performance of this complete pipeline.

*Split your initial dataset into a ''preprocessing dataset'' and a ''train/test dataset''. You can do your feature selection + hyperparameter optimization on the ''preprocessing dataset''. Then, you fix your selected features and hyperparameters, and do k-fold cross validation on the ''train/test dataset''. Doing this means that k-fold cross validation gives you unbiased estimates of the performance of your ML algorithm given the fixed feature-set and hyperparameter values.
Note how the two solutions result in slightly different estimates of performance. Which one is more interesting depends on your use-case, depends on how you plan to deploy your machine learning solutions in practice. If you're, for example, a company that intends to have the complete pipeline of feature selection + hyperparameter optimization + training running automatically every day/week/month/year/whatever, you'll also be interested in the performance of that complete pipeline, and you'll want the first solution.
If, on the other hand, you can only afford to do the feature selection + hyperparameter optimization a single time in your life, and afterwards only somewhat regularly re-train your algorithm (with feature-set and hyperparam values fixed), then the performance of only that step will be what you're interested in, and you should go for the second solution
A: @DennisSoemers has a great solution. I'll add a two similar solutions that are a bit more explicit and based on Feature Engineering and Selection: A Practical Approach for Predictive Models by Max Kuhn and Kjell Johnson. 
Kuhn uses the term resample to describe a fold of a dataset, but the dominant term on StackExchange seems to be fold, so I will use the term fold below.
Option 1 - nested search
If compute power is not a limiting factor, a nested validation approach is recommended, in which there are 3 levels of nesting:
1) the external folds, each fold with a different feature subset
2) the internal folds, each fold with a hyperparameter search
3) the internal folds of each hyperparameter search, each fold with a different hyperparameter set.
Here's the algorithm:
-> Split data into train and test sets.
-> For each external fold of train set:
    -> Select feature subset.
    -> Split into external train and test sets.

    -> For each internal fold of external train set:
        -> Split into internal train and test sets.
        -> Perform hyperparameter tuning on the internal train set. Note that this
           step is another level of nesting in which the internal train set is split
           into multiple folds and different hyperparameter sets are trained and tested on
           different folds.
    -> Examine the performance of the best hyperparameter tuned model 
       from each of the inner test folds. If performance is consistent, redo 
       the internal hyperparameter tuning step on the entire external train set.
    -> Test the model with the best hyperparameter set on the external test set.

-> Choose the feature set with the best external test score.
-> Retrain the model on all of the training data using the best feature set 
   and best hyperparameters for that feature set. 


Image from Chapter 11.2: Simple Filters
The -> Select feature subset step is implied to be random, but there are other techniques, which are outlined in the book in Chapter 11.
To clarify the -> Perform hyperparameter tuning step, you can read about the recommended approach of nested cross validation. The idea is to test the robustness of a training process by repeatedly performing the training and testing process on different folds of the data, and looking at the average of test results.
Option 2 - separate hyperparameter and feature selection search
-> Split data into hyperameter_train, feature_selection_train, and test sets.

-> Select a reasonable subset of features using expert knowledge.

-> Perform nested cross validation with the initial features and the 
   hyperparameter_train set to find the best hyperparameters as outlined in option 1.

-> Use the best hyperparameters and the feature_selection_train set to find 
   the best set of features. Again, this process could be nested cross 
   validation or not, depending on the computational cost that it would take 
   and the cost that is tolerable.

Here's how Kuhn and Johsnon phrase the process:

When combining a global search method with a model that has tuning
  parameters, we recommend that, when possible, the feature set first be
  winnowed down using expert knowledge about the problem. Next, it is
  important to identify a reasonable range of tuning parameter values.
  If a sufficient number of samples are available, a proportion of them
  can be split off and used to find a range of potentially good
  parameter values using all of the features. The tuning parameter
  values may not be the perfect choice for feature subsets, but they
  should be reasonably effective for finding an optimal subset.

Chapter 12.5: Global Search Methods
A: I think you are overthinking quite a bit there. Feature selection, which is part of feature engineering, is usually helpful but some redundant features are not much harmful in early stage of a machine learning system. So best practice is that you generate all meaningful features first, then use them to select algorithms and tune models, after tuning the model you can trim the feature set or decide to use new features.
The machine learning procedure is actually an iterating process, in which you do feature engineering, then try with some algorithms, then tune the models and go back until you are satisfied with the result.
