A mapping f ： Z^n → Rn is said to possess the direction preserving property if fi（x） 〉 0 implies fi（y） ≥ 0 for any integer points x and y with ｜｜x - y｜｜∞≤ 1. In this paper, a simplicial algorithm is deve...
详细信息
A mapping f ： Z^n → Rn is said to possess the direction preserving property if fi（x） 〉 0 implies fi（y） ≥ 0 for any integer points x and y with ｜｜x - y｜｜∞≤ 1. In this paper, a simplicial algorithm is developed for computing an integer zero point of a mapping with the direction preserving property. We assume that there is an integer point x^0 with c ≤ x^0≤d satisfying that maxl≤i≤（xi - xi^0）fi（x） 〉 0 for any integer point x with f（x） ≠ 0 on the boundary of H = {x ∈R^n [c-e ≤ x〈d＋e},wherecanddaretwo finite integer points with c 〈 d and e = （1, 1,... , 1）^T E R^n. This assumption is implied by one of two conditions for the existence of an integer zero point of a mapping with the preserving property in van der Laan et al. （2004）. Under this assumption, starting at x^0, the algorithm follows a finite simplicial path and terminates at an integer zero point of the mapping. This result has applications in general economic equilibrium models with indivisible commodities.
In this paper, a simplicial algorithm is developed to solve the nonlinear complementarity problem on S(n) x R+(m). Furthermore, a condition for convergence is formulated. The triangulation which underlies the algorith...
详细信息
In this paper, a simplicial algorithm is developed to solve the nonlinear complementarity problem on S(n) x R+(m). Furthermore, a condition for convergence is formulated. The triangulation which underlies the algorithm is a combination of the V-triangulation of S(n) and the K-triangulation of R+(m). Therefore, we will call it the VK-triangulation.
A simplicial algorithm is proposed to compute a robust stationary point of a continuous function f from the (n - 1)-dimensional unit simplex S-n-1 into R(n). The concept of robust stationary point is a refinement of t...
详细信息
A simplicial algorithm is proposed to compute a robust stationary point of a continuous function f from the (n - 1)-dimensional unit simplex S-n-1 into R(n). The concept of robust stationary point is a refinement of the concept of stationary point of f on S-n-1. Starting from an arbitrarily chosen interior point v in S-n-1, the algorithm generates a piecewise linear path of points in S-n-1. This path is followed by alternating linear programming pivot steps and replacement steps in a specific simplicial subdivision of the relative interior of S-n-1 In this way an approximate robust stationary point of any a priori chosen accuracy is reached within a finite number of steps. The algorithm leaves the starting point along one out of n! rays. When the path approaches the boundary of S-n-1, the mesh size of the triangulation along the path automatically goes to zero. This makes the algorithm different from all simplicial restart algorithms and homotopy algorithms known so far. Roughly speaking, the algorithm is a blend of a restart and a homotopy algorithm and maintains the basic properties of both. However, the algorithm does not need an extra dimension as homotopy algorithms do. Some examples are discussed.
Particle swarm optimization algorithm (PSO) has been optimized from various aspects since it was proposed. Optimization of PSO can be realized by optimizing its iterative process or the initial parameters and heuristi...
详细信息
Particle swarm optimization algorithm (PSO) has been optimized from various aspects since it was proposed. Optimization of PSO can be realized by optimizing its iterative process or the initial parameters and heuristic methods have been combined with the initial PSO algorithm to improve its performance. In this paper, we introduce the simplicial algorithm (SA) of fixed point theory into the optimization of PSO and proposed a FP-PSO (Fixed-point PSO) improved algorithm. In FP-PSO algorithm, the optimization of target function is converted into the problem of solving a fixed point equation set, and the solution set obtained by simplicial algorithm (SA) of fixed point theory is used as the initial population of PSO algorithm, then the remaining parameters can be obtained accordingly with classical PSO algorithm. Since the fixed point method has sound mathematical properties, the initial population obtained with FP-PSO include nearly all the approximate local extremes which maintain the diversity of population and can optimize the flight direction of particles, and shows their advantages on setting other initial parameters. We make an experimental study with five commonly used testing functions from UCI (University of California Irvine) which include two single-peak functions and three multi-peak functions. The results indicate that the convergence accuracy, stability, and robustness of FP-PSO algorithm are significantly superior to existing improve strategies which also optimize PSO algorithm by optimizing initial population, especially when dealing with complex situations. In addition, we nest the FP-PSO algorithm with four classical improved PSO algorithms that improve PSO by optimizing iterative processes, and carry out contrast experiments on three multi-peak functions under different conditions (rotating or non-rotating). The experimental results show that the performance of the improved algorithm using nested strategy are also significantly enhanced compared with
The simplicial algorithm is a kind of branch-and-bound method for computing a globally optimal solution of a convex maximization problem. Its convergence under the omega-subdivision strategy was an open question for s...
详细信息
The simplicial algorithm is a kind of branch-and-bound method for computing a globally optimal solution of a convex maximization problem. Its convergence under the omega-subdivision strategy was an open question for some decades until Locatelli and Raber proved it (J Optim Theory Appl 107: 69-79, 2000). In this paper, we modify their linear programming relaxation and give a different and simpler proof of the convergence. We also develop a new convergent subdivision strategy, and report numerical results of comparing it with existing strategies.
The simplicial algorithm is a popular branch-and-bound approach to the convex maximization problem with multiple local maxima. In this paper, we discuss some difficulties revealed when implementing this algorithm unde...
详细信息
The simplicial algorithm is a popular branch-and-bound approach to the convex maximization problem with multiple local maxima. In this paper, we discuss some difficulties revealed when implementing this algorithm under the omega-subdivision rule. To overcome those, we modify the bounding process and extend the omega-subdivision rule. We also report numerical results for the simplicial algorithm according to the new subdivision rule.
In this paper, we refine the proof of convergence by Kuno-Buckland (J Global Optim 52: 371-390, 2012) for the simplicial algorithm with omega-subdivision and generalize their omega-bisection rule to establish a class ...
详细信息
In this paper, we refine the proof of convergence by Kuno-Buckland (J Global Optim 52: 371-390, 2012) for the simplicial algorithm with omega-subdivision and generalize their omega-bisection rule to establish a class of subdivision rules, omega-called.k-section, which bounds the number of subsimplices generated in a single execution of subdivision by a prescribed number k. We also report some numerical results of comparing the omega-k-section rule with the usual omega-subdivision rule.
In this paper, we obtain an existence theorem of a connected set of solutions to a nonlinear variational inequality with explicit nonlinear constraints. This result follows in a constructive way by designing a simplic...
详细信息
In this paper, we obtain an existence theorem of a connected set of solutions to a nonlinear variational inequality with explicit nonlinear constraints. This result follows in a constructive way by designing a simplicial algorithm. The algorithm operates on a triangulation of the unbounded regions and generates a piecewise linear path of parametrized stationary points. Each point on the path is an approximate solution. (c) 2006 Elsevier Ltd. All rights reserved.
A new variable dimension simplicial restart algorithm is introduced to compute economic equilibria. The number of rays along which the algorithm can leave the starting point differs from the thusfar known algorithms. ...
详细信息
A new variable dimension simplicial restart algorithm is introduced to compute economic equilibria. The number of rays along which the algorithm can leave the starting point differs from the thusfar known algorithms. More precisely, the new algorithm has one ray to each of the 2 n+1?2 faces of then-dimensional price simplex, whereas the existing algorithms haven+1 rays either to each facet or to each vertex of the unit simplex. The path of points followed by the algorithm can be interpreted as a globally and universally convergent price adjustment process. The process is also economically meaningful and therefore it is a good alternative for the well-known Walras' tatonnement process. Computational results show that the algorithm is competitive with the most efficient simplicial algorithms developed thusfar.
We present an efficient simplicial algorithm for computing a zero of a point-to-set mapping that is formed by piecing together smooth functions. Such mappings arise in nonlinear programming and economic equilibrium pr...
详细信息
We present an efficient simplicial algorithm for computing a zero of a point-to-set mapping that is formed by piecing together smooth functions. Such mappings arise in nonlinear programming and economic equilibrium problems. Our algorithm, under suitable regularity conditions on the problem, generates a sequence converging at least Q-superlinearly to a zero of the mapping. Asymptotically, it operates in a space of reduced dimension, analogous to an active set strategy in the optimization setting, but it switches active sets automatically. Results of computational experiments are given.
暂无评论