Global minimization by reducing the duality gap. (English) Zbl 0807.90101

The authors discuss nonlinear optimization problems of the form \[ (P_ Q)\qquad \min_{x,q} \bigl\{f_ 0(q,x): q\in Q,\;f_ j(q,x)\leq 0,\;j= 1,\dots,m\bigr\}, \] where \(Q\) is a nonempty set. The aim is to find lower bounds for the global minimum of \((P_ Q)\). One of the most important ways is based on the introduction of the Lagrange dual problem \((D_ Q)\) but in general no strict duality relations hold. To reduce the duality gap the authors provide an interesting approach by partitioning the set \(Q\). If \(Q= \bigcup_{i\in I} Q_ i\) then it is easy to show that \[ \min(P_ Q)= \min_{i\in I}\{\min (P_{Q_ i})\}\geq \min_{i\in I} \{\max(D_{Q_ i})\}\geq \max(D_ Q). \] So the value \(\min_{i\in I} \{\max(D_{Q_ i})\}\) is a better estimation for the optimal value of \((P_ Q)\). Moreover, one can guess that the gap will be smaller if the partition is taken finer i.e. if the radius of the partition (the radius of the smallest ball containing the sets \(Q_ i\)) tends to zero. Naturally, suitable convexity and regularity conditions for the partial problems \((P_{Q_ i})\) must be assumed.
For “partially linear” problems (here all functions are linear in the variable \(x\) and \(Q\) is a polytop) the authors provide sufficient conditions that for any \(\varepsilon> 0\) there exists a partition of \(Q\) with the duality gap smaller than \(\varepsilon\).
It is worthy to state that for such problems all dual problems reduce to linear semi-infinite problems which can simplified by additional convexity assumptions for the variable \(q\).
At the end of the paper a branch-and-bound type algorithm and first results by solving a special two-stage process are presented.


90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
90C34 Semi-infinite programming
49N15 Duality theory (optimization)
Full Text: DOI


[1] E. Alperovits and U. Shamir, ”Design of optimal water distribution system,”Water Resources Research 13(6) (1977) 885–900.
[2] B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer,Nonlinear Parametric Optimization (Birkhauser, Basel, 1983). · Zbl 0502.49002
[3] A. Ben-Tal, G. Eiger, J. Outrata and J. Zowe, ”A nondifferential approach to decomposable optimization problems with an application to the design of water distribution networks,” in: W. Oettlie and D. Pallaschke, eds.,Advances in Optimization, Lecture Notes in Econom. and Math. Syst. No. 382 (Springer, Berlin, 1992). · Zbl 0790.90064
[4] C.A. Floudas and A. Aggarwal, ”A decomposition approach for global optimum search in the pooling problem,”ORSA Journal on Computing 2(3) (1990) 225–235. · Zbl 0755.90091
[5] C.A. Floudas and P.M. Pardalos, ”A collection of test problems for constrained global optimization algorithms,”Lecture Notes in Comput. Sci. No. 455 (Springer, Berlin, 1987). · Zbl 0718.90054
[6] C.A. Floudas and V. Visweswaran, ”A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory,”Computers and Chemical Engineering 14(12) (1990) 1397–1417.
[7] C.A. Floudas and V. Visweswaran, ”A primal-relaxed dual global optimization approach,” to appear in:Journal of Optimization Theory and Applications (1992). · Zbl 0796.90056
[8] O. Fujiwara and D.B. Khang, ”A two-phase decomposition method for optimal design of looped water distribution networks,”Water Resources Research 26(4) (1990) 539–549.
[9] O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New Jersey, 1969).
[10] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1972). · Zbl 0224.49003
[11] H. Schramm and J. Zowe, ”A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,”SIAM Journal on Optimization 2 (1992). · Zbl 0761.90090
[12] N.Z. Shor,Minimization Methods for Nondifferentiable Functions (Springer, Berlin, 1985). · Zbl 0561.90058
[13] V. Visweswaran and C.A. Floudas, ”A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: II. Application of theory and test problems,”Computers and Chemical Engineering 14(12) (1990) 1417–1434.
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.