This paper works on a heuristic algorithm with determinacy for the global optimization of Continuous PieceWise Linear(CPWL) programming. The widely applied CPWL programming can be equivalently transformed into D.C. pr...This paper works on a heuristic algorithm with determinacy for the global optimization of Continuous PieceWise Linear(CPWL) programming. The widely applied CPWL programming can be equivalently transformed into D.C. programming and concave optimization over a polyhedron. Considering that the super-level sets of concave piecewise linear functions are polyhedra, we propose the Hill Tunneling via Weighted Simplex Centroid(HTWSC) algorithm, which can escape a local optimum to reach the other side of its contour surface by cutting across the super-level set. The searching path for hill tunneling is established via the weighted centroid of a constructed simplex. In the numerical experiments, different weighting methods are studied first, and the best is chosen for the proposed HTWSC algorithm. Then, the HTWSC algorithm is compared with the hill detouring method and the software CPLEX for the equivalent mixed integer programming, with results indicating its superior performance in terms of numerical efficiency and the global search capability.展开更多
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.展开更多
基金jointly supported by the National Key Basic Research and Development (973) Program of China (No. 2012CB720505)the National Natural Science Foundation of China (Nos. 61473165 and 61134012)
文摘This paper works on a heuristic algorithm with determinacy for the global optimization of Continuous PieceWise Linear(CPWL) programming. The widely applied CPWL programming can be equivalently transformed into D.C. programming and concave optimization over a polyhedron. Considering that the super-level sets of concave piecewise linear functions are polyhedra, we propose the Hill Tunneling via Weighted Simplex Centroid(HTWSC) algorithm, which can escape a local optimum to reach the other side of its contour surface by cutting across the super-level set. The searching path for hill tunneling is established via the weighted centroid of a constructed simplex. In the numerical experiments, different weighting methods are studied first, and the best is chosen for the proposed HTWSC algorithm. Then, the HTWSC algorithm is compared with the hill detouring method and the software CPLEX for the equivalent mixed integer programming, with results indicating its superior performance in terms of numerical efficiency and the global search capability.
基金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.
