Month: July 2003

Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines

  • Thomas Serafini
  • Luca Zanni
  • Gaetano Zanghirati
    • Categories Data-Mining, Quadratic Programming Tags , , , ,

    Gradient projection methods based on the Barzilai-Borwein spectral steplength choices are considered for quadratic programming problems with simple constraints. Well known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches the behavior of different combinations of the two spectral steplengths is investigated. A nw adaptive stplength alternating rule is proposed, … Read more

    Reservoir Operation by Ant Colony Optimization Algorithms

  • Abbas Afshar
  • Mohammad Reza Jalali
  • M. A. Marino
    • Categories Civil and Environmental Engineering, Meta Heuristics

    In this paper, ant colony optimization (ACO) algorithms are proposed for reservoir operation. Through a collection of cooperative agents called ants, the nearoptimum solution to the reservoir operation can be effectively achieved. To apply ACO algorithms, the problem is approached by considering a finite horizon with a time series of inflow, classifying the reservoir volume … Read more

    Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming

  • Levent Tunçel
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more

    Polyhedral Analysis for Concentrator Location Problems

  • Martine Labbé
  • Hande Yaman
    • Categories Branch and Cut Algorithms, Polyhedra, Telecommunications Tags , ,

    The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We … Read more

    Domination analysis for minimum multiprocessor scheduling

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms Tags , ,

    Let $P$ be a combinatorial optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,s)$ is the maximal real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $s$ is not worse than at least the fraction $q$ of the feasible solutions … Read more

    Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more

    Sharpening the Karush-John optimality conditions

  • Arnold Neumaier
  • Hermann Schichl
    • Categories Constrained Nonlinear Optimization Tags , ,

    A refined version of the Karush-John first order optimality conditions is presented which reduces the number of constraints for which a constraint qualification is needed. This version is a generalization both of the Karush-John conditions and of the first order optimality conditions for concave constraints. Article Download View Sharpening the Karush-John optimality conditions

    Mathematical optimization for the inverse problem of intensity modulated radiation therapy

  • Yair Censor
    • Categories Biomedical Applications, Global Optimization Applications Tags , , , , ,

    In this tutorial we discuss modeling issues in intensity modulated radiation therapy, contrasting the continuous model with the fully-discretized one and considering feasibility formulations versus optimization setups. We review briefly some mathematical optimization techniques for IMRT. These include global optimization, multi-objective optimization, linear and mixed integer programming and projection methods. Citation in: J.R. Palta and … Read more

    The global optimization of Morse clusters by potential energy transformations

  • Jon P. K. Doye
  • Marco Locatelli
  • Robert H. Leary
  • Fabio Schoen
    • Categories Basic Sciences Applications, Biomedical Applications, Stochastic Approaches

    The Morse potential is a simple model pair potential that has a single parameter $\rho$ which determines the width of the potential well and allows a wide variety of materials to be modelled. Morse clusters provide a particularly tough test system for global optimization algorithms, and one that is highly relevant to methods that are … Read more

    Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , ,

    We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear costs on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory capacities explicitly and give exact separation algorithms. We also give a … Read more