Month: March 2006

Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    Two corrector-predictor interior point algorithms are proposed for solving mono\-tone linear complementarity problems. The algorithms produce a sequence of iterates in the $\caln_{\infty}^{-}$ neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm … Read more

    Towards nonsymmetric conic optimization

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we propose a new interior-point method, which is based on an extension of the ideas of self-scaled optimization to the general cones. We suggest using the primal correction process to find a {\em scaling point}. This point is used to compute a strictly feasible primal-dual pair by simple projection. Then, we define … Read more

    Packing and Partitioning Orbitopes

  • Volker Kaibel
  • Marc E. Pfetsch
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal sub ject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain … Read more

    OSiL: An Instance Language for Optimization

  • Robert Fourer
  • Jun Ma
  • Kipp Martin
    • Categories Modeling Languages and Systems, Optimization Software and Modeling Systems, Optimization Software Design Principles

    Distributed computing technologies such as Web Services are growing rapidly in importance in today’s computing environment. In the area of mathematical optimization, it is becoming increasingly common to separate modeling languages from optimization solvers. In fact, the modeling language software, solver software, and data used to generate a model instance might reside on different machines … Read more

    A unified approach for inversion problems in intensity-modulated radiation therapy

  • Thomas Bortfeld
  • Yair Censor
  • Benjamin Martin
  • Alexei Trofimov
    • Categories Biomedical Applications, Nonlinear Optimization

    We propose and study a unified model for handling dose constraints (physical dose, equivalent uniform dose (EUD), etc.) and radiation source constraints in a single mathematical framework based on the split feasibility problem. The model does not impose on the constraints an exogenous objective (merit) function. The optimization algorithm minimizes a weighted proximity function that … Read more

    Nonserial dynamic programming and local decomposition algorithms in discrete programming

  • Arnold Neumaier
  • Oleg Shcherbina
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

    One of perspective ways to exploit sparsity in the dependency graph of an optimization problem as J.N. Hooker stressed is nonserial dynamic programming (NSDP) which allows to compute solution in stages, each of them uses results from previous stages. The class of discrete optimization problems with the block-tree-structure matrix of constraints is considered. Nonserial dynamic … Read more

    On forests, stable sets and polyhedras associated with clique partitions

  • Denis Cornaz
    • Categories Combinatorial Optimization, Graphs and Matroids, Polyhedra Tags , ,

    Let $G=(V,E)$ be a simple graph on $n$ nodes. We show how to construct a partial subgraph $D$ of the line graph of $G$ satisfying the identity: $\overline \chi(G)+\alpha(D)=n$, where $\overline \chi(G)$ denotes the minimum number of cliques in a clique partition of $G$ and $\alpha(D)$ denotes the maximum size of a stable set of … Read more

    A Particle Swarm Pattern Search Method for Bound Constrained Nonlinear Optimization

  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Global Optimization, Nonlinear Optimization, Optimization Software Benchmark Tags , , , , ,

    In this paper we develop, analyze, and test a new algorithm for the global minimization of a function subject to simple bounds without the use of derivatives. The underlying algorithm is a pattern search method, more specifically a coordinate search method, which guarantees convergence to stationary points from arbitrary starting points. In the optional search … Read more

    On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis

  • Laurent El Ghaoui
    • Categories Robust Optimization, Semi-definite Programming, Statistics Tags , , ,

    We examine the problem of approximating a positive, semidefinite matrix $\Sigma$ by a dyad $xx^T$, with a penalty on the cardinality of the vector $x$. This problem arises in sparse principal component analysis, where a decomposition of $\Sigma$ involving sparse factors is sought. We express this hard, combinatorial problem as a maximum eigenvalue problem, in … Read more

    The p-median polytope of restricted Y-graphs

  • Mourad Baiou
  • Francisco Barahona
    • Categories Polyhedra Tags , ,

    We further study the effect of odd cycle inequalities in the description of the polytopes associated with the p-median and uncapacitated facility location problems. We show that the obvious integer linear programming formulation together with the odd cycle inequalities completely describe these polytopes for the class of restricted Y-graphs. This extends our results for the … Read more