A discussion of objective function representation methods in global optimization

doi:10.15302/J-FEM-2018044

Front. Eng

2018, Vol. 5

Issue (4) : 515-523 https://doi.org/10.15302/J-FEM-2018044

RESEARCH ARTICLE

A discussion of objective function representation methods in global optimization

Panos M. PARDALOS(

), Mahdi FATHI

Department of Industrial Engineering and Systems Engineering, University of Florida, Gainesville, FL 116595, USA

Download: PDF(229 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Panos M. PARDALOS

Just Accepted Date: 28 August 2018 Online First Date: 09 November 2018 Issue Date: 29 November 2018

Cite this article:

Panos M. PARDALOS,Mahdi FATHI. A discussion of objective function representation methods in global optimization[J]. Front. Eng, 2018, 5(4): 515-523.

URL:

https://academic.hep.com.cn/fem/EN/10.15302/J-FEM-2018044
https://academic.hep.com.cn/fem/EN/Y2018/V5/I4/515

Fig.1 DC algorithm

1	Alperin H, Nowak I (2005). Lagrangian smoothing heuristics for max-cut. Journal of Heuristics, 11(5–6): 447–463 https://doi.org/10.1007/s10732-005-3603-z
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 https://doi.org/10.1023/A:1009661804163
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 https://doi.org/10.1109/JPROC.2006.887322
14	Chinchuluun A, Pardalos P M (2007). A survey of recent developments in multiobjective optimization. Annals of Operations Research, 154(1): 29–50 https://doi.org/10.1007/s10479-007-0186-0
15	Dantzig G B, Wolfe P (1960). Decomposition principle for linear programs. Operations Research, 8(1): 101–111 https://doi.org/10.1287/opre.8.1.101
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 https://doi.org/10.1007/BF02592064
19	Ehrgott M, Gandibleux X (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum, 22(4): 425–460 https://doi.org/10.1007/s002910000046
20	Fisher M L (1980). Worst-case analysis of heuristic algorithms. Management Science, 26(1): 1–17 https://doi.org/10.1287/mnsc.26.1.1
21	Fletcher R, Leyffer S (1994). Solving mixed integer nonlinear programs by outer approximation. Mathematical Programming, 66(1–3): 327–349 https://doi.org/10.1007/BF01581153
22	Floudas C, Aggarwal A, Ciric A (1989). Global optimum search for nonconvex nlp and minlp problems. Computers & Chemical Engineering, 13(10): 1117–1132 https://doi.org/10.1016/0098-1354(89)87016-4
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 https://doi.org/10.1126/science.8346439 pmid: 8346439
27	Geoffrion A M (1972). Generalized benders decomposition. Journal of Optimization Theory and Applications, 10(4): 237–260 https://doi.org/10.1007/BF00934810
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) https://doi.org/10.1145/227683.227684
30	Goertzel B (1999). Global optimization with space-filling curves. Applied Mathematics Letters, 12(8): 133–135 https://doi.org/10.1016/S0893-9659(99)00134-2
31	Grossmann I E (2002). Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3(3): 227–252 https://doi.org/10.1023/A:1021039126272
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 https://doi.org/10.1007/s11590-006-0021-6
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 https://doi.org/10.1007/BF01580863
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 https://doi.org/10.1016/S0377-2217(96)00058-6
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 https://doi.org/10.1057/palgrave.jors.2600523
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 https://doi.org/10.1007/s10107-004-0503-1
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 https://doi.org/10.1126/science.220.4598.671 pmid: 17813860
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 https://doi.org/10.1021/ie00069a026
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 https://doi.org/10.15807/jorsj.46.125
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 https://doi.org/10.1137/S1052623400366802
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 https://doi.org/10.1016/j.apnum.2009.10.004
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 https://doi.org/10.1007/s10589-007-9113-1
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 https://doi.org/10.1007/s10107-017-1139-2
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 https://doi.org/10.3233/AIS-170436
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 https://doi.org/10.1007/BF02022084
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 https://doi.org/10.1007/BF01580665
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 https://doi.org/10.1063/1.1699114
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 https://doi.org/10.1137/S1052623495283024
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 https://doi.org/10.1017/S0962492904000194
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 https://doi.org/10.1023/A:1019248506301
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 https://doi.org/10.1137/1033004
75	Palacios-Gomez F, Lasdon L, Engquist M (1982). Nonlinear optimization by successive linear programming. Management Science, 28(10): 1106–1120 https://doi.org/10.1287/mnsc.28.10.1106
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 https://doi.org/10.1109/JSAC.2006.879350
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 https://doi.org/10.1016/0898-1221(91)90163-X
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 https://doi.org/10.1137/1028106
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 https://doi.org/10.1287/opre.37.6.902
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 https://doi.org/10.1016/j.ejor.2016.12.005
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 https://doi.org/10.1007/BF00138693
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 https://doi.org/10.1023/A:1021845304798
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 https://doi.org/10.1016/S0098-1354(98)00286-5
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 https://doi.org/10.1016/j.neunet.2014.05.015 pmid: 25036646
97	Sprecher D A, Draghici S (2002). Space-filling curves and Kolmogorov superposition-based neural networks. Neural Networks, 15(1): 57–67 https://doi.org/10.1016/S0893-6080(01)00107-1 pmid: 11958490
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 https://doi.org/10.1137/S1052623499362822
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 https://doi.org/10.1016/0098-1354(95)00219-7
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 https://doi.org/10.1016/S0098-1354(98)00293-2
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 https://doi.org/10.1016/0098-1354(90)87085-4
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 https://doi.org/10.1016/0098-1354(95)87027-X
112	Westerlund T, Pettersson F, Grossmann I E (1994). Optimization of pump configurations as a minlp problem. Computers & Chemical Engineering, 18(9): 845–858 https://doi.org/10.1016/0098-1354(94)E0006-9
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 https://doi.org/10.1007/s10107-018-1242-z
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 https://doi.org/10.1016/S0098-1354(96)00346-8
115	Zamora J M, Grossmann I E (1998b). Continuous global optimization of structured process systems models. Computers & Chemical Engineering, 22(12): 1749–1770 https://doi.org/10.1016/S0098-1354(98)00244-0
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 https://doi.org/10.1016/j.cam.2005.10.034
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 https://doi.org/10.1007/s10479-012-1092-7
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

[1]	Fikri KUCUKSAYACIGIL, Gündüz ULUSOY. Hybrid genetic algorithm for bi-objective resource-constrained project scheduling[J]. Front. Eng, 2020, 7(3): 426-446.
[2]	Sameh Al-SHIHABI, Mohammad AlDURGAM. Multi-objective optimization for the multi-mode finance-based project scheduling problem[J]. Front. Eng, 2020, 7(2): 223-237.
[3]	Stefan JANAQI, Mériam CHÈBRE, Guillaume PITOLLAT. Online gasoline blending with EPA Complex Model for predicting emissions[J]. Front. Eng, 2018, 5(2): 214-226.
[4]	Xiao-jun Liu,Zhen-yu Guo,Chao Ding,Han-liang Fu. Industrial Structure Adjustment of Shaanxi Province under the Limited Water Resources Condition[J]. Front. Eng, 2014, 1(4): 378-384.

Viewed

Full text

Abstract

Cited

Shared

Discussed