Month: February 2011

Derivative-free Optimization of Expensive Functions with Computational Error Using Weighted Regression

  • Stephen Billups
  • Peter Graf
  • Jeffrey Larson
    • Categories Unconstrained Optimization Tags , , ,

    We propose a derivative-free algorithm for optimizing computationally expensive functions with computational error. The algorithm is based on the trust region regression method by Conn, Scheinberg, and Vicente [4], but uses weighted regression to obtain more accurate model functions at each trust region iteration. A heuristic weighting scheme is proposed which simultaneously handles i) differing … Read more

    SOME REGULARITY RESULTS FOR THE PSEUDOSPECTRAL ABSCISSA AND PSEUDOSPECTRAL RADIUS OF A MATRIX

  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Global Optimization Theory, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    The $\epsilon$-pseudospectral abscissa $\alpha_\epsilon$ and radius $\rho_\epsilon$ of an n x n matrix are respectively the maximal real part and the maximal modulus of points in its $\epsilon$-pseudospectrum, defined using the spectral norm. It was proved in [A.S. Lewis and C.H.J. Pang. Variational analysis of pseudospectra. SIAM Journal on Optimization, 19:1048-1072, 2008] that for fixed … Read more

    On Nesterov’s Nonsmooth Chebyschev-Rosenbrock Functions

  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization

    We discuss two nonsmooth functions on R^n introduced by Nesterov. We show that the first variant is partly smooth in the sense of [A.S. Lewis. Active sets, nonsmoothness and sensitivity. SIAM Journal on Optimization, 13:702–725, 2003.] and that its only stationary point is the global minimizer. In contrast, we show that the second variant has … Read more

    Dippy — a simplified interface for advanced mixed-integer programming

  • Iain Dunning
  • Stuart Mitchell
  • Cameron Walker
  • Qi-Shan Lim
  • Michael O'Sullivan
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems

    Mathematical modelling languages such as AMPL, GAMS, and Xpress-MP enable mathematical models such as mixed-integer linear programmes (MILPs) to be expressed clearly for solution in solvers such as CPLEX, MINOS and Gurobi. However some models are sufficiently difficult that they cannot be solved using “out-of-the-box” solvers, and customisation of the solver framework to exploit model-specific … Read more

    A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming

    Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In … Read more

    Affine recourse for the robust network design problem: between static and dynamic routing

  • Michael Poss
  • Christian Raack
    • Categories Combinatorial Optimization, Network Optimization, Robust Optimization Tags , , , , ,

    Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework … Read more

    On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Optimization Tags , , ,

    We estimate the worst-case complexity of minimizing an unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularization method applied to it takes at most O($\epsilon^{-2}$) function-evaluations to reduce the … Read more

    There is no variational characterization of the cycles in the method of periodic projections

  • J.-B. Baillon
  • Patrick L. Combettes
  • Roberto Cominetti
    • Categories Convex Optimization, Infinite Dimensional Optimization Tags , , ,

    The method of periodic projections consists in iterating projections onto $m$ closed convex subsets of a Hilbert space according to a periodic sweeping strategy. In the presence of $m\geq 3$ sets, a long-standing question going back to the 1960s is whether the limit cycles obtained by such a process can be characterized as the minimizers … Read more

    On the Number of Solutions Generated by Dantzig’s Simplex Method for LP with Bounded Variables

  • Tomonari Kitahara
  • Tomomi Matsui
  • Shinji Mizuno
    • Categories Linear Programming Tags , , , , ,

    We give an upper bound for the number of different basic feasible solutions generated by Dantzig’s simplex method (the simplex method with the most negative pivoting rule) for LP with bounded variables by extending the result of Kitahara and Mizuno (2010). We refine the analysis by them and improve an upper bound for a standard … Read more