An optimal bound for d.c. programs with convex constraints

Math Meth Oper Res (2001) 54:47±51 aaaaa 2001 An optimal bound for d.c. programs with convex constraints* Emilio Carrizosay yFacultad de Matema Âticas. Universidad de Sevilla. Tar®a s/n, 41012 Sevilla, Spain. (e-mail: [email protected]) Manuscript received: November 2000/Final version received: April 2001 Abstract. A well-known strategy for obtaining a lower bound on the minimum of a d.c. function fgover a compact convex set SHRnconsists of replacing the convex function fby a linear minorant at x0AS. In this note we show that the x 0giving the optimal bound can be obtained by solving a convex minimization program, which corresponds to a Lagrangian decomposition of the problem. Moreover, if Sis a simplex, the optimal Lagrangian multiplier can be obtained by solving a system of n1 linear equations. Key words: d.c. programs; bounds; Lagrangian decomposition 1 Problem statement Let Sbe a nonempty compact convex subset of Rn, and let f;gbe convex and ®nite on Rn. Our aim is to ®nd a lower bound on the optimal value zof the d.c. program min xASfxgx1 Obtaining such lower bounds may be a real need when one is solving global optimization problems by a branch-and-bound strategy, [2, 1, 3], both in the bounding process (indeed, one needs to ®nd good lower bounds for subproblems in the form (1) at each stage in the resolution of min xAWfx gxusing polyhedral, ± say, simplicial or hyperrectangular ± branching schemes) and in order to check feasibility as well (showing that a lower bound * The research of this author is partially supported by Grant PB96-1416-C02-02 of Direccio Ân General de EnsenÄanza Superior, Spain for minxASfxgxis strictly positive implies the infeasibility of the (sub)- problem minfhx:fxgxa0;xASg). In both cases, it is important to have the bounds as sharp as possible, since this may considerably reduce the computational e¨ort. Now we introduce some notation: let extSdenote the set of extreme points of the convex set S, and, for any x0AS, let qfx0denote the subdi¨erential of fat x0. One immediately derives the following result from the de®nition of subgradients and the fact that a concave function attains its minimum on a bounded convex set Sat some point in extS, e.g. [2]. Proposition 1. For any x0AS and u0Aqfx0, it follows zbmin xASfx0hu0;xx0igx min xAextSfx0hu0;xx0igx The bound given in Proposition 1 strongly depends on the choice of the point x0AS. Such bound can then be sharpened if one choses the best possible x0, Corollary 1. De®ne zPsup min xAextSfx0hu0;xx0igx:x0AS;u0Aqfx0  2 Then, zPaz. Finding the optimal lower bound zPfrom the de®nition amounts to solving a maxmin nonlinear problem with nonconvex constraints, thus, at ®rst glance, it does not seem obvious at all that the possible enhancement of the bound zPwith respect to any of the simple bounds given in Proposition 1 will deserve the resolution of the global-optimization problem (2). It turns out however that (2) can be formulated as a convex program, as shown in Section 2. 2 A Lagrangian decomposition scheme Lower bounds for zcan also be obtained via Lagrangian decomposition, [4]. Indeed, (1) can be equivalently rephrased as minffxgy:xy;xAS;yASg Dualizing the constraints xy, one obtains the Lagrangian dual zDmax uARnLu;3 48 E. Carrizosa with Lu min x;yASfxhu;xigyhu;yi min xASfxhu;ximin yASgyhu;yi:4 We see that (3) is a bilevel problem, since the mere evaluation of the Lagrangian function Lat a given uARnamounts to solving the convex minimization program min xASfxhu;xiand the concave minimization program maxyASgyhu;yi. Since the latter reduces to vertex enumeration if Sis polyhedral, Lcan be evaluated in ®nite time for particular instances (e.g., when fis polyhedral or quadratic and Sis a polytope), whilst for general problems Lmust be approximated by ®nding a near-optimal solution of a nonlinear program. The next result shows that ®nding an optimal multiplier is equivalent to solving (2). Proposition 2. One has zDzP Proof. Let fSthe restriction of fto S, fSx fx;if xAS y;else  and let f Sdenote the Fenchel conjungate of fS, [5] f Spsupfhp;xifSx:xARng We will show now that LuazPEuARn5 Indeed, for any given uARn, Luf Sumin yAShu;yigy Moreover, there exists x0ASsuch that f Suhu;x0ifSx0, thus it follows that uAqfSx0, see [5]. Hence, by de®nition of subgradients, Lufx0hu;x0imin yAShu;yigy min yAShu;x0ifx0hu;yigy min yAextShu;x0ifx0hu;yigy azP Hence, (5) holds. An optimal bound for d.c. programs with convex constraints 49 Conversely, given x0ASand u0Aqfx0, one has that f Su0fSx0 hu0;x0i, thus min xASfx0hu0;xx0igx fx0hu0;x0imin xAShu0;xigx f Su0min xAShu0;xigx Lu0 azDr Since, by (4), the function L:uARn7! LuminxASfxhu;xi minxASgxhu;xiis minimum of a½ne functions, thus concave, Proposition 2 implies that zPcan be obtained by solving the concave maximization problem max uARnLu6 Although much simpler than the original expression (1), solving (6) still involves some computational burden, since it is a (nondi¨erentiable as a rule) nonlinear concave program, the objective function of which has no known analytical expression but must be evaluated by solving a convex minimization problem. This implies that, in practice, ®nding the optimal multiplier in (6) may be too costly, and, as customary in branch-and-bound approaches to combinatorial problems, see [6], one just performs a few iterations of some concavemaximization algorithm, leading to a lower bound on zP. This should be the strategy for an arbitrary compact convex set S. However, branch-and-bound schemes often assume Sto be a simplex in Rn, see e.g. [2]. In that case, Proposition 2 can be further strengthened, since ®nding the optimal multiplier for (6) is reduced to solving a linear system of n1 equations. Indeed, one has Proposition 3. Let S be a simplex in Rn, with vertices v0;...;vn, and let ^ u be the solution to the system of linear equations gv1hv1;uigv0hv0;ui gv2hv2;uigv0hv0;ui ... ... gvnhvn;uigv0hv0;ui 7 Then, zDL^ u Proof. First of all, since Sis assumed to be a simplex, the system of equations (7) has a unique solution, thus ^ uis well de®ned. In order to show the result, it 50 E. Carrizosa su½ces to show that ^ uis an optimal solution to the convex program min uARn Lu, by showing that 0 is a subgradient of Lat ^ u. Indeed, since fis ®nite at Sand Sis compact, the optimal value of the optimization problem max xASfxh^ u;xi is attained at some x0AS. In other words, x0satis®es fSx0h^ u;x0if S^ u: Hence, by Theorem 23.5 of [5], x0Aqf S^ u. Moreover, since the piecewise linear function h:uARn7! humax0aianhvi;uigvihas all its components active at ^ u, it follows that qh^ uconvfv0;...;vng S: Hence x0Aqh^ u, thus 0Aqf S^ uqh^ u qL^ u; showing that ^ uminimizes L, as asserted. r Acknowledgements. The author thanks Dr. Christian Michelot (Universite Âde Bourgogne) and Dr. Frank Plastria (Vrije Universiteit Brussel) for their helpful comments. References [1] Horst R, Thoai NV (1999) DC programming: Overview. Journal of Optimization Theory and Applications 103:1±43 [2] Horst R, Tuy H (1996) Global optimization. Deterministic approaches. Springer Verlag, Berlin. Third revised edition [3] Tuy H (1995) D.C. optimization: Theory, methods and algorithms. Handbook of Global Optimization, Edited by Horst R and Pardalos PM. Kluwer Academic Press, Dordrecht, pp 149±216 [4] Guignard M, Kim S (1987) Lagrangean decomposition: A model yielding stronger lagrangean bounds. Mathematical Programming 2:215±228 [5] Rockafellar RT (1970) Convex analysis. Princeton university press, Princeton [6] Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York An optimal bound for d.c. programs with convex constraints 51