New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming. (English) Zbl 1490.90212
Summary: In this work, we propose a new approach called “Successive Linear Programming Algorithm (SLPA)” for finding an approximate global minimizer of general nonconvex quadratic programs. This algorithm can be initialized by any extreme point of the convex polyhedron of the feasible domain. Furthermore, we generalize the simplex algorithm for finding a local minimizer of concave quadratic programs written in standard form. We prove a new necessary and sufficient condition for local optimality, then we describe the Revised Primal Simplex Algorithm (RPSA). Finally, we propose a hybrid local-global algorithm called “SLPLEX”, which combines RPSA with SLPA for solving general concave quadratic programs. In order to compare the proposed algorithms to the branch-and-bound algorithm of CPLEX12.8 and the branch-and-cut algorithm of Quadproga, we develop an implementation with MATLAB and we present numerical experiments on 139 nonconvex quadratic test problems.
MSC:
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
nonconvex quadratic programming; concave quadratic programming; successive linear programming; simplex algorithm; extreme point; local minimizer; global minimizer; approximate global minimizer; numerical experimentsReferences:
| [1] | Absil, P-A; Tits, AL, Newton-KKT interior-point methods for indefinite quadratic programming, Comput. Optim. Appl., 36, 5-41 (2007) · Zbl 1278.90288 · doi:10.1007/s10589-006-8717-1 |
| [2] | Bentobache, M., Bibi, M.O.: Numerical methods of linear and quadratic programming: theory and algorithms. French Academic Editions, Germany (2016) (in French) |
| [3] | Bentobache, M., Telli, M., Mokhtari A.: A simplex algorithm with the smallest index rule for concave quadratic programming. In: proceedings of the Eighth International Conference on Advanced Communications and Computation, INFOCOMP 2018, Barcelona, Spain, July 22-26, pp. 88-93 (2018) |
| [4] | Bentobache, M., Telli, M., Mokhtari, A.: A sequential linear programming algorithm for continuous and mixed-integer nonconvex quadratic programming. In: Le Thi, H.A., et al. (eds.) Optimizatin of Complex Systems: Theory, Models, Algorithms and Applications 991, 26-36. Springer, Cham (2020) · Zbl 1463.90152 |
| [5] | Bertsekas, DP, Nonlinear Programming (1999), Belmont: Second Athena Scientific, Belmont · Zbl 1015.90077 |
| [6] | Chikhaoui, A.; Djebbar, B.; Belabbaci, A.; Mokhtari, A., Optimization of a quadratic function under its canonical form, Asian J. Appl. Sci., 2, 26, 499-510 (2009) · doi:10.3923/ajaps.2009.499.510 |
| [7] | Chinchuluun, A.; Pardalos, PM; Enkhbat, R., Global minimization algorithms for concave quadratic programming problems, Optimization, 54, 6, 627-639 (2005) · Zbl 1147.90385 · doi:10.1080/02331930500342534 |
| [8] | CPLEX12.8. Ilog. Inc., Armonk, NY (2017) |
| [9] | Dantzig, G.B.: Linear programming and extensions. Princeton University Press, Princeton (1963) · Zbl 0108.33103 |
| [10] | Enkhbat, R., An algorithm for maximizing a convex function over a simple set, J. Glob. Optim., 8, 379-391 (1996) · Zbl 0851.90091 · doi:10.1007/BF02403999 |
| [11] | Enkhbat, R.: On some theory, methods and algorithms for concave programming. In: Series on Computers and Operations Research, Optimization and Optimal Control 1, 79-102 (2003) · Zbl 1111.90352 |
| [12] | Enkhbat, R., Bazarsad, Y.: General quadratic programming and its applications in response surface analysis. In: Chinchuluun, A., et al. (eds.) Optimization and Optimal Control, Springer Optimization and Its Applications 39, 121-137. Springer, Cham (2010) · Zbl 1204.90073 |
| [13] | Floudas, CA; Pardalos, PM; Adjiman, C.; Esposito, WR; Gümüs, ZH; Harding, ST; Klepeis, JL; Meyer, CA; Schweiger, CA, Handbook of Test Problems in Local and Global Optimization (Nonconvex Optimization and Its Applications) (1999), Cham: Springer, Cham · Zbl 0943.90001 |
| [14] | Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. Q., 3, 95-110 (1956) · doi:10.1002/nav.3800030109 |
| [15] | Globallib : Gamsworld global optimization library. http://www.gamsworld.org/global/globallib.htm |
| [16] | Gould, NIM; Orban, D.; Toint, PL, CUTEr, a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Soft., 29, 373-394 (2003) · Zbl 1068.90526 · doi:10.1145/962437.962439 |
| [17] | Horst, R., An algorithm for nonconvex programming problems, Math. Program., 10, 1, 312-321 (1976) · Zbl 0337.90062 · doi:10.1007/BF01580678 |
| [18] | Hiriart-Urruty, JB; Ledyaev, YS, A note on the characterization of the global maxima of a (tangentially) convex function over a convex set, J. Convex Anal., 3, 55-62 (1996) · Zbl 0877.49017 |
| [19] | Ikheneche, N.: Support method for the minimization of a convex quadratic function, Master thesis, University of Bejaia (2004) (in French) |
| [20] | Le Thi, HA; Pham Dinh, T., Solving a class of linearly constrained indefinite quadratic problems by DC algorithms, J. Glob. Optim., 11, 3, 253-285 (1997) · Zbl 0905.90131 · doi:10.1023/A:1008288411710 |
| [21] | Le Thi, H.A., Pham Dinh, T., Muu, L.D.: A combined D.C. optimization-ellipsoidal branch-and-bound algorithm for solving nonconvex quadratic programming problems. J. Comb. Optim. 2(1), 9-28 (1998) · Zbl 0904.90134 |
| [22] | Le Thi, H.A., Pham Dinh, T.: A branch-and-bound method via D.C. optimization algorithm and ellipsoidal technique for box constrained nonconvex quadratic problems. J. Glob. Optim. 13, 171-206 (1998) · Zbl 0912.90233 |
| [23] | Le Thi, HA; Pham Dinh, T., A continuous approach for globally solving linearly constrained quadratic zero-one programming problems, Optimization, 50, 1-2, 93-120 (2001) · Zbl 1039.90050 · doi:10.1080/02331930108844555 |
| [24] | Le Thi, HA; Pham Dinh, T., Dc programming and dca: thirty years of developments, Math. Program., 169, 1, 5-68 (2018) · Zbl 1387.90197 · doi:10.1007/s10107-018-1235-y |
| [25] | Niu, Y.S.: Programmation dc et dca en optimisation combinatoire et optimisation polynomiale via les techniques de sdp: codes et simulations numériques. Ph.D. thesis, INSA-Rouen (2010) |
| [26] | Pardalos, PM; Rodgers, G., Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45, 2, 131-144 (1990) · Zbl 0721.65034 · doi:10.1007/BF02247879 |
| [27] | Pham Dinh, T.; Le Thi, HA; Akoa, F., Combining DCA (DC Algorithms) and interior point techniques for large-scale nonconvex quadratic programming, Optim. Methods Softw., 23, 4, 609-629 (2008) · Zbl 1151.90508 · doi:10.1080/10556780802263990 |
| [28] | Pham Dinh, T.; Nguyen Canh, N.; Le Thi, HA, An efficient combined DCA and B&B using DCSDP relaxation for globally solving binary quadratic programs, J. Glob. Optim., 48, 4, 595-632 (2010) · Zbl 1226.90060 · doi:10.1007/s10898-009-9507-y |
| [29] | Pham Dinh, T.; Le Thi, HA; Pham, VN; Niu, YS, DC programming approaches for discrete portfolio optimization under concave transaction costs, Optim. Lett., 10, 2, 1-22 (2016) · Zbl 1343.90072 · doi:10.1007/s11590-015-0931-2 |
| [30] | Ploskas, N., Samaras, N.: Linear programming using MATLAB, Springer Optimization and Its Applications 127. Springer, Cham (2017) · Zbl 1386.90003 |
| [31] | Rusakov, AI, Concave programming under simplest linear constraints, Comput. Math. Math. Phys., 43, 7, 908-917 (2003) · Zbl 1136.90443 |
| [32] | Sahni, S., Computationally related problems, SIAM J. Comput., 3, 262-279 (1974) · Zbl 0272.68040 · doi:10.1137/0203021 |
| [33] | Strekalovsky, A.S.: On global maximum search of convex function over a feasible set. J. Numer. Math. Math. Phys. 3, 349-363 (1993). (in Russian) · Zbl 0804.90106 |
| [34] | Strekalovsky, AS, Global optimality conditions for nonconvex optimization, J. Glob. Optim., 12, 4, 415-434 (1998) · Zbl 0908.90243 · doi:10.1023/A:1008277314050 |
| [35] | Strekalovsky, A.S., Kuznetsova, A.A., Yakovleva, T.V.: Global optimality conditions for nonconvex optimization. On nonconvex quadratic optimization. Sib. Zh. Vychisl. Mat. 4(2), 185-199 (2001) (in Russian) · Zbl 0997.90099 |
| [36] | Sung, YY; Rosen, JB, Global minimum test problem construction, Math. Program., 24, 1, 353-355 (1982) · Zbl 0509.90067 · doi:10.1007/BF01585116 |
| [37] | Telli, M.; Bentobache, M.; Mokhtari, A., A successive linear approximation algorithm for the global minimization of a concave quadratic program., Comput. Appl. Math., 39, 4, 272 (2020) · Zbl 1463.90152 · doi:10.1007/s40314-020-01317-1 |
| [38] | Tuy, H., Concave programming under linear constraints, Soviet Math., 5, 1437-1440 (1964) · Zbl 0132.40103 |
| [39] | Tuy, H.: Convex analysis and global optimization: Springer Optimization and Its Applications. 110, 2nd edn. Springer, Cham (2016) · Zbl 1362.90001 |
| [40] | Wang, F., A new exact algorithm for concave knapsack problems with integer variables, Int. J. Comput. Math., 96, 1, 126-134 (2019) · Zbl 1499.90189 · doi:10.1080/00207160.2017.1418505 |
| [41] | Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 382-398 (1959) · Zbl 0103.37603 · doi:10.2307/1909468 |
| [42] | Xia, W.; Vera, JC; Zuluaga, LF, Globally solving nonconvex quadratic programs via linear integer programming techniques, INFORMS J. Comput., 32, 1, 1-17 (2019) · Zbl 07284452 |
| [43] | Zamani, M., A new algorithm for concave quadratic programming, J. Glob. Optim., 75, 655-681 (2019) · Zbl 1434.90120 · doi:10.1007/s10898-019-00787-w |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
