Determining The Optimal Weights In Multiple Objective Function Optimization

Michael A. Gennert, Alan L. Yuille

Abstract

In computer vision and signal processing, reconstruction problems often involve balancing multiple competing objective functions. Determining the appropriate weights for these functions is a non-trivial task, typically requiring manual tuning or prior knowledge of noise levels. This paper introduces the Min-Max Principle, a theoretical framework for automatically determining optimal weights. By maximizing the minimum possible cost, this principle provides a mathematically rigorous way to balance objectives, ensuring that no single constraint is ignored.

Introduction: The Weight Selection Problem

Many problems in image reconstruction and computer vision are "ill-posed," meaning they lack a unique solution without additional constraints. To address this, researchers employ regularization, combining multiple objective functions—such as a data fidelity term and a smoothness term—into a single total cost function.

The central challenge lies in selecting the weights ($\lambda$) for these terms. If a weight is too low, the corresponding constraint is effectively ignored; if too high, it may amplify noise or over-smooth the result. Traditionally, these weights are chosen through trial and error or based on known Signal-to-Noise Ratios (SNR). This paper proposes a method to automate this selection without requiring a priori knowledge of the data's noise levels.

The Min-Max Principle: A Theoretical Framework

The authors propose treating weight selection as an optimization problem in its own right. They define a total cost function $e(\lambda, z)$ as a weighted sum of individual objectives $y_i(z)$. For any fixed set of weights $\lambda$, an "inner" optimization is performed to find the state $z$ that minimizes the cost, yielding the function $e^*(\lambda)$.

Figure 1: The optimized cost function $e^*(\lambda)$ as a function of the weight $\lambda$. The concavity of the function ensures a unique maximum at $\lambda^*$, representing the optimal weight balance.

A key insight of the paper is the proof that $e^*(\lambda)$ is a concave function, regardless of whether the underlying objective functions $y_i$ are convex. As shown in Figure 1, this concavity guarantees the existence of a global maximum. The Min-Max Principle suggests that the "optimal" weight $\lambda^*$ is the one that maximizes this minimum cost $e^*(\lambda)$.

Mathematical Properties and Constraints

To prevent weights from growing indefinitely, the authors analyze two types of constraints:

  1. Linear Constraint: The weights must sum to one ($\sum \lambda_i = 1$).
  2. Spherical Constraint: The sum of the squares of the weights must be one ($|\lambda| = 1$).

Under the linear constraint, the Min-Max Principle yields a "fairness" result: at the optimum, all objective functions contribute equally to the final cost ($y_1 = y_2 = \dots = y_n$). In the spherical case, the objective values at the optimum are proportional to their respective weights ($y_i = e^* \lambda_i$). These results provide a clear mathematical interpretation of what "optimal balance" means in a multi-objective context.

Implementation and Computational Considerations

Finding the optimal $\lambda$ requires solving the inner optimization problem multiple times. The authors suggest using efficient search techniques, such as the Fibonacci search, to navigate the concave surface of $e^*(\lambda)$. To mitigate the computational burden, they propose using "warm starts"—using the solution $z$ from a previous weight iteration as the starting point for the next—which significantly accelerates convergence.

Conclusion

The Min-Max Principle offers a robust, automated alternative to manual weight tuning in multi-objective optimization. By leveraging the universal concavity of the optimized cost function, it provides a principled way to avoid degenerate solutions where constraints are ignored. While the paper is primarily theoretical, its derivations for linear and spherical constraints offer a foundation for more efficient and objective-driven signal reconstruction in computer vision.

Summary updated

Abstract

An important problem in computer vision is the determination of weights for multiple objective function optimization. This problem arises naturally in many reconstruction problems, where one wishes to reconstruct a function belonging to a constrained class of signals based upon noisy observed data. A common approach is to combine the objective functions into a single total cxt function. The problem then is to determine appropriate weights for the objective functions. In this paper we propose techniques for automatically determining the weights, and discuss their properties. The Min-Max Principle, which avoids the problems of extremely low or high weights, is introduced. ExpresEions are derived relating the optimal weights, objective function values, and total cost.
BibTeX
@inproceedings{gennert1988determining,
  author = {Michael A. Gennert and Alan L. Yuille},
  title = {{Determining The Optimal Weights In Multiple Objective Function Optimization}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {1988},
  url = {https://openreview.net/forum?id=HyZzqgMdWH},
}
Figure