Input optimization is a conceptually new level of optimization, at which the mathematical programming model, rather than a usual program, is optimized. This is achieved by optimizing the optimal value function by stable perturbations of the parameters considered as ''input''. Every mathematical program, with additional information on parameters (such as the cost of purchasing an extra unit of energy or improving efficiency of the machine) can be considered as an input optimization problem. This paper is the first of several in which theory, numerical methods, and applications of input optimization are presented. It deals with optimality conditions for identifying an optimal choice of parameters over regions of stability for linear and bi-convex models.