Lagrangian duality and saddle points for sparse linear programming

作     者：Chen Zhao Ziyan Luo Weiyue Li Houduo Qi Naihua Xiu 

作者机构：Department of MathematicsBeijing Jiaotong UniversityBeijing100044China State Key Lab of Rail Trac Control and SafetyBeijing Jiaotong UniversityBeijing100044China School of MathematicsUniversity of SouthamptonSouthampton SO171BJUK 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2019年第62卷第10期

页      面：2015-2032页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by National Natural Science Foundation of China(Grant Nos.11431002,11771038 and 11728101) the State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University(Grant No.RCS2017ZJ001) China Scholarship Council(Grant No.201707090019) 

主　　题：sparse linear programming Lagrangian dual problem strong duality saddle point theorem optimality condition 

摘      要：The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property *** this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.