Proteek Chandan Roy

Most practical optimization problems are comprised of multiple conflicting objectives and constraints which involve time-consuming simulations. Construction of metamodels of objectives and constraints from a few high-fidelity solutions and a subsequent optimization of metamodels to find in-fill solutions in an iterative manner remain a common metamodeling based optimization strategy. The authors have previously proposed a taxonomy of 10 different metamodeling frameworks for multiobjective optimization problems, each of which constructs metamodels of objectives and constraints independently or in an aggregated manner. Of the 10 frameworks, five follow a generative approach in which a single Pareto-optimal solution is found at a time and other five frameworks were proposed to find multiple Pareto-optimal solutions simultaneously. Of the 10 frameworks, two frameworks (M3-2 and M4-2) are detailed here for the first time involving multimodal optimization methods. In this paper, we also propose an adaptive switching based metamodeling (ASM) approach by switching among all 10 frameworks in successive epochs using a statistical comparison of metamodeling accuracy of all 10 frameworks. On 18 problems from three to five objectives, the ASM approach performs better than the individual frameworks alone. Finally, the ASM approach is compared with three other recently proposed multiobjective metamodeling methods and superior performance of the ASM approach is observed. With growing interest in metamodeling approaches for multiobjective optimization, this paper evaluates existing strategies and proposes a viable adaptive strategy by portraying importance of using an ensemble of metamodeling frameworks for a more reliable multiobjective optimization for a limited budget of solution evaluations.

We study the computational complexity of the non-dominated sorting problem (NDS): Given a set P of n points in R^m, for each point p ∈ P, compute ℓ, the length of longest domination chain p1 > p2 > ··· > pℓ = p, where x dominates y (denoted as x > y) if x is not larger than y in every coordinate. A special case of NDS, which we label as NDS1, is to find all the non-dominated points in P. NDS has emerged as a critical component for multi-objective optimization problems (MOPs). For m ≤ 3, Θ(n log n)-time is known. For a fixed small m > 3, the best bound is O(n log^m-2n log log n). For larger m, the best result is an O(mn²)-time algorithm. We show that the O(mn²) running time is nearly optimal by proving an almost matching conditional lower bound: for any ∈ > 0, and ω(log n) ≤ m ≤ (log n)^o(1), there is no O(mn^2-ε)-time algorithm for NDS or NDS1 unless a popular conjecture in fine-grained complexity theory is false. To complete our results, we present an algorithm for NDS with an expected running time O(mn + n²/m + n log²n) on uniform random inputs.

One of the main enabling technologies of 5G wireless networks is to use mm-Wave spectrum band. Despite its large and wide frequency bandwidth, the obtained data rate can be diminished due to link blockage in this frequency band. In this paper, we formulate a bi-objective optimization problem to optimize user association in cellular networks with mm-Wave enabled base stations. The two objectives to minimize are maximum base station utility and blockage score (to indicate the chance of a link getting blocked). We simulate three different scalarization methods to turn a bi-objective vector into a scalar. Since the combinatorial bi-objective problem is NP-Hard, we conduct Lagrangian dual analysis on all of the scalarization methods. Solving the dual problem decreases the time complexity of the solver algorithm, but the solution has a distance from the optimal point created by solving the primal. We also solve the primal optimization problem with a single objective optimization tool. Compared to the time complexity of the primal problem of scalarization methods, the time complexities of solutions to the dual problems are lower. The results show that our solution to bi-objective optimization problem has a better outcome in terms of the number of link blockage and the maximum base station utility compared to optimizing each objective alone. ¹

One of the main difficulties in applying an optimization algorithm to a practical problem is that evaluation of objectives and constraints often involve computationally expensive procedures. To handle such problems, a metamodel is first formed from a few exact (high-fidelity) solution evaluations and then optimized by an algorithm in a progressive manner. However, in solving multi-or many-objective optimization problems involving multiple constraints, a simple extension of the idea to form one metamodel for each objective and constraint function may not constitute the most efficient approach. The cumulative effect of errors from each metamodel may turn out to be detrimental for the accuracy of the overall optimization procedure. In this paper, we propose a taxonomy of different plausible metamodeling frameworks for multi-and many-objective optimization and provide a comparative study by discussing advantages and disadvantages of each framework. The results presented in this paper are obtained using the well-known Kriging metamodeling approach. Based on our extensive simulation studies on proposed frameworks, we report intriguing observations about the behavior of each framework, which may provide salient guidelines for further studies in this emerging area within evolutionary multi-objective optimization.

Nondominated sorting is a key operation used in multiobjective evolutionary algorithms (MOEA). Worst case time complexity of this algorithm is O(MN²), where N is the number of solutions and M is the number of objectives. For stochastic algorithms like MOEAs, it is important to devise an algorithm which has better average case performance. In this paper, we propose a new algorithm that makes use of faster scalar sorting algorithm to perform nondominated sorting. It finds partial orders of each solution from all objectives and use these orders to skip unnecessary solution comparisons. We also propose a specific order of objectives that reduces objective comparisons. The proposed method introduces a weighted binary search over the fronts when the rank of a solution is determined. It further reduces total computational effort by a large factor when there is large number of fronts. We prove that the worst case complexity can be reduced to ϴ(MNCmaxlog2(F+1)), where the number of fronts is F and the maximum number of solutions per front is Cmax; however, in general cases, our worst case complexity is still O(MN²). Our best case time complexity is O(MNlogN). We also achieve the best case complexity O(MNlogN+N²), when all solutions are in a single front. This method is compared with other state-of-the-art algorithms--efficient nondomination level update, deductive sort, corner sort, efficient nondominated sort and divide-and-conquer sort--in four different datasets. Experimental results show that our method, namely, bounded best order sort, is computationally more efficient than all other competing algorithms.