Nonlinear Optimization

Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints

  • Stephen Wright
  • Yue Xie
    • Categories Constrained Nonlinear Optimization

    We analyze worst-case complexity of a Proximal augmented Lagrangian (Proximal AL) framework for nonconvex optimization with nonlinear equality constraints. When an approximate first-order (second-order) optimal point is obtained in the subproblem, an $\epsilon$ first-order (second-order) optimal point for the original problem can be guaranteed within $\mathcal{O}(1/ \epsilon^{2 – \eta})$ outer iterations (where $\eta$ is a … Read more

    Random projections for quadratic programs

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories Quadratic Programming Tags , , , ,

    Random projections map a set of points in a high dimensional space to a lower dimen- sional one while approximately preserving all pairwise Euclidean distances. While random projections are usually applied to numerical data, we show they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving … Read more

    Sparse PCA on fixed-rank matrices

  • Alberto Del Pia
    • Categories Global Optimization Theory, Quadratic Programming Tags , , , ,

    Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if … Read more

    The Generalized Trust Region Subproblem: solution complexity and convex hull results

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Constrained Nonlinear Optimization, Quadratic Programming

    We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this … Read more

    Stabilized Barzilai-Borwein method

  • Oleg Burdakov
  • Yu-Hong Dai
  • Na Huang
    • Categories Unconstrained Optimization Tags , , ,

    The Barzilai-Borwein (BB) method is a popular and efficient tool for solving large-scale unconstrained optimization problems. Its search direction is the same as for the steepest descent (Cauchy) method, but its stepsize rule is different. Owing to this, it converges much faster than the Cauchy method. A feature of the BB method is that it … Read more

    Mordukhovich Stationarity for Mathematical Programs with Switching Constraints under Weak Constraint Qualifications

  • Lei Guo
  • Gao-Xi Li
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    The mathematical program with switching constraints (MPSC), which is recently introduced, is a difficult class of optimization problems since standard constraint qualifications are very likely to fail at local minimizers. MPSC arises from the discretization of optimal control problems with switching constraints which appears frequently in the field of control. Due to the failure of … Read more

    HyperNOMAD: Hyperparameter optimization of deep neural networks using mesh adaptive direct search

  • Dounia Lakhmiri
  • Sébastien Le Digabel
  • Christophe Tribes
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , , , , ,

    The performance of deep neural networks is highly sensitive to the choice of the hyperparameters that define the structure of the network and the learning process. When facing a new application, tuning a deep neural network is a tedious and time consuming process that is often described as a “dark art”. This explains the necessity … Read more

    Complexity and performance of an Augmented Lagrangian algorithm

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , , ,

    Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM Journal on Optimization 18, pp. 1286-1309, 2008]. Complexity results that report its worst-case behavior in terms of iterations and evaluations of functions and … Read more

    Accelerated Symmetric ADMM and Its Applications in Signal Processing

  • Jianchao Bai
  • Ke Guo
  • Yang Jing
  • Junli Liang
    • Categories Constrained Nonlinear Optimization, Other Topics Tags , , , ,

    The alternating direction method of multipliers (ADMM) were extensively investigated in the past decades for solving separable convex optimization problems. Fewer researchers focused on exploring its convergence properties for the nonconvex case although it performed surprisingly efficient. In this paper, we propose a symmetric ADMM based on different acceleration techniques for a family of potentially … Read more

    Optimal K-Thresholding Algorithms for Sparse Optimization Problems

  • Yun-Bin Zhao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Data-Mining Tags , , , , ,

    The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherit drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop … Read more