Abstract: Abstract
This paper presents new techniques for filtering boxes in the presence of an additional quadratic constraint, a problem relevant for branch and bound methods for global optimization and constraint satisfaction. This is done by generating powerful linear and parabolic relaxations from a quadratic constraint and bound constraints, which are then subject to standard constraint propagation techniques. The techniques are often applicable even if the original box is unbounded in some but not all variables. As an auxiliary tool—needed to make our theoretical results implementable in floating-point arithmetic without sacrificing mathematical rigor—we extend the directed Cholesky factorization from Domes and Neumaier (SIAM J Matrix Anal Appl 32:262–285, 2011) to a partial directed Cholesky factorization with pivoting. If the quadratic constraint is convex and the initial bounds are sufficiently wide, the final relaxation and the enclosure are optimal up to rounding errors. Numerical tests show the usefulness of the new factorization methods in the context of filtering. PubDate: 2016-07-01

Abstract: Abstract
This paper discusses the use of splines as constraints in mathematical programming. By combining the mature theory of the B-spline and the widely used branch-and-bound framework a novel spatial branch-and-bound (sBB) method is obtained. The method solves nonconvex mixed-integer nonlinear programming (MINLP) problems with spline constraints to global optimality. A broad applicability follows from the fact that a spline may represent any (piecewise) polynomial and accurately approximate other nonlinear functions. The method relies on a reformulation–convexification technique which results in lifted polyhedral relaxations that are efficiently solved by an LP solver. The method has been implemented in the sBB solver Convex ENvelopes for Spline Optimization (CENSO). In this paper CENSO is compared to several state-of-the-art MINLP solvers on a set of polynomially constrained NLP problems. To further display the versatility of the method a realistic pump synthesis problem of class MINLP is solved with exact and approximated pump characteristics. PubDate: 2016-07-01

Abstract: Abstract
In this paper, we first introduce the notion of cooperative equilibria in multi-leader-multi-follower games, and then establish an existence theorem. Next, we shift out attention to the generic stability of these cooperative equilibria. After studying the class of games satisfying the sufficient conditions of the existence theorem, we identify a dense residual subset of these games whose cooperative equilibria are all essential. PubDate: 2016-07-01

Abstract: Abstract
For a nonlinear program with inequalities and under a Slater constraint qualification, it is shown that the duality between optimal solutions and saddle points for the corresponding Lagrangian is equivalent to the infsup-convexity—a not very restrictive generalization of convexity which arises naturally in minimax theory—of a finite family of suitable functions. Even if we dispense with the Slater condition, it is proven that the infsup-convexity is nothing more than an equivalent reformulation of the Fritz John conditions for the nonlinear optimization problem under consideration. PubDate: 2016-07-01

Abstract: Abstract
Global optimization problems with limited structure (e.g., convexity or differentiability of the objective function) can arise in many fields. One approach to solving these problems is by modeling the evolution of a probability density function over the solution space, similar to the Fokker–Planck equation for diffusions, such that at each time instant, additional weight is given to better solutions. We propose an addition to the class of model-based methods, cumulative weighting optimization (CWO), whose general version can be proven convergent to an optimal solution and stable under disturbances (e.g., floating point inaccuracy). These properties encourage us to design a class of CWO algorithms for solving global optimization problems. Beyond the general convergence and stability analysis, we prove that with some additional assumptions the Monte Carlo version of the CWO algorithm is also convergent and stable. Interestingly, the well known cross-entropy method is a CWO algorithm. PubDate: 2016-07-01

Abstract: Abstract
This paper is concerned with a general model of financial flows and prices related to individual entities, called sectors, which invest in financial instruments as assets and as liabilities. In particular, using delicate tools of Functional Analysis, besides existence results of financial equilibrium, in the dual formulation, the Lagrange functions
\(\rho _j^{*1}(t)\)
and
\(\rho _j^{*2}(t)\)
, called “deficit” and “surplus” variables, appear and reveal to be very relevant in order to analyze the financial model and the possible insolvencies, which can lead to a financial contagion. In the paper the continuity of these Lagrange functions is proved. Finally, a procedure for the calculus of these variables is suggested. PubDate: 2016-07-01

Abstract: Abstract
We introduce a relaxed-projection splitting algorithm for solving variational inequalities in Hilbert spaces for the sum of nonsmooth maximal monotone operators, where the feasible set is defined by a nonlinear and nonsmooth continuous convex function inequality. In our scheme, the orthogonal projections onto the feasible set are replaced by projections onto separating hyperplanes. Furthermore, each iteration of the proposed method consists of simple subgradient-like steps, which does not demand the solution of a nontrivial subproblem, using only individual operators, which exploits the structure of the problem. Assuming monotonicity of the individual operators and the existence of solutions, we prove that the generated sequence converges weakly to a solution. PubDate: 2016-07-01

Abstract: Abstract
A filter based template for bound and otherwise constrained global optimization of non-smooth black-box functions is presented. The constraints must include finite upper and lower bounds, and can include nonlinear equality and inequality constraints. Almost sure convergence is shown for a wide class of algorithms conforming to this template. An existing method for bound constrained global optimization (oscars) is easily modified to conform to this template. Numerical results show the modified oscars is competitive with other methods on test problems including those listed by Koziel and Michalewicz. PubDate: 2016-07-01

Abstract: Abstract
Providing partial preference information for multiple criteria ranking or sorting problems results in the indetermination of the preference model. Investigating the influence of this indetermination on the suggested recommendation, we may obtain the necessary, possible and extreme results confirmed by, respectively, all, at least one, or the most and least advantageous preference model instances compatible with the input preference information. We propose a framework for answering questions regarding stability of these results. In particular, we are investigating the minimal improvement that warrants feasibility of some currently impossible outcome as well as the maximal deterioration by which some already attainable result still holds. Taking into account the setting of multiple criteria ranking and sorting problems, we consider such questions in view of pairwise preference relations, or attaining some rank, or assignment. The improvement or deterioration of the sort of an alternative is quantified with the change of its performances on particular criteria and/or its comprehensive score. The proposed framework is useful in terms of design, planning, formulating the guidelines, or defining the future performance targets. It is also important for robustness concern because it finds which parts of the recommendation are robust or sensitive with respect to the modification of the alternatives’ performance values or scores. Application of the proposed approach is demonstrated on the problem of assessing environmental impact of main European cities. PubDate: 2016-07-01

Abstract: Abstract
We establish formulas for computing/estimating the regular and Mordukhovich coderivatives of implicit multifunctions defined by generalized equations in Asplund spaces. These formulas are applied to obtain conditions for solution stability of parametric variational systems over perturbed smooth-boundary constraint sets. PubDate: 2016-07-01

Abstract: Abstract
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17–19 % on average. Most importantly, more instances can be solved when using OBBT. PubDate: 2016-06-17

Abstract: Abstract
Free-sign pure discrete signomial (FPDS) terms are vital to and are frequently observed in many nonlinear programming problems, such as geometric programming, generalized geometric programming, and mixed-integer non-linear programming problems. In this study, all variables in the FPDS term are discrete variables. Any improvement to techniques for linearizing FPDS term contributes significantly to the solving of nonlinear programming problems; therefore, relative techniques have continually been developed. This study develops an improved exact method to linearize a FPDS term into a set of linear programs with minimal logarithmic numbers of zero-one variables and constraints. This method is tighter than current methods. Various numerical experiments demonstrate that the proposed method is significantly more efficient than current methods, especially when the problem scale is large. PubDate: 2016-06-17

Abstract: Abstract
We tackle a combinatorial problem that consists of finding the optimal configuration of a binary matrix. The configuration is determined by the ordering of the rows in the matrix and the objective function value is associated with a value B, the so-called bandpass number. In the basic version of the problem, the objective is to maximize the number of non-overlapping blocks containing B consecutive cells with a value of one in each column of the matrix. We explore variants of this basic problem and use them to test heuristic strategies within the scatter search framework. An existing library of problem instances is used to perform scientific testing of the proposed search procedures to gain insights that may be valuable in other combinational optimization settings. We also conduct competitive testing to compare outcomes with methods published in the literature and to improve upon previous results. PubDate: 2016-06-09

Abstract: Abstract
A bar framework (G, p) in dimension r is a graph G whose nodes are points
\(p^1,\ldots ,p^n\)
in
\(\mathbb {R}^r\)
and whose edges are line segments between pairs of these points. Two frameworks (G, p) and (G, q) are equivalent if each edge of (G, p) has the same (Euclidean) length as the corresponding edge of (G, q). A pair of non-adjacent vertices i and j of (G, p) is universally linked if
\( p^i-p^j \)
=
\( q^i-q^j \)
in every framework (G, q) that is equivalent to (G, p). Framework (G, p) is universally rigid iff every pair of non-adjacent vertices of (G, p) is universally linked. In this paper, we present a unified treatment of the universal rigidity problem based on the geometry of spectrahedra. A spectrahedron is the intersection of the positive semidefinite cone with an affine space. This treatment makes it possible to tie together some known, yet scattered, results and to derive new ones. Among the new results presented in this paper are: (1) The first sufficient condition for a given pair of non-adjacent vertices of (G, p) to be universally linked. (2) A new, weaker, sufficient condition for a framework (G, p) to be universally rigid thus strengthening the existing known condition. An interpretation of this new condition in terms of the Strong Arnold Property is also presented. PubDate: 2016-06-02

Abstract: Abstract
A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported. PubDate: 2016-06-01

Abstract: Abstract
A new approach to solving a large class of factorable nonlinear programming (NLP) problems to global optimality is presented in this paper. Unlike the traditional strategy of partitioning the decision-variable space employed in many branch-and-bound methods, the proposed approach approximates the NLP problem by a reverse-convex programming (RCP) problem to a controlled precision, with the latter then solved by an enumerative search. To establish the theoretical guarantees of the method, the notion of “RCP regularity” is introduced and it is proven that enumeration is guaranteed to yield a global optimum when the RCP problem is regular. An extended RCP algorithmic framework is then presented and its performance is examined for a small set of test problems. PubDate: 2016-06-01

Abstract: Abstract
The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that
\(X = WH\)
. In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope. PubDate: 2016-06-01

Abstract: Abstract
We further develop our phi-function technique for solving Cutting and Packing problems. Here we introduce quasi-phi-functions for an analytical description of non-overlapping and containment constraints for 2D- and 3D-objects which can be continuously rotated and translated. These new functions can work well for various types of objects, such as ellipses, for which ordinary phi-functions are too complicated or have not been constructed yet. We also define normalized quasi-phi-functions and pseudonormalized quasi-phi-functions for modeling distance constraints. To show the advantages of our new quasi-phi-functions we apply them to the problem of placing a given collection of ellipses into a rectangular container of minimal area. We use radical free quasi-phi-functions to reduce it to a nonlinear programming problem and develop an efficient solution algorithm. We present computational results that compare favourably with those published elsewhere recently. PubDate: 2016-06-01

Abstract: Abstract
We propose a hierarchy of semidefinite programming (SDP) relaxations for polynomial optimization with sparse patterns over unbounded feasible sets. The convergence of the proposed SDP hierarchy is established for a class of polynomial optimization problems. This is done by employing known sums-of-squares sparsity techniques of Kojima and Muramatsu Comput Optim Appl 42(1):31–41, (2009) and Lasserre SIAM J Optim 17:822–843, (2006) together with a representation theorem for polynomials over unbounded sets obtained recently in Jeyakumar et al. J Optim Theory Appl 163(3):707–718, (2014). We demonstrate that the proposed sparse SDP hierarchy can solve some classes of large scale polynomial optimization problems with unbounded feasible sets using the polynomial optimization solver SparsePOP developed by Waki et al. ACM Trans Math Softw 35:15 (2008). PubDate: 2016-06-01

Abstract: Abstract
This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances. PubDate: 2016-06-01