Month: September 2005

A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , , , , , , , ,

    The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

    Support Vector Machine via Sequential Subspace Optimization

  • Guy Narkiss
  • Michael Zibulevsky
    • Categories Data-Mining, Unconstrained Optimization Tags , , , ,

    We present an optimization engine for large scale pattern recognition using Support Vector Machine (SVM). Our treatment is based on conversion of soft-margin SVM constrained optimization problem to an unconstrained form, and solving it using newly developed Sequential Subspace Optimization (SESOP) method. SESOP is a general tool for large-scale smooth unconstrained optimization. At each iteration … Read more

    Pricing a class of exotic options via moments and SDP relaxations

  • Jean-Bernard Lasserre
  • Thomas Prieto-Rumeau
  • Mihail Zervos
    • Categories Finance and Economics, Optimization of Systems modeled by PDEs

    We present a new methodology for the numerical pricing of a class of exotic derivatives such as Asian or barrier options when the underlying asset price dynamics are modelled by a geometric Brownian motion or a number of mean-reverting processes of interest. This methodology identifies derivative prices with infinite-dimensional linear programming problems involving the moments … Read more

    Nonlinear optimal control: Numerical approximations via moments and LMI-relaxations

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Christophe Prieur
    • Categories Control Applications, Systems governed by Differential Equations Optimization

    We consider the class of nonlinear optimal control problems with all data (differential equation, state and control constraints, cost) being polynomials. We provide a simple hierarchy of LMI-relaxations whose optimal values form a nondecreasing sequence of lower bounds on the optimal value. Preliminary results show that good approximations are obtained with few moments. Citation LAAS … Read more

    SOS approximation of polynomials nonnegative on a real algebraic set

  • Jean-Bernard Lasserre
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory

    Let $V\subset R^n$ be a real algebraic set described by finitely many polynomials equations $g_j(x)=0,j\in J$, and let $f$ be a real polynomial, nonnegative on $V$. We show that for every $\epsilon>0$, there exist nonnegative scalars $\{\lambda_j\}_{j\in J}$ such that, for all $r$ sufficiently large, $f+\epsilon\theta_r+\sum_{j\in J} \lambda_j g_j^2$ is a sum of squares. Here, … Read more

    A sum of squares approximation of nonnegative polynomials

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Nonlinear Optimization

    We show that every real nonnegative polynomial $f$ can be approximated as closely as desired (in the $l_1$-norm of its coefficient vector) by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. The novelty is that each $f_\epsilon$ has a simple and explicit form in terms of $f$ and $\epsilon$. Citation SIAM J. Optimization … Read more

    A Homogeneous Model for Mixed Complementarity Problems over Symmetric Cones

  • Yedong Lin
  • Akiko Yoshise
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper, we propose a homogeneous model for solving monotone mixed complementarity problems over symmetric cones, by extending the results in \cite{YOSHISE04} for standard form of the problems. We show that the extended model inherits the following desirable features: (a) A path exists, is bounded and has a trivial starting point without any regularity … Read more

    The multi-item capacitated lot-sizing problem with setup times and shortage costs

  • Nabil Absi
  • Safia Kedad-Sidhoum
    • Categories Branch and Cut Algorithms, Production and Logistics Tags , , , , , ,

    We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities … Read more

    A Note on Multiobjective Optimization and Complementarity Constraints

  • Sven Leyffer
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Multi-Criteria Optimization Tags , , ,

    We propose a new approach to convex nonlinear multiobjective optimization that captures the geometry of the Pareto set by generating a discrete set of Pareto points optimally. We show that the problem of finding an optimal representation of the Pareto surface can be formulated as a mathematical program with complementarity constraints. The complementarity constraints arise … Read more

    Blind Source Separation using Relative Newton Method combined with Smoothing Method of Multipliers

  • Michael Zibulevsky
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , , , ,

    We study a relative optimization framework for quasi-maximum likelihood blind source separation and relative Newton method as its particular instance. The structure of the Hessian allows its fast approximate inversion. In the second part we present Smoothing Method of Multipliers (SMOM) for minimization of sum of pairwise maxima of smooth functions, in particular sum of … Read more