Abstract: Abstract
This paper presents a stabilized filter sequential quadratic programming (SQP) method for the general nonlinear optimization problems. The technique of stabilizing the inner quadratic programmings is an efficient strategy for the degenerate problem and brings the local superlinear convergence, while the integrated filter technique works effectively and guarantees the global convergence. The new algorithm works on both the primal and dual variables and solves the problem within the computational complexity comparable to the classical SQP algorithm. For the convergence, we show that (1) it converges either to a Karush–Kuhn–Tucker point at which the cone-continuity property holds, or to a stationary point in the sense of minimizing the constraint violation, and (2) under some second-order sufficient conditions, it converges locally superlinearly without any constraint qualifications. Our preliminary numerical results on a set of CUTEr test problems as well as on degenerate problems demonstrate the efficiency of the new algorithm. PubDate: 2016-08-01

Abstract: Abstract
We model the two-stage production-capacitated lot-sizing problem as a concave minimum cost network flow problem and characterize the possible patterns of flow between successive periods in which transportation occurs. We demonstrate that production and transportation decisions can be made based only on the local state of transportation patterns between successive transportation periods. Utilizing this observation together with the insight that it is not necessary to consider transportation decisions between transportation periods, we provide a novel improved
\(O(T^6)\)
algorithm (where T is the length of the planning horizon). We extend this approach to special cases, and develop an
\(O(T^5)\)
algorithm for the case with non-speculative costs, and an
\(O(T^4)\)
algorithm for the case with linear costs. PubDate: 2016-08-01

Abstract: Abstract
In a partial inverse combinatorial problem, given a partial solution, the goal is to modify data as small as possible such that there exists an optimal solution containing the given partial solution. In this paper, we study a constraint version of the partial inverse matroid problem in which the weight can only be increased. Two polynomial time algorithms are presented for this problem. PubDate: 2016-08-01

Abstract: Abstract
In this paper we discuss how to derive the non polyhedral convex envelopes for some functions, called 1-convex throughout the paper, over boxes. The main result is about n-dimensional 1-convex functions, but we get to it by first discussing in detail some special cases, namely functions
\(xyz^\delta \)
,
\(\delta >1\)
, and, next, more general trivariate functions. The relation between the class of functions investigated in this paper and other classes investigated in the existing literature is discussed. PubDate: 2016-08-01

Abstract: Abstract
We consider concave minimization problems over nonconvex sets. Optimization problems with this structure arise in sparse principal component analysis. We analyze both a gradient projection algorithm and an approximate Newton algorithm where the Hessian approximation is a multiple of the identity. Convergence results are established. In numerical experiments arising in sparse principal component analysis, it is seen that the performance of the gradient projection algorithm is very similar to that of the truncated power method and the generalized power method. In some cases, the approximate Newton algorithm with a Barzilai–Borwein Hessian approximation and a nonmonotone line search can be substantially faster than the other algorithms, and can converge to a better solution. PubDate: 2016-08-01

Abstract: Abstract
Given a set of lightpath requests, the problem of routing and wavelength (RWA) assignment in wavelength division multiplexing (WDM) optical networks consists in routing a subset of these requests and assigning a wavelength to each of them, such that two lightpaths that share a common link are assigned to different wavelengths. There are many variants of this problem in the literature. We focus in the variant in which the objective is to maximize the number of requests that may be accepted, given a limited set of available wavelengths. This problem is called max-RWA and it is of practical and theoretical interest, because algorithms for this variant can be extended for other RWA problems that arise from the design of WDM optical networks. A number of exact algorithms based on integer programming formulations have been proposed in the literature to solve max-RWA, as well as algorithms to provide upper bounds to the optimal solution value. However, the algorithms based on the state-of-the-art formulations in the literature cannot solve the largest instances to optimality. For these instances, only upper bounds to the value of the optimal solutions are known. The literature on heuristics for max-RWA is short and focus mainly on solving small size instances with up to 27 nodes. In this paper, we propose new greedy constructive heuristics and a biased random-key genetic algorithm, based on the best of the proposed greedy heuristics. Computational experiments showed that the new heuristic outperforms the best ones in literature. Furthermore, for the largest instances in the literature where only upper bounds to the value of the optimal solutions are known, the average optimality gap of the best of the proposed heuristics is smaller than 4 %. PubDate: 2016-08-01

Abstract: Abstract
Interval Branch and Bound algorithms are used to solve rigorously continuous constraint satisfaction and constrained global optimization problems. In this paper, we explain the basic principles behind interval Branch and Bound algorithms. We detail the main components and describe issues that should be considered to improve the efficiency of the algorithms. PubDate: 2016-08-01

Abstract: Abstract
In this paper, continuous and differentiable nonlinear programming models and algorithms for packing ellipsoids in the n-dimensional space are introduced. Two different models for the non-overlapping and models for the inclusion of ellipsoids within half-spaces and ellipsoids are presented. By applying a simple multi-start strategy combined with a clever choice of starting guesses and a nonlinear programming local solver, illustrative numerical experiments are presented. PubDate: 2016-08-01

Abstract: Abstract
We present a more generalized model for the bandwidth packing problem with queuing delays under congestion than available in the extant literature. The problem, under Poison call arrivals and general service times, is set up as a network of spatially distributed independent M/G/1 queues. We further present two exact solution approaches to solve the resulting nonlinear integer programming model. The first method, called finite linearization method, is a conventional Big-M based linearization, resulting in a finite number of constraints, and hence can be solved using an off-the-shelve MIP solver. The second method, called constraint generation method, is based on approximating the non-linear delay terms using supporting hyperplanes, which are generated as needed. Based on our computational study, the constraint generation method outperforms the finite linearization method. Further comparisons of results of our proposed constraint generation method with the Lagrangean relaxation based solution method reported in the literature for the special case of exponential service times clearly demonstrate that our approach outperforms the latter, both in terms of the quality of solution and computation times. PubDate: 2016-08-01

Abstract: Abstract
In many engineering optimization problems, the objective and the constraints which come from complex analytical models are often black-box functions with extensive computational effort. In this case, it is necessary for optimization process to use sampling data to fit surrogate models so as to reduce the number of objective and constraint evaluations as soon as possible. In addition, it is sometimes difficult for the constrained optimization problems based on surrogate models to find a feasible point, which is the premise of further searching for a global optimal feasible solution. For this purpose, a new Kriging-based Constrained Global Optimization (KCGO) algorithm is proposed. Unlike previous Kriging-based methods, this algorithm can dispose black-box constrained optimization problem even if all initial sampling points are infeasible. There are two pivotal phases in KCGO algorithm. The main task of the first phase is to find a feasible point when there is no feasible data in the initial sample. And the aim of the second phase is to obtain a better feasible point under the circumstances of fewer expensive function evaluations. Several numerical problems and three design problems are tested to illustrate the feasibility, stability and effectiveness of the proposed method. PubDate: 2016-07-22

Abstract: Abstract
Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems. PubDate: 2016-07-18

Abstract: Abstract
Multiple criteria decision making is a well established field encompassing aspects of search for solutions and selection of solutions in presence of more than one conflicting objectives. In this paper, we discuss an approach aimed towards the latter. The decision maker is presented with a limited number of Pareto optimal outcomes and is required to identify regions of interest for further investigation. The inherent sparsity of the given Pareto optimal outcomes in high dimensional space makes it an arduous task for the decision maker. To address this problem, an existing line of thought in literature is to generate a set of approximated Pareto optimal outcomes using piecewise linear interpolation. We present an approach within this paradigm, but one that delivers a comprehensive linearly interpolated set as opposed to its subset delivered by existing methods. We illustrate the advantage in doing so in comparison to stricter non-dominance conditions imposed in existing PAreto INTerpolation method. The interpolated set of outcomes delivered by the proposed approach are non-dominated with respect to the given Pareto optimal outcomes, and additionally the interpolated outcomes along uniformly distributed reference directions are presented to the decision maker. The errors in the given interpolations are also estimated in order to further aid decision making by establishing confidence in achieving true Pareto outcomes in their vicinity. The proposed approach for interpolation is computationally less demanding (for higher number of objectives) and also further amenable to parallelization. We illustrate the performance of the approach using six well established tri-objective test problems and two real-life examples. The problems span different types of fronts, such as convex, concave, mixed, degenerate, highlighting the wide applicability of the approach. PubDate: 2016-07-13

Abstract: Abstract
In this paper we present a method of applying the GPGPU technology to compute the approximate optimal solution to the Heilbronn problem for nine points in the unit square, namely, points
\(P_1,P_2,\ldots ,P_9\)
in
\([0,1]\times [0,1]\)
so that the minimal area of triangles
\(P_iP_jP_k\,(1\le i<j<k\le 9)\)
gets the maximal value
\(h_9(\Box )\)
. We construct nine rectangles with edge length 1 / 80 in the unit square which contain all optimal Heilbronn configurations up to possible rotation and reflection, and prove that
\(\frac{9\sqrt{65}-55}{320}=0.054875999\cdots<h_9(\Box )<0.054878314\)
, the lower bound here comes from Comellas and Yebra’s paper. PubDate: 2016-07-11

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
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