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.