×

zbMATH — the first resource for mathematics

On the generalization of ECP and OA methods to nonsmooth convex MINLP problems. (English) Zbl 1295.90022
Summary: In this article, generalization of some mixed-integer nonlinear programming algorithms to cover convex nonsmooth problems is studied. In the extended cutting plane method, gradients are replaced by the subgradients of the convex function and the resulting algorithm shall be proved to converge to a global optimum. It is shown through a counterexample that this type of generalization is insufficient with certain versions of the outer approximation algorithm. However, with some modifications to the outer approximation method a special type of nonsmooth functions for which the subdifferential at any point is a convex combination of a finite number of subgradients at the point can be considered. Numerical results with extended cutting plane method are also reported.

MSC:
90C11 Mixed integer programming
90C25 Convex programming
90C56 Derivative-free methods and methods using generalized derivatives
PDF BibTeX Cite
Full Text: DOI
References:
[1] DOI: 10.1016/S0167-6377(02)00231-6 · Zbl 1046.90057
[2] DOI: 10.1007/s10107-004-0553-4 · Zbl 1066.90079
[3] DOI: 10.1137/0715011 · Zbl 0384.65032
[4] DOI: 10.1007/BF02592064 · Zbl 0619.90052
[5] DOI: 10.1007/BF01581153 · Zbl 0833.90088
[6] Fletcher R, Numerical experience with lower bounds for MIQP branch-and-bound (1995) · Zbl 0912.90225
[7] DOI: 10.1080/02331939208843808 · Zbl 0817.90076
[8] DOI: 10.1023/A:1021039126272 · Zbl 1035.90050
[9] Hiriart-Urruty J-B, Convex Analysis and Minimization Algorithms I (1993)
[10] DOI: 10.1137/0108053 · Zbl 0098.12104
[11] DOI: 10.1137/0327039 · Zbl 0694.65026
[12] DOI: 10.1007/BF01585731 · Zbl 0697.90060
[13] DOI: 10.1023/A:1022650107080 · Zbl 0955.90102
[14] DOI: 10.1080/10556780290027828 · Zbl 1050.90027
[15] DOI: 10.1142/1493
[16] DOI: 10.1016/0098-1354(92)80028-8
[17] DOI: 10.1137/040603875 · Zbl 1114.90093
[18] Schramm H, Ph.D. thesis, Bayreuther Mathematische Schriften (1989)
[19] DOI: 10.1137/0802008 · Zbl 0761.90090
[20] DOI: 10.1007/978-3-642-82118-9
[21] DOI: 10.1007/0-306-48332-7_126
[22] DOI: 10.1016/0098-1354(95)87027-X
[23] Womersley RS, Ph.D. thesis (1981)
[24] DOI: 10.1016/0255-2701(89)80035-2
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.