Study of an adaptive single-phase method for approximating the multidimensional Pareto frontier in nonlinear systems

G. K. Kamenev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 12, pp. 2103-2113

Résumé

The problem of approximating the Pareto frontier (nondominated frontier) of the feasible set of criteria vectors in nonlinear multicriteria optimization problems is considered. The problem is solved by approximating the Edgeworth–Pareto hull (EPH), i.e., the maximum set with the same Pareto frontier as the original feasible set of criteria vectors. An EPH approximation method is studied that is based on the statistical accuracy estimation of the current approximation and on adaptive supplement of a metric net whose EPH approximates the desired set. The convergence of the method is proved, estimates for the convergence rate are obtained, and the efficiency of the method is studied in the case of a compact feasible set and continuous criteria functions. It is shown that the convergence rate of the method with respect to the number $k$ of iterations is no lower than $o(k^{1/\overline{\mathrm{dm}}}Y)$, where $\overline{\mathrm{dm}}Y$ is the upper metric dimension of the feasible set of criteria vectors.