Yager family of t-norms is a parametric family of continuous nilpotent t-norms which is also one of the most frequently applied one. This family of t-norms is strictly increasing in its parameter and covers the whole spectrum of t-norms when the parameter is changed from zero to infinity. In this paper, we study a nonlinear optimization problem where the feasible region is formed as a system of fuzzy relational equations (FRE) defined by the Yager t-norm. We firstly investigate the resolution of the feasible region when it is defined with max-Yager composition and present some necessary and sufficient conditions for determining the feasibility and some procedures for simplifying the problem. Since the feasible solutions set of FREs is non-convex and the finding of all minimal solutions is an NP-hard problem, conventional nonlinear programming methods may involve high computation complexity. For these reasons, a method is used, which preserves the feasibility of new generated solutions. The proposed method does not need to initially find the minimal solutions. Also, it does not need to check the feasibility after generating the new solutions. Moreover, we present a technique to generate feasible max-Yager FREs as test problems for evaluating the performance of the current algorithm. The proposed method has been compared with Lu and Fang’s algorithm. The obtained results confirm the high performance of the proposed method in solving such nonlinear problems.