Objective Variation Simplex Algorithm for Continuous Piecewise Linear Programming

作     者：Yu Bai Zhiming Xu Xiangming Xi Shuning Wang 

作者机构：Department of AutomationTsinghua National Laboratory for Information Science and Technology(TNList)Tsinghua UniversityBeijing100084China Faculty of College of ScienceAir Force Engineering UniversityXi'an 710051 Department of AutomationTsinghua UniversityBeijing 100084China 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2017年第22卷第1期

页      面：73-82页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China (Nos. 61473165 and 61134012) the National Key Basic Research and Development (973) Program of China (No. 2012CB720505) 

主　　题：local optimization continuous piecewise linear programming modified simplex algorithm 

摘      要：This paper works on a modified simplex algorithm for the local optimization of Continuous Piece Wise Linear（CPWL） programming with generalization of hinging hyperplane objective and linear constraints. CPWL programming is popular since it can be equivalently transformed into difference of convex functions programming or concave optimization. Inspired by the concavity of the concave CPWL functions, we propose an Objective Variation Simplex Algorithm（OVSA）, which is able to find a local optimum in a reasonable time. Computational results are presented for further insights into the performance of the OVSA compared with two other algorithms on random test problems.