American Journal of Oper ations Research, 2011, 1, 185189 doi:10.4236/ajor.2011.13021 Published Online September 2011 (http://www.SciRP.org/journal/ajor) Copyright © 2011 SciRes. AJOR An Exact Penalty Approach for Mixed Integer Nonlinear Programming Problems Roohollah Aliakbari Shandiz, Nezam MahdaviAmiri Faculty of Mathematical Sciences, Sharif Un iversity of Technology, Tehran, Iran Email: aliakbari_r@mehr.sharif.edu, neza mm@sharif.ed u Received July 31, 2011; revised August 19, 2011; accepted September 15, 2011 Abstract We propose an exact penalty approach for solving mixed integer nonlinear programming (MINLP) problems by converting a general MINLP problem to a finite sequence of nonlinear programming (NLP) problems with only continuous variables. We express conditions of exactness for MINLP problems and show how the exact penalty approach can be extended to constrained problems. Keywords: Mixed Integer Nonlinear Programming, Continuous Programming, Exact Penalty Method, Exact Penalty Functions 1. Introduction One way for relaxing the integer constraints on the vari ables of a problem is adding an appropriate penalty term to the objective function to create a new problem with only continuous variables. This approach was first intro duced by Ragavachari [1] to solve 01 linear program ming problems and was used by several researchers for solving real nonlinear discrete programming problems [25]. Recently, Murray and Ng [6] have extended this approach for large scale 01 nonlinear programming problems with linear constraints. In [7], the exact penalty approach was extended to nonlinear integer programming problems. In [3,8], sev eral penalty functions were presented and the exactness of some of them were proved in [9]. Here, using ideas of Lucidi [9] we introduce conditions for exactness of a penalty function for mixed integer nonlinear program ming (MINLP) problems. Then, we extend the exact penalty approach to constrained mixed integer nonlinear programming problems. Notation 1. Let denote the optimal value of prob lem . (.)v (.) 2. Penalty Method for Unconstrained MINLP Problems An unconstrained mixed integer nonlinear programming problem is expressed as: min , .., , fxy UMINL P txXyY where, f is a realvalued continuous function on nm , X is a finite subset of in the form {0 , and Y is a compact subset in . n m ,1}n LP The continuous relaxation of can be ex pressed as: UMIN min , ..0,1 ,. n fxy R tx yY We construct the following problem by adding some constraints to the relaxed problem : R =1 min , .. ==0 0,1 ,, n ii i n fxy UNLPs tqxqx yY where, the ii qx nonnegative continuous functions as follows: are 1,,. 0,0,1 , == >0,0,1, i ii i x qxi n x (1) It is easy to see that UMINL P =1 =n ii iq x and are equivalent, because is zero on points UNL P qx
R. ALIAKBARI SHANDIZ ET AL. 186 ,, n in and is positive on points in {0,1}n(0,1) . n i q ,=1,i ,=1, ,i , Some appropriate definitions for the are: 1=1 ii ii qqxx xn 2=1cos2π. ii i qqx x Now, for every , let >0r ,= , r xyf xyrqx and consider the following penalty problem for the : UNL P min,= .. 0,1 r rn , , . xy fqx EN st x xy r y Y UP UP Note that the problem r is a continuous ver sion of the problem . UPEN LPUMIN Under certain assumptions, we show that for some fi nite value of penalty parameter r, problem is equivalent to . r EN UMINLP For , 0< <12 , define a punctured neighborhood of in [0, as follows: {0,1} 1] =0,1 ,1J . (2) Assumption 1. There exist >0 and >0 such that i) for every ,n n0,1, yJY Y we have ,<,=1,,, i xy i x n ii) each i is differentiable on q and for each i J , we have >, <, <, >1, i ii i x x i x == n q 1,,. q' Note that if f has bounded derivatives, then it satisfies Assumption 1(i), and as an example, (1) satisfies As sumption 1(ii). The following theorem shows that we can find a solu tion of an unconstrained MINLP problem by solving a finite sequence of NLP problems. Theorem 1. Under Assumption 1, there exists a finite 0 such that for any 0 any solution of r>,rr r UPEN also solves with UMINLP = rvU ) . vUPEN (, MINLP Proof. For any feasible point y for UMINLP , we have ,= , r = ,. xyfxy rqxfxy Since any feasible point for (UMINLP) is also feasible for , the above relation implies: UPE r N . r vUMINLPvUPEN (3) For any , let >0r , rr y be an optimal solution of r UPEN . Suppose that , rr y is a convergent sub sequence of optimal solutions of r UPEN and , y ,1 is its limit. Note that since , rr 0 n yY and 0,1 nY is compact, at least one convergent subse quence exists. Since r x , there exists an r such that for every >rr , we have: <. r xx Therefore, (2) implies that 0,1 r i x or r i J . Now, let 0=mrax ,r and suppose that 0. If >rr 0,1 , r i x then . r i J Since f and i are dif ferentiable on q and the firstorder necessary condi tions for problem holds in subspace r UPEN , then we have ,=0, rr y r i Hx x ,, rr ii qxy xx =0, rr fxy r ,=0. rr r ii ii fxyr qx xx Assumption 1(ii) implies: ,=> =. rr r ii i fxy rqx x This is clearly a contradiction to Assumption 1(i). Therefore, for we have Thus, 0 >,rr 0,1 n r x. , rr y is feasible for and . Fur thermore, UMINLP qx r=0 =, =, =, . rr rr rr r rr vUPENHx y xy rqx fxy vUMINLP (4) Relations (3) and (4) imply: ,= = =,. rr r rr r xyvUMINLP vUPEN Hxy Therefore, for any 0 >,rr , rr y is an optimal solu tion for both problems. 3. Exact Penalty Functions The following penalty functions have been suggested [3, 9] for zeroone problems (): 01 i x 3=41 iii i qqxx x , 1 2, , 2 4= 1 21,>, 2 ii ii ii xx qqx xx Copyright © 2011 SciRes. AJOR
R. ALIAKBARI SHANDIZ ET AL. 187 5=loglog1 loglog 1, ii ii qqxxx 6= 1 1, p ii ii p p qqx xx 7=1exp 1exp 11exp, ii i i qqx x x 8=1 q q ii ii qqxxx1, 1 1 1 9=1exp 1exp 1 11exp , 2 ii i i qqxx x where, ,>0p , 0< <12 and . Penalty functions were introduced in [9]. Here, to have (1) satisfied, we add a fixed number to every func tion 0< <1q (5)q (5)(9). qq (9) q Also, two other penalty functions for zeroone prob lems can be defined as follows: 10=sinπ, ii i qqx x 11= 11, iiii ii qqxxxx x where, >0 . Note that any bounded MINLP problem can be refor mulated as a mixed zeroone programming problem by using the following representation for the integer vari ables (see [7]): =0 =2 ,0,1,=1,, Mii k ikk k , yyin where, M is an upper integer bound for log i . Thus, we can use the penalty functions for all bounded integer problems. Also, note that direct use of penalty functions for MINLP problems (not zeroone) is not suitable, because due to the structure of the i (see (1)), the resulting nonconvex optimization problem, in general, may have many local minimizers (see [4]). q Now, we show that r UPEN with the penalty func tions are exact for (3)(11)qq UMINLP 1).q . Note that exactness of have already been proved in [9]. Here, by using Theorem 1, we prove the exactness corresponding to all of (5)q(9)q (3) (1q Let us suppose that f satisfies Assumption 1 1). We then need to show that Assumption 1 2) holds for every one of(3 For) (11).qq=13, we have =0,13 23 ,1J . It is easy to show that for the functions we have (3) (11),qq 1 0,,>1 3> 0, 3 iiii xqxq and 2,1,<23<0. 3 iiii xqxq Therefore, Assumption 1(ii) is satisfied for (3)(11)qq . Thus, the penalty problem with any one of the functions . r UPEN (3) (11)qq is exact for . LPUMIN 4. Extension to Constrained Problems A constrained mixed integer nonlinear programming problem is expressed as: min , ..,0,=1,,, 0,1 ,, j n fxy INLPs tgxyjl xyY where, Y is a compact subset in . m Let =,0,1,0,= 1,, n j SxyYgxy jl . A penalty function for INLP is defined as fol lows: 0, , ,= >0, ,. yS pxy yS A typical penalty function for the constraints in INLP is: =1 ,=max0,, l j j pxygxy . (5) Consider the penalty problem of INLP as: min, =,, ..0,1,, n xyf xypxy PEN stxyY and define the following continuous penalty problem for INLP : , , ,= ,, min ..0,1 ,. r r n xyf xypxy rq x PEN stxy Y To prove the exactness of for ,r PEN , INLP first we show that for some penalty function p, PEN is exact for INLP . Note that exactness for some penalty functions, such as absolutevalue penalty func tion, for the nonlinear programming (NLP) problems or nonlinear integer programming (NLIP) problems has already been proved (see [10,11]), that is, it has been shown that for a finite value of the penalty parameter, the main problem and the corresponding penalty problem are equivalent. Here, we prove exactness for the constrained Copyright © 2011 SciRes. AJOR
R. ALIAKBARI SHANDIZ ET AL. 188 MINLP problems. Theorem 2. Consider INLP and for every x, define the following NLP pr oblem, min , ..,0,=1,,, , xj fxy NLPstgxyjl yY and its corresponding penalty problem, min, =,, .. . x xyf xypxy PEN sty Y Suppose that for any x feasible to , NLP there exists a such that for every >, problems NLP and PEN are equivalent. Then, there exists a 0 such that for every 0 >, any solution of PEN also solves INLP and =NvM (, ) NLPvPEI. Proof. For any feasible point y of INLP , we have ,= ,,= ,. xyf xypxyf xy Since any feasible point for INLP is also feasi ble for PEN , it follows from the above equality that .v MINLPv PEN (6) We know: ,0,1 ,0,1 0,1 =, min =, min =, min min n xy Y n xy Y nyY x vPENH xy , ,. xy pxy xy pxy For any fixed x, define =,0,=1, xj SyYgxy jl ,. . Consider the following two cases. Case 1: . Consider the following problem: x S ,, min yY xy pxy From the assumption of the theorem, there exists such that for any >, any solution of the above problem is also a solution of the following problem, min, . yS x xy Case 2: . From the definition of = x S S, for any , Y we have . Since Y is compact, then ,>0pxy ,= >0 min x yYpxy . Let be a lower bound of f on 0,1 , nY and =1. ,,>, , =1 x xx fxypxy fxypxy fvMINLP . , This means that if > then ,,fxy pxyP >vMINL 1 > . Thus, (6) implies that if , then minimum does not occur in this case. Now, let 0,1 0=. max n x For any 0 >, if , y is an optimal solution of PEN , then from the previous implication we get that Case 2 does not oc cur. From Case 1, we have 0,1 0,1 ,,= =, min min =,. min min nyY x nyS xx fxypxy vPEN , xy pxy fxy Let be an upper bound of f on Then 0,1 . nY ,,. xypxy f Since this relation holds for any 0 > , we have ,=0 xy . Therefore, , y is feasible to INLP . Furthermore, 0,1 0,1 ,,,0 ,= =, min min =, min =. nyS xx n xyYgxy j fxy vPEN fxy xy vMINLP Thus, , y is an optimal solution for both EN and INLP . Theorem 2 shows that if p is an exact penalty function for an NLP problem, then it is also exact for the MINLP problem. Thus, (5) is an exact penalty function for INLP . Now, we show that ,r PEN is exact for INLP , that is, for finite penalty parameter values of r and , ,r PEN and INLP are equivalent. Assumption 2. Assumption 1(i) holds for each , namely, for each , n, yJY we have ,<,=1,,,=1,, j i . xyin jl x Theorem 3. Suppose that both Assumption 1 and As sumption hold and p is an exact penalty function for INLP . Then, there exist 0 and 0 r such that for every and 00 r>r>, any solution of ,r PEN also solves INLP and N vM =.INLP ,r Proof. Since p is an exact penalty function for vPE INLP , there exists a 0 such that for each 0 >, any solu tion for ,r N PE also solves INLP and x vMINLP f For any >, we have Copyright © 2011 SciRes. AJOR
R. ALIAKBARI SHANDIZ ET AL. Copyright © 2011 SciRes. AJOR 189 =vPEN vMINLP PEN. Theorem 1 on implies that there exists an 0 such that for every , any solution of is also a solution of ,r 0 >rrr ,r PEN PEN and ,r vP =vPENEN Therefore, for every 0 > and 0 any solution of also solves >,rr ,r PEN INLP MINLP and ,r vPEN =v. 5. Summary We proposed an exact penalty approach for solving mixed integer nonlinear programming (MINLP) prob lems and showed how to convert a MINLP problem to a finite sequence of NLP problems. We stated conditions for exactness of a penalty function for MINLP problems and showed how exact penalty functions for NLP prob lems could serve as exact penalty functions for MINLP problems. 6. Acknowledgements The second author thanks the support of Research Coun cil of Sharif University of Technology. 7. References [1] M. Ragavachari, “On Connections between ZeroOne Integer Programming and Concave Programming under Linear Constraints,” Operations Research, Vol. 17, No. 4, 1969, pp. 680684. doi:10.1287/opre.17.4.680 [2] J. Cai and G. Thierauf, “Discrete Optimization of Struc tures Using an Improved Penalty Function Method,” En gineering Optimization, Vol. 21, No. 4, 1993, pp. 293306. doi:10.1080/03052159308940981 [3] J. F. Fu, R. G. Fenton and W. L. Cleghorn, “A Mixed IntegerDiscreteContinuous Programming Method and Its Application to Engineering Design Optimization,” Engineering Optimization, Vol. 17, No. 4, 1991, pp. 263 280. doi:10.1080/03052159108941075 [4] S. S. Rao, “Engineering Optimization: Theory and Prac tice,” 4th Edition, Wiley, Hoboken, 2009. [5] D. K. Shin, Z. Gürdal and O. H. Griffin Jr., “A Penalty Approach for Nonlinear Optimization with Discrete De sign Variables,” Engineering Optimization, Vol. 16, No. 1, 1990, pp. 2942. doi:10.1080/03052159008941163 [6] W. Murray and K. M. Ng, “An Algorithm for Nonlinear Optimization Problems with Binary Variables,” Compu tational Optimization and Applications, Vol. 47, No. 2, 2008, pp. 257288. doi:10.1007/s1058900892181 [7] F. Giannessi and F. Niccolucci, “Connections between Nonlinear and Integer Programming Problems,” Sympo sia Mathematica, Vol. 19, 1976, pp. 161176. [8] F. Rinaldi, “New Results on the Equivalence between ZeroOne Programming and Continuous Concave Pro gramming,” Optimation Letters, Vol. 3, No. 3, 2009, pp. 377386. doi:10.1007/s115900090117x [9] S. Lucidi and F. Rinaldi, “Exact Penalty Functions for Nonlinear Integer Programming Problems,” Journal of Optimization Theory and Applications, Vol. 145, No. 3, 2010, pp. 479488. doi:10.1007/s1095701097007 [10] D. Li and X. Sun, “Nonlinear Integer Programming,” Springer, New York, 2006. [11] D. G. Luenberger and Y. Ye, “Linear and Nonlinear Pro gramming,” 3rd Edition, Springer, New York, 2008.
