In order to recover a signal from its compressive measurements, the compressed sensing theory seeks the sparsest signal that agrees with the measurements, which is actually an l;norm minimization problem. In this pape...In order to recover a signal from its compressive measurements, the compressed sensing theory seeks the sparsest signal that agrees with the measurements, which is actually an l;norm minimization problem. In this paper, we equivalently transform the l;norm minimization into a concave continuous piecewise linear programming,and propose an optimization algorithm based on a modified interior point method. Numerical experiments demonstrate that our algorithm improves the sufficient number of measurements, relaxes the restrictions of the sensing matrix to some extent, and performs robustly in the noisy scenarios.展开更多
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 programm...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.展开更多
This is a brief report on our recent work in network piecewise linear programming (NPLP),and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical n...This is a brief report on our recent work in network piecewise linear programming (NPLP),and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical network linear program generator NETGEN. The generator creates networks of the same topological structures as NETGEN, but each arc is associated with a convex piecewise linear cost. The purpose of this program is to provide a set of standard test problems which can be used to compare the performance of various algorithms for NPLP. In the second part,we introduce a network simplex method that directly solves a network piecewise linear program without reformulating it as a network linear program of higher dimension. Forty benchmark NPLP problems are solved by this method and a reformulation method. The computational results are in favor of the direct method and show that solving an NPLP problem is not much harder than solving a network linear program of the same dimension.展开更多
基金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)
文摘In order to recover a signal from its compressive measurements, the compressed sensing theory seeks the sparsest signal that agrees with the measurements, which is actually an l;norm minimization problem. In this paper, we equivalently transform the l;norm minimization into a concave continuous piecewise linear programming,and propose an optimization algorithm based on a modified interior point method. Numerical experiments demonstrate that our algorithm improves the sufficient number of measurements, relaxes the restrictions of the sensing matrix to some extent, and performs robustly in the noisy scenarios.
基金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)
文摘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.
文摘This is a brief report on our recent work in network piecewise linear programming (NPLP),and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical network linear program generator NETGEN. The generator creates networks of the same topological structures as NETGEN, but each arc is associated with a convex piecewise linear cost. The purpose of this program is to provide a set of standard test problems which can be used to compare the performance of various algorithms for NPLP. In the second part,we introduce a network simplex method that directly solves a network piecewise linear program without reformulating it as a network linear program of higher dimension. Forty benchmark NPLP problems are solved by this method and a reformulation method. The computational results are in favor of the direct method and show that solving an NPLP problem is not much harder than solving a network linear program of the same dimension.
