A discussion of objective function representation methods in global optimization

Abstract

Non-convex optimization can be found in several smart manufacturing systems. This paper presents a short review on global optimization (GO) methods. We examine decomposition techniques and classify GO problems on the basis of objective function representation and decomposition techniques. We then explain Kolmogorov’s superposition and its application in GO. Finally, we conclude the paper by exploring the importance of objective function representation in integrated artificial intelligence, optimization, and decision support systems in smart manufacturing and Industry 4.0.

Keywords

global optimization / decomposition techniques / multi-objective / DC programming / Kolmogorov’s superposition / space-filling curve / smart manufacturing and Industry 4.0

References

[1] Alperin H, Nowak I (2005). Lagrangian smoothing heuristics for max-cut. Journal of Heuristics, 11(5–6): 447–463

[2] Arnol’d V I (1959). On the representation of continuous functions of three variables by superpositions of continuous functions of two variables. Matematicheskii Sbornik, 90(1): 3–74

[3] Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (2012). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties.Berlin: Springer Science & Business Media

[4] Babayev D A, Bell G I (2001). An optimization problem with a separable non-convex objective function and a linear constraint. Journal of Heuristics, 7(2): 169–184

[5] Becker R W, Lago G (1970). A global optimization algorithm. In: Proceedings of the 8th Allerton Conference on Circuits and Systems Theory. 3–12

[6] Bertsekas D P (1999). Nonlinear Programming.Belmont: Athena Scientific

[7] Bliek C (1998). Coconut deliverable d1-algorithms for solving nonlinear and constrained optimization problems. The COCONUT Project

[8] Boddy M S, Johnson D P (2002). A new method for the global solution of large systems of continuous constraints. In: Bliek C, Jermann C, Neumaier A, eds. International Workshop on Global Optimization and Constraint Satisfaction.Berlin: Springer

[9] Boender C G E, Romeijn H E (1995). Stochastic methods. In: Pardalos P M, Romeijin H E, eds. Handbook of global optimization. Berlin: Springer

[10] Bomze I M, Csendes T, Horst R, Pardalos P M (1997). Developments in Global Optimization.Berlin: Springer Science & Business Media

[11] Boyd S, Xiao L, Mutapcic A, Mattingley J (2007). Notes on Decomposition Methods.Stanford: Stanford University

[12] Burkard R E, Kocher M, Rüdolf R (1997). Rounding strategies for mixed integer programs arising from chemical production planning. Yugoslav Journal of Operations Research

[13] Chiang M, Low S H, Calderbank A R, Doyle J C (2007). Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1): 255–312

[14] Chinchuluun A, Pardalos P M (2007). A survey of recent developments in multiobjective optimization. Annals of Operations Research, 154(1): 29–50

[15] Dantzig G B, Wolfe P (1960). Decomposition principle for linear programs. Operations Research, 8(1): 101–111

[16] Dixon L C W, Szegö G P (1974). Towards global optimisation. In: Proceedings of a workshop at the university of Cagliari, Italy

[17] Du D Z, Pardalos P M (2013). Handbook of Combinatorial Optimization: Supplement, Vol. 1.Berlin: Springer Science & Business Media

[18] Duran M A, Grossmann I E (1986). An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming, 36(3): 307–339

[19] Ehrgott M, Gandibleux X (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum, 22(4): 425–460

[20] Fisher M L (1980). Worst-case analysis of heuristic algorithms. Management Science, 26(1): 1–17

[21] Fletcher R, Leyffer S (1994). Solving mixed integer nonlinear programs by outer approximation. Mathematical Programming, 66(1–3): 327–349

[22] Floudas C, Aggarwal A, Ciric A (1989). Global optimum search for nonconvex nlp and minlp problems. Computers & Chemical Engineering, 13(10): 1117–1132

[23] Floudas C A (2013). Deterministic Global Optimization: Theory, Methods and Applications, Vol. 37.Berlin: Springer Science & Business Media

[24] Floudas C A, Pardalos P M (2013). State of the Art in Global Optimization: Computational Methods and Applications, Vol. 7.Berlin: Springer Science & Business Media

[25] Floudas C A, Pardalos P M (2014). Recent Advances in Global Optimization.Princeton: Princeton University Press

[26] Forrest S (1993). Genetic algorithms: principles of natural selection applied to computation. Science, 261(5123): 872–878

[27] Geoffrion A M (1972). Generalized benders decomposition. Journal of Optimization Theory and Applications, 10(4): 237–260

[28] Glover F, Laguna M (1997). Tabu Search.Berlin: Springer

[29] Goemans M X, Williamson D P (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the Association for Computing Machinery, 42(6): 1115–1145 (JACM)

[30] Goertzel B (1999). Global optimization with space-filling curves. Applied Mathematics Letters, 12(8): 133–135

[31] Grossmann I E (2002). Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3(3): 227–252

[32] Grossmann I E, Kravanja Z (1997). Mixed-integer nonlinear programming: A survey of algorithms and applications. In: Biegler L T, Colleman T F, Conn A R, Samtosa F N, eds. Large-scale Optimization with Applications. Berlin: Springer

[33] Gu F Q (2016). Many objective optimization: Objective reduction and weight design. Dissertation for the Doctoral Degree.Hongkong: HKBU

[34] Henrion D, Lasserre J B (2002). Solving global optimization problems over polynomials with gloptipoly 2.1. In: Proceedings of International Workshop on Global Optimization and Constraint Satisfaction.Berlin: Springe

[35] Hirsch M J, Meneses C, Pardalos P M, Resende M G (2007). Global optimization by continuous grasp. Optimization Letters, 1(2): 201–212

[36] Hochbaum D, Jansen K, Rolim J D, Sinclair A (1999). Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: In: Proceedings of Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems.Berlin: Springer Science & Business Media

[37] Holmberg K (1990). On the convergence of cross decomposition. Mathematical Programming, 47(1–3): 269–296

[38] Holmberg K, Ling J (1997). A lagrangean heuristic for the facility location problem with staircase costs. European Journal of Operational Research, 97(1): 63–74

[39] Hooker J (2011). Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Vol. 2.Hoboken: John Wiley & Sons

[40] Horst R, Pardalos P M (2013). Handbook of Global Optimization, Vol. 2.Berlin: Springer Science & Business Media

[41] Horst R, Pardalos P M, Van Thoai N (2000). Introduction to Global Optimization.Berlin: Springer Science & Business Media

[42] Horst R, Tuy H (2013). Global Optimization: Deterministic Approaches.Berlin: Springer Science & Business Media

[43] Kelly F P, Maulloo A K, Tan D K (1998). Rate control for communication networks: Shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49(3): 237–252

[44] Kesavan P, Allgor R J, Gatzke E P, Barton P I (2004). Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. Mathematical Programming, 100(3): 517–535

[45] Khakifirooz M, Chien C-F, Pardalos F M, Panos M (2018). Management suggestions on semiconductor manufacturing engineering: An operations research and data science perspective.Berlin: Springer

[46] Khakifirooz M, Pardalos P M, Fathi M, Power D J (2018). Decision support for smart manufacturing. Encyclopedia of IST, 5th Edition, IGI Global Book

[47] Kirkpatrick S, Gelatt C D Jr, Vecchi M P (1983). Optimization by simulated annealing. Science, 220(4598): 671–680

[48] Kobayashi Y (2014). The complexity of maximizing the difference of two matroid rank functions, METR2014–42. University of Tokyo

[49] Kocis G R, Grossmann I E (1987). Relaxation strategy for the structural optimization of process flow sheets. Industrial & Engineering Chemistry Research, 26(9): 1869–1880

[50] Kojima M, Kim S, Waki H (2003). A general framework for convex relaxation of polynomial optimization problems over cones. Journal of the Operations Research Society of Japan, 46(2): 125–144

[51] Kolmogorov A (1956). On the representation of continuous functions of several variables as superpositions of functions of smaller number of variables.Berlin: Springer

[52] Lasserre J B (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3): 796–817

[53] Lera D, Sergeyev Y D (2010). Lipschitz and Hölder global optimization using space-filling curves. Applied Numerical Mathematics, 60(1–2): 115–129

[54] Li D, Sun X, Wang J, McKinnon K I (2009). Convergent lagrangian and domain cut method for nonlinear knapsack problems. Computational Optimization and Applications, 42(1): 67–104

[55] Locatelli M (2002). Simulated annealing algorithms for continuous global optimization. In: Horst R, Pardalos P M, eds. Handbook of global optimization.Berlin: Springer

[56] Maehara T, Marumo N, Murota K (2018). Continuous relaxation for discrete DC programming. Mathematical Programming, 169(1): 199–219

[57] Mane S U, Rao M N (2017). Many-objective optimization: Problems and evolutionary algorithms–A short review. International Journal of Applied Engineering Research, 12(20): 9774–9793

[58] Marques M, Agostinho C, Zacharewicz G, Jardim-Goncalves R (2017). Decentralized decision support for intelligent manufacturing in industry 4.0. Journal of Ambient Intelligence and Smart Environments, 9(3): 299–313

[59] Mart R, Panos P, Resende M (2018). Handbook of Heuristics.Berlin: Springer

[60] Mawengkang H, Murtagh B (1986). Solving nonlinear integer programs with large-scale optimization software. Annals of Operations Research, 5(2): 425–437

[61] McCormick G P (1974). A Mini-manual for Use of the Sumt Computer Program and the Factorable Programming Language.Stanford: Stanford University

[62] McCormick G P (1976). Computability of global solutions to factorable nonconvex programs: Part iconvex underestimating problems. Mathematical Programming, 10(1): 147–175

[63] McCormick G P (1983). Nonlinear Programming: Theory, Algorithms, and Applications.New York: Wiley

[64] Metropolis N, Rosenbluth A W, Rosenbluth M N, Teller A H, Teller E (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6): 1087–1092

[65] Miettinen K (1999). Nonlinear Multiobjective Optimization. International Series in Operations Research and Management Science.Berlin: Springer

[66] Migdalas A, Pardalos P M, Värbrand P (2013). Multilevel Optimization: Algorithms and Applications, Vol. 20.Berlin: Springer Science & Business Media

[67] Mockus J (2012). Bayesian Approach to Global Optimization: Theory and Applications, Vol. 37.Berlin: Springer Science & Business Media

[68] Moré J J, Wu Z (1997). Global continuation for distance geometry problems. SIAM Journal on Optimization, 7(3): 814–836

[69] Mylander W C, Holmes R L, McCormick G P (1971). A guide to sumt-version 4: The computer program implementing the sequential unconstrained minimization technique for nonlinear programming (Technical Report RAC-P-63).Mclean: Research Analysis Corporation

[70] Neumaier A (2004). Complete search in continuous global optimization and constraint satisfaction. Acta Numerica, 13: 271–369

[71] Nowak I (2005). Relaxation and decomposition methods for mixed integer nonlinear programming, Vol. 152.Berlin: Springer Science & Business Media

[72] Nowak I, Breitfeld N, Hendrix E M, Njacheun-Njanzoua G (2018). Decomposition-based inner-and outerrefinement algorithms for global optimization. Journal of Global Optimization, (4–5): 1–17

[73] Nowak M P, Römisch W (2000). Stochastic lagrangian relaxation applied to power scheduling in a hydrothermal system under uncertainty. Annals of Operations Research, 100(1–4): 251–272

[74] Padberg M, Rinaldi G (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1): 60–100

[75] Palacios-Gomez F, Lasdon L, Engquist M (1982). Nonlinear optimization by successive linear programming. Management Science, 28(10): 1106–1120

[76] Palomar D P, Chiang M (2006). A tutorial on decomposition methods for network utility maximization. IEEE Journal on Selected Areas in Communications, 24(8): 1439–1451

[77] Pardalos P M (1991). Global optimization algorithms for linearly constrained indefinite quadratic problems. Computers & Mathematics with Applications (Oxford, England), 21(6–7): 87–97

[78] Pardalos P M, Migdalas A, Pitsoulis L (2008). Pareto optimality, game theory and equilibria, Vol. 17.Berlin: Springer Science & Business Media

[79] Pardalos P M, Rosen J B (1986). Methods for global concave minimization: A bibliographic survey. SIAM Review, 28(3): 367–379

[80] Pardalos P M, Rosen J B (1987). Constrained Global Optimization: Algorithms and Applications.New York: Springer-Verlag

[81] Pardalos P M, Wolkowicz H (1998). Topics in semidefinite and interior-point methods. American Mathematical Society

[82] Pardalos P M, Zilinskas A, Zilinskas J (2017). Non-convex multi-objective optimization, Vol. 123.Berlin: Springer

[83] Paules G E I V IV, Floudas C A (1989). Apros: Algorithmic development methodology for discrete-continuous optimization problems. Operations Research, 37(6): 902–915

[84] Pintér J D (1996). Global Optimization in Action.Dordrecht: Kluwer Academic Publishers

[85] Rahmaniani R, Crainic T G, Gendreau M, Rei W (2017). The benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3): 801–817

[86] Resende M G C, Ribeiro C C (2003). Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G, eds. Hand Book of Metaheuristics.Dordrecht: Kluwer Academic Publishers

[87] Rockafellar R T (2016). Problem decomposition in block-separable convex optimization: Ideas old and new. In: Proceedings of the 5th Asian Conference on Nonlinear Analysis and Optimization, Niigata, Japan

[88] Sahinidis N V (1996). Baron: A general purpose global optimization software package. Journal of Global Optimization, 8(2): 201–205

[89] Schelstraete S, Schepens W, Verschelde H (1999). Energy minimization by smoothing techniques: A survey.Molecular Dynamics: from Classical to Quantum Methods

[90] Schichl H (2010). Mathematical Modeling and Global Optimization.Cambridge: Cambridge University Press

[91] Sellmann M, Fahle T (2003). Constraint programming based lagrangian relaxation for the automatic recording problem. Annals of Operations Research, 118(1–4): 17–33

[92] Sergeyev Y D, Strongin R G, Lera D (2013). Introduction to Global Optimization Exploiting Space-Filling Curves.Berlin: Springer Science & Business Media

[93] Smith E M, Pantelides C C (1996). Global optimisation of general process models. In: Grossmann I E, eds. Global Optimization in Engineering Design.Berlin: Springer

[94] Smith E M, Pantelides C C (1999). A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex minlps. Computers & Chemical Engineering, 23(4–5): 457–478

[95] Sprecher D (2013). Kolmogorov superpositions: A new computational algorithm. In: Igelnik B, eds. Efficiency and Scalability Methods for Computational Intellect.New York: IGI Global

[96] Sprecher D (2014). On computational algorithms for real-valued continuous functions of several variables. Neural Networks, 59: 16–22

[97] Sprecher D A, Draghici S (2002). Space-filling curves and Kolmogorov superposition-based neural networks. Neural Networks, 15(1): 57–67

[98] Strongin R, Sergeyev Y D (2000). Global Optimization with Non-Convex Constraints.Dordrecht: Kluwer Academic Publishers

[99] Svanberg K (2002). A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM Journal on Optimization, 12(2): 555–573

[100] Tawarmalani M, Sahinidis N V (2002). Convexification and Global Optimization in Continuous and Mixedinteger Nonlinear Programming: Theory, Algorithms, Software, and Applications, Vol. 65.Berlin: Springer Science & Business Media

[101] Tikhomirov V (1991). On the representation of continuous functions of several variables as superpositions of continuous functions of one variable and addition. In: Kolmogorov A N, Shiryaeu A, eds. Selected Works of AN Kolmogorov.Berlin: Springer

[102] Torn A, Zilinskas A (1989). Global Optimization.New York: Springer-Verlag

[103] Trivedi A, Srinivasan D, Sanyal K, Ghosh A (2017). A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Transactions on Evolutionary Computation, 21(3): 440–462

[104] Türkay M, Grossmann I E (1996). Logic-based minlp algorithms for the optimal synthesis of process networks. Computers & Chemical Engineering, 20(8): 959–978

[105] Vaidyanathan R, El-Halwagi M (1996). Global optimization of nonconvex minlps by interval analysis. In: Grossmann I E, eds. Global Optimization in Engineering Design.Berlin: Springer

[106] Van Hentenryck P, Michel L, Deville Y (1997). Numerica: A Modeling Language for Global Optimization.Boston: MIT Press

[107] Vazirani V V (2013). Approximation Algorithms.Berlin: Springer Science & Business Media

[108] Vecchietti A, Grossmann I E (1999). Logmip: A disjunctive 0–1 non-linear optimizer for process system models. Computers & Chemical Engineering, 23(4–5): 555–565

[109] Viswanathan J, Grossmann I E (1990). A combined penalty function and outer-approximation method for minlp optimization. Computers & Chemical Engineering, 14(7): 769–782

[110] Westerlund T, Lundqvist K (2001). Alpha-ECP, version 5.01: An interactive MINLP-solver based on the extended cutting plane method.

[111] Westerlund T, Pettersson F (1995). An extended cutting plane method for solving convex minlp problems. Computers & Chemical Engineering, 19: 131–136

[112] Westerlund T, Pettersson F, Grossmann I E (1994). Optimization of pump configurations as a minlp problem. Computers & Chemical Engineering, 18(9): 845–858

[113] Wu C, Wang Y, Lu Z, Pardalos P M, Xu D, Zhang Z, Du D Z (2018). Solving the degree-concentrated fault-tolerant spanning subgraph problem by dc programming. Mathematical Programming, 169(1): 255–275

[114] Zamora J M, Grossmann I E (1998a). A global minlp optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Computers & Chemical Engineering, 22(3): 367–384

[115] Zamora J M, Grossmann I E (1998b). Continuous global optimization of structured process systems models. Computers & Chemical Engineering, 22(12): 1749–1770

[116] Zhang H, Wang S (2006). Global optimization of separable objective functions on convex polyhedra via piecewise-linear approximation. Journal of Computational and Applied Mathematics, 197(1): 212–217

[117] Zheng Q P, Wang J, Pardalos P M, Guan Y (2013). A decomposition approach to the two-stage stochastic unit commitment problem. Annals of Operations Research, 210(1): 387–410

[118] Zwick U (1999). Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceedings of the 31st annual ACM symposium on Theory of computing, ACM. 679–687

Acknowledgments

Professor Pardalos’ research is partially supported by the Paul and Heidi Brown Preeminent Professorship at ISE, University of Florida. Dr. Mahdi Fathi would like to thank Prof. Murray Brown and Mrs. Helen Brown for their encouragement and support during this research.

RIGHTS & PERMISSIONS

2018 The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)