Authors:D. Gerard; M. Köppe; Q. Louveaux Pages: 685 - 711 Abstract: We study the spatial Brand-and-Bound algorithm for the global optimization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch-and-Bound-based solvers use a non-global solver at a few nodes to try to find better incumbents. We show that it is possible to improve the branching rules and the node priority by exploiting the solutions from the non-global solver. We also propose several smart adaptive strategies to choose when to run the non-global solver. We show that despite the time spent in solving more NLP problems in the nodes, the new strategies enable the algorithm to find the first good incumbents faster and to prove the global optimality faster. Numerous easy, medium size as well as hard NLP instances from the Coconut library are benchmarked. All experiments are run using the open source solver Couenne. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0503-3 Issue No:Vol. 68, No. 4 (2017)

Authors:Rudolf Scitovski Pages: 713 - 727 Abstract: In this paper, we consider a global optimization problem for a symmetric Lipschitz continuous function \(g:[a,b]^k\rightarrow {\mathbb {R}}\) , whose domain \([a,b]^k\subset {\mathbb {R}}^k\) consists of k! hypertetrahedrons of the same size and shape, in which function g attains equal values. A global minimum can therefore be searched for in one hypertetrahedron only, but then this becomes a global optimization problem with linear constraints. Apart from that, some known global optimization algorithms in standard form cannot be applied to solving the problem. In this paper, it is shown how this global optimization problem with linear constraints can easily be transformed into a global optimization problem on hypercube \([0,1]^k\) , for the solving of which an applied DIRECT algorithm in standard form is possible. This approach has a somewhat lower efficiency than known global optimization methods for symmetric Lipschitz continuous functions (such as SymDIRECT or DISIMPL), but, on the other hand, this method allows for the use of publicly available and well developed computer codes for solving a global optimization problem on hypercube \([0,1]^k\) (e.g. the DIRECT algorithm). The method is illustrated and tested on standard symmetric functions and very demanding center-based clustering problems for the data that have only one feature. An application to the image segmentation problem is also shown. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0510-4 Issue No:Vol. 68, No. 4 (2017)

Authors:Abay Molla Kassa; Semu Mitiku Kassa Pages: 729 - 747 Abstract: In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0502-4 Issue No:Vol. 68, No. 4 (2017)

Authors:Rui Diao; Ya-Feng Liu; Yu-Hong Dai Pages: 749 - 775 Abstract: The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals \(\left\{ [a_{i,1},a_{i,2}]\right\} _{i=1}^n\) and a target integer T, the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target T but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0–1 knapsack problem. We also identify several subclasses of the ISSP which are polynomial time solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme for solving the general ISSP problem. The time and space complexities of the proposed scheme are \({{\mathcal {O}}}\left( n \max \left\{ 1 / \epsilon ,\log n\right\} \right) \) and \(\mathcal{O}\left( n+1/\epsilon \right) ,\) respectively, where \(\epsilon \) is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with \(n=100{,}000\) and \(\epsilon =0.1\%\) within 1 s. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0514-0 Issue No:Vol. 68, No. 4 (2017)

Authors:Rundong Du; Da Kuang; Barry Drake; Haesun Park Pages: 777 - 798 Abstract: The importance of unsupervised clustering and topic modeling is well recognized with ever-increasing volumes of text data available from numerous sources. Nonnegative matrix factorization (NMF) has proven to be a successful method for cluster and topic discovery in unlabeled data sets. In this paper, we propose a fast algorithm for computing NMF using a divide-and-conquer strategy, called DC-NMF. Given an input matrix where the columns represent data items, we build a binary tree structure of the data items using a recently-proposed efficient algorithm for computing rank-2 NMF, and then gather information from the tree to initialize the rank-k NMF, which needs only a few iterations to reach a desired solution. We also investigate various criteria for selecting the node to split when growing the tree. We demonstrate the scalability of our algorithm for computing general rank-k NMF as well as its effectiveness in clustering and topic modeling for large-scale text data sets, by comparing it to other frequently utilized state-of-the-art algorithms. The value of the proposed approach lies in the highly efficient and accurate method for initializing rank-k NMF and the scalability achieved from the divide-and-conquer approach of the algorithm and properties of rank-2 NMF. In summary, we present efficient tools for analyzing large-scale data sets, and techniques that can be generalized to many other data analytics problem domains along with an open-source software library called SmallK. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0515-z Issue No:Vol. 68, No. 4 (2017)

Authors:Radosław Rudek Pages: 799 - 814 Abstract: In this paper, we analyse the parallel machine makespan minimization problem with the general sum of processing time based learning or aging effects. First, we prove that an optimal solution to the single machine case can be found by priority rules. Next, for the considered parallel machine problem, we construct the exact dynamic programming algorithm that can operate on real-valued job processing times, which is the only exact algorithm for the analysed problem. The computational analysis confirms that it can solve optimally moderate problem instances. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0509-x Issue No:Vol. 68, No. 4 (2017)

Authors:Tao Sun; Hao Jiang; Lizhi Cheng Pages: 815 - 826 Abstract: In this paper, we investigate the convergence of the proximal iteratively reweighted algorithm for a class of nonconvex and nonsmooth problems. Such problems actually include numerous models in the area of signal processing and machine learning research. Two extensions of the algorithm are also studied. We provide a unified scheme for these three algorithms. With the Kurdyka–Łojasiewicz property, we prove that the unified algorithm globally converges to a critical point of the objective function. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0507-z Issue No:Vol. 68, No. 4 (2017)

Authors:Nobuo Namura; Koji Shimoyama; Shigeru Obayashi Pages: 827 - 849 Abstract: The Kriging surrogate model, which is frequently employed to apply evolutionary computation to real-world problems, with a coordinate transformation of the design space is proposed to improve the approximation accuracy of objective functions with correlated design variables. The coordinate transformation is conducted to extract significant trends in the objective function and identify the suitable coordinate system based on either one of two criteria: likelihood function or estimated gradients of the objective function to each design variable. Compared with the ordinary Kriging model, the proposed methods show higher accuracy in the approximation of various test functions. The proposed method based on likelihood shows higher accuracy than that based on gradients when the number of design variables is less than six. The latter method achieves higher accuracy than the ordinary Kriging model even for high-dimensional functions and is applied to an airfoil design problem with spline curves as an example with correlated design variables. This method achieves better performances not only in the approximation accuracy but also in the capability to explore the optimal solution. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0516-y Issue No:Vol. 68, No. 4 (2017)

Authors:Chang Fang; Xinbao Liu; Panos M. Pardalos; Jianyu Long; Jun Pei; Chao Zuo Pages: 851 - 878 Abstract: Hybrid manufacturing and remanufacturing systems have become a topic of considerable interest in the advanced manufacturing industry due in part to the profit and cost saving by reusing remaufacturable parts in the end-of-use products. In this paper, we investigate a production planning problem in such a hybrid system with the integration of resource capacity planning that is shared by both manufacturing and remanufacturing processes. Due to the uncertain nature in practice, both new and remanufactured product demands are stochastic. Taking a scenario-based approach to express the stochastic demands according to the historical data, we formulate the stochastic aggregate production planning problem as a mixed integer linear programming (MILP) model. Based on the Lagrangian relaxation (LR) technique, the MILP model is decomposed into four sets of sub-problems. For these sub-problems, four heuristic procedures are developed, respectively. Then, a LR based heuristic for the main problem is proposed and further tested on a large set of problem instances. The results show that the algorithm generates solutions very close to optimums in an acceptable time. At last, the impact of demands uncertainty on the solution is analyzed by the sensitivity analysis on a number of scenarios. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0500-6 Issue No:Vol. 68, No. 4 (2017)

Authors:Michel Minoux; Riadh Zorgati Pages: 879 - 898 Abstract: The present paper investigates Gaussian bilateral inequalities in view of solving related probability maximization problems. Since the function f representing the probability of satisfaction of a given Gaussian bilateral inequality is not concave everywhere, we first state and prove a necessary and sufficient condition for negative semi-definiteness of the Hessian. Then, the (nonconvex) problem of globally maximizing f over a given polyhedron in \(\mathbb {R}^{n}\) is adressed, and shown to be polynomial-time solvable, thus yielding a new-comer to the (short) list of nonconvex global optimization problems which can be solved exactly in polynomial time. Application to computing upper bounds to the maximum joint probability of satisfaction of a set of m independent Gaussian bilateral inequalities is discussed and computational results are reported. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0501-5 Issue No:Vol. 68, No. 4 (2017)

Authors:Marius Durea; Radu Strugariu Pages: 899 - 923 Abstract: In this paper we use a double penalization procedure in order to reduce a set-valued optimization problem with functional constraints to an unconstrained one. The penalization results are given in several cases: for weak and strong solutions, in global and local settings, and considering two kinds of epigraphical mappings of the set-valued map that defines the constraints. Then necessary and sufficient conditions are obtained separately in terms of Bouligand derivatives of the objective and constraint mappings. PubDate: 2017-08-01 DOI: 10.1007/s10898-017-0505-1 Issue No:Vol. 68, No. 4 (2017)

Authors:Kaisa Joki; Adil M. Bagirov; Napsu Karmitsa; Marko M. Mäkelä Pages: 501 - 535 Abstract: In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an \(\varepsilon \) -critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems. PubDate: 2017-07-01 DOI: 10.1007/s10898-016-0488-3 Issue No:Vol. 68, No. 3 (2017)

Authors:Nadia Martinez; Hadis Anahideh; Jay M. Rosenberger; Diana Martinez; Victoria C. P. Chen; Bo Ping Wang Pages: 563 - 586 Abstract: Multivariate adaptive regression spline (MARS) is a statistical modeling method used to represent a complex system. More recently, a version of MARS was modified to be piecewise linear. This paper presents a mixed integer linear program, called MARSOPT, that optimizes a non-convex piecewise linear MARS model subject to constraints that include both linear regression models and piecewise linear MARS models. MARSOPT is customized for an automotive crash safety system design problem for a major US automaker and solved using branch and bound. The solutions from MARSOPT are compared with those from customized genetic algorithms. PubDate: 2017-07-01 DOI: 10.1007/s10898-016-0494-5 Issue No:Vol. 68, No. 3 (2017)

Authors:Hongtan Sun; Thomas C. Sharkey Pages: 623 - 640 Abstract: In this paper, we provide approximation guarantees of algorithms for the fractional optimization problems arising in the dispatching rules from recent literature for Integrated Network Design and Scheduling problems. These fractional optimization problem are proved to be NP-hard. The approximation guarantees are based both on the number of arcs in the network and on the number of machines in the scheduling environment. We further demonstrate, by example, the tightness of the factors for these approximation algorithms. PubDate: 2017-07-01 DOI: 10.1007/s10898-017-0498-9 Issue No:Vol. 68, No. 3 (2017)

Authors:Jared T. Guilbeau; Md. Istiaq Hossain; Sam D. Karhbet; Ralph Baker Kearfott; Temitope S. Sanusi; Lihong Zhao Pages: 677 - 683 Abstract: Linear program solvers sometimes fail to find a good approximation to the optimum value, without indicating possible failure. However, it may be important to know how close the value such solvers return is to an actual optimum, or even to obtain mathematically rigorous bounds on the optimum. In a seminal 2004 paper, Neumaier and Shcherbina, propose a method by which such rigorous lower bounds can be computed; we now have significant experience with this method. Here, we review the technique. We point out typographical errors in two formulas in the original publication, and illustrate their impact. Separately, implementers and practitioners can also easily make errors. To help implementers avoid such problems, we cite a technical report where we explain things to mind and where we present rigorous bounds corresponding to alternative formulations of the linear program. PubDate: 2017-07-01 DOI: 10.1007/s10898-016-0489-2 Issue No:Vol. 68, No. 3 (2017)

Authors:Xiucui Guan; Xinyan He; Panos M. Pardalos; Binwu Zhang Abstract: The inverse max \(+\) sum spanning tree (MSST) problem is considered by modifying the sum-cost vector under the Hamming Distance. On an undirected network G(V, E, w, c), a weight w(e) and a cost c(e) are prescribed for each edge \(e\in E\) . The MSST problem is to find a spanning tree \(T^*\) which makes the combined weight \(\max _{e\in T}w(e)+\sum _{e\in T}c(e)\) as small as possible. It can be solved in \(O(m\log n)\) time, where \(m:= E \) and \(n:= V \) . Whereas, in an inverse MSST problem, a given spanning tree \(T_0\) of G is not an optimal MSST. The sum-cost vector c is to be modified to \(\bar{c}\) so that \(T_0\) becomes an optimal MSST of the new network \(G(V,E,w,\bar{c})\) and the cost \(\Vert \bar{c}-c\Vert \) can be minimized under Hamming Distance. First, we present a mathematical model for the inverse MSST problem and a method to check the feasibility. Then, under the weighted bottleneck-type Hamming distance, we design a binary search algorithm whose time complexity is \(O(m log^2 n)\) . Next, under the unit sum-type Hamming distance, which is also called \(l_0\) norm, we show that the inverse MSST problem (denoted by IMSST \(_0\) ) is \(NP-\) hard. Assuming \({\textit{NP}} \nsubseteq {\textit{DTIME}}(m^{{\textit{poly}} \log m})\) , the problem IMSST \(_0\) is not approximable within a factor of \(2^{\log ^{1-\varepsilon } m}\) , for any \(\varepsilon >0\) . Finally, We consider the augmented problem of IMSST \(_0\) (denoted by AIMSST \(_0\) ), whose objective function is to multiply the \(l_0\) norm \(\Vert \beta \Vert _0\) by a sufficiently large number M plus the \(l_1\) norm \(\Vert \beta \Vert _1\) . We show that the augmented problem and the \(l... PubDate: 2017-07-15 DOI: 10.1007/s10898-017-0546-5

Authors:D. Russell Luke; Shoham Sabach; Marc Teboulle; Kobi Zatlawey Abstract: We study the single source localization problem which consists of minimizing the squared sum of the errors, also known as the maximum likelihood formulation of the problem. The resulting optimization model is not only nonconvex but is also nonsmooth. We first derive a novel equivalent reformulation as a smooth constrained nonconvex minimization problem. The resulting reformulation allows for deriving a delightfully simple algorithm that does not rely on smoothing or convex relaxations. The proposed algorithm is proven to generate bounded iterates which globally converge to critical points of the original objective function of the source localization problem. Numerical examples are presented to demonstrate the performance of our algorithm. PubDate: 2017-07-14 DOI: 10.1007/s10898-017-0545-6

Authors:Dawid Tarłowski Abstract: This paper focuses on the convergence rate problem of general Markov search for global minimum. Many of existing methods are designed for overcoming a very hard problem which is how to efficiently localize and approximate the global minimum of the multimodal function f while all information which can be used are the f-values evaluated for generated points. Because such methods use poor information on f, the following problem may occur: the closer to the optimum, the harder to generate a “better” (in sense of the cost function) state. This paper explores this issue on theoretical basis. To do so the concept of lazy convergence for a globally convergent method is introduced: a globally convergent method is called lazy if the probability of generating a better state from one step to another goes to zero with time. Such issue is the cause of very undesired convergence properties. This paper shows when an optimization method has to be lazy and the presented general results cover, in particular, the class of simulated annealing algorithms and monotone random search. Furthermore, some attention is put on accelerated random search and evolution strategies. PubDate: 2017-07-07 DOI: 10.1007/s10898-017-0544-7

Authors:Bin Liu Abstract: We propose a global optimization algorithm based on the sequential Monte Carlo (SMC) sampling framework. In this framework, the objective function is normalized to be a probabilistic density function (pdf), based on which a sequence of annealed target pdfs is designed to asymptotically converge on the set of global optimum. A sequential importance sampling procedure is performed to simulate the resulting targets and the maxima of the objective function are assessed from the yielded samples. The disturbing issue lies in the design of the importance sampling (IS) pdf, which crucially influences the IS efficiency. We propose an approach to design the IS pdf by embedding a posterior exploration (PE) procedure into each iteration of the SMC framework. The PE procedure can explore the important regions of the solution space supported by the target pdf. A byproduct of the PE procedure is an adaptive mechanism to design the annealing temperature schedule. We compare the proposed algorithm with related existing methods using a dozen benchmark functions. The result demonstrates the appealing properties of our algorithm. PubDate: 2017-07-05 DOI: 10.1007/s10898-017-0543-8

Authors:Fabián Flores-Bazán; William Echegaray; Fernando Flores-Bazán; Eladio Ocaña Abstract: Primal or dual strong-duality (or min-sup, inf-max duality) in nonconvex optimization is revisited in view of recent literature on the subject, establishing, in particular, new characterizations for the second case. This gives rise to a new class of quasiconvex problems having zero duality gap or closedness of images of vector mappings associated to those problems. Such conditions are described for the classes of linear fractional functions and that of quadratic ones. In addition, some applications to nonconvex quadratic optimization problems under a single inequality or equality constraint, are presented, providing new results for the fulfillment of zero duality gap or dual strong-duality. PubDate: 2017-07-01 DOI: 10.1007/s10898-017-0542-9