Multiple Objective Optimization and Implications for Single Objective Optimization
Multiple Objective Optimization and Implications for Single Objective Optimization
复制标题
多目标优化以及对单目标优化的影响
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jochen Gorski
中科院分区：
文献类型：
--
作者：
Jochen Gorski
做出正确的决定是日常生活中的一个重要方面。如果必须仅根据一个标准作出决定，则通常很容易找到问题的令人满意的解决方案。然而，只有在极少数情况下，重要的决定受到单一标准的影响。通常需要考虑几个独立和相互冲突的方面。基于这些不同的标准，人们面临的问题是在许多可能的决策中找到“最佳”的选择。这个想法导致了多目标优化的概念，其中可行解的最优性a是基于帕累托概念定义的。更详细地说，这样一个问题的解决方案被称为有效的，当不存在任何其他的解决方案，是一样好的给定的一个在所有考虑的标准，并严格优于至少一个标准。
虽然传统上，从单目标优化的方法来确定一个给定的多目标问题的有效解决方案，在这项工作中采取相反的方法。更详细地，它讨论了如何从多目标优化的思想可以用来解决单目标问题，主要集中在两个不同的方面。一方面，从多目标优化的解决方案的概念被用来直接获得组合优化的背景下，单目标问题的最优解。另一方面，现有的单目标问题的解决方案的概念的改进版本，利用所考虑的单目标问题的多目标描述引起的额外信息。在这方面，从双凸优化问题进行了进一步详细讨论。
除了这个主题的几个相关方面，特别是从（多目标）组合优化领域进行了讨论。例如，研究了组合问题如最短路、指派或背包问题的有效集的连通性。从理论的角度来看，有效解的连通性是一个强大的属性，因为它允许使用简单的邻域搜索技术来构建完整的有效集。它表明，在这项工作中，有效的集合是非连接的许多类的组合问题，但存在特殊版本的拟阵和背包问题，满足这一属性。
从组合问题的结果与瓶颈目标的一种新的目标，所谓的k-最大目标的介绍，推广了瓶颈函数的概念。给定一个k-max优化问题，并不关心可行解的最大成本系数，而是旨在最小化这些系数中的第k个最大值。基于一般算法解决多目标组合问题的瓶颈和k-最大目标，它示出了如何这些方法可以用来解决约束单目标问题，以及涉及这些目标的代数和问题。更详细地，最小偏差问题，平衡优化问题，以及k-和优化问题和这些问题的广义版本的解决方案。
除了这些组合优化的主题，连续和混合整数优化问题的双凸优化领域的研究。在这种情况下，一个优化问题被称为双凸，如果它的变量集可以被划分成两个不相交的块，使得所得的两个子问题相对于一个块是凸的，如果另一个块被假设为固定的。众所周知，双凸问题的局部最优解可以通过交替求解两个诱导凸子问题来找到。在这项工作中，从多目标优化的想法被用来开发这种解决方案的方法的增强版本，考虑到额外的下降信息包含在块中的固定变量作为第二个标准，在两个不同的子问题。除其他外，这种增强的方法的几个变种，并通过详细的数值测试所提出的算法的位置理论的双凸优化问题的例子相比，原来的搜索策略。
Taking the right decisions is one of the main aspects in everyday life. If a decision has to be made with respect to only a single criterion, it is often quite simple to find a satisfactory solution for the problem. However, only in rare cases important decisions are influenced by a single criterion. Often several independent and conflicting aspects have to be taken into account. Based on these different criteria, one is faced with the problem to find the "best" alternative among many possible decisions. This idea leads to the concept of multiple objective optimization, where optimality a of feasible solution is defined based on the Pareto-concept. In more detail, a solution of such a problem is called efficient, when there does not exist any other solution that is as good as the given one in all considered criteria and strictly better in at least one criterion.
While traditionally, methods from single objective optimization are used to determine efficient solutions of a given multiple objective problem, the reverse approach is taken in this work. In more detail, it is discussed how ideas from multiple objective optimization can be used to solve single objective problems, mainly focusing on two different aspects. On the one hand, solution concepts from multiple objective optimization are used to directly derive optimal solutions for single objective problems in the context of combinatorial optimization. On the other hand, improved versions of existing solution concepts for single objective problems are presented that exploit additional information induced by a multiple objective description of the considered single objective problem. In this context, problems from biconvex optimization are discussed in further detail.
In addition to this main topic several related aspects, especially from the field of (multiple objective) combinatorial optimization are discussed. For example, the connectedness of the efficient set for combinatorial problems like the shortest-path, the assignment or the knapsack problem is investigated. From a theoretical point of view the connectedness of efficient solutions is a powerful property since it allows the construction of the complete efficient set using simple neighborhood search techniques. It is shown in this work that the efficient set is non-connected for many classes of combinatorial problems but that there exist special versions of matroid and knapsack problems that satisfy this property.
Starting from results for combinatorial problems with bottleneck objectives a new kind of objective, the so-called k-max objective is introduced that generalizes the concept of a bottleneck function. Given a k-max optimization problem, not the largest cost coefficient of a feasible solution is of interest, but it is aimed to minimize the k-th largest among these coefficients. Based on general algorithms for solving multiple objective combinatorial problems with bottleneck and k-max objectives it is shown how these approaches can be used to solve constrained single objective problems as well as algebraic sum problems involving such objectives. In more detail, solution approaches for the minimum deviation problem, the balanced optimization problem as well as the k-sum optimization problem and generalized versions of these problems are presented.
Besides these topics from combinatorial optimization, continuous and mixed-integer optimization problems from the field of biconvex optimization are investigated. In this context, an optimization problem is called biconvex if its set of variables can be partitioned into two disjoint blocks such that the resulting two subproblems are convex with respect to one block if the other block is assumed to be fixed. It is well-known that local optimal solutions for biconvex problems can be found by alternately solving the two induced convex subproblems. In this work, ideas from multiple objective optimization are used to develop enhanced versions of this solution approach taking into account additional descent information contained in the block of fixed variables as a second criterion in the two different subproblems. Amongst others, several variants of this enhanced approach are presented and compared to the original search strategy by means of detailed numerical tests of the proposed algorithms at the example of a biconvex optimization problem from location theory.