Global Optimization

Welfare-Maximizing Correlated Equilibria using Kantorovich Polynomials with Sparsity

  • Fook Wai Kong
  • Berc Rustem
    • Categories Game Theory, Global Optimization, Semi-definite Programming Tags , , , , ,

    We propose an algorithm that computes the epsilon-correlated equilibria with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive an infinite-dimensional formulation of epsilon-correlated equilibria using Kantorovich polynomials and re-express it as a polynomial positivity constraint. In addition, we exploit polynomial sparsity to achieve a leaner problem formulation involving Sum-Of-Squares … Read more

    An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Global Optimization Theory Tags , ,

    We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of nonlinear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme … Read more

    Constrained Derivative-Free Optimization on Thin Domains

  • José Mario Martínez
  • Francisco N. C. Sobral
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Nonlinear Optimization Tags , , , ,

    Many derivative-free methods for constrained problems are not efficient for minimizing functions on “thin” domains. Other algorithms, like those based on Augmented Lagrangians, deal with thin constraints using penalty-like strategies. When the constraints are computationally inexpensive but highly nonlinear, these methods spend many potentially expensive objective function evaluations motivated by the difficulties of improving feasibility. … Read more

    Proximal point method on Finslerian manifolds and the “Effort Accuracy Trade off”

  • J. X. da Cruz Neto
  • Paulo Roberto Oliveira
  • Antoine Soubeyran
  • Pedro A. Soares Jr.
    • Categories Applications - Science and Engineering, Global Optimization Applications, Nonlinear Optimization

    In this paper we consider minimization problems with constraints. We will show that if the set of constraints is a Finslerian manifold of non positive flag curvature, and the objective function is di fferentiable and satisfi es the property Kurdyka-Lojasiewicz, then the proximal point method is naturally extended to solve that class of problems. We will prove … Read more

    A Python/C library for bound-constrained global optimization with continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Ricardo M.A. Silva
    • Categories Global Optimization, Optimization Software and Modeling Systems, Stochastic Approaches Tags , , , , , , , ,

    This paper describes libcgrpp, a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an … Read more

    Global optimization of expensive black box problems with a known lower bound

  • Andrea Cassioli
  • Fabio Schoen
    • Categories Global Optimization, Optimization of Simulated Systems Tags , , , ,

    In this paper we propose an algorithm for the global optimization of computationally expensive black–box functions. For this class of problems, no information, like e.g. the gradient, can be obtained and function evaluation is highly expensive. In many applications, however, a lower bound on the objective function is known; in this situation we derive a … Read more

    Representing quadratically constrained quadratic programs as generalized copositive programs

  • Samuel Burer
  • Hongbo Dong
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We show that any nonconvex quadratically constrained quadratic program(QCQP) can be represented as a generalized copositive program. In fact,we provide two representations. The first is based on the concept of completely positive (CP) matrices over second order cones, while the second is based on CP matrices over the positive semidefinte cone. Our analysis assumes that … Read more

    Line search methods with variable sample size for unconstrained optimization

  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Global Optimization Tags , , , ,

    Minimization of unconstrained objective function in the form of mathematical expectation is considered. Sample Average Approximation – SAA method transforms the expectation objective function into a real-valued deterministic function using large sample and thus deals with deterministic function minimization. The main drawback of this approach is its cost. A large sample of the random variable … Read more

    An Outcome Space Algorithm for Minimizing the Product of Two Convex Functions over a Convex Set

  • Quang Thuy Le
  • Thi Bach Kim Nguyen
  • Nam Nguyen Canh
    • Categories Global Optimization, Nonlinear Optimization Tags , , ,

    This paper presents an outcome-space outer approximation algorithm for solving the problem of minimizing the product of two convex functions over a compact convex set in $\R^n$. The computational experiences are reported. The proposed algorithm is convergent. ArticleDownload View PDF

    Unharnessing the power of Schrijver’s permanental inequality

  • Leonid Gurvits
    • Categories Combinatorial Optimization, Global Optimization Theory Tags ,

    Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality \begin{equation} \label{le} per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n \end{equation} We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\ For all … Read more