Date of Award
8-2025
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
School of Mathematical and Statistical Sciences
Committee Chair/Advisor
Margaret Wiecek
Committee Member
Cheng Guo
Committee Member
Whitney Huang
Committee Member
Cameron Turner
Abstract
Online optimization (OO) is an iterative process of decision making under uncertainty. At every step, a decision is made before the outcome of this decision is known. For the online optimization model, the objective function is unknown at the time the decision is being made. It is very likely that the taken decision is not optimal, so the decision maker incurs a loss, called regret, in every iteration. The goal of the online optimization algorithm is to compute a decision at every step so that the overall regret cost is minimized. In particular, the average regret produced by an ideal online optimization algorithm should approach zero as the process continues for an infinite number of iterations. This indicates that the algorithm is learning
In a single-objective setting, the concept of regret and an online optimization algorithm are first proposed by Zinkevich (2003). Interest in OO has grown as learning algorithms have become more prominent and resulted in extensive studies for single-objective optimization problems. However, very few have studied online multiobjective optimization (OMO). In OMO, solutions are computed before the objective functions are revealed. As a result, these solutions are not Pareto for the associated offline multiobjective problem and incur a cost, measured by regret.
First, the online multiobjective problem is scalarized using the Weighted-Sum Method (Geoffrion, 1968) and results from online single-objective optimization for scalar regret are applied to these problems. Numerical results are included for various biobjective problems.
A new concept of set-based regret (SBR) for OMO, that generalizes the scalar regret to a multiobjective case, is introduced next. This SBR recognizes that a set of efficient (nondominated, Pareto-optimal) solutions rather than a single optimal solution is inherent to multiobjective optimization problems. The SBR is defined as the region between two sets associated with OMO: the online accumulated outcome set, that is computed for all online decisions taken at every iteration, and the offline Pareto set, that is computed after all objective functions become known. The proposed definition is not specific enough to be used in computation, so we utilize multiobjective performance indicators as means of computing the SBR. We design algorithms that minimize the performance indicator at every iteration and make the average SBR go to zero. Numerical results and comparisons are provided for these set-based algorithms. These numerical results feature examples of problems where the set-based algorithms have smaller regret than scalar regret counterparts.
Lastly, the newly designed OMO techniques are applied to an engineering design problem for an autonomous vehicle. The vehicle traverses an unknown path and must decide on its acceleration before the next segment of path is revealed. A biobjective model is derived that minimizes the elapsed time of the vehicle and minimizes the energy lost by the vehicle on each segment. Numerical results are included for the single-objective problem that minimizes the elapsed time. These results highlight that online optimization results in (i) better traversal times than choosing a fixed, constant acceleration for the vehicle over the entire path; (ii) traversal times that are not significantly worse in comparison to the times achieved with non-autonomous driving.
Recommended Citation
Joyce, Kristen, "Online Multiobjective Optimization" (2025). All Dissertations. 4056.
https://open.clemson.edu/all_dissertations/4056