Can we optimize regression problems that have categorical variables by encoding them if on the other hand we are inserting multicollinearity? Can we optimize regression problems that have categorical variables by encoding them if, on the other hand, we are inserting multicollinearity?
Multicollinearity can be a problem if you choose to optimize linear regression with ordinary least squares (OLS). Because the data matrix $X$ can have less than full rank, therefore the moment matrix $XᵀX$ cannot be inverted. 

If you choose to optimize linear regression with gradient descent, multicollinearity is not an issue in finding an optimal solution.