In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II.