Continuous piecewise linear programming via concave optimization and genetic algorithm

This paper describes continuous piecewise linear (CPWL) programming where the objective and constraints are in the form of hinging hyperplane (HH). And HH has received wide attention due to its simplicity and good performance in system identification. When solving a CPWL programming problem, some excellent features inspire us to come up with more efficient algorithms: the two distinguished states of a hinge function reminds us of application of genetic algorithm, while the piecewise linearity and concavity of the problem of minimization of HH naturally lead to the usage of well developed methods for concave programming, such as the cutting plane method. In order to find the global minima, we propose an improved genetic algorithm (GA) incorporating the cutting plane method. The main improvement lies in three aspects. First, it utilizes binary strings that derive local minima as chromosomes, with the proposed local minima locating method. Second, a stopping criterion has been established to ensure the global optimality of GA, with the structure information provided by γ extension of local minima. And third, genetic operations have also been revised to enhance the performance of the algorithm, which is assessed by the computational experiments.