Multi-objective optimization

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.

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.

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[4][5] 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.[6]

Product and process design can be largely improved using modern modeling, simulation and optimization techniques. The key question in optimal design is the measure of what is good or desirable about a design. Before looking for optimal designs it is important to identify characteristics which 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 recovery of the product, 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 typically are conflicting, i.e. achieving the optimal value for one objective requires some compromise on one or more of other 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 parameter from their nominal values, ii) minimization of expected time of breaks and iii) minimization of investment cost of storage volumes. Here, maximum volume of towers are design variables. This example of optimal design of a paper mill is a simplification of the model used in.[7] Multi-objective design optimization have also been implemented in engineering systems in circumstances such as control cabinet layout optimization,[8] airfoil shape optimization using scientific workflows,[9] design of nano-CMOS semiconductors,[10] system on chip design, design of solar-powered irrigation systems,[11] optimization of sand mould systems,[12][13] engine design,[14][15] optimal sensor deployment[16] and optimal controller design.[17][18]

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 provided a good approximation of the Pareto frontier with acceptable trade-offs between the objectives.[19]

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 and 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.[20]

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.[21] Applications involving chemical extraction[22] and bioethanol production processes[23] 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.[24] 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.[25]

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. The application of 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.[26]

The purpose of radio resource management is to satisfy the data rates that are requested by the users of a cellular network.[27] 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.[27] 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.[28]

Reconfiguration, by exchanging the functional links between the elements of the system, represents one of the most important measures which can improve the operational performance of a distribution system. The problem of optimization through the reconfiguration of a power distribution system, in terms of its definition, is a historical single objective problem with constraints. Since 1975, when Merlin and Back [29] introduced the idea of distribution system reconfiguration for active power loss reduction, until nowadays, a lot of researchers have proposed diverse methods and algorithms to solve the reconfiguration problem as a single objective problem. Some authors have proposed Pareto optimality based approaches (including active power losses and reliability indices as objectives). For this purpose, different artificial intelligence based methods have been used: microgenetic,[30] branch exchange,[31] particle swarm optimization [32] and non-dominated sorting genetic algorithm.[33]

Autonomous inspection of infrastructure has the potential to reduce costs, risks and environmental impacts, as well as ensuring better periodic maintenance of inspected assets. Typically, planning such missions has been viewed as a single-objective optimization problem, where one aims to minimize the energy or time spent in inspecting an entire target structure.[34] For complex, real-world structures, however, covering 100% of an inspection target is not feasible, and generating an inspection plan may be better viewed as a multiobjective optimization problem, where one aims to both maximize inspection coverage and minimize time and costs. A recent study has indicated that multiobjective inspection planning indeed has the potential to outperform traditional methods on complex structures[35]

In the utility function method, it is assumed that the decision maker's utility function is available. A mapping ${\displaystyle u\colon Y\rightarrow \mathbb {R} }$ is a utility function if for all ${\displaystyle \mathbf {y} ^{1},\mathbf {y} ^{2}\in Y}$ if it holds that ${\displaystyle u(\mathbf {y} ^{1})>u(\mathbf {y} ^{2})}$ if the decision maker prefers ${\displaystyle \mathbf {y} ^{1}}$ to ${\displaystyle \mathbf {y} ^{2}}$, and ${\displaystyle u(\mathbf {y} ^{1})=u(\mathbf {y} ^{2})}$ if the decision maker is indifferent between ${\displaystyle \mathbf {y} ^{1}}$ and ${\displaystyle \mathbf {y} ^{2}}$. The utility function specifies an ordering of the decision vectors (recall that vectors can be ordered in many different ways). Once ${\displaystyle u}$ is obtained, it suffices to solve

${\displaystyle \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[1] - particularly since the Pareto front is unknown before the optimization begins.

The lexicographic method assumes that the objectives can be ranked in the order of importance. We assume that the objective functions are in the order of importance so that ${\displaystyle f_{1}}$ is the most important and ${\displaystyle f_{k}}$ the least important to the decision maker. Subject to this assumption, various methods can be used to attain the lexicograpically optimal solution. Note that a goal or target value is not specified for any objective here, which makes it different from the Lexicographic Goal Programming method.

Scalarizing a multi-objective optimization problem is an a priori method, which means formulating a single-objective optimization problem such that optimal solutions to the single-objective optimization problem are Pareto optimal solutions to the multi-objective optimization problem.[2] In addition, it is often required that every Pareto optimal solution can be reached with some parameters of the scalarization.[2] With different parameters for the scalarization, different Pareto optimal solutions are produced. A general formulation for a scalarization of a multiobjective optimization is thus

${\displaystyle {\begin{array}{ll}\min &g(f_{1}(x),\ldots ,f_{k}(x),\theta )\\{\text{s.t }}x\in X_{\theta },\end{array}}}$

where ${\displaystyle \theta }$ is a vector parameter, the set ${\displaystyle X_{\theta }\subseteq X}$ is a set depending on the parameter ${\displaystyle \theta }$ and ${\displaystyle g:\mathbb {R} ^{k+1}\rightarrow \mathbb {R} }$ is a function.

Very well-known examples are the so-called

• linear scalarization

${\displaystyle \min _{x\in X}\sum _{i=1}^{k}w_{i}f_{i}(x),}$

where the weights of the objectives ${\displaystyle w_{i}>0}$ are the parameters of the scalarization, and the

• ${\displaystyle \epsilon }$-constraint method (see, e.g.[1])

${\displaystyle {\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 ${\displaystyle \epsilon _{j}}$ are parameters as above and ${\displaystyle f_{j}}$ is the objective to be minimized.

Somewhat more advanced examples are the:

• achievement scalarizing problems of Wierzbicki.[40] One example of the achievement scalarizing problems can be formulated as

${\displaystyle {\begin{array}{ll}\min &\max _{i=1,\ldots ,k}\left[{\frac {f_{i}(x)-{\bar {z}}_{i}}{z_{i}^{\text{nad}}-z_{i}^{\text{utopian}}}}\right]+\rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopian}}}}\\{\text{subject to }}&x\in S,\end{array}}}$

where the term ${\displaystyle \rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopian}}}}}$ is called the augmentation term, ${\displaystyle \rho >0}$ is a small constant, and ${\displaystyle z^{\text{nad}}}$ and ${\displaystyle z^{\text{utopian}}}$ are the nadir and utopian vectors, respectively. In the above problem, the parameter is the so-called reference point ${\displaystyle {\bar {z}}}$ which represents objective function values preferred by the decision maker.

• Sen's Multi-Objective Programming[41]

$${\displaystyle {\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 ${\displaystyle W_{j}}$ is individual optima (Absolute) for objectives of maximization ${\displaystyle r}$ and minimization ${\displaystyle r+1}$ to ${\displaystyle s}$.

• Hypervolume/Chebyshev Scalarization[42]

${\displaystyle \min _{x\in X}\max _{i}{\frac {f_{i}(x)}{w_{i}}},}$

where the weights of the objectives ${\displaystyle 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,[42] even when the front is non-convex.

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 ${\displaystyle \mu _{P}}$ in the problem of choosing portfolio shares so as to minimize the portfolio's variance of return ${\displaystyle \sigma _{P}}$ subject to a given value of ${\displaystyle \mu _{P}}$; see Mutual fund separation theorem for details. Alternatively, the efficient set can be specified by choosing the portfolio shares so as to maximize the function ${\displaystyle \mu _{P}-b\sigma _{P}}$; the set of efficient portfolios consists of the solutions as b ranges from zero to infinity.

Well-known examples of mathematical programming-based a posteriori methods are the Normal Boundary Intersection (NBI),[43] Modified Normal Boundary Intersection (NBIm)[44] Normal Constraint (NC),[45][46] Successive Pareto Optimization (SPO),[47] and Directed Search Domain (DSD) methods, which solve the multi-objective optimization problem by constructing several scalarizations. The solution to each scalarization yields a Pareto optimal solution, whether locally or globally. The scalarizations of the NBI, NBIm, NC and DSD methods are constructed with the target of obtaining evenly distributed Pareto points that give a good evenly distributed approximation of the real set of Pareto points.

Evolutionary algorithms are popular approaches to generating Pareto optimal solutions to a multi-objective optimization problem. Currently, most evolutionary multi-objective optimization (EMO) algorithms apply Pareto-based ranking schemes. Evolutionary algorithms such as the Non-dominated Sorting Genetic Algorithm-II (NSGA-II)[48] or its extended version NSGA-III[49][50] and Strength Pareto Evolutionary Algorithm 2 (SPEA-2)[51] have become standard approaches, although some schemes based on particle swarm optimization and simulated annealing[52] are significant. The main advantage of evolutionary algorithms, when applied to solve multi-objective optimization problems, is the fact that they typically generate sets of solutions, allowing computation of an approximation of the entire Pareto front. The main disadvantage of evolutionary algorithms is their lower speed and the Pareto optimality of the solutions cannot be guaranteed, it is only known that none of the generated solutions is dominated by another.

Another paradigm for multi-objective optimization based on novelty using evolutionary algorithms was recently improved upon.[53] This paradigm searches for novel solutions in objective space (i.e., novelty search[54] on objective space) in addition to the search for non-dominated solutions. Novelty search is like stepping stones guiding the search to previously unexplored places. It is especially useful in overcoming bias and plateaus as well as guiding the search in many-objective optimization problems.

Deep learning conditional methods are new approaches to generating several Pareto optimal solutions. The idea is to use the generalization capacity of deep neural networks to learn a model of the entire Pareto front, from a limited number of example trade-offs along that front, a task called Pareto Front Learning.[55] Several approaches address this setup, including using hypernetworks,[55] and using Stein variational gradient descent.[56]

Commonly known a posteriori methods are listed below:

• ε-constraints method[57][58]
• Pareto-Hypernetworks [55]
• Multiple-objective Branch-and-Bound[59][60][61]
• Normal Boundary Intersection (NBI)[43]
• Modified Normal Boundary Intersection (NBIm)[44] Normal Constraint (NC),[45][46]
• Successive Pareto Optimization (SPO)[47]
• Directed Search Domain (DSD)
• NSGA-II[48]
• PGEN (Pareto surface generation for convex multi-objective instances)[62]
• IOSO (Indirect Optimization on the basis of Self-Organization)
• SMS-EMOA (S-metric selection evolutionary multi-objective algorithm)[63]
• Approximation-Guided Evolution (first algorithm to directly implement and optimise the formal concept of approximation from theoretical computer science)[64]
• Reactive Search Optimization (using machine learning for adapting strategies and objectives),[65][66] implemented in LIONsolver
• Benson's algorithm for multiple objective linear programs and for multiple objective convex programs
• Multi-objective particle swarm optimization
• Subpopulation Algorithm based on Novelty[53]
• MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition)

There are different interactive methods involving different types of preference information. Three of those types can be identified based on

1. trade-off information,
2. reference points and
3. classification of objective functions.[67]

On the other hand, a fourth type of generating a small sample of solutions is included:[68][69] An example of interactive method utilizing trade-off information is the Zionts-Wallenius method,[70] where the decision maker is shown several objective trade-offs at each iteration, and (s)he is expected to say whether (s)he likes, dislikes or is indifferent with respect to each trade-off. In reference point based methods (see e.g.[71][72]), the decision maker is expected at each iteration to specify a reference point consisting of desired values for each objective and a corresponding Pareto optimal solution(s) is then computed and shown to him/her for analysis. In classification based interactive methods, the decision maker is assumed to give preferences in the form of classifying objectives at the current Pareto optimal solution into different classes indicating how the values of the objectives should be changed to get a more preferred solution. Then, the classification information given is taken into account when new (more preferred) Pareto optimal solution(s) are computed. In the satisficing trade-off method (STOM)[73] three classes are used: objectives whose values 1) should be improved, 2) can be relaxed, and 3) are acceptable as such. In the NIMBUS method,[74][75] two additional classes are also used: objectives whose values 4) should be improved until a given bound and 5) can be relaxed until a given bound.

In the case of bi-objective problems, informing the decision maker concerning the Pareto front is usually carried out by its visualization: the Pareto front, often named the tradeoff curve in this case, can be drawn at the objective plane. The tradeoff curve gives full information on objective values and on objective tradeoffs, which inform how improving one objective is related to deteriorating the second one while moving along the tradeoff curve. The decision maker takes this information into account while specifying the preferred Pareto optimal objective point. The idea to approximate and visualize the Pareto front was introduced for linear bi-objective decision problems by S.Gass and T.Saaty.[80] This idea was developed and applied in environmental problems by J.L. Cohon.[81] A review of methods for approximating the Pareto front for various decision problems with a small number of objectives (mainly, two) is provided in.[82]

There are two generic ideas on how to visualize the Pareto front in high-order multi-objective decision problems (problems with more than two objectives). One of them, which is applicable in the case of a relatively small number of objective points that represent the Pareto front, is based on using the visualization techniques developed in statistics (various diagrams, etc. – see the corresponding subsection below). The second idea proposes the display of bi-objective cross-sections (slices) of the Pareto front. It was introduced by W.S. Meisel in 1973[83] who argued that such slices inform the decision maker on objective tradeoffs. The figures that display a series of bi-objective slices of the Pareto front for three-objective problems are known as the decision maps. They give a clear picture of tradeoffs between three criteria. Disadvantages of such an approach are related to two following facts. First, the computational procedures for constructing the bi-objective slices of the Pareto front are not stable since the Pareto front is usually not stable. Secondly, it is applicable in the case of only three objectives. In the 1980s, the idea W.S. Meisel of implemented in a different form – in the form of the Interactive Decision Maps (IDM) technique.[84] More recently N. Wesner[85] proposed to use a combination of a Venn diagramm and multiple scatterplots views of the objective space for the exploration of the Pareto frontier and the selection of optimal solutions.