2.2. Multiple Criteria Optimization
Multiple Criteria Optimization (MCO) is a field from Engineering Mathematics that deals with making decisions in the presence of multiple performance measures in conflict, i.e., decisions where optimizing one criterion results in moving away from optimality in at least another criterion. Because of the presence of conflict, an MCO problem does not find a single best solution but rather a set of best compromising solutions in light of the performance measures under analysis. The best compromises define solutions called Pareto-Efficient (or simply Efficient, for short) that define the Efficient Frontier of the MCO problem at hand. A typical multiple criteria optimization with two conflicting performance measures (objectives), PMs, can be visualized as in Figure 1. In this figure, a set of seven candidate points, characterized by their values on both performance measures, are shown. The performance measure represented in the x-axis is to be maximized while the performance measure in the y-axis is to be minimized in this example. The problem is to find those candidate points that dominate all of the other points in both performance measures. In the face of conflict, this will result in a group of candidates in the southeast extreme of the set in Figure 1, solutions 3 and 5. These are Pareto-efficient solutions and, when all of them are accounted for, they integrate the Efficient Frontier of the MCO problem. In this example, it can be noted that among efficient solutions, an improvement in one performance measure can only come strictly at the detriment of another one: moving from solution 5 to solution 3 will result in an improvement in the performance measure associated to the vertical direction, but in a loss in the performance measure associated to the horizontal direction. Note that the general problem involves at least two performance measures to be optimized, where only the case with two performance measures has a convenient graphical representation. An MCO problem, however, can include as many dimensions (or performance measures) as necessary.
The general mathematical formulation of an unconstrained MCO problem is as follows: (1) Find x toMinimize fj(x)     j=1,2,…,J
The MCO problem in (1) can be discretized onto a set K  with |K| points in the space of the decision variables so as to define particular solutions xk,  (k=1,2,…, |K|) which can, in turn, be evaluated in the J performance measures to result in values fj(xk). That is, the kth combination of values for the decision variables evaluated in the jth objective function. The illustrative example in Figure 1 follows this discretization with J=2 performance measures and |K|=7 solutions.
The MCO formulation under such discretization is, then as follows: (2) Find xk (k∈K) toMinimize fj(xk)     j=1,2,…,J
The solutions to (2) are, then, the Pareto-efficient solutions of the discretized MCO problem. Considering formulation (2), a particular combination x0 with evaluations fj(x0) will yield a Pareto-Efficient solution to (2) if and only if no other solution xψ exists that meets two conditions, from this point on called Pareto-optimality conditions: (Condition 1) fj(xψ)≤fj(x0) ∀j (Condition 2) fj(xψ)<fj(x0) in at least one j
Conditions (1) and (2) imply that no other solution xψ dominates the solution under evaluation, x0, in all performance measures simultaneously.
Figure 1  Representation of a multiple criteria optimization problem with two performance measures.   In previous publications [3,4] our group has demonstrated that if a set of candidate solutions evaluated by multiple performance measures is available, it is possible to determine a series of best compromises between all criteria through a technique called Data Envelopment Analysis (DEA). The idea behind DEA is to use an optimization model to compute a relative efficiency score for each particular solution with respect to the rest of the candidate solutions. The resulting best compromises, identified through their efficiency score, form the envelope of the solution set, therefore the name Data Envelopment Analysis. These solutions are indeed Pareto-efficient solutions of the problem under analysis.
The DEA linear programming formulations proposed by Banks, Charnes, and Cooper [5] are shown below: (3) Find  μ, ν, μ0+,μ0−  toMaximize μTY0max+  μ0+−μ0−Subject to   νTY0min=1μTYjmax− νTYjmin+μ0+−μ0−≤0   j=1,…,n   μT≥ε·1   νT≥ε·1   μ0+,μ0− ≥0 (4) Find  μ, ν,ν0+−ν0−     toMinimize νTY0max+  ν0+−ν0−Subject to   μTY0max=1  νTYjmin−μTYjmax+ν0+−ν0−≥0   j=1,…,n   νT≥ε·1   μT≥ε·1   ν0+,ν0− ≥0 where μ and ν are column vectors containing multipliers to be optimally determined together with scalar variables μ0+ and μ0− in the first case and together with ν0+ and ν0− in the second case; Yjmin and Yjmax are column vectors containing the values of the jth combination of performance measures to be minimized and maximized respectively; and ε is a scalar usually set to a value of 1 × 10−6.
Model (3) is called the BCC Input Oriented Model and Model (4) is called the BCC Output Oriented Model. Both models are applied to each of the n candidate solutions. A particular solution with an objective function score of 1 (i.e., an efficiency score of 1) using both formulations is in the envelope of the set and is considered to be an efficient solution to the MCO problem. The BCC model is just one of many possible DEA formulations, albeit a very powerful one. This model’s mathematical linear nature provides it with the capability of finding efficient solutions associated with the data set under analysis through a series of piece-wise linear segments. Nonlinear behavior is, then, approached with tractability and with the certainty that at least the efficient solutions lying in the convex part of the frontier are being found. Figure 2 shows an MCO problem solved through with DEA, specifically with the BCC model.
DEA has several advantages including: (i) computational efficiency owing to its linear optimization structure; (ii) objectivity and consistency of results, which follows from not requiring the adjustment of parameters or assigning weights to the different performance measures by the user, and (iii) capability of analyzing several microarray experiments with incommensurate units. Appendix A discusses the volcano plot, a widely used tool to detect differentially expressed genes, to illustrate how the analyst can bias the results. On the other hand, one limitation of DEA is that of depending on a series of local linear approximations, as shown in Figure 2. Every time that a linear segment is superimposed over the set under analysis, there are genes lying in the nonconvex part of the set frontier that escape detection. These genes could be potential biomarkers, however. In order to circumvent the said disadvantage, the authors proposed that DEA be applied successively 10 times, each time removing the genes found in a particular iteration from the set for subsequent analyses. This strategy results in 10 frontiers, as seen in Figure 3. The number of efficient frontiers is, admittedly, an arbitrary number at this point, thus further refinement is necessary in this aspect.
Figure 2  Multiple Criteria Optimization Problem solved using Data Envelopment Analysis (BCC model). The efficient solutions are identified through the use of piecewise-linear segments.
Figure 3  A case with genes characterized by two performance measures. Referring to this figure, and following the proposed method, at this point it is recommended to identify the first 10 efficient frontiers. This can be easily done by identifying the genes in the first efficient frontier through DEA, then removing them from the set and continue with a second DEA iteration.   At the end of Stage 1, the analyst is left with a set of differentially expressed genes that can be investigated to establish their role in the condition or illness under study, cancer in this case. This set of genes in the proposed method, however, will be used to determine how these are maximally correlated in Stage 2.