A hybrid algorithm for nonlinear equality constrained optimization problems: global and local convergence theory

  • Mohammedi El Hallabi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Robust Optimization Tags , , , , , , ,

    In this paper we combine both trust-region and linesearch globalization strategies in a globally convergent hybrid algorithm to solve a continuously differentiable nonlinear equality constrained minimization problem. First, the trust-region approach is used to determine a descent direction of the augmented Lagrangian chosen as the merit function, and second, linesearch techniques are used to obtain … Read more

    Maximising Revenue in the Airline Industry Under One-Way Pricing

  • Miguel F. Anjos
  • Russell C H Cheng
  • Christine S M Currie
    • Categories Airline Optimization, Applications - OR and Management Sciences, Yield Management Tags , , ,

    This paper describes a methodology that has been implemented in a major British airline to find the optimal price to charge for airline tickets under one-way pricing. An analytical model has been developed to describe the buying behaviour of customers for flights over the selling period. Using this model and a standard analytical method for … Read more

    Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Control Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more

    Partition of a Set of Integers into Subsets with Prescribed Sums

  • Wang Yiju
    • Categories Graphs and Matroids Tags , ,

    A nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k \rangle$ is said to be {\em $n$-realizable\/} if the set $I_n=\{ 1,2,\cdots,n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,\cdots, S_k$ such that $\sum\limits_{x\in S_i}x=m_i$ for each $1\le i\le k$. In this paper, we will prove that a nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k\rangle$ is … Read more

    Effective reformulations of the truss topology design problem

  • Michal Kočvara
  • Jiri V. Outrata
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Nonlinear Optimization Tags ,

    We present a new formulation of the truss topology problem that results in unique design and unique displacements of the optimal truss. This is reached by adding an upper level to the original optimization problem and formulating the new problem as an MPCC (Mathematical Program with Complementarity Constraints). We derive optimality conditions for this problem … Read more

    Computational study of large-scale p-Median problems

  • Pasquale Avella
  • Antonio Sassano
  • Igor Vasil'ev
    • Categories Branch and Cut Algorithms Tags , ,

    Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure … Read more

    Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter $t$ and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation … Read more

    When the greedy algorithm fails

  • Joergen Bang-Jensen
  • Gregory Gutin
  • Anders Yeo
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics

    We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message … Read more

    Design and analysis of an approximation algorithm for Stackelberg network pricing

  • Patrice Marcotte
  • Sébastien Roch
  • Gilles Savard
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where … Read more