On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization

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

    The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente … Read more

    SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

  • Luigi Grippo
  • Veronica Piccialli
  • Laura Palagi
  • Mauro Piacentini
  • Giovanni Rinaldi
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more

    A quasi-Newton strategy for the sSQP method for variational inequality and optimization problems

  • Damián Fernández
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    The quasi-Newton strategy presented in this paper preserves one of the most important features of the stabilized Sequential Quadratic Programming method, the local convergence without constraint qualifications assumptions. It is known that the primal-dual sequence converges quadratically assuming only the second-order sufficient condition. In this work, we show that if the matrices are updated by … Read more

    Fairer Benchmarking of Optimization Algorithms via Derivative Free Optimization

  • Warren Hare
  • Y Wang
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Global Optimization Applications Tags , ,

    Research in optimization algorithm design is often accompanied by benchmarking a new al- gorithm. Some benchmarking is done as a proof-of-concept, by demonstrating the new algorithm works on a small number of dicult test problems. Alternately, some benchmarking is done in order to demonstrate that the new algorithm in someway out-performs previous methods. In this … Read more

    Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures

  • Vincent Guigues
  • Werner Romisch
    • Categories Stochastic Programming

    We define a risk averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk averse formulation of the problem. This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of … Read more

    On the acceleration of augmented Lagrangian method for linearly constrained optimization

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , ,

    The classical augmented Lagrangian method (ALM) plays a fundamental role in algorithmic development of constrained optimization. In this paper, we mainly show that Nesterov’s influential acceleration techniques can be applied to accelerate ALM, thus yielding an accelerated ALM whose iteration-complexity is O(1/k^2) for linearly constrained convex programming. As a by-product, we also show easily that … Read more

    Portfolio Selection under Model Uncertainty: A Penalized Moment-Based Optimization Approach

  • Roy H. Kwon
  • Jonathan Y. Li
    • Categories Finance and Economics, Robust Optimization, Semi-definite Programming Tags ,

    We present a new approach for portfolio selection when the underlying distribution of asset returns is uncertain or ambiguous to investors. In particular, we consider the case that an investor can formulate some reference financial models based on his/her prior beliefs or information, but is concerned about misspecification of the reference models and the associated … Read more

    Robust and Stochastically Weighted Multi-Objective Optimization Models and Reformulations

  • Jian Hu
  • Sanjay Mehrotra
    • Categories Multi-Criteria Optimization, Robust Optimization, Stochastic Programming Tags , , ,

    In this paper we introduce robust and stochastically weighted sum approaches to deterministic and stochastic multi-objective optimization. The robust weighted sum approach minimizes the worst case weighted sum of objectives over a given weight region. We study the reformulations of the robust weighted sum problem under different definitions of deterministic weight regions. We next introduce … Read more

    Total variation superiorization schemes in proton computed tomography image reconstruction

  • Yair Censor
  • Scott Penfold
  • Anatoly Rosenfeld
  • Reinhard W. Schulte
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Other Topics Tags ,

    Purpose: Iterative projection reconstruction algorithms are currently the preferred reconstruction method in proton computed tomography (pCT). However, due to inconsistencies in the measured data arising from proton energy straggling and multiple Coulomb scattering, noise in the reconstructed image increases with successive iterations. In the current work, we investigated the use of total variation superiorization (TVS) … Read more

    Quest for the control on the second order derivatives: topology optimization with functional includes the state’s curvature

  • Rouhollah Tavakoli
    • Categories Distributed Control, Multidisciplinary Design Optimization, Optimization of Systems modeled by PDEs Tags , , , ,

    Many physical phenomena, governed by partial differential equations (PDEs), are second order in nature. This makes sense to pose the control on the second order derivatives of the field solution, in addition to zero and first order ones, to consistently control the underlaying process. However, this type of control is nontrivial and to the best … Read more