Nonlinear-Programming Reformulation of the Order-Value Optimization problem

  • Roberto Andreani
  • José Mario Martínez
  • Cibele Dunder
    • Categories Nonlinear Optimization Tags , , , ,

    Order-value optimization (OVO) is a generalization of the minimax problem motivated by decision-making problems under uncertainty and by robust estimation. New optimality conditions for this nonsmooth optimization problem are derived. An equivalent mathematical programming problem with equilibrium constraints is deduced. The relation between OVO and this nonlinear-programming reformulation is studied. Particular attention is given to … Read more

    A shifted Steihaug-Toint method for computing a trust-region step.

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Unconstrained Optimization Tags , , , , ,

    Trust-region methods are very convenient in connection with the Newton method for unconstrained optimization. The More-Sorensen direct method and the Steihaug-Toint iterative method are most commonly used for solving trust-region subproblems. We propose a method which combines both of these approaches. Using the small-size Lanczos matrix, we apply the More-Sorensen method to a small-size trust-region … Read more

    Semi-Lagrangian relaxation

  • Cesar Beltran
  • Jean-Philippe Vial
  • Claude Tadonki
    • Categories Combinatorial Optimization Tags , , ,

    Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We propose a modified Lagrangian relaxation which used in (linear) combinatorial optimization with equality constraints generates an optimal integer solution. We call this new concept semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median … Read more

    Constrained Global Optimization with Radial Basis Functions

  • Jan-Erik Käck
    • Categories Global Optimization Theory, Optimization of Simulated Systems Tags , , ,

    Response surface methods show promising results for global optimization of costly non convex objective functions, i.e. the problem of finding the global minimum when there are several local minima and each function value takes considerable CPU time to compute. Such problems often arise in industrial and financial applications, where a function value could be a … Read more

    Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification

  • Roberto Andreani
  • Ernesto G. Birgin
  • José Mario Martínez
  • María Laura Schuverdt
    • Categories Nonlinear Optimization Tags , , ,

    Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under … Read more

    Perturbation analysis of second order programming problems

  • Joseph Frédéric Bonnans
  • Héctor Ramírez
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming Tags , , , ,

    We discuss first and second order optimality conditions for nonlinear second-order cone programming problems, and their relation with semidefinite programming problems. For doing this we extend in an abstract setting the notion of optimal partition. Then we state a characterization of strong regularity in terms of second order optimality conditions. Citation Research Report 5293 (August … Read more

    Survivable IP network design with OSPF routing

  • Luciana S. Buriol
  • Mauricio G.C. Resende
  • Mikkel Thorup
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , ,

    Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing … Read more

    Dual versus primal-dual interior-point methods for linear and conic programming

  • Michael J. Todd
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path to detect primal infeasibility and dual unboundedness, dual methods are implicitly moving {\em away} from the analytic center of … Read more

    Domination between traffic matrices

  • Gianpaolo Oriolo
    • Categories Combinatorial Optimization, Network Optimization, Telecommunications Tags ,

    A traffic matrix $D^1$ dominates a traffic matrix $D^2$ if $D^2$ can be routed on every (capacitated) network where $D^1$ can be routed. We prove that $D^1$ dominates $D^2$ if and only if $D^1$, considered as a capacity vector, supports $D^2$. We show several generalizations of this result. Citation Centro Vito Volterra, Universita’ di Roma … Read more

    Complex Quadratic Optimization and Semidefinite Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more