Global Optimization

NONLINEAR OPTIMIZATION IN MODELING ENVIRONMENTS: Software Implementations for Compilers, Spreadsheets, Modeling Languages, and Integrated Computing Systems

  • János Pintér
    • Categories Applications - Science and Engineering, Global Optimization, Optimization Software and Modeling Systems Tags ,

    We present a review of several professional software products that serve to analyze and solve nonlinear (global and local) optimization problems across a variety of hardware and software environments. The product versions discussed have been implemented for compiler platforms, spreadsheets, algebraic (optimization) modeling languages, and for integrated scientific-technical computing systems. The discussion highlights some of … Read more

    A Population Based Approach for Hard Global Optimization Problems Based on Dissimilarity Measures

  • Andrea Grosso
  • Marco Locatelli
  • Fabio Schoen
    • Categories Chemical Engineering, Global Optimization, Stochastic Approaches Tags , , , , ,

    When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different … Read more

    A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

    GRASP with path-relinking for the weighted maximum satisfiability problem

  • Paola Festa
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Leonidas S. Pitsoulis
    • Categories Meta Heuristics, Stochastic Approaches Tags , , ,

    A GRASP with path-relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multi-start metaheuristic, where at each iteration locally optimal solutions are constructed, each independent of the others. Previous experimental results indicate its effectiveness for solving weighted … Read more

    Convergence of a hybrid projection-proximal point algorithm coupled with approximation methods in convex optimization

  • Felipe Álvarez
  • Miguel Carrasco
  • Karine Pichard
    • Categories Convex Optimization, Global Optimization

    In order to minimize a closed convex function that is approximated by a sequence of better behaved functions, we investigate the global convergence of a generic diagonal hybrid algorithm, which consists of an inexact relaxed proximal point step followed by a suitable orthogonal projection onto a hyperplane. The latter permits to consider a fixed relative … Read more

    Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

    Jordan-algebraic aspects of nonconvex optimization over symmetric cones

  • Leonid Faybusovich
  • Ye Lu
    • Categories Global Optimization Theory Tags , ,

    We illustrate the usefulness of Jordan-algebraic technique for nonconvex optimization by considering a potential-reduction algorithm for a nonconvex quadratic function over the domain obtained as the intersection of a symmetric cone with an affine subspace CitationPreprint, September,2004ArticleDownload View PDF

    Optimal distance separating halfspace

  • Emilio Carrizosa
  • Frank Plastria
    • Categories Data-Mining, Global Optimization Applications Tags , ,

    One recently proposed criterion to separate two datasets in discriminant analysis, is to use a hyperplane which minimises the sum of distances to it from all the misclassified data points. Here all distances are supposed to be measured by way of some fixed norm,while misclassification means lying on the wrong side of the hyperplane, or … Read more

    Optimal expected-distance separating halfspace

  • Emilio Carrizosa
  • Frank Plastria
    • Categories Data-Mining, Global Optimization Applications, Statistics Tags , ,

    One recently proposed criterion to separate two datasets in discriminant analysis, is to use a hyperplane which minimises the sum of distances to it from all the misclassified data points. Here all distances are supposed to be measured by way of some fixed norm, while misclassification means lying on the wrong side of the hyperplane, … Read more

    A Piecewise Linearization Framework for Retail Shelf Space Management Models

  • Faiz Al-Khayyal
  • Jens Irion
  • J-C Lu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Marketing

    Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more