Authors:Hatim Djelassi; Alexander Mitsos Pages: 227 - 253 Abstract: Abstract A discretization-based algorithm for the global solution of semi-infinite programs (SIPs) is proposed, which is guaranteed to converge to a feasible, \(\varepsilon \) -optimal solution finitely under mild assumptions. The algorithm is based on the hybridization of two existing algorithms. The first algorithm (Mitsos in Optimization 60(10–11):1291–1308, 2011) is based on a restriction of the right-hand side of the constraints of a discretized SIP. The second algorithm (Tsoukalas and Rustem in Optim Lett 5(4):705–716, 2011) employs a discretized oracle problem and a binary search in the objective space. Hybridization of the approaches yields an algorithm, which leverages the strong convergence guarantees and the relatively tight upper bounding problem of the first approach while employing an oracle problem adapted from the second approach to generate cheap lower bounds and adaptive updates to the restriction of the first approach. These adaptive updates help in avoiding a dense population of the discretization. The hybrid algorithm is shown to be superior to its predecessors both theoretically and computationally. A proof of finite convergence is provided under weaker assumptions than the assumptions in the references. Numerical results from established SIP test cases are presented. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0476-7 Issue No:Vol. 68, No. 2 (2017)

Authors:S. Dempe; F. Mefo Kue Pages: 255 - 277 Abstract: Abstract In this article, we consider two classes of discrete bilevel optimization problems which have the peculiarity that the lower level variables do not affect the upper level constraints. In the first case, the objective functions are linear and the variables are discrete at both levels, and in the second case only the lower level variables are discrete and the objective function of the lower level is linear while the one of the upper level can be nonlinear. Algorithms for computing global optimal solutions using Branch and Cut and approximation of the optimal value function of the lower level are suggested. Their convergence is shown and we illustrate each algorithm via an example. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0478-5 Issue No:Vol. 68, No. 2 (2017)

Authors:Alberto Seeger; José Vidal -Nuñez Pages: 279 - 306 Abstract: Abstract Consider a finite collection \(\{\xi _k\}_{k=1}^p\) of vectors in the space \(\mathbb {R}^n\) . The \(\xi _k\) ’s are not to be seen as position points but as directions. This work addresses the problem of computing the ellipsoidal cone of minimal volume that contains all the \(\xi _k\) ’s. The volume of an ellipsoidal cone is defined as the usual n-dimensional volume of a certain truncation of the cone. The central axis of the ellipsoidal cone of minimal volume serves to define the central direction of the datapoints, whereas its volume can be used as measure of dispersion of the datapoints. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0464-y Issue No:Vol. 68, No. 2 (2017)

Authors:Duy Khuong Nguyen; Tu Bao Ho Pages: 307 - 328 Abstract: Abstract Nonnegative matrix factorization (NMF) is a powerful technique for dimension reduction, extracting latent factors and learning part-based representation. For large datasets, NMF performance depends on some major issues such as fast algorithms, fully parallel distributed feasibility and limited internal memory. This research designs a fast fully parallel and distributed algorithm using limited internal memory to reach high NMF performance for large datasets. Specially, we propose a flexible accelerated algorithm for NMF with all its \(L_1\) \(L_2\) regularized variants based on full decomposition, which is a combination of exact line search, greedy coordinate descent, and accelerated search. The proposed algorithm takes advantages of these algorithms to converges linearly at an over-bounded rate \((1-\frac{\mu }{L})(1 - \frac{\mu }{rL})^{2r}\) in optimizing each factor matrix when fixing the other factor one in the sub-space of passive variables, where r is the number of latent components, and \(\mu \) and L are bounded as \(\frac{1}{2} \le \mu \le L \le r\) . In addition, the algorithm can exploit the data sparseness to run on large datasets with limited internal memory of machines, which is is advanced compared to fast block coordinate descent methods and accelerated methods. Our experimental results are highly competitive with seven state-of-the-art methods about three significant aspects of convergence, optimality and average of the iteration numbers. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0471-z Issue No:Vol. 68, No. 2 (2017)

Authors:Veit Elser Pages: 329 - 355 Abstract: Abstract The decomposition of a matrix, as a product of factors with particular properties, is a much used tool in numerical analysis. Here we develop methods for decomposing a matrix C into a product XY, where the factors X and Y are required to minimize their distance from an arbitrary pair \(X_0\) and \(Y_0\) . This type of decomposition, a projection to a matrix product constraint, in combination with projections that impose structural properties on X and Y, forms the basis of a general method of decomposing a matrix into factors with specified properties. Results are presented for the application of these methods to a number of hard problems in exact factorization. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0466-9 Issue No:Vol. 68, No. 2 (2017)

Authors:Lek-Heng Lim Pages: 357 - 366 Abstract: Abstract We show that deciding whether a convex function is self-concordant is in general an intractable problem. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0469-6 Issue No:Vol. 68, No. 2 (2017)

Authors:J. M. Martínez; M. Raydan Pages: 367 - 385 Abstract: Abstract In a recent paper, we introduced a trust-region method with variable norms for unconstrained minimization, we proved standard asymptotic convergence results, and we discussed the impact of this method in global optimization. Here we will show that, with a simple modification with respect to the sufficient descent condition and replacing the trust-region approach with a suitable cubic regularization, the complexity of this method for finding approximate first-order stationary points is \(O(\varepsilon ^{-3/2})\) . We also prove a complexity result with respect to second-order stationarity. Some numerical experiments are also presented to illustrate the effect of the modification on practical performance. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0475-8 Issue No:Vol. 68, No. 2 (2017)

Authors:T. Bittencourt; O. P. Ferreira Pages: 387 - 411 Abstract: Abstract Extension of concepts and techniques of linear spaces for the Riemannian setting has been frequently attempted. One reason for the extension of such techniques is the possibility to transform some Euclidean non-convex or quasi-convex problems into Riemannian convex problems. In this paper, a version of Kantorovich’s theorem on Newton’s method for finding a singularity of differentiable vector fields defined on a complete Riemannian manifold is presented. In the presented analysis, the classical Lipschitz condition is relaxed using a general majorant function, which enables us to not only establish the existence and uniqueness of the solution but also unify earlier results related to Newton’s method. Moreover, a ball is prescribed around the points satisfying Kantorovich’s assumptions and convergence of the method is ensured for any starting point within this ball. In addition, some bounds for the Q-quadratic convergence of the method, which depends on the majorant function, are obtained. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0472-y Issue No:Vol. 68, No. 2 (2017)

Authors:Jai Rajyaguru; Mario E. Villanueva; Boris Houska; Benoît Chachuat Pages: 413 - 438 Abstract: Abstract This article presents an arithmetic for the computation of Chebyshev models for factorable functions and an analysis of their convergence properties. Similar to Taylor models, Chebyshev models consist of a pair of a multivariate polynomial approximating the factorable function and an interval remainder term bounding the actual gap with this polynomial approximant. Propagation rules and local convergence bounds are established for the addition, multiplication and composition operations with Chebyshev models. The global convergence of this arithmetic as the polynomial expansion order increases is also discussed. A generic implementation of Chebyshev model arithmetic is available in the library MC++. It is shown through several numerical case studies that Chebyshev models provide tighter bounds than their Taylor model counterparts, but this comes at the price of extra computational burden. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0474-9 Issue No:Vol. 68, No. 2 (2017)

Authors:Francesco Cesarone; Fabio Tardella Pages: 439 - 461 Abstract: Abstract Risk Parity (RP), also called equally weighted risk contribution, is a recent approach to risk diversification for portfolio selection. RP is based on the principle that the fractions of the capital invested in each asset should be chosen so as to make the total risk contributions of all assets equal among them. We show here that the Risk Parity approach is theoretically dominated by an alternative similar approach that does not actually require equally weighted risk contribution of all assets but only an equal upper bound on all such risks. This alternative approach, called Equal Risk Bounding (ERB), requires the solution of a nonconvex quadratically constrained optimization problem. The ERB approach, while starting from different requirements, turns out to be strictly linked to the RP approach. Indeed, when short selling is allowed, we prove that an ERB portfolio is actually an RP portfolio with minimum variance. When short selling is not allowed, there is a unique RP portfolio and it contains all assets in the market. In this case, the ERB approach might lead to the RP portfolio or it might lead to portfolios with smaller variance that do not contain all assets, and where the risk contributions of each asset included in the portfolio is strictly smaller than in the RP portfolio. We define a new riskiness index for assets that allows to identify those assets that are more likely to be excluded from the ERB portfolio. With these tools we then provide an exact method for small size nonconvex ERB models and a very efficient and accurate heuristic for larger problems of this type. In the case of a common constant pairwise correlation among all assets, a closed form solution to the ERB model is obtained and used to perform a parametric analysis when varying the level of correlation. The practical advantages of the ERB approach over the RP strategy are illustrated with some numerical examples. Computational experience on real-world and on simulated data confirms accuracy and efficiency of our heuristic approach to the ERB model also in comparison with some state-of-the-art local and global optimization codes. PubDate: 2017-06-01 DOI: 10.1007/s10898-016-0477-6 Issue No:Vol. 68, No. 2 (2017)

Authors:F. Domes; A. Goldsztejn Pages: 1 - 22 Abstract: Abstract The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method. PubDate: 2017-05-01 DOI: 10.1007/s10898-016-0462-0 Issue No:Vol. 68, No. 1 (2017)

Abstract: Abstract In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ( \(w^p\) with \(0<p<1\) ) and their increasing concave relatives. We provide (i) a sufficient condition (which applies to functions more general than root functions) for our smoothing to be increasing and concave, (ii) a proof that when \(p=1/q\) for integers \(q\ge 2\) , our smoothing lower bounds the root function, (iii) substantial progress (i.e., a proof for integers \(2\le q\le 10{,}000\) ) on the conjecture that our smoothing is a sharper bound on the root function than the natural and simpler “shifted root function”, and (iv) for all root functions, a quantification of the superiority (in an average sense) of our smoothing versus the shifted root function near 0. PubDate: 2017-05-25

Abstract: Abstract We study the problem of checking pseudoconvexity of a twice differentiable function on an interval domain. Based on several characterizations of pseudoconvexity of a real function, we propose sufficient conditions for verifying pseudoconvexity on a domain formed by a Cartesian product of real intervals. We carried out numerical experiments to show which methods perform well from two perspectives—the computational complexity and effectiveness of recognizing pseudoconvexity. PubDate: 2017-05-25

Abstract: Abstract In this study, we consider the nadir points of multiobjective integer programming problems. We introduce new properties that restrict the possible locations of the nondominated points necessary for computing the nadir points. Based on these properties, we reduce the search space and propose an exact algorithm for finding the nadir point of multiobjective integer programming problems. We present an illustrative example on a three objective knapsack problem. We conduct computational experiments and compare the performances of two recent algorithms and the proposed algorithm. PubDate: 2017-05-23

Authors:Rohit Kannan; Paul I. Barton Abstract: Abstract Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions. PubDate: 2017-05-11 DOI: 10.1007/s10898-017-0531-z

Authors:Benjamin Martin; Marco Correia; Jorge Cruz 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-05-10 DOI: 10.1007/s10898-017-0529-6

Authors:Giovanni Felici; Kumar Parijat Tripathi; Daniela Evangelista; Mario Rosario Guarracino Abstract: Abstract The analysis of high throughput gene expression patients/controls experiments is based on the determination of differentially expressed genes according to standard statistical tests. A typical bioinformatics approach to this problem is composed of two separate steps: first, a subset of genes with altered expression level is identified; then the pathways which are statistically enriched by those genes are selected, assuming they play a relevant role for the biological condition under study. Often, the set of selected pathways contains elements that are not related to the condition. This is due to the fact that the statistical significance is not sufficient for biological relevance. To overcome these problems, we propose a method based on a large mixed integer program that implements a new feature selection model to simultaneously identify the genes whose over- and under-expressions, combined together, discriminate different cancer subtypes, as well as the pathways that are enriched by these genes. The innovation in this model is the solutions are driven towards the enrichment of pathways. That may indeed introduce a bias in the search; such a bias is counter-balanced by a wide exploration of the solution space, varying the involved parameters in their feasible region, and then using a global optimization approach. The conjoint analysis of the pool of solutions obtained by this exploration should indeed provide a robust final set of genes and pathways, overcoming the potential drawbacks of relying solely on statistical significance. Experimental results on transcriptomes for different types of cancer from the Cancer Genome Atlas are presented. The method is able to identify crisp relations between the considered subtypes of cancer and few selected pathways, eventually validated by the biological analysis. PubDate: 2017-05-09 DOI: 10.1007/s10898-017-0530-0

Authors:Ville-Pekka Eronen; Jan Kronqvist; Tapio Westerlund; Marko M. Mäkelä; Napsu Karmitsa 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-05-04 DOI: 10.1007/s10898-017-0528-7