This paper derives asymptotically optimal tests for testing problems in which a nuisance parameter exists under the alternative hypothesis but not under the null. For example, the results apply to tests of one-time structural change with unknown change-point. Several other examples are discussed in the paper. The results of the paper are of interest, because the testing problem considered is nonstandard and the classical asymptotic optimality results for the Lagrange multiplier (LM), Wald, and likelihood ratio (LR) tests do not apply. A weighted average power criterion is used here to generate optimal tests. This criterion is similar to that used by Wald (1943) to obtain the classical asymptotic optimality properties of Wald tests in "regular" testing problems. In fact, the optimal tests introduced here reduce to the standard LM, Wald, and LR tests when standard regularity conditions hold. Nevertheless, in the nonstandard cases of main interest, new optimal tests are obtained and the LR test is not found to be an optimal test.