Multi-objective optimization

Multi-objective optimization or Pareto optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, or multiattribute optimization) is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives. For a multi-objective optimization problem, it is not guaranteed that a single solution simultaneously optimizes each objective. The objective functions are said to be conflicting. A solution is called nondominated, Pareto optimal, Pareto efficient or noninferior, if none of the objective functions can be improved in value without degrading some of the other objective values.…

Multi-objective optimization or Pareto optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, or multiattribute optimization) is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives. For a multi-objective optimization problem, it is not guaranteed that a single solution simultaneously optimizes each objective. The objective functions are said to be conflicting. A solution is called nondominated, Pareto optimal, Pareto efficient or noninferior, if none of the objective functions can be improved in value without degrading some of the other objective values. Without additional subjective preference information, there may exist a (possibly infinite) number of Pareto optimal solutions, all of which are considered equally good. Researchers study multi-objective optimization problems from different viewpoints and, thus, there exist different solution philosophies and goals when setting and solving them. The goal may be to find a representative set of Pareto optimal solutions, and/or quantify the trade-offs in satisfying the different objectives, and/or finding a single solution that satisfies the subjective preferences of a human decision maker (DM). Bicriteria optimization denotes the special case in which there are two objective functions. There is a direct relationship between multitask optimization and multi-objective optimization. If some objective function is to be maximized, it is equivalent to minimize its negative or its inverse. We denote Y \subseteq \mathbb R^k the image of X ; x^*\in X a feasible solution or feasible decision; and z^* = f(x^*) \in \mathbb R^k an objective vector or an outcome. In multi-objective optimization, there does not typically exist a feasible solution that minimizes all objective functions simultaneously. Therefore, attention is paid to Pareto optimal solutions; that is, solutions that cannot be improved in any of the objectives without degrading at least one of the other objectives. In mathematical terms, a feasible solution x_1\in X is said to (Pareto) dominate another solution x_2\in X , if \forall i \in \{1, \dots, k\}, f_i(x_1) \leq f_i(x_2) , and \exists i \in \{1, \dots, k\}, f_i(x_1) . A solution x^*\in X (and the corresponding outcome f(x^*) ) is called Pareto optimal if there does not exist another solution that dominates it. The set of Pareto optimal outcomes, denoted X^* , is often called the Pareto frontier, Pareto front, or Pareto boundary. The Pareto front of a multi-objective optimization problem is bounded by a so-called nadir objective vector z^{nadir} and an ideal objective vector z^{ideal} , if these are finite. The nadir objective vector is defined as z^{nadir} = \begin{pmatrix} \sup_{x^* \in X^*} f_1(x^*) \\ \vdots \\ \sup_{x^* \in X^*} f_k(x^*) \end{pmatrix} and the ideal objective vector as z^{ideal} = \begin{pmatrix} \inf_{x^* \in X^*} f_1(x^*) \\ \vdots \\ \inf_{x^* \in X^*} f_k(x^*) \end{pmatrix} In other words, the components of the nadir and ideal objective vectors define the upper and lower bounds of the objective function of Pareto optimal solutions. In practice, the nadir objective vector can only be approximated as, typically, the whole Pareto optimal set is unknown. In addition, a utopian objective vector z^{utop} , such that z^{utop}_i = z^{ideal}_{i} - \epsilon, \forall i \in \{1, \dots , k\} where \epsilon>0 is a small constant, is often defined because of numerical reasons. ===Economics=== In economics, many problems involve multiple objectives along with constraints on what combinations of those objectives are attainable. For example, consumer's demand for various goods is determined by the process of maximization of the utilities derived from those goods, subject to a constraint based on how much income is available to spend on those goods and on the prices of those goods. This constraint allows more of one good to be purchased only at the sacrifice of consuming less of another good; therefore, the various objectives (more consumption of each good is preferred) are in conflict with each other. A common method for analyzing such a problem is to use a graph of indifference curves, representing preferences, and a budget constraint, representing the trade-offs that the consumer is faced with. Another example involves the production possibilities frontier, which specifies what combinations of various types of goods can be produced by a society with certain amounts of various resources. The frontier specifies the trade-offs that the society is faced with — if the society is fully utilizing its resources, more of one good can be produced only at the expense of producing less of another good. A society must then use some process to choose among the possibilities on the frontier. Macroeconomic policy-making is a context requiring multi-objective optimization. Typically a central bank must choose a stance for monetary policy that balances competing objectives — low inflation, low unemployment, low balance of trade deficit, etc. To do this, the central bank uses a model of the economy that quantitatively describes the various causal linkages in the economy; it simulates the model repeatedly under various possible stances of monetary policy, in order to obtain a menu of possible predicted outcomes for the various variables of interest. Then in principle it can use an aggregate objective function to rate the alternative sets of predicted outcomes, although in practice central banks use a non-quantitative, judgement-based, process for ranking the alternatives and making the policy choice. ===Finance=== In finance, a common problem is to choose a portfolio when there are two conflicting objectives — the desire to have the expected value of portfolio returns be as high as possible, and the desire to have risk, often measured by the standard deviation of portfolio returns, be as low as possible. This problem is often represented by a graph in which the efficient frontier shows the best combinations of risk and expected return that are available, and in which indifference curves show the investor's preferences for various risk-expected return combinations. The problem of optimizing a function of the expected value (first moment) and the standard deviation (square root of the second central moment) of portfolio return is called a two-moment decision model. ===Optimal control=== In engineering and economics, many problems involve multiple objectives which are not describable as the-more-the-better or the-less-the-better; instead, there is an ideal target value for each objective, and the desire is to get as close as possible to the desired value of each objective. For example, energy systems typically have a trade-off between performance and cost or one might want to adjust a rocket's fuel usage and orientation so that it arrives both at a specified place and at a specified time; or one might want to conduct open market operations so that both the inflation rate and the unemployment rate are as close as possible to their desired values. Often such problems are subject to linear equality constraints that prevent all objectives from being simultaneously perfectly met, especially when the number of controllable variables is less than the number of objectives and when the presence of random shocks generates uncertainty. Commonly a multi-objective quadratic objective function is used, with the cost associated with an objective rising quadratically with the distance of the objective from its ideal value. Since these problems typically involve adjusting the controlled variables at various points in time and/or evaluating the objectives at various points in time, intertemporal optimization techniques are employed. ===Optimal design=== Product and process design can be largely improved using modern modeling, simulation, and optimization techniques. The key question in optimal design is measuring what is good or desirable about a design. Before looking for optimal designs, it is important to identify characteristics that contribute the most to the overall value of the design. A good design typically involves multiple criteria/objectives such as capital cost/investment, operating cost, profit, quality and/or product recovery, efficiency, process safety, operation time, etc. Therefore, in practical applications, the performance of process and product design is often measured with respect to multiple objectives. These objectives are typically conflicting, i.e., achieving the optimal value for one objective requires some compromise on one or more objectives. For example, when designing a paper mill, one can seek to decrease the amount of capital invested in a paper mill and enhance the quality of paper simultaneously. If the design of a paper mill is defined by large storage volumes and paper quality is defined by quality parameters, then the problem of optimal design of a paper mill can include objectives such as i) minimization of expected variation of those quality parameters from their nominal values, ii) minimization of the expected time of breaks and iii) minimization of the investment cost of storage volumes. Here, the maximum volume of towers is a design variable. This example of optimal design of a paper mill is a simplification of the model used in. Multi-objective design optimization has also been implemented in engineering systems in the circumstances such as control cabinet layout optimization, airfoil shape optimization using scientific workflows, design of nano-CMOS, system on chip design, design of solar-powered irrigation systems, optimization of sand mould systems, engine design, optimal sensor deployment and optimal controller design. === Process optimization === Multi-objective optimization has been increasingly employed in chemical engineering and manufacturing. In 2009, Fiandaca and Fraga used the multi-objective genetic algorithm (MOGA) to optimize the pressure swing adsorption process (cyclic separation process). The design problem involved the dual maximization of nitrogen recovery and nitrogen purity. The results approximated the Pareto frontier well with acceptable trade-offs between the objectives. In 2010, Sendín et al. solved a multi-objective problem for the thermal processing of food. They tackled two case studies (bi-objective and triple-objective problems) with nonlinear dynamic models. They used a hybrid approach consisting of the weighted Tchebycheff and the Normal Boundary Intersection approach. The novel hybrid approach was able to construct a Pareto optimal set for the thermal processing of foods. In 2013, Ganesan et al. carried out the multi-objective optimization of the combined carbon dioxide reforming and partial oxidation of methane. The objective functions were methane conversion, carbon monoxide selectivity, and hydrogen to carbon monoxide ratio. Ganesan used the Normal Boundary Intersection (NBI) method in conjunction with two swarm-based techniques (Gravitational Search Algorithm (GSA) and Particle Swarm Optimization (PSO)) to tackle the problem. Applications involving chemical extraction and bioethanol production processes have posed similar multi-objective problems. In 2013, Abakarov et al. proposed an alternative technique to solve multi-objective optimization problems arising in food engineering. The Aggregating Functions Approach, the Adaptive Random Search Algorithm, and the Penalty Functions Approach were used to compute the initial set of the non-dominated or Pareto-optimal solutions. The Analytic Hierarchy Process and Tabular Method were used simultaneously for choosing the best alternative among the computed subset of non-dominated solutions for osmotic dehydration processes. In 2018, Pearce et al. formulated task allocation to human and robotic workers as a multi-objective optimization problem, considering production time and the ergonomic impact on the human worker as the two objectives considered in the formulation. Their approach used a Mixed-Integer Linear Program to solve the optimization problem for a weighted sum of the two objectives to calculate a set of Pareto optimal solutions. Applying the approach to several manufacturing tasks showed improvements in at least one objective in most tasks and in both objectives in some of the processes. ===Radio resource management=== The purpose of radio resource management is to satisfy the data rates that are requested by the users of a cellular network. The main resources are time intervals, frequency blocks, and transmit powers. Each user has its own objective function that, for example, can represent some combination of the data rate, latency, and energy efficiency. These objectives are conflicting since the frequency resources are very scarce, thus there is a need for tight spatial frequency reuse which causes immense inter-user interference if not properly controlled. Multi-user MIMO techniques are nowadays used to reduce the interference by adaptive precoding. The network operator would like to both bring great coverage and high data rates, thus the operator would like to find a Pareto optimal solution that balance the total network data throughput and the user fairness in an appropriate subjective manner. Radio resource management is often solved by scalarization; that is, selection of a network utility function that tries to balance throughput and user fairness. The choice of utility function has a large impact on the computational complexity of the resulting single-objective optimization problem. For example, the common utility of weighted sum rate gives an NP-hard problem with a complexity that scales exponentially with the number of users, while the weighted max-min fairness utility results in a quasi-convex optimization problem with only a polynomial scaling with the number of users. The utility function method assumes the decision maker's utility function is available. A mapping u\colon Y\rightarrow\mathbb{R} is a utility function if for all \mathbf{y}^1,\mathbf{y}^2\in Y it holds that u(\mathbf{y}^1)>u(\mathbf{y}^2) if the decision maker prefers \mathbf{y}^1 to \mathbf{y}^2 , and u(\mathbf{y}^1)=u(\mathbf{y}^2) if the decision maker is indifferent between \mathbf{y}^1 and \mathbf{y}^2 . The utility function specifies an ordering of the decision vectors (recall that vectors can be ordered in many different ways). Once u is obtained, it suffices to solve \max\;u(\mathbf{f}(\mathbf{x}))\text{ subject to }\mathbf{x}\in X, but in practice, it is very difficult to construct a utility function that would accurately represent the decision maker's preferences, particularly since the Pareto front is unknown before the optimization begins. \min_{x\in X} \sum_{i=1}^k w_if_i(x) where the weights of the objectives w_i>0 are the parameters of the scalarization. \epsilon -constraint method (see, e.g. ) \begin{array}{ll} \min & f_j(x)\\ \text{s.t.} & x \in X\\ & f_i(x)\leq \epsilon_i \text{ for }i\in\{1,\ldots,k\}\setminus\{j\} \end{array} where upper bounds \epsilon_j are parameters as above and f_j is the objective to be minimized. Somewhat more advanced examples are the following: achievement scalarizing problems of Wierzbicki One example of the achievement scalarizing problems can be formulated as \begin{align} \min & \max_{i=1,\ldots,k} \left[\frac{f_i(x)-\bar z_i}{z^{nadir}_i-z_i^{utop}}\right] + \rho\sum_{i=1}^k\frac{f_i(x)}{z_i^{nadir}-z_i^{utop}}\\ \text{s.t. } & x\in S \end{align} where the term \rho\sum_{i=1}^k\frac{f_i(x)}{z_i^{nadir}-z_i^{utop}} is called the augmentation term, \rho>0 is a small constant, and z^{nadir} and z^{utop} are the nadir and utopian vectors, respectively. In the above problem, the parameter is the so-called reference point \bar z representing objective function values preferred by the decision maker. Sen's multi-objective programming \begin{array}{ll} \max & \frac{\sum_{j=1}^r Z_j}{W_j}- \frac{\sum_{j=r+1}^s Z_j}{W_{r+1}} \\ \text{s.t. } & AX=b \\ & X\geq 0 \end{array} where W_j is individual optima (absolute) for objectives of maximization r and minimization r+1 to s . hypervolume/Chebyshev scalarization \min_{x\in X} \max_i \frac{ f_i(x)}{w_i} where the weights of the objectives w_i>0 are the parameters of the scalarization. If the parameters/weights are drawn uniformly in the positive orthant, it is shown that this scalarization provably converges to the Pareto front, even when the front is non-convex. g_{u}^{\mathrm{STCH}}\!\bigl(x\mid\boldsymbol{\lambda}\bigr)= u\,\ln\!\Bigl(\sum_{i=1}^{k}\exp\!\bigl(\tfrac{\lambda_{i}\,[\,f_{i}(x)-z^{\mathrm{ideal}}_{i}\,]}{u}\bigr)\Bigr), \qquad u>0,\; \boldsymbol{\lambda}\in\Delta_{k-1}, where u is the smoothing parameter and \boldsymbol{\lambda}=(\lambda_{1},\dots ,\lambda_{k}) is a weight vector on the probability simplex \Delta_{k-1} . As u\to 0^{+} this converges to the classical (non-smooth) Chebyshev form g^{\mathrm{TCH}}\!\bigl(x\mid\boldsymbol{\lambda}\bigr)= \max_{i}\lambda_{i}\,[\,f_{i}(x)-z^{\mathrm{ideal}}_{i}\,]. The parameter u controls the trade-off between differentiability and approximation accuracy: smaller values yield a closer match to the classical Chebyshev scalarisation but reduce the Lipschitz constant of the gradient, while larger values give a smoother surface at the cost of looser approximation. Properties Smoothness and complexity — g_{u}^{\mathrm{STCH}} is continuously differentiable with an L -Lipschitz gradient. When every f_{i} is convex the function is convex, and an \varepsilon -optimal point is reachable in \mathcal{O}(1/\varepsilon) first-order iterations; sub-gradient descent on g^{\mathrm{TCH}} needs \mathcal{O}(1/\varepsilon^{2}) iterations. Pareto optimality — For any u>0 every minimizer of g_{u}^{\mathrm{STCH}}(\cdot\mid\boldsymbol{\lambda}) is weakly Pareto-optimal; if all \lambda_{i}>0 (or the minimizer is unique) it is Pareto-optimal. Exhaustiveness — There exists a threshold u^{*}>0 such that, for 0 , every Pareto-optimal point can be obtained as a minimizer of g_{u}^{\mathrm{STCH}} for some weight vector \boldsymbol{\lambda} ; when the Pareto front is convex this holds for all u>0 . For example, portfolio optimization is often conducted in terms of mean-variance analysis. In this context, the efficient set is a subset of the portfolios parametrized by the portfolio mean return \mu_P in the problem of choosing portfolio shares to minimize the portfolio's variance of return \sigma_P subject to a given value of \mu_P ; see Mutual fund separation theorem for details. Alternatively, the efficient set can be specified by choosing the portfolio shares to maximize the function \mu_P - b \sigma_P ; the set of efficient portfolios consists of the solutions as b ranges from zero to infinity. Some of the above scalarizations involve invoking the minimax principle, where always the worst of the different objectives is optimized. The roots for hybrid multi-objective optimization can be traced to the first Dagstuhl seminar organized in November 2004 (see here). Here, some scholars in EMO (Professor Kalyanmoy Deb, Professor Jürgen Branke, etc.) and MCDM (Professor Kaisa Miettinen, Professor Ralph E. Steuer, etc.) realized the potential in combining ideas and approaches of MCDM and EMO fields to prepare hybrids of them. Subsequently, many more Dagstuhl seminars have been arranged to foster collaboration. Recently, hybrid multi-objective optimization has become an important theme in several international conferences in the area of EMO and MCDM (see e.g., ).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377208341 under CC BY-SA 4.0; modifications have been made.