Convexification for a Class of Global Optimization Problems with C1,1 Functions

Expand
  • 1 College of Sciences, Chongqing University of Technology, Chongqing 400054, China;
    2 College of Mathematics, Sichuan University, Chengdu, Sichuan 610065, China;
    3 National Center for Applied Mathematics of Chongqing, Chongqing 401331, China;
    4 College of Mathematical Science, Chongqing Normal University, Chongqing 401331, China

Received date: 2022-11-16

  Revised date: 2023-09-12

  Online published: 2025-12-19

Supported by

This work was supported by the Major Program of the National Natural Science Foundation of China (Nos. 11991020, 11991024), the National Natural Science Foundation of China (No. 11871128), Scientific Research Foundation of Chongqing University of Technology (No. 2023ZDZ021), Youth project of science and technology research program of Chongqing Education Commission of China (No. KJQN202301160).

Abstract

A general convexification method via domain transformation scheme is presented for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems with C1,1 functions can be converted into equivalent convex optimization problems by using the proposed convexification method. Finally, an example is shown to illustrate how a monotone non-convex optimization problem can be transformed into an equivalent convex minimization problem.

Cite this article

Qian Yan, Xin-Min Yang, Zhi-You Wu . Convexification for a Class of Global Optimization Problems with C1,1 Functions[J]. Journal of the Operations Research Society of China, 2025 , 13(4) : 900 -918 . DOI: 10.1007/s40305-023-00521-0

References

[1] Tzafestas, S.G.: Optimization of system reliability: a survey of problems and techniques. Int. J. Syst. Sci. 11, 455–486 (1980)
[2] Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge (1988)
[3] Li, D., Sun, X.L., Biswal, M.P., Gao, F.: Convexification, concavification, and monotonization in global optimization. Ann. Oper. Res. 105, 213–226 (2001)
[4] Sun, X.L., Mckinnon, K.I.M., Li, D.: A convexification method for a class of global optimization problems with applications to reliability optimization. J. Glob. Optim. 21, 185–199 (2001)
[5] Xia, Y.: A survey of hidden convex optimization. J. Oper. Res. Soc. China 8, 1–28 (2020)
[6] Benson, H.P.: Deterministic algorithms for constrained concave minimization: a unified critical survey. Naval Res. Log. 43, 765–795 (1996)
[7] Hoffman, K.L.: A method for globally minimizing concave functions over convex sets. Math. Program. 20, 22–32 (1981)
[8] Horst, R., Pardalos, P.M., Van Thoai, N.: Introduction to Global Optimization. Springer (2000)
[9] Tuy, H.: Monotonic optimization: problems and solution approaches. SIAM J. Optim. 11, 464–494 (2000)
[10] Tuy, H.: Convex Analysis and Global Optimization. Spring, Berlin (2016)
[11] Horst, R.: On the convexification of nonlinear programming problems: an applications-oriented survey. Eur. J. Oper. Res. 15, 382–392 (1984)
[12] Xu, G.X.: Global optimization of signomial geometric programming problems. Eur. J. Oper. Res. 233, 500–510 (2014)
[13] Lu, H.C., Yao, L.M.: Efficient convexification strategy for generalized geometric programming problems. INFORMS J. Comput. 31, 226–234 (2019)
[14] Wu, Z.Y., Zhang, L.S., Bai, F.S., Yang, X.M.: Convexification and convexification methods for some global optimization problems. J. Syst. Sci. Complex 17, 421–436 (2004)
[15] Wu, Z.Y., Bai, F.S., Zhang, L.S.: Convexification and concavification for a general class of global optimization problems. J. Glob. Optim. 31, 45–60 (2005)
[16] Wu, Z.Y., Lee, H.W.J., Yang, X.M.: A class of convexification and concavification methods for nonmonotone optimization problems. Optimization 54, 605–625 (2005)
[17] Li, D., Wu, Z.Y., Lee, H.W.J., Yang, X.M., Zhang, L.S.: Hidden convex minimization. J. Glob. Optim. 31, 211–233 (2005)
[18] Sun, X.L., Luo, H.Z., Li, D.: Convexification of nonsmooth monotone functions. J. Optim. Theory Appl. 132, 339–351 (2007)
[19] Li, D.: Convexification of a noninferior frontier. J. Optim. Theory Appl. 88, 177–196 (1996)
[20] Zhang, L.S., Wu, D.H.: Convexification, concavification and monotonization in nonlinear programming. Chin. Ann. Math. Ser. A 23, 537–544 (2002)
[21] Yan, Q., Yang, X.M., Wu, Z.Y.: On convexification for a class of global optimization problems. J. Oper. Res. Soc. China. https://doi.org/10.1007/s40305-021-00379-0
[22] Rockafellar, R.T.: Solving a nonlinear programming problem by way of a dual problem. Symp. Math. 19, 135–160 (1976)
[23] Beck, A.: First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2017)
[24] Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980)
[25] Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121–140 (1996)
[26] Chang, T.J., Meade, N., Beasley, J.E., Sharaiha, Y.M.: Heuristics for cardinality constrained portfolio optimisation. Comput. Oper. Res. 27, 1271–1302 (2000)
[27] La Torre, D., Vercellis, C.: C1, 1 approximations of generalized support vector machines. J. Concr. Appl. Math. 3, 41–54 (2005)
[28] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer (2009)
[29] Ginchev, I., La Torre, D., Rocca, M.: Ck, 1 functions, characterization, Taylor’s formula and optimization: a survey. Real Anal. Exch. 35, 311–342 (2010)
[30] Yang, X.Q.: Generalized second-order directional derivatives and optimization conditions. Ph.D. Disseration, University of New South Wales, Australia (1994)
[31] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
[32] Yang, X.Q., Jeyakumar, V.: Generalized second-order directional derivatives and optimization with C1, 1 functions. Optimization 26, 165–185 (1991)
Options
Outlines

/