Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

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

    We present an improved evaluation complexity bound for nonlinear least squares problems using higher order regularization methods. Citation Technical Report NA 15-17, Numerical Analysis Group, University of Oxford, 2015 Article Download View Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

    Blessing of Massive Scale: Spatial Graphical Model Estimation with a Total Cardinality Constraint

  • Ethan Fang
  • Mengdi Wang
  • Han Liu
    • Categories Combinatorial Optimization, Statistics Tags , , , ,

    We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the l0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this ‘blessing of massive scale’ phenomenon. Motivated by this result, we propose … Read more

    Lagrangian relaxation for SVM feature selection

  • Manlio Gaudioso
  • Enrico Gorgone
  • Martine Labbé
  • Antonio M. Rodríguez-Chía
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    We discuss a Lagrangian-relaxation-based heuristics for dealing with feature selection in a standard L1 norm Support Vector Machine (SVM) framework for binary classification. The feature selection model we adopt is a Mixed Binary Linear Programming problem and it is suitable for a Lagrangian relaxation approach. Based on a property of the optimal multiplier setting, we … Read more

    Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization

  • José Mario Martínez
  • M. Raydan
    • Categories Unconstrained Optimization Tags , , ,

    In a recent paper we introduced a trust-region method with variable norms for unconstrained minimization and we proved standard asymptotic convergence results. Here we will show that, with a simple modification with respect to the sufficient descent condition and replacing the trust-region approach with a suitable cubic regularization, the complexity of this method for finding … Read more

    Robust Optimal Control with Adjustable Uncertainty Sets

  • Angelos Georghiou
  • Paul J. Goulart
  • Maryam Kamgarpour
  • John Lygeros
  • Xiaojing Zhang
    • Categories Robust Optimization Tags , , ,

    Robust control design for constrained uncertain systems is a well-studied topic. Given a known uncertainty set, the objective is to find a control policy that minimizes a given cost and satisfies the system’s constraints for all possible uncertainty realizations. In this paper, we extend the classical robust control setup by treating the uncertainty sets as … Read more

    Scenario Decomposition for 0-1 Stochastic Programs: Improvements and Asynchronous Implementation

  • Shabbir Ahmed
  • Deepak Rajan
  • Kevin Ryan
    • Categories Parallel Algorithms, Stochastic Programming Tags , ,

    A recently proposed scenario decomposition algorithm for stochastic 0-1 programs finds an optimal solution by evaluating and removing individual solutions that are discovered by solving scenario subproblems. In this work, we develop an asynchronous, distributed implementation of the algorithm which has computational advantages over existing synchronous implementations of the algorithm. Improvements to both the synchronous … Read more

    hBcnorm regularization algorithms for optimization over permutation matrices

  • Bo Jiang
  • Ya-Feng Liu
  • Zaiwen Wen
    • Categories 0-1 Programming, Constrained Nonlinear Optimization Tags , , , , , ,

    Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more

    Ambiguous Joint Chance Constraints under Mean and Dispersion Information

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Vladimir Roitch
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We study joint chance constraints where the distribution of the uncertain parameters is only known to belong to an ambiguity set characterized by the mean and support of the uncertainties and by an upper bound on their dispersion. This setting gives rise to pessimistic (optimistic) ambiguous chance constraints, which require the corresponding classical chance constraints … Read more

    Partial outer convexification for traffic light optimization in road networks

  • Simone Göttlich
  • Andreas Potschka
  • Ute Ziegler
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , ,

    We consider the problem of computing optimal traffic light programs for urban road intersections using traffic flow conservation laws on networks. Based on a Partial Outer Convexification approach, which has been successfully applied in the area of mixed-integer optimal control for systems of ordinary or differential algebraic equations, we develop a computationally tractable two-stage solution … Read more

    Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization

  • Roberto Andreani
  • José Mario Martínez
  • Alberto Ramos
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Sequential optimality conditions for constrained optimization are necessarily satisfied by local minimizers, independently of the fulfillment of constraint qualifications. These conditions support the employment of different stopping criteria for practical optimization algorithms. On the other hand, when an appropriate strict constraint qualification associated with some sequential optimality condition holds at a point that satisfies the … Read more