On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , ,

    When solving the general smooth nonlinear optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy $\epsilon$ can be obtained by a second-order method using cubic regularization in at most $O(\epsilon^{-3/2})$ problem-functions evaluations, the same order bound as in the unconstrained case. This result is obtained by first showing that the … Read more

    On the Transportation Problem with Market Choice

  • Pelin Damci-Kurt
  • Santanu S. Dey
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , ,

    We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice … Read more

    2-Stage Robust MILP with continuous recourse variables

  • Alain Billionnet
  • Marie-Christine Costa
  • Pierre-Louis Poirion
    • Categories Combinatorial Optimization Tags ,

    We solve a linear robust problem with mixed-integer first-stage variables and continuous second stage variables. We consider column wise uncertainty. We first focus on a problem with right hand-side uncertainty which satisfies a “full recourse property” and a specific definition of the uncertainty. We propose a solution based on a generation constraint algorithm. Then we … Read more

    Maxwell-Boltzmann and Bose-Einstein Distributions for the SAT Problem

  • Claudio Angione
  • Giuseppe Nicosia
  • Annalisa Occhipinti
    • Categories Applications - Science and Engineering, Combinatorial Optimization Tags , , ,

    Recent studies in theoretical computer science have exploited new algorithms and methodologies based on statistical physics for investigating the structure and the properties of the Satisfiability problem. We propose a characterization of the SAT problem as a physical system, using both quantum and classical statistical-physical models. We associate a graph to a SAT instance and … Read more

    A double projection method for solving variational inequalities without monotonicity

  • Ye Minglu
  • He Yiran
    • Categories Complementarity and Variational Inequalities Tags , ,

    We present a double projection algorithm for solving variational inequalities without monotonicity. If the solution of dual variational inequality does exist, then the sequence produced by our method is globally convergent to a solution. Under the same assumption, the sequence produced by known methods has only a subsequence converging to a solution. Numerical experiments are … Read more

    Which Nonnegative Matrices Are Slack Matrices?

  • João Gouveia
  • Volker Kaibel
  • R. Grappe
  • K. Pashkovich
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear Programming, Polyhedra Tags , , ,

    In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verifi cation problem whose complexity is unknown. CitationApril 2013ArticleDownload View PDF

    A Perturbed Sums of Squares Theorem for Polynomial Optimization and its Applications

  • Masakazu Muramatsu
  • Levent Tunçel
  • Hayato Waki
    • Categories Convex Optimization, Quadratic Programming, Semi-definite Programming

    We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a Polynomial Optimization Problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by $(f^¥ast – ¥epsilon)$ and from above by $f^¥ast … Read more

    Adjustable Robust Parameter Design with Unknown Distributions

  • Dick den Hertog
  • Jack P.C. Kleijnen
  • Ihsan Yanıkoğlu
    • Categories Robust Optimization

    This article presents a novel combination of robust optimization developed in mathematical programming, and robust parameter design developed in statistical quality control. Robust parameter design uses metamodels estimated from experiments with both controllable and environmental inputs (factors). These experiments may be performed with either real or simulated systems; we focus on simulation experiments. For the … Read more

    Incremental and Encoding Formulations for Mixed Integer Programming

  • Juan Pablo Vielma
  • Sercan Yildiz
    • Categories (Mixed) Integer Linear Programming

    The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this … Read more

    Optimal scaling of the ADMM algorithm for distributed quadratic programming

  • Euhanna Ghadimi
  • Mikael Johansson
  • Henrik Sandberg
  • Iman Shames
  • André Teixeira
    • Categories Network Optimization, Quadratic Programming Tags ,

    This paper presents optimal scaling of the alternating directions method of multipliers (ADMM) algorithm for a class of distributed quadratic programming problems. The scaling corresponds to the ADMM step-size and relaxation parameter, as well as the edge-weights of the underlying communication graph. We optimize these parameters to yield the smallest convergence factor of the algorithm. … Read more