修正多面体法在无形状约束效用提取及鲁棒优化保守性降低中的应用
Modified Polyhedral Method for Elicitation of Shape-Free Utility and Conservatism Reduction in Robust Optimization
摘要 Abstract
本文提出了一种修正的多面体方法,用于提取决策者(DM)的非线性单变量效用函数,该方法不依赖于效用函数形状结构、Lipschitz模量以及拐点的显式信息。该方法受Toubia等人(2004年)提出的线性多变量效用提取方法的启发,并需克服两个主要困难才能取得成功。首先,我们利用连续分段线性函数(PLF)逼近非线性效用,并通过线性片段增量向量表示PLF。随后,非线性效用的提取对应于缩小增量向量的多面体可行集。其次,通过自适应生成新的查询(即对彩票进行成对比较),构造连续的超平面切割以减小多面体的规模,其中彩票参数通过求解一些优化问题获得。在此过程中,由于PLF近似误差可能导致切割超平面的方向误差。为解决这一问题,我们通过将新彩票的支持点添加到PLF的断点集中开发了一种策略。作为应用,我们将所有查询响应用于构建效用函数的模糊集合,允许基于最差情况下的效用做出决策,并在具有适当保守性减少方案的偏好鲁棒优化问题中应用修正的多面体方法。初步数值测试结果表明,所提出的方法表现良好。
In this paper, we propose a modified polyhedral method to elicit a decision maker's (DM's) nonlinear univariate utility function, which does not rely on explicit information about the shape structure, Lipschitz modulus, and the inflection point of the utility. The method is inspired by Toubia et al. (2004) for elicitation of the linear multi-variate utility and the success of the modification needs to overcome two main difficulties. First, we use the continuous piecewise linear function (PLF) to approximate the nonlinear utility and represent the PLF in terms of the vector of increments of linear pieces. Subsequently, elicitation of the nonlinear utility corresponds to reducing the polyhedral feasible set of the vectors of increments. Second, we reduce the size of the polyhedron by successive hyperplane cuts constructed by adaptively generating new queries (pairwise comparison lotteries) where the parameters of the lotteries are obtained by solving some optimization problems. In this reduction procedure, direction error of the cut hyperplane may occur due to the PLF approximation error. To tackle the issue, we develop a strategy by adding the support points of new lotteries to the set of breakpoints of the PLF. As an application, we use all the responses to the queries to construct an ambiguity set of utility functions which allows one to make decisions based on the worst-case utility and apply the modified polyhedral method in a preference robust optimization problem with proper conservatism reduction scheme. The preliminary numerical test results show that the proposed methods work very well.