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

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.

### 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
Full Text:

### References:

  Benson, H. P. (1991), Separable Concave Minimization via Partial Outer Approximation and Branch and Bound, forthcoming in Operations Research Letters.  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  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  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  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  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  Hoffman, K. L. (1981), A Method for Globally Minmizing Concave Functions over Convex Sets, Mathematical Programming 20, 22-32. · Zbl 0441.90096  Horst, R. (1976), An Algorithm for Nonconvex Programming Problems, Mathematical Programming 10, 312-321. · Zbl 0337.90062  Horst, R. (1980), A Note on the Convergence of an Algorithm for Nonconvex Programming Problems, Mathematical Programming 19, 237-238. · Zbl 0437.90069  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  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  Horst, R. (1989), On Consistency of Bounding Operations in Deterministic Global Optimization, J. of Optimization Theory and Applications 61, 143-146. · Zbl 0642.90080  Horst, R. (1990), Deterministic Global Optimization: Recent Advances and New Fields of Application, Naval Research Logistics 37, 433-471. · Zbl 0709.90093  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  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  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  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  Horst, R., Thoai, N. V., and Tuy, H. (1989), On an Outer Approximation Concept in Global Optimization, Optimization 20, 255-264. · Zbl 0675.90077  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  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  Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches, Springer, Berlin. · Zbl 0704.90057  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  Pardalos, P. M., Glick, J. H., and Rosen, J. B. (1987), Global Minimization of Indefinite Quadratic Problems, Computing 39, 281-291. · Zbl 0627.65072  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  Polak, E. (1987), On the Mathematical Foundations of Nondifferentiable Optimization in Engineering Design, SIAM Review 29, 21-89.  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  Rockafellar, R. T. (1970), Convex Analysis, Princeton University Press. · Zbl 0193.18401  Thach, P. T. (1988), The Design Centering Problem as a D.C. Program, Mathematical Programming 41, 229-248. · Zbl 0651.90065  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  Thoai, N. V. (1988), A Modified Version of Tuy’s Method for Solving D.C. Programming Problems, Optimization 19, 665-674. · Zbl 0662.90069  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  Tuy, H. (1983), On Outer Approximation Methods for Solving Concave Minimization Problems, Acta Mathematica Vietnamica 8, 3-34. · Zbl 0574.90074  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.  Tuy, H. (1987), Convex Programs with an Additional Reverse Convex Constraint, J. of Optimization Theory and Applications 52, 463-485. · Zbl 0585.90071  Tuy, H. (1987a), Global Minimization of a Difference of Two Convex Functions, Mathematical Programming Study 30, 150-182. · Zbl 0619.90061  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  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  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  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  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.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.