On solving a d.c. programming problem by a sequence of linear programs. (English) Zbl 0755.90076

Horst, R.; Phong, T. Q.; Thoai, Ng. V.; de Vries, J.

J. Glob. Optim. 1, No. 2, 183-203 (1991).

Consider the problem of finding the global minimum of the difference of two convex functions over a closed convex set in \(R^ n\), that is \[ \text{glob }\min(f(x)-g(x))\quad\text{s.t. } h_ j(x)\leq 0\;(j=1,\dots,J),\tag{P} \] where \(f\), \(g\), \(h_ j\) are finite convex functions on \(R^ n\). Problem (P) is usually called a d.c. optimization problem and general properties have been investigated by J.-B. Hiriart-Urruty [in: Convexity and duality in optimization, Proc. Symp., Groningen/Neth. 1984, Lect. Notes Econ. Math. Syst. 256, 37-70 (1985; Zbl 0591.90073)], by Hoang Tuy [Math. Program. Study 30, 150-182 (1987; Zbl 0619.90061)], P. M. Pardalos and J. B. Rosen [“Constrained global optimization: algorithms and applications” (1987; Zbl 0638.90064)] and by the first, second and third author [Ann. Oper. Res. 25, No. 1-4, 1-18 (1990; Zbl 0717.90057)]. It can be transformed by introducing an additional variable \(t\) into the equivalent concave minimization problem \[ \text{glob }\min(t-g(x))\quad\text{s.t. } f(x)\leq t,\;h_ j(x)\leq 0\;(j=1,\dots,J).(CP) \] For solving the (CP) problem branch and bounds methods or outer approximation procedures have been proposed, but these techniques have proved to be numerically expensive. An algorithm by the first and third author and H. P. Benson [Math. Program., Ser. A 50, No. 2, 259-274 (1991; Zbl 0734.90092)] which combines both techniques has successfully overcome some drawbacks. Following this attempt, a new algorithm is presented, which shows to be numerically more appealing. The authors prove the convergence of the new procedure and report some numerical results.

Reviewer: M.Gaviano (Cagliari)

MSC:

90C30	Nonlinear programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

d.c. programming; difference of two convex functions

Citations:

Zbl 0591.90073; Zbl 0619.90061; Zbl 0638.90064; Zbl 0717.90057; Zbl 0734.90092

References:

[1]	Benson, H. P. (1991), Separable Concave Minimization via Partial Outer Approximation and Branch and Bound, forthcoming in Operations Research Letters.
[2]	Benson, H. P. and Horst, R. (1991), A Branch and Bound-Outer Approximation Algorithm for Concave Minimization over a Convex Set, forthcoming in J. of Computers and Mathematics with Applications. · Zbl 0722.90055
[3]	Falk, J. E. and Hoffman, K. R. (1976), A Successive Underestimation Method for Concave Minimization Problems, Mathematics of Operations Research 1, 271-280. · Zbl 0362.90082
[4]	Giannessi, F., Jurina, L., and Maier, G. (1979), Optimal Excavation Profile for a Pipeline Freely Resting on the Sea Floor, Engineering Structures 1, 81-91. · Zbl 0426.90092
[5]	Heron, B. and Sermange, M. (1982), Nonconvex Methods for Computing Free Boundary Equilibria of Axially Symmetric Plasmas, Applied Mathematics and Optimization 8, 351-382. · Zbl 0495.65052
[6]	Hiriart-Urruty, J. B. (1985), Generalize Differentiability, Duality and Optimization for Problems Dealing with Differences of Convex Functions, Lecture Notes in Economics and Mathematical Systems 256, Springer-Verlag, 36-69. · Zbl 0591.90073
[7]	Hoffman, K. L. (1981), A Method for Globally Minmizing Concave Functions over Convex Sets, Mathematical Programming 20, 22-32. · Zbl 0441.90096
[8]	Horst, R. (1976), An Algorithm for Nonconvex Programming Problems, Mathematical Programming 10, 312-321. · Zbl 0337.90062
[9]	Horst, R. (1980), A Note on the Convergence of an Algorithm for Nonconvex Programming Problems, Mathematical Programming 19, 237-238. · Zbl 0437.90069
[10]	Horst, R. (1986), A General Class of Branch and Bound Methods in Global Optimization with Some New Approaches for Concave Minimization, J. of Optimization Theory and Applications 51, 271-291. · Zbl 0581.90073
[11]	Horst, R. (1988), Deterministic Global Optimization with Partition Sets Whose Feasibility is Not Known. Application to Concave Minimization, Reverse Convex Constraints, D.C.-Programming and Lipschitzian Optimization, J. of Optimization Theory and Application 58, 11-37. · Zbl 0621.90064
[12]	Horst, R. (1989), On Consistency of Bounding Operations in Deterministic Global Optimization, J. of Optimization Theory and Applications 61, 143-146. · Zbl 0642.90080
[13]	Horst, R. (1990), Deterministic Global Optimization: Recent Advances and New Fields of Application, Naval Research Logistics 37, 433-471. · Zbl 0709.90093
[14]	Horst, R., Phong, T. Q. and Thoai, N. V. (1990), On Solving General Reverse Convex Programming Problems by a Sequence of Linear Programs and Line Searches, Annals of Operations Research 25, 1-18. · Zbl 0717.90057
[15]	Horst, R. and Thoai, N. V. (1989), Modification, Implementation and Comparison of Three Algorithms for Globally Solving Linearly Constrained Concave Minimization Problems, Computing 42, 271-289. · Zbl 0675.65063
[16]	Horst, R., Thoai, N. V., and Benson, H. P. (1991), Concave Minimization via Conical Partitions and Polyhedral Outer Approximation, forthcoming in Mathematical Programming. · Zbl 0734.90092
[17]	Horst, R., Thoai, N. V., and Tuy, H. (1987), Outer Approximation by Polyhedral Convex Sets, Operations Research Spektrum 9 (3), 153-159. · Zbl 0642.90094
[18]	Horst, R., Thoai, N. V., and Tuy, H. (1989), On an Outer Approximation Concept in Global Optimization, Optimization 20, 255-264. · Zbl 0675.90077
[19]	Horst, R., Thoai, N.V., and deVries, J. (1987), On Finding New Vertices and Redundant Constraints in Cutting Plane Algorithms for Global Optimization, Operations Research Letters, 7, 85-90. · Zbl 0644.90085
[20]	Horst, R. and Tuy, H. (1987), On the Convergence of Global Methods in Multiextremal Optimization, J. of Optimization Theory and Applications 54, 253-271. · Zbl 0595.90079
[21]	Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches, Springer, Berlin. · Zbl 0704.90057
[22]	Nguyen, V. H. and Strodiot, J. J. (1988), Computing a Global Solution to a Design Centering Problem, Technical Report 88/12, Facultés Universitaires de Namur. · Zbl 0751.90071
[23]	Pardalos, P. M., Glick, J. H., and Rosen, J. B. (1987), Global Minimization of Indefinite Quadratic Problems, Computing 39, 281-291. · Zbl 0627.65072
[24]	Pardalos, P. M. and Rosen, J. B. (1987), Constrained Global Optimization: Algorithms and Applications, Lecture Notes on Computer Science 268, Springer XIV. · Zbl 0638.90064
[25]	Polak, E. (1987), On the Mathematical Foundations of Nondifferentiable Optimization in Engineering Design, SIAM Review 29, 21-89.
[26]	Polak, E. and Vincentelly, A. S. (1979), Theoretical and Computational Aspects of the Optimal Design Centering Tolerancing and Tuning Problem, IEEE Transactions Circuits and Systems CAS-26, 795-813. · Zbl 0425.90084
[27]	Rockafellar, R. T. (1970), Convex Analysis, Princeton University Press. · Zbl 0193.18401
[28]	Thach, P. T. (1988), The Design Centering Problem as a D.C. Program, Mathematical Programming 41, 229-248. · Zbl 0651.90065
[29]	Thieu, T. V., Tam, B. T., and Ban, V. T. (1983), An Outer Approximation Method for Globally Minimizing a Concave Function over a Compact Convex Set, Acta Mathematica Vietnamica 8, 21-40. · Zbl 0562.90069
[30]	Thoai, N. V. (1988), A Modified Version of Tuy’s Method for Solving D.C. Programming Problems, Optimization 19, 665-674. · Zbl 0662.90069
[31]	Toland, J. F. (1979), A Duality Principle for Nonconvex Optimization and the Calculus of Variations, Archive of Radional Mechanics and Analysis 71, 41-61. · Zbl 0411.49012
[32]	Tuy, H. (1983), On Outer Approximation Methods for Solving Concave Minimization Problems, Acta Mathematica Vietnamica 8, 3-34. · Zbl 0574.90074
[33]	Tuy, H. (1986), A General Deterministic Approach to Global Optimization via D.C. Programming, in Hiriart-Urruty, J. B. (ed.), Fermat Days 1985: Mathematics for Optimization, North Holland, Amsterdam, 137-162.
[34]	Tuy, H. (1987), Convex Programs with an Additional Reverse Convex Constraint, J. of Optimization Theory and Applications 52, 463-485. · Zbl 0585.90071
[35]	Tuy, H. (1987a), Global Minimization of a Difference of Two Convex Functions, Mathematical Programming Study 30, 150-182. · Zbl 0619.90061
[36]	Tuy (1991), Effect of the Subdivision Strategy on Convergence and Efficiency of Some Global Optimization Algorithms, J. of Global Optimization 1, 23-36. · Zbl 0744.90083
[37]	Tuy, H. and Horst, R. (1988), Convergence and Restart in Branch and Bound Algorithms for Global Optimization. Application to Concave Minimization and DC-Optimization Problems, Mathematical Programming 41, 161-183. · Zbl 0651.90063
[38]	Tuy, H., Thieu, T. V., and Thai, N. Q. (1985), A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research 10, 498-514. · Zbl 0579.90078
[39]	Tuy, H. and Thuong, N. V. (1988), On the Global Minimization of a Convex Function under General Nonconvex Constraints, Applied Mathematics and Optimization 18, 119-142. · Zbl 0657.90083
[40]	Vidigal, L. M. and Director, S. W. (1982), A Design Centering Algorithm for Nonconvex Regions of Acceptability, IEEE Transactions on Computer-Aided-Design of Integrated Circuits and Systems CAD-I, 13-24.