Weighted Sum Method

The weighted sum method performs linear scalarization, combining multiple objective functions into a single aggregate objective function. For objectives (f_1(x), f_2(x), ..., f_k(x)) and non-negative weights (w_1, w_2, ..., w_k), the scalarized function is:

[ F(x) = w_1 f_1(x) + w_2 f_2(x) + ... + w_k f_k(x) ]

• The weights represent the relative importance or preference of each objective.
• This linear combination is then optimized using standard single-objective solvers.

The weight vector (w = (w_1, w_2, ..., w_k)) is the primary control mechanism. Its interpretation is crucial:

• Relative Scaling: Weights must account for differences in the scale and units of each objective. A weight of 0.5 on revenue (in millions) and 0.5 on latency (in milliseconds) is meaningless without normalization.
• Preference Direction: A higher weight directs the search to favor improvement in that specific objective.
• Convex Combination: Weights are often normalized so that (\sum_{i=1}^k w_i = 1), turning them into a convex combination that defines a search direction in the objective space.

A critical limitation is that the standard weighted sum method is guaranteed to find only Pareto optimal solutions that lie on the convex hull of the Pareto front. This has major implications:

• Works for Convex Fronts: It can effectively sample the entire Pareto front if the front is convex.
• Fails for Non-Convex Fronts: It cannot discover Pareto optimal solutions that lie in the concave regions of the front, as these points are not optimal for any linear combination of objectives.
• This makes the method unsuitable for problems with complex, non-convex trade-off surfaces without modification.

Because objectives often have incompatible units and scales, objective normalization is an essential preprocessing step before applying weights. Common techniques include:

• Min-Max Normalization: (f_i'(x) = \frac{f_i(x) - f_i^{min}}{f_i^{max} - f_i^{min}})
• Ideal-Nadir Scaling: Scaling based on the ideal point (best possible) and nadir point (worst Pareto optimal) estimates.
• Without normalization, the weight vector becomes meaningless, as a large-magnitude objective will dominate the sum regardless of its assigned weight.

For a given, fixed set of normalized weights ((w_1, w_2, ..., w_k)), solving the scalarized problem yields a single Pareto optimal solution (or a point on the convex hull). To approximate the full Pareto front, the algorithm must be run multiple times with systematically varied weight vectors.

• This is often done via a weight sweep, e.g., varying (w_1) from 0 to 1 in increments of 0.1, with (w_2 = 1 - w_1) for a two-objective problem.
• Each run produces one candidate solution, making the method computationally intensive for generating a dense approximation of the front.

The method directly bridges optimization and Multi-Criteria Decision Making (MCDM). The weight vector is a formalization of the decision-maker's preference articulation.

• A Priori Preference: Weights are set before optimization based on known priorities. The method then finds the solution that best fits that specific preference.
• Interactive Exploration: Decision-makers can adjust weights, re-solve, and observe the resulting solution, interactively exploring the trade-off space.
• It is a core component of the MOEA/D (Multi-Objective EA Based on Decomposition) framework, where multiple weight vectors define a set of scalar subproblems solved in parallel.

Scalarization is the fundamental technique of transforming a vector-valued objective function into a single scalar objective to enable the use of standard single-objective optimizers. The Weighted Sum Method is the most common linear scalarization approach.

• Core Purpose: Converts a multi-objective problem into a format solvable by gradient descent, evolutionary algorithms, or linear programming.
• Other Methods: Includes epsilon-constraint and goal programming, which handle objectives via constraints or deviation minimization.
• Limitation: Linear scalarization cannot find solutions on non-convex regions of the Pareto front.

A solution is Pareto optimal (or Pareto efficient) if no objective can be improved without degrading at least one other objective. The Weighted Sum Method finds a specific point on the Pareto front based on the chosen weights.

• Key Relation: For a convex Pareto front, any Pareto optimal solution can be obtained by the Weighted Sum Method with an appropriate weight vector.
• Decision Space vs. Objective Space: The Pareto set is the collection of optimal solutions in decision variable space; the Pareto front is its image in objective value space.
• Dominance: A solution Pareto dominates another if it is at least as good in all objectives and strictly better in at least one.

The epsilon-constraint method is an alternative scalarization technique that optimizes one primary objective while treating all others as constraints with allowable violation limits (epsilon values).

• Mechanism: For objectives f1...fm, it solves: minimize f_k(x) subject to f_i(x) ≤ ε_i for all i ≠ k.
• Advantage over Weighted Sum: Can find Pareto optimal solutions on non-convex regions of the Pareto front that the Weighted Sum Method misses.
• Practical Use: Requires the decision-maker to set meaningful epsilon (ε) bounds, which can be challenging without prior knowledge of the objective space.

A Multi-Objective Evolutionary Algorithm (MOEA) is a population-based metaheuristic designed to approximate the entire Pareto front in a single run, rather than finding a single solution like the Weighted Sum Method.

• Population Approach: Maintains a diverse set of candidate solutions that collectively represent the trade-off surface.
• Key Algorithms: NSGA-II (Non-dominated Sorting Genetic Algorithm II) and MOEA/D (Multi-Objective EA Based on Decomposition) are industry standards.
• Decomposition (MOEA/D): This variant explicitly uses scalarization techniques, including the Weighted Sum Method, to decompose the multi-objective problem into many single-objective subproblems solved cooperatively.

In multi-objective decision-making, a utility function is a scalar-valued function that maps a vector of objective values to a single measure of preference or desirability for a decision-maker. The Weighted Sum is a simple, linear utility function.

• Role: Encodes the decision-maker's preferences and trade-offs. Maximizing utility is the ultimate goal.
• Beyond Linear: Real-world preferences often require non-linear utility functions (e.g., diminishing returns, risk aversion).
• Preference Articulation: The process of defining this function or its parameters (like weights) is called preference articulation.

The ideal point and nadir point are critical reference points in the objective space used to normalize objectives and understand the range of possible trade-offs.

• Ideal Point (z)* : A vector where each component is the best achievable value for each individual objective (often utopian and unattainable).
• Nadir Point (z^nad) : A vector where each component is the worst value among the Pareto optimal solutions.
• Use in Weighted Sum: Normalizing objectives using these points (e.g., (f_i - z*_i) / (z^nad_i - z*_i)) makes the weighted sum more meaningful and weight selection less sensitive to objective scales.