Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver
Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver
复制标题
利用多目标线性规划求解器进行凸多面体和多面体凸函数的微积分
作者：
Daniel Ciripoi;Andreas Löhne;Benjamin Weißing
本文讨论了在凸多面体或多面体凸函数上定义的运算。给定两个凸多面体，考虑Minkowski和、交和并的闭凸包等运算。一个凸多面体的基本运算有极坐标、圆锥壳和仿射变换后的像。引入了凸多面体的p表示的概念。证明了许多多面体微积分运算可以用p表示来显式地表示。我们指出，多面体微积分的所有相关计算工作都是计算凸多面体的投影。为了计算投影，我们使用了最近的一个结果，即多目标线性规划（MOLP）等价于多面体投影问题。基于MOLP求解器bensolve，开发了Matlab和GNU Octave的多面体微积分工具箱。讨论了一些数值实验。
ABSTRACT The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.