The optimization toolbox has existed for MANY years before 2006. I had a copy in my 1988 release. (Back then, it was called a version.) So, yes, it does exist, and it always has existed as far as you would be concerned.
While this question is literally ancient, the solution is to veriy that your MATLAB release was correctly installed. So I would first do an online re-install as the first option. Make sure that nothing failed in the installation.
