I was discussing moving our process to become more agile with our (mostly traditional) Chief Information Officer (CIO).

The CIO's stance was that >=80% of the requirements need to be defined (and set in stone) up-front, before work on the project can begin. Essentially, fixed scope.

I argued that frequent feedback and fixed schedule would result in better products, and would not need such a large percentage of the scope to be fixed at the onset. That when new scope came up, either other scope should be removed or the schedule be renegotiated.

The CIO then posed to me a question which I was unsure how to answer - namely, how to then justify the original project schedule/cost to the CEO at the beginning to the project. The CEO expects gap and cost analyses before a project begins.

I could argue that agile development processes would overall provide more value to the business, but, given the biases involved (on both sides), I don't think that would be sufficient justification to change if the CIO doesn't continue to provide the analyses that the CEO expects.

So, my question:

How can sufficient upfront analysis be done to satisfy a traditional CEO without locking down a project's scope from the beginning, thereby hobbling much of agile's benefits? Is it impossible? Or am I simply on the wrong track here, and I'm missing something?