Search

In this paper we study numerical stability of path-based algorithms for the traffic assignment problem. These algorithms are based on decomposition of the original problem into smaller sub-problems which are optimized sequentially. Previously, path-based algorithms were numerically tested only in the setting of moderate requirements to the level of solution precision. In this study we analyse convergence of these methods when the convergence measure approaches machine epsilon of IEEE double precision format. In particular, we demonstrate that the straightforward implementation of one of the algorithms of this group (projected gradient) suffers from loss of precision and is not able to converge to highly precise solution. We propose a way to solve this problem and test the proposed adjusted version of the algorithm on various benchmark instances. [ABSTRACT FROM AUTHOR]

The eigenvalue complementarity problem (EiCP) differs from the traditional eigenvalue problem in that the primal and dual variables belong to a closed and convex coneKand its dual, respectively, and satisfy a complementarity condition. In this paper we investigate the solution of the second-order cone EiCP (SOCEiCP) whereKis the Lorentz cone. We first show that the SOCEiCP reduces to a special Variational Inequality Problem on a compact set defined byKand a normalization constraint. This guarantees that SOCEiCP has at least one solution, and a new enumerative algorithm is introduced for finding a solution to this problem. The method is based on finding a global minimum of an appropriate nonlinear programming (NLP) formulation of the SOCEiCP using a special branching scheme along with a local nonlinear optimizer that computes stationary points on subsets of the feasible region of NLP associated with the nodes generated by the algorithm. A semi-smooth Newton's method is combined with this enumerative algorithm to enhance its numerical performance. Our computational experience illustrates the efficacy of the proposed techniques in practice. [ABSTRACT FROM AUTHOR]

This paper extends the technique used in the damped BFGS method of Powell [Algorithms for nonlinear constraints that use Lagrange functions, Math. Program. 14 (1978), 224–248] to the Broyden family of quasi-Newton methods with applications to unconstrained optimization problems. Appropriate conditions on the damped technique are proposed to enforce safely the positive definiteness property for all Broyden's updates. It is shown that this technique maintains theq-superlinear convergence property of the restricted Broyden family of methods for uniformly convex functions. It also extends the global convergence property to all members of the family. Preliminary numerical results are described which show that appropriate ways for employing the proposed technique improve the performance of all members of the Broyden family of methods substantially and significantly in certain cases. They also enforce convergence of divergent quasi-Newton methods. [ABSTRACT FROM AUTHOR]

The Chinese postman problem is a famous and classical problem in graph theory. This paper introduces a new variant of this problem, namely, the time-dependent rural postman problem, which is motivated by applications, involving scheduling with time-dependent processing time. We present an arc-path formulation for the problem with a constraint set that is divided into two parts. The first part is linear and has a strong combinatorial structure, which defines the polytope of the arc-path alternation sequence (APAS), while the second part is nonlinear and is closely related to time-dependent travel time. First, we investigate the facial structure of the APAS polytope and present several facet inequalities. Second, considering the travel and service time functions as piecewise functions, we linearize the nonlinear inequalities and propose several strong, valid inequalities. Finally, we propose a cutting plane algorithm and report numerical results on several randomly generated instances. [ABSTRACT FROM PUBLISHER]

This paper first proposes a trust region algorithm to obtain a stationary point of unconstrained multiobjective optimisation problem. Under suitable assumptions, the global convergence of the new algorithm is established. We then extend the trust region method to solve the non-smooth multiobjective optimisation problem. [ABSTRACT FROM PUBLISHER]

In this paper, we propose nonlinear programming (NLP) formulations and difference of convex functions (DC) programming approaches for the asymmetric eigenvalue complementarity problem (EiCP). The EiCP has a solution if and only if these NLP formulations have zero global optimal value. We reformulate the NLP formulations as DC programs which can be efficiently solved by a DC algorithm. Some preliminary numerical results illustrate the good performance of the proposed methods. [ABSTRACT FROM PUBLISHER]

Augmented Lagrangian methods are effective tools for solving large-scale nonlinear programming problems. At each outer iteration, a minimization subproblem with simple constraints, whose objective function depends on updated Lagrange multipliers and penalty parameters, is approximately solved. When the penalty parameter becomes very large, solving the subproblem becomes difficult; therefore, the effectiveness of this approach is associated with the boundedness of the penalty parameters. In this paper, it is proved that under more natural assumptions than the ones employed until now, penalty parameters are bounded. For proving the new boundedness result, the original algorithm has been slightly modified. Numerical consequences of the modifications are discussed and computational experiments are presented. [ABSTRACT FROM AUTHOR]

In this paper, we suggest a new conjugate gradient algorithm that for all k≥0 both the descent and the conjugacy conditions are guaranteed. The search direction is selected as a linear combination of−g k+1 and s k , where g k+1=∇ f(x k+1), s k =x k+1−x k and the coefficients in this linear combination are selected in such a way that both the descent and the conjugacy conditions are satisfied at every iteration. In order to define the algorithm and to prove its convergence, the modified Wolfe line search is introduced, in which the parameter in the standard second Wolfe condition is changed at every iteration. It is shown that for general nonlinear functions, the algorithm with modified Wolfe line search generates directions bounded away from infinity. The algorithm uses an acceleration scheme modifying the step length α k in such a manner as to improve the reduction of the function values along the iterations. Numerical comparisons with some conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that the computational scheme outperforms the known conjugate gradient algorithms like Hestenes and Stiefel, Polak et al., Dai and Yuan or hybrid Dai and Yuan, as well as the CG_DESCENT method by Hager and Zhang with the Wolfe line search conditions. [ABSTRACT FROM PUBLISHER]

Particle swarm optimization (PSO) is a population-based stochastic and derivative-free method that has been used to solve various optimization problems due to its simplicity and efficiency. While solving high-dimensional or complicated problems, PSO requires a large number of particles to explore the problem domains and consequently introduces high computational costs. In this paper, we focus on the acceleration of PSO for solving box-constrained, load-balanced optimization problems by parallelization on a graphics processing unit (GPU). We propose a GPU-accelerated PSO (GPSO) algorithm by using a thread pool model and implement GPSO on a GPU. Numerical results show that the GPU architecture fits the PSO framework well by reducing computational timing, achieving high parallel efficiency and finding better optimal solutions by using a large number of particles. For example, while solving the 100-dimensional test problems with 65,536 (16×212) particles, GPSO has achieved up to 280X and 83X speedups on a NVIDIA Tesla C1060 1.30 GHz GPU relative to an Intel Xeon-X5450 3.00 GHz central processing unit running in single- and quad-core mode, respectively. GPSO provides a promising method for tackling high-dimensional and difficult optimization problems using a low-cost and many-core GPU system. [ABSTRACT FROM PUBLISHER]

A level set method for the topological optimization of domains is proposed and analysed in this paper. The framework of the analysis is that of elliptic optimal control problems with a binary control acting as a source term of the state equation. The main ingredient of the algorithm is the concept of topological derivative. Convergence results are proven and illustrated by some numerical experiments. [ABSTRACT FROM AUTHOR]

We propose a quasi-Newton line-search method that uses negative curvature directions for solving unconstrained optimization problems. In this method, the symmetric rank-one (SR1) rule is used to update the Hessian approximation. The SR1 update rule is known to have a good numerical performance; however, it does not guarantee positive definiteness of the updated matrix. We first discuss the details of the proposed algorithm and then concentrate on its practical behaviour. Our extensive computational study shows the potential of the proposed method from different angles, such as its performance compared with some other existing packages, the profile of its computations, and its large-scale adaptation. We then conclude the paper with the convergence analysis of the proposed method. [ABSTRACT FROM AUTHOR]

Detection of copositivity plays an important role in combinatorial and quadratic optimization. Recently, an algorithm for copositivity detection by simplicial partition has been proposed. In this paper, we develop an improved depth-first simplicial partition algorithm which reduces memory requirements significantly and therefore enables copositivity checks of much larger matrices - of size up to a few thousands instead of a few hundreds. The algorithm has been investigated experimentally on a number of MaxClique problems as well as on generated random problems. We present numerical results showing that the algorithm is much faster than a recently published linear algebraic algorithm for copositivity detection based on traditional ideas - checking properties of principal sub-matrices. We also show that the algorithm works very well for solving MaxClique problems through copositivity checks. [ABSTRACT FROM AUTHOR]

The paper describes the design of our interior-point implementation to solve large-scale quadratically constrained convex optimization problems. We outline the details of the implemented algorithm, which is based on the primal-dual interior-point method. Our discussion includes topics related to starting point strategies and to the implementation of the numerical algebra employed, with emphasis on sparsity and stability issues. Computational results are given on a demonstrative set of convex quadratically constrained quadratic problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider correcting an inconsistent set of linear inequalities by minimal changes in problem data using the l2-norm. A new formulation of the problem is introduced, which involves minimizing a nonconvex fractional function. Then by utilizing the generalized Newton (GN) method, two heuristic algorithms are developed to solve the fractional minimization problem. We further consider correcting inconsistent linear inequalities with extra non-negativity constraints on the variables. For this specific case, we also propose two heuristic algorithms. Finally, we report encouraging numerical results. [ABSTRACT FROM AUTHOR]

A numerical study of model-based methods for derivative-free optimization is presented. These methods typically include a geometry phase whose goal is to ensure the adequacy of the interpolation set. The paper studies the performance of an algorithm that dispenses with the geometry phase altogether (and therefore does not attempt to control the position of the interpolation set). Data are presented describing the evolution of the condition number of the interpolation matrix and the accuracy of the gradient estimate. The experiments are performed on smooth unconstrained optimization problems with dimensions ranging between 2 and 15. [ABSTRACT FROM AUTHOR]

Motivated by a numerical example that shows that a feasible version of Mehrotra's original predictor-corrector algorithm might be inefficient in practice, Salahi et al. [M. Salahi, J. Peng and T. Terlaky, On Mehrotra-type predictor-corrector algorithms, to apper in SIAM J. Optim.] proposed a so-called safeguard-based variant of the algorithm that enjoys polynomial iteration complexity, although its practical efficiency is preserved. In this paper, we analyse the same Mehrotra's algorithm from a different perspective. We give a condition on the maximum step size in the predictor direction, the violation of which might imply a very small or zero step size in the corrector direction of the algorithm. This might explain the reason for occasional ill behaviour of the feasible version of Mehrotra's original algorithm. We propose to cut the maximum step size in the predictor direction if it is above a certain threshold. If this cut does not give a desirable step size, then we cut it for the second time that allows us to give a lower bound for the step size in the corrector direction. This enables us to prove an O(n5/2log (n/ε)) worst case iteration complexity bound for the new algorithm. By slightly modifying the Newton system in the corrector step, we reduce the iteration complexity to O (n3/2log (n/ε)). Finally, we report some illustrative computational results using the McIPM software package. [ABSTRACT FROM AUTHOR]