I work without exceptions, and the typical solution is to crash the whole program (using assert) if the parameter is invalid. This way you can preserve the invariant.
To avoid crashing, the caller has to validate the parameters before calling the constructor, and handle the invalid parameters at this time rather than in the exception handler, but in the end it's the same.