Search

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

Many evolutionary multi-objective optimization (EMO) methodologies have been proposed and performed very well on finding a representative set of Pareto-optimal solutions, but this advantage will be weakened with the increasing number of objectives. And in real applications, what decision makers (DMs) want is a unique solution or a set of solutions rather than the overall Pareto-optimal front. It is a difficult task to solve many-objective problems by using preference information provided by decision maker (DM) during optimization process. In this paper, a new angle-based preference selection mechanism is proposed, which replaces the traditional crowding distance with the aid of preference information provided by the DMs. Particularly, we combine it with a multi-objective immune algorithm with non-dominated neighbor-based selection. The proposed method has been extensively compared with other recently proposed preference-based EMO approaches over DTLZ1, DTLZ2, and DTLZ3 test problems with 4-100 objectives. The results of the experiment indicate that the proposed algorithm can achieve competitive and better results. [ABSTRACT FROM AUTHOR]

In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach. [ABSTRACT FROM AUTHOR]

The nonmonotone globalization technique is useful in difficult nonlinear problems, because of the fact that it may help escaping from steep sided valleys and may improve both the possibility of finding the global optimum and the rate of convergence. This paper discusses the nonmonotonicity degree of nonmonotone line searches for the unconstrained optimization. Specifically, we analyze some popular nonmonotone line search methods and explore, from a computational point of view, the relations between the efficiency of a nonmonotone line search and its nonmonotonicity degree. We attempt to answer this question how to control the degree of the nonmonotonicity of line search rules in order to reach a more efficient algorithm. Hence in an attempt to control the nonmonotonicity degree, two adaptive nonmonotone rules based on the morphology of the objective function are proposed. The global convergence and the convergence rate of the proposed methods are analysed under mild assumptions. Numerical experiments are made on a set of unconstrained optimization test problems of the CUTEr (Gould et al. in ACM Trans Math Softw 29:373-394, 2003) collection. The performance data are first analysed through the performance profile of Dolan and Moré (Math Program 91:201-213, 2002). In the second kind of analyse, the performance data are analysed in terms of increasing dimension of the test problems. [ABSTRACT FROM AUTHOR]

Scheduling of jobs and resources on a shop floor is an ever green optimization problem. Job shop scheduling problem (JSSP) is an allocation of 'n' jobs on 'm' machines so as to complete processing of all jobs in a minimum possible time. The JSSP has been addressed by various direct, indirect methods, programs, and algorithms in the last 40 year of literature. This paper presents a new paradigm of invasive weed optimization which mimics the process of weed colonization and distribution to solve JSSPs. The algorithm had shown encouraging and promising outputs on standard benchmarking problems. [ABSTRACT FROM AUTHOR]

In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287-1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson's algorithm in Hamel et al. (J Global Optim 59(4):811-836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans-Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with the Evans-Steuer algorithm. For highly degenerate problems Benson's algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans-Steuer algorithm. [ABSTRACT FROM AUTHOR]

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a 'non natural' behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability. [ABSTRACT FROM AUTHOR]

In this paper, we study the link between a Chance-Constrained optimization Problem (CCP) and its sample counterpart (SP). SP has a finite number, say N, of sampled constraints. Further, some of these sampled constraints, say k, are discarded, and the final solution is indicated by $x^{\ast}_{N,k}$. Extending previous results on the feasibility of sample convex optimization programs, we establish the feasibility of $x^{\ast}_{N,k}$ for the initial CCP problem. Constraints removal allows one to improve the cost function at the price of a decreased feasibility. The cost improvement can be inspected directly from the optimization result, while the theory here developed permits to keep control on the other side of the coin, the feasibility of the obtained solution. In this way, trading feasibility for performance is put on solid mathematical grounds in this paper. The feasibility result here obtained applies to a vast class of chance-constrained optimization problems, and has the distinctive feature that it holds true irrespective of the algorithm used to discard k constraints in the SP problem. For constraints discarding, one can thus, e.g., resort to one of the many methods introduced in the literature to solve chance-constrained problems with discrete distribution, or even use a greedy algorithm, which is computationally very low-demanding, and the feasibility result remains intact. We further prove that, if constraints in the SP problem are optimally removed-i.e., one deletes those constraints leading to the largest possible cost improvement-, then a precise optimality link to the original chance-constrained problem CCP in addition holds. [ABSTRACT FROM AUTHOR]

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied. [ABSTRACT FROM AUTHOR]

Abstract  The study and research of evolutionary algorithms (EAs) is getting great attention in recent years. Although EAs have earned extensive acceptance through numerous successful applications in many fields, the problem of finding the best combination of evolutionary parameters especially for population size that need the manual settings by the user is still unresolved. In this paper, our system is focusing on differential evolution (DE) and its control parameters. To overcome the problem, two new systems were carried out for the self-adaptive population size to test two different methodologies (absolute encoding and relative encoding) in DE and compared their performances against the original DE. Fifty runs are conducted for every 20 well-known benchmark problems to test on every proposed algorithm in this paper to achieve the function optimization without explicit parameter tuning in DE. The empirical testing results showed that DE with self-adaptive population size using relative encoding performed well in terms of the average performance as well as stability compared to absolute encoding version as well as the original DE. [ABSTRACT FROM AUTHOR]

Abstract  This paper introduces a novel version of the particle swarm optimisation (PSO) algorithm which we call self-organising swarm SOSwarm. SOSwarm can be used for unsupervised learning. In the algorithm, input vectors are projected into a lower-dimensional map space producing a visual representation of the input data in a manner similar to a self-organising map (SOM). In SOSwarm, particles react to input data during the learning process by modifying their velocities using an adaptation of the PSO velocity update function. SOSwarm is successfully applied to ten benchmark problems drawn from the UCI Machine Learning repository. The paper also demonstrates how the canonical SOM can be explored within the PSO paradigm. Illustrating this linkage between the heretofore distinct literatures of SOM and PSO opens up several new avenues of research for the development of novel self-organising algorithms. [ABSTRACT FROM AUTHOR]

This paper focuses on a class of discrete-time interconnected pendulumlike systems. Sufficient conditions for the global convergence of systems with both structured and unstructured uncertainties in its linear part are established in terms of linear matrix inequalities (LMIs). In the traditional decentralized control of large scale systems, the effects of interconnections were seldom studied. In this paper, a square matrix specifying the interconnecting structure is introduced in order to discuss the effects of nonlinear interconnections. It is shown that the global convergence of the whole interconnected system can be achieved by designing an appropriate interconnection matrix. In order to solve the nonlinear matrix inequalities (NMIs) arising in the synthesis problem, a global optimization algorithm is presented which can be used to handle a class of NMI problems. An illustrative example is given to demonstrate the applicability and validity of the main results and the presented algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space Rn (corresponding to constrained optimization) and the Rn space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than Rn, the newalgorithms are very efficient. Convergence rates are obtained. Applications are discussed. [ABSTRACT FROM AUTHOR]

In this paper, a new sequential penalty algorithm, based on the L[sub ∞] exact penalty function, is proposed for a general nonlinear constrained optimization problem. The algorithm has the following characteristics: it can start from an arbitrary initial point; the feasibility of the subproblem is guaranteed; the penalty parameter is adjusted automatically; global convergence without any regularity assumption is proved. The update formula of the penalty parameter is new. It is proved that the algorithm proposed in this paper behaves equivalently to the standard SQP method after sufficiently many iterations. Hence, the local convergence results of the standard SQP method can be applied to this algorithm. Preliminary numerical experiments show the efficiency and stability of the algorithm. [ABSTRACT FROM AUTHOR]

Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information. [ABSTRACT FROM AUTHOR]

Consider a data set of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a convex optimization problem, called reaper, that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors and uses a relaxation of the set of orthogonal projectors to reach the convex formulation. The paper provides an efficient algorithm for solving the reaper problem, and it documents numerical experiments that confirm that reaper can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when reaper can approximate this subspace. [ABSTRACT FROM AUTHOR]

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the $$k$$ -robust model where the possible scenarios tomorrow are given by all demand-subsets of size $$k$$ . In this paper, we give the following simple and intuitive template for $$k$$ -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for $$k$$ -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our $$k$$ -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal-dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max-min problems of the form: ' given a covering problem instance, which $$k$$ of the elements are costliest to cover?' For the problems mentioned above, we show that their $$k$$ -max-min versions have performance guarantees similar to those for the $$k$$ -robust problems. [ABSTRACT FROM AUTHOR]

The present paper studies the integrated size and topology optimization of skeletal structures under natural frequency constraints. It is found that, unlike the conventional compliance-oriented topology optimization problems, the considered problem may be strongly singular in the sense that the corresponding feasible domain may be disconnected and the global optimal solutions are often located at the tips of some separated low dimensional sub-domains when the cross-sectional areas of the structural components are used as design variables. As in the case of stress-constrained topology optimization, this unpleasant behavior may prevent the gradient-based numerical optimization algorithms from finding the true optimal topologies. To overcome the difficulties posed by the strongly singular optima, some particular forms of area/moment of inertia-density interpolation schemes, which can restore the connectedness of the feasible domain, are proposed. Based on the proposed optimization model, the probability of finding the strongly singular optimum with gradient-based algorithms can be increased. Numerical examples demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O( n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists. [ABSTRACT FROM AUTHOR]

A new local search algorithm for multiobjective optimization problems is proposed to find the global optima accurately and diversely. This paper models the cooperatively local search as a potential field, which is called neighborhood field model (NFM). Using NFM, a new Multiobjective Neighborhood Field Optimization (MONFO) algorithm is proposed. In MONFO, the neighborhood field can drive each individual moving towards the superior neighbor and away from the inferior neighbor. MONFO is compared with other popular multiobjective algorithms under twelve test functions. Intensive simulations show that MONFO is able to deliver promising results in the respects of accuracy and diversity, especially for multimodal problems. [ABSTRACT FROM AUTHOR]

Ruggedness has a strong influence on the performance of algorithms, but it has been barely studied in real-coded optimization, mainly because of the difficulty of isolating it from a number of involved topological properties. In this paper, we propose a framework consisting of increasing ruggedness function sets built by a mechanism which generates multiple funnels. This mechanism introduces different levels of sinusoidal distortion which can be controlled to isolate the singular influence of some related features. Some commonly used measures of ruggedness have been applied to analyze these sets of functions, and a numerical study to compare the performance of some representative algorithms has been carried out. The results confirm that ruggedness has an influence on the performance of the algorithm, proving that it depends on the multi-funnel structure and peak features, such as height and relative size of the global peak, and not on the number of peaks. [ABSTRACT FROM AUTHOR]

Balanced minimum evolution (BME) is a statistically consistent distance-based method to reconstruct a phylogenetic tree from an alignment of molecular data. In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear functional over the BME polytope, the convex hull of the BME vectors obtained from Pauplin's formula applied to all binary trees. The BME method is related to the Neighbor Joining (NJ) Algorithm, now known to be a greedy optimization of the BME principle. Further, the NJ and BME algorithms have been studied previously to understand when the NJ Algorithm returns a BME tree for small numbers of taxa. In this paper we aim to elucidate the structure of the BME polytope and strengthen knowledge of the connection between the BME method and NJ Algorithm. We first prove that any subtree-prune-regraft move from a binary tree to another binary tree corresponds to an edge of the BME polytope. Moreover, we describe an entire family of faces parameterized by disjoint clades. We show that these clade-faces are smaller dimensional BME polytopes themselves. Finally, we show that for any order of joining nodes to form a tree, there exists an associated distance matrix (i.e., dissimilarity map) for which the NJ Algorithm returns the BME tree. More strongly, we show that the BME cone and every NJ cone associated to a tree T have an intersection of positive measure. [ABSTRACT FROM AUTHOR]

Noise is present in many real-world continuous optimization problems. Stochastic search algorithms such as Evolution Strategies (ESs) have been proposed as effective search methods in such contexts. In this paper, we provide a mathematical analysis of the convergence of a (1+1)-ES on unimodal spherical objective functions in the presence of noise. We prove for a multiplicative noise model that for a positive expected value of the noisy objective function, convergence or divergence happens depending on the infimum of the support of the noise. Moreover, we investigate convergence rates and show that log-linear convergence is preserved in presence of noise. This result is a strong theoretical foundation of the robustness of ESs with respect to noise. [ABSTRACT FROM AUTHOR]

very efficient technique to drastically reduce the number of multipliers and adders in narrow transition-band linear-phase finite-impulse response digital filters is to use the one-stage or multistage frequency-response masking (FRM) approach, which has been originally introduced by Lim and further improved by Lim and Lian. In these original synthesis techniques, the subfilters in the overall implementation are separately designed. As shown earlier by the authors of this contribution together with Johansson, the arithmetic complexity in one-stage FRM filter designs can be considerably reduced by using the following two-step technique for simultaneously optimizing all the subfilters. First, a suboptimal solution is found by using a simple design scheme. Second, this solution is used as a start-up solution for further optimization, which is carried out with the aid of an efficient nonlinear optimization algorithm. This paper exploits this approach to synthesizing multistage FRM filters. An example taken from the literature illustrates that both the number of multipliers and the number of adders for the resulting optimized multistage FRM filters are approximately 70 percent compared with those of the filters synthesized using the original multistage FRM filter design schemes. Additional examples are included in order to show the benefits provided by the proposed synthesis scheme over other recently published design techniques, in terms of an improved performance of the resulting solution, a higher accuracy of the solution, and a faster speed required to arrive at the best solution. [ABSTRACT FROM AUTHOR]

In this paper, based on the implementation of semiclassical quantum Fourier transform, we first propose the concept of generation vector of ternary binary representation, construct the generation function's truth table, prove that the generation vector of ternary binary representation is one kind of k's NAF representation and further find that its number of nonzero is not more than [(⌈log k⌉ +1)/2] . Then we redesign a quantum circuit for Shor's algorithm, whose computation resource is approximately equal to that of Parker (Their requirements of elementary quantum gate are both O(⌈log N⌉³), and our circuit requires 2 qubits more than Parker's). However, our circuit is twice as fast as Parker's. [ABSTRACT FROM AUTHOR]

Celebrating the sixtieth anniversary since the zeroth International Symposium on Mathematical Programming was held in 1949, this paper discusses several promising paradigms in mathematical programming that have gained momentum in recent years but have yet to reach the main stream of the field. These are: competition, dynamics, and hierarchy. The discussion emphasizes the interplay between these paradigms and their connections with existing subfields including disjunctive, equilibrium, and nonlinear programming, and variational inequalities. We will describe the modeling approaches, mathematical formulations, and recent results of these paradigms, and sketch some open mathematical and computational challenges arising from the resulting optimization and equilibrium problems. Our goal is to elucidate the need for a systematic study of these problems and to inspire new research in the field. [ABSTRACT FROM AUTHOR]

The disassembly line is the best choice for automated disassembly of disposal products. Therefore, disassembly line should be designed and balanced so that it can work as efficiently as possible. In this paper, a mathematical model for the multi-objective disassembly line balancing problem is formalized firstly. Then, a novel multi-objective ant colony optimization (MOACO) algorithm is proposed for solving this multi-objective optimization problem. Taking into account the problem constraints, a solution construction mechanism based on the method of tasks assignment is utilized in the algorithm. Additionally, niche technology is used to embed in the updating operation to search the Pareto optimal solutions. Moreover, in order to find the Pareto optimal set, the MOACO algorithm uses the concept of Pareto dominance to dynamically filter the obtained non-dominated solution set. To validate the performance of algorithm, the proposed algorithm is measured over published results obtained from single-objective optimization approaches and compared with multi-objective ACO algorithm based on uniform design. The experimental results show that the proposed MOACO is well suited to multi-objective optimization in disassembly line balancing. [ABSTRACT FROM AUTHOR]

This paper presents a simplified algorithm for the profiling of the rack gear tool to generate the active profile associated with rolling centrodes. The algorithm is based on the enveloping surfaces principles and reduces the computational problem by proposing an approximate representation of tool’s profile using only three or four points on the profile to be generated by using Bezier representations of the surfaces. The algorithm computes the coefficients of a Bezier substitution polynomial instead of computing hundreds of points on the active profile. This simplifies the solution methodology and requires only a limited number of points along the profile to be generated. The algorithm is computationally efficient and can also be used in the case when the active profile to be generated is physically measured at a few points. Examples include mill tools, splined shafts, and gears. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods. [ABSTRACT FROM AUTHOR]

This paper presents a new technique to compute nondominated solutions in multiobjective linear-fractional programming (MOLFP) by using reference points. The basic idea consists in dividing the nondominated region approximately through the “middle” making two subregions, which are then analyzed in order to try to discard one of them. The process is repeated with the remaining region(s), and it ends when the regions become so small that the differences among their nondominated solutions are lower than a predefined margin of error. The results of several tests carried out to evaluate the performance of the technique are reported. [ABSTRACT FROM AUTHOR]

Abstract  Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This paper investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, two diversity maintaining methods, called adaptive dual mapping and triggered random immigrants, respectively, are also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer evolutionary algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, a memetic algorithm (MA) based on differential evolution (DE), namely MADE, is proposed for the multi-objective no-wait flow-shop scheduling problems (MNFSSPs). Firstly, a largest-order-value rule is presented to convert individuals in DE from real vectors to job permutations so that the DE can be applied for solving flow-shop scheduling problems (FSSPs). Secondly, the DE-based parallel evolution mechanism is applied to perform effective exploration, and several local searchers developed according to the landscape of multi-objective FSSPs are applied to emphasize local exploitation. Thirdly, a speed-up computing method is developed based on the property of the no-wait FSSPs. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Due to the well balance between DE-based global search and problem-dependent local search as well as the utilization of the speed-up evaluation, the MNFSSPs can be solved effectively and efficiently. Simulation results and comparisons demonstrate the effectiveness and efficiency of the proposed MADE. [ABSTRACT FROM AUTHOR]

In this paper a new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter β k is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. β=(1− θ k) β+ θ k β. The parameter θ k in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is the study of sufficient and/or necessary conditions for existence of solutions of equilibrium problems. We discuss some of the assumptions of the problem, under which the introduced conditions are sufficient and/or necessary, and also analyze the effect of these assumptions on the connection between the solution sets of the equilibrium problem and of a related convex feasibility problem. [ABSTRACT FROM AUTHOR]

An even factor in a digraph, introduced by Cunningham and Geelen (Vertex-disjoint dipaths and even dicircuits. manuscript, 2001), is a collection of vertex-disjoint dipaths and even dicycles, which generalizes a path-matching of Cunningham and Geelen (Combinatorica 17, 315–337, 1997). In a restricted class of digraphs, called odd-cycle-symmetric, Pap (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3509, pp. 66–80, Springer, Heidelberg, 2005) presented a combinatorial algorithm to find a maximum even factor. For odd-cycle-symmetric weighted digraphs, which are odd-cycle-symmetric digraphs accompanied by a weight vector satisfying a certain property, Király and Makai (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3064, pp. 416–430, Springer, Heidelberg, 2004) provided a linear program that describes the maximum weight even factor problem, and proved the dual integrality. In this paper, we present a primal-dual algorithm to find a maximum weight even factor for an odd-cycle-symmetric weighted digraph. This algorithm is based on the weighted matching algorithm of Edmonds and the maximum even factor algorithm of Pap. The running time of the algorithm is O( n 3 m), where n and m are the numbers of the vertices and arcs, respectively, which is better than that of the existing algorithms for the special cases. The algorithm also gives a constructive proof for the dual integrality. [ABSTRACT FROM AUTHOR]

The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual solutions to converge linearly with their duality gaps. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to establish the second-order nonsmooth sufficient unconstrained optimality condition for so called ℓ-stable at some point functions and in this way to generalize some previous results in this direction. We provide the comparisons with other results by examples. [ABSTRACT FROM AUTHOR]

Abstract  Instead of the past mathematical analyses, an intuitive geometric analysis of the collaborative optimization (CO) algorithm is presented in this paper, which reveals some geometric properties of CO and gives a direct geometric interpretation of the reason for the reported computational difficulties in CO. The analysis shows that if the system-level optimum point at one iteration is outside the feasible region of the original optimization problem, at the next iteration, the system-level optimization problem may be infeasible due to the system-level consistency equality constraints. One way to solve the problem of the infeasibility is to relax the system-level consistency equality constraints using inequality constraints. However it is a delicate job to determine a rational relaxed tolerance because feasibility and consistency have conflicting requirements for the tolerance, that is, the more relaxed the better for feasibility while the stricter the better for consistency. Based on the geometric analysis, a method of variable relaxed tolerance is put forward to solve this problem. In this method, an adaptive adjustment of the tolerance is made at each iteration according to the quantified inconsistency between two subsystems. In the last section, the capabilities and limitations of the proposed method are illustrated by three examples. [ABSTRACT FROM AUTHOR]

This paper addresses a new class of linearly constrained fractional programming problems where the objective function is defined as the ratio of two functions which are the sums of the absolute values of affine functions. This problem has an important application in financial optimization. This problem is a convex-convex type of fractional program which cannot be solved by standard algorithms. We propose a branch-and-bound algorithm and an integer programming algorithm. We demonstrate that a fairly large scale problem can be solved within a practical amount of time. [ABSTRACT FROM AUTHOR]

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated. In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B. Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete. [ABSTRACT FROM AUTHOR]

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n). [ABSTRACT FROM AUTHOR]

This paper provides new insights into the solution of optimal stochastic control problems by means of a system of partial differential equations, which characterize directly the optimal control. This new system is obtained by the application of the stochastic maximum principle at every initial condition, assuming that the optimal controls are smooth enough. The type of problems considered are those where the diffusion coefficient is independent of the control variables, which are supposed to be interior to the control region. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the strong convergence of an inexact proximalpoint algorithm. It is known that the proximal-point algorithm converges weakly to a solution of a maximal monotone operator, but fails to converge strongly. Solodov and Svaiter (Math. Program. 87:189–202, 2000) introduced a new proximal-type algorithm to generate a strongly convergent sequence and established a convergence result in Hilbert space. Subsequently, Kamimura and Takahashi (SIAM J. Optim. 13:938–945, 2003) extended the Solodov and Svaiter result to the setting of uniformly convex and uniformly smooth Banach space. On the other hand, Rockafellar (SIAM J. Control Optim. 14:877–898, 1976) gave an inexact proximal-point algorithm which is more practical than the exact one. Our purpose is to extend the Kamimura and Takahashi result to a new inexact proximal-type algorithm. Moreover, this result is applied to the problem of finding the minimizer of a convex function on a uniformly convex and uniformly smooth Banach space. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm for solving a mathematical programming problem with complementarity (or equilibrium) constraints (MPEC) is introduced, which uses the active-set methodology while maintaining the complementarity restrictions throughout the procedure. Finite convergence of the algorithm to a strongly stationary point of the MPEC is established under reasonable hypotheses. The algorithm can be easily implemented by adopting any active-set code for nonlinear programming. Computational experience is included to highlight the efficacy of the proposed method in practice. [ABSTRACT FROM AUTHOR]

In this paper, we conduct three case studies to assess the effectiveness of a recently proposed first-order method for robust nonlinear programming [Zhang, Y.: J. Optim. Theory Appl. 132, 111-124 (2007)]. Three robust nonlinear programming problems were chosen from the literature using the criteria that results calculated using other methods must be available and the problems should be realistic, but fairly simple. Our studies show that the first-order method produced reasonable solutions when the level of uncertainty was small to moderate. In addition, we demonstrate a method for leveraging a theoretical result to eliminate constraint violations. Since the first-order method is relatively inexpensive in comparison to other robust optimization techniques, our studies indicate that, under moderate uncertainty, the first-order approach may be more suitable than other methods for large problems. [ABSTRACT FROM AUTHOR]

This paper is concerned with an efficient algorithm for solving a convexconvex type quadratic fractional program whose objective function is defined as the ratio of two convex quadratic functions and whose constraints are linear. This is a typical nonconcave maximization problem with multiple local maxima. The algorithm to be proposed here is a combination of (i) the classical Dinkelbach approach, (ii) the integer programming approach for solving nonconvex quadratic programming problems and (iii) the standard nonlinear programming algorithm. It will be shown that an exact algorithm which is a combination of (i) and (ii) above can solve problems much larger than those solved by an earlier algorithm based on a branch and bound algorithm. It addition, the combination of (i)—(iii) can solve much larger problems within a practical amount of time. [ABSTRACT FROM AUTHOR]

We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. To our knowledge, the practical benefit that can be obtained by embedding interpolated subadditive cuts in a cutting plane algorithm was not investigated computationally by previous authors. In this paper we compute, for the first time, the lower bound value obtained when adding (implicitly) all the interpolated subadditive cuts that can be derived from the individual rows of an optimal LP tableau, thus approximating the optimization over the intersection of the Gomory corner polyhedron with the LP relaxation of the original problem formulation. The computed bound is compared with that obtained when only Gomory mixed-integer cuts are used, on a very large test-bed of MIP instances. [ABSTRACT FROM AUTHOR]

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. [ABSTRACT FROM AUTHOR]