Authors:Peter Kirst; Fabian Rigterink; Oliver Stein Pages: 283 - 307 Abstract: Abstract We propose a new branch-and-bound framework for global optimization of disjunctive programs with general logical expressions. We do not assume the logical expressions to be in any normal form, and, under slightly stronger assumptions, we allow the use of negations and implications. In contrast to the widely used reformulation as a mixed-integer program, we compute the lower bounds and evaluate the logical expression in one step. Thus, we reduce the size of the problem and work exclusively with continuous variables, which is computationally advantageous. We present preliminary numerical results as proof of concept. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0526-9 Issue No:Vol. 69, No. 2 (2017)

Authors:Amir Beck; Dror Pan Pages: 309 - 342 Abstract: Abstract We suggest a branch and bound algorithm for solving continuous optimization problems where a (generally nonconvex) objective function is to be minimized under nonconvex inequality constraints which satisfy some specific solvability assumptions. The assumptions hold for some special cases of nonconvex quadratic optimization problems. We show how the algorithm can be applied to the problem of minimizing a nonconvex quadratic function under ball, out-of-ball and linear constraints. The main tool we utilize is the ability to solve in polynomial computation time the minimization of a general quadratic under one Euclidean sphere constraint, namely the so-called trust region subproblem, including the computation of all local minimizers of that problem. Application of the algorithm on sparse source localization problems is presented. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0521-1 Issue No:Vol. 69, No. 2 (2017)

Authors:Sattar Sattari; Mohammad Izadi Pages: 343 - 367 Abstract: Abstract Given a triangulation of a point set on the plane, dilation of any pair of the points is the ratio of their shortest path length to their Euclidean distance. The maximum dilation over all pairs of points is called the dilation of this triangulation. Minimum dilation triangulation problem seeks a triangulation with the least possible dilation of an input point set. For this problem no polynomial time algorithm is known. We present an exact algorithm based on a branch and bound method for finding minimum dilation triangulations. This deterministic algorithm after generating an initial solution, iteratively computes a lower bound for the answer and then applies a branch and bound method to find a better solution. It also uses a local search method to improve the initial solution and the obtained solution of the branch and bound method. We implemented our algorithm and conducted computational experiments on some benchmark instances. The efficacy of the approach is demonstrated by comparing its results with two other published methods. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0517-x Issue No:Vol. 69, No. 2 (2017)

Authors:Andreas Löhne; Andrea Wagner Pages: 369 - 385 Abstract: Abstract A class of non-convex optimization problems with DC objective function is studied, where DC stands for being representable as the difference \(f=g-h\) of two convex functions g and h. In particular, we deal with the special case where one of the two convex functions g or h is polyhedral. In case g is polyhedral, we show that a solution of the DC program can be obtained from a solution of an associated polyhedral projection problem. In case h is polyhedral, we prove that a solution of the DC program can be obtained by solving a polyhedral projection problem and finitely many convex programs. Since polyhedral projection is equivalent to multiple objective linear programming (MOLP), a MOLP solver (in the second case together with a convex programming solver) can be used to solve instances of DC programs with polyhedral component. Numerical examples are provided, among them an application to locational analysis. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0519-8 Issue No:Vol. 69, No. 2 (2017)

Authors:K. Boufi; A. Roubi Pages: 387 - 426 Abstract: Abstract In this paper we analyze the method of centers for generalized fractional programs, with further insights. The introduced method is based on a different parametric auxiliary problem than Dinkelbach’s type. With the help of this auxiliary parametric problem, we present a new dual for convex generalized fractional programs. We then propose an algorithm to solve this problem, and subsequently the original primal program. The proposed algorithm generates a sequence of dual values that converges from below to the optimal value. The method also generates a bounded sequence of dual solutions whose every accumulation point is a solution of the dual problem. The rate of convergence is shown to be at least linear. In the penultimate section, we specialize the results obtained for the linear case. The computational results show that the different variants of our algorithms, primal as well as dual, are competitive. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0523-z Issue No:Vol. 69, No. 2 (2017)

Authors:M. Ruiz Galán Pages: 427 - 442 Abstract: Abstract In this paper we are concerned with a Gordan-type theorem involving an arbitrary number of inequality functions. We not only state its validity under a weak convexity assumption on the functions, but also show it is an optimal result. We discuss generalizations of several recent results on nonlinear quadratic optimization, as well as a formula for the Fenchel conjugate of the supremum of a family of functions, in order to illustrate the applicability of that theorem of the alternative. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0525-x Issue No:Vol. 69, No. 2 (2017)

Authors:Ville-Pekka Eronen; Jan Kronqvist; Tapio Westerlund; Marko M. Mäkelä; Napsu Karmitsa Pages: 443 - 459 Abstract: Abstract In this paper, we generalize the extended supporting hyperplane algorithm for a convex continuously differentiable mixed-integer nonlinear programming problem to solve a wider class of nonsmooth problems. The generalization is made by using the subgradients of the Clarke subdifferential instead of gradients. Consequently, all the functions in the problems are assumed to be locally Lipschitz continuous. The algorithm is shown to converge to a global minimum of an MINLP problem if the objective function is convex and the constraint functions are \(f^{\circ }\) -pseudoconvex. With some additional assumptions, the constraint functions may be \(f^{\circ }\) -quasiconvex. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0528-7 Issue No:Vol. 69, No. 2 (2017)

Authors:Benjamin Martin; Marco Correia; Jorge Cruz Pages: 461 - 484 Abstract: Abstract Reliability-based optimization problems are optimization problems considering a constraint that measures reliability of the modelled system: the probability of a safety event with respect to controllable decision variables and uncertain random variables. Most solving approaches use approximate techniques for evaluating this reliability constraint. As a consequence, the reliability of the computed optimal decision is not guaranteed. In this paper, we investigate an interval-based Branch & Bound for solving globally reliability-based optimization problems with numerical guarantee. It combines an interval Branch & Bound framework with a certified reliability analysis technique. This technique considers the reliability constraint and induced safety region modelled within Probabilistic Continuous Constraint Programming paradigm. The certified reliability analysis is numerically handled by an interval quadrature algorithm. In addition, a new interval quadrature function for two random variables, based on linear models of the safety region is described. Two implementations of the Branch & Bound, which differ on how the certified reliability analysis is handled throughout the optimization process, are presented. A numerical study of these two variants shows the relevance of the interval linear model-based quadrature function. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0529-6 Issue No:Vol. 69, No. 2 (2017)

Authors:Gabriele Eichfelder; Corinna Krüger; Anita Schöbel Pages: 485 - 510 Abstract: Abstract In many real-world optimization problems, a solution cannot be realized in practice exactly as computed, e.g., it may be impossible to produce a board of exactly 3.546 mm width. Whenever computed solutions are not realized exactly but in a perturbed way, we speak of decision uncertainty. We study decision uncertainty in multiobjective optimization problems and we propose the concept of decision robust efficiency for evaluating the robustness of a solution in this case. This solution concept is defined by using the framework of set-valued maps. We prove that convexity and continuity are preserved by the resulting set-valued maps. Moreover, we obtain specific results for particular classes of objective functions that are relevant for solving the set-valued problem. We furthermore prove that decision robust efficient solutions can be found by solving a deterministic problem in case of linear objective functions. We also investigate the relationship of the proposed concept to other concepts in the literature. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0518-9 Issue No:Vol. 69, No. 2 (2017)

Authors:Zhongyi Jiang; Qiying Hu; Xiaojin Zheng Pages: 511 - 523 Abstract: Abstract Order-value optimization problems and low order-value optimization problems are new subclasses of optimization problems which arise from decision-making problems under uncertainty and robust estimation problems. In this paper, We present KKT necessary and sufficient conditions for low order-value optimization problems under convexity hypothesis in this paper. A smooth reformulation of low order-value optimization problems are presented whose local solutions satisfy the KKT necessary conditions. we prove that order-value optimization problems is NP-hard in the strong sense even when constraints are polytope. Order-value optimization problems and low order-value optimization problems are NP-hard even when their presentation functions are linear and constraints are polytope. Some special cases that could be solved in polynomial time are proposed. PubDate: 2017-10-01 DOI: 10.1007/s10898-017-0520-2 Issue No:Vol. 69, No. 2 (2017)

Authors:Christoph Buchheim; Marianna De Santis; Francesco Rinaldi; Long Trieu Abstract: Abstract We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. We address this class of convex mixed-integer minimization problems by designing a branch-and-bound algorithm, where at each node, the continuous relaxation is solved by a non-monotone Frank–Wolfe type algorithm with away-steps. Experimental results on portfolio optimization problems show that our approach can outperform the MISOCP solver of CPLEX 12.6 for instances where a linear risk-weighting function is considered. PubDate: 2017-09-20 DOI: 10.1007/s10898-017-0571-4

Authors:Jian Lv; Li-Ping Pang; Fan-Yun Meng Abstract: Abstract We propose an inexact proximal bundle method for constrained nonsmooth nonconvex optimization problems whose objective and constraint functions are known through oracles which provide inexact information. The errors in function and subgradient evaluations might be unknown, but are merely bounded. To handle the nonconvexity, we first use the redistributed idea, and consider even more difficulties by introducing inexactness in the available information. We further examine the modified improvement function for a series of difficulties caused by the constrained functions. The numerical results show the good performance of our inexact method for a large class of nonconvex optimization problems. The approach is also assessed on semi-infinite programming problems, and some encouraging numerical experiences are provided. PubDate: 2017-09-14 DOI: 10.1007/s10898-017-0565-2

Authors:Manlio Gaudioso; Giovanni Giallombardo; Giovanna Miglionico; Adil M. Bagirov Abstract: Abstract We introduce a proximal bundle method for the numerical minimization of a nonsmooth difference-of-convex (DC) function. Exploiting some classic ideas coming from cutting-plane approaches for the convex case, we iteratively build two separate piecewise-affine approximations of the component functions, grouping the corresponding information in two separate bundles. In the bundle of the first component, only information related to points close to the current iterate are maintained, while the second bundle only refers to a global model of the corresponding component function. We combine the two convex piecewise-affine approximations, and generate a DC piecewise-affine model, which can also be seen as the pointwise maximum of several concave piecewise-affine functions. Such a nonconvex model is locally approximated by means of an auxiliary quadratic program, whose solution is used to certify approximate criticality or to generate a descent search-direction, along with a predicted reduction, that is next explored in a line-search setting. To improve the approximation properties at points that are far from the current iterate a supplementary quadratic program is also introduced to generate an alternative more promising search-direction. We discuss the main convergence issues of the line-search based proximal bundle method, and provide computational results on a set of academic benchmark test problems. PubDate: 2017-09-13 DOI: 10.1007/s10898-017-0568-z

Authors:Zai-Yun Peng; Jian-Wen Peng; Xian-Jun Long; Jen-Chih Yao Abstract: Abstract This paper is concerned with the stability of semi-infinite vector optimization problems (SVO). Under weak assumptions, we establish sufficient conditions of the Berge-lower semicontinuity and lower Painlev \(\acute{e}\) –Kuratowski convergence of weak efficient solutions for (SVO) under functional perturbations of both objective functions and constraint sets. Some examples are given to illustrate that our results are new and interesting. PubDate: 2017-09-12 DOI: 10.1007/s10898-017-0553-6

Authors:Ignacio Araya; Bertrand Neveu Abstract: Abstract Smear-based variable selection strategies are well-known and commonly used by branch-and-prune interval-based solvers. They estimate the impact of the variables on each constraint of the system by using the partial derivatives and the sizes of the variable domains. Then they aggregate these values, in some way, to estimate the impact of each variable on the whole system. The variable with the greatest impact is then selected. A problem of these strategies is that they, generally, consider all constraints equally important. In this work, we propose a new variable selection strategy which first weights the constraints by using the optimal Lagrangian multipliers of a linearization of the original problem. Then, the impact of the variables is computed with a typical smear-based function but taking into account the weights of the constraints. The strategy isg tested on a set of well-known benchmark instances outperforming significantly the classical variable selection strategies. PubDate: 2017-09-12 DOI: 10.1007/s10898-017-0569-y

Authors:Huan Gao; Haibin Zhang; Zhibao Li; Kai Tu Abstract: Abstract Partially sparse recovery problem is a special sparse recovery optimization problem with part of the support of the solution is known in advance. Such a problem is closely related to the problems on compressive sensing where the \(l_1\) -norm of the whole solution vector is minimized. In this paper, we propose the partial range space property to obtain some uniqueness conditions on the solution of the partially sparse recovery problem, it is somewhat stronger than the range space property for general sparse recovery problem. And any pair of solution to partial \(l_0\) -minimization problem satisfying the partial range space property is also the unique solution to partial \(l_1\) -minimization problem under mild condition. PubDate: 2017-09-12 DOI: 10.1007/s10898-017-0567-0

Abstract: Abstract This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively. PubDate: 2017-09-08 DOI: 10.1007/s10898-017-0563-4

Authors:Chenchen Wu; Dachuan Xu; Dongmei Zhang; Peng Zhang Abstract: Abstract In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based \((3+\epsilon )\) -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a \( (4+ 1/ (e-1) +\epsilon )\) -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately. PubDate: 2017-09-04 DOI: 10.1007/s10898-017-0566-1

Authors:Taoran Fu; Bo Jiang; Zhening Li Abstract: Abstract Complex polynomial optimization has recently gained more attention in both theory and practice. In this paper, we study optimization of a real-valued general conjugate complex form over various popular constraint sets including the m-th roots of complex unity, the complex unit circle, and the complex unit sphere. A real-valued general conjugate complex form is a homogenous polynomial function of complex variables as well as their conjugates, and always takes real values. General conjugate form optimization is a wide class of complex polynomial optimization models, which include many homogenous polynomial optimization in the real domain with either discrete or continuous variables, and Hermitian quadratic form optimization as well as its higher degree extensions. All the problems under consideration are NP-hard in general and we focus on polynomial-time approximation algorithms with worst-case performance ratios. These approximation ratios improve previous results when restricting our problems to some special classes of complex polynomial optimization, and improve or equate previous results when restricting our problems to some special classes of polynomial optimization in the real domain. The algorithms are based on tensor relaxation and random sampling. Our novel technical contributions are to establish the first set of probability lower bounds for random sampling over the m-th root of unity, the complex unit circle, and the complex unit sphere, and to propose the first polarization formula linking general conjugate forms and complex multilinear forms. Some preliminary numerical experiments are conducted to show good performance of the proposed algorithms. PubDate: 2017-09-02 DOI: 10.1007/s10898-017-0561-6

Authors:Wei-Kun Chen; Liang Chen; Mu-Ming Yang; Yu-Hong Dai Abstract: Abstract Cutting plane methods are an important component in solving the mixed integer programming (MIP). By carefully studying the coefficient strengthening method, which is originally a presolving method, we are able to generalize this method to generate a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. The invariant property of the GCS inequalities is established under bound substitutions. Furthermore, we develop a separation algorithm for finding the violated GCS inequalities for a general mixed integer set. The separation algorithm is proved to have the polynomial time complexity. Extensive numerical experiments are made on standard MIP test sets, which demonstrate the usefulness of the resulting GCS separator. PubDate: 2017-09-02 DOI: 10.1007/s10898-017-0562-5