Nonlinear Optimization

Approximating Hessians in multilevel unconstrained optimization

  • Vincent Malmedy
  • Philippe L. Toint
    • Categories Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , , ,

    We consider Hessian approximation schemes for large-scale multilevel unconstrained optimization problems, which typically present a sparsity and partial separability structure. This allows iterative quasi-Newton methods to solve them despite of their size. Structured finite-difference methods and updating schemes based on the secant equation are presented and compared numerically inside the multilevel trust-region algorithm proposed by … Read more

    A proximal method for composite minimization

  • Adrian Lewis
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions … Read more

    Generalized power method for sparse principal component analysis

  • Michel Journee
  • Yurii Nesterov
  • Peter Richtarik
  • Rodolphe Sepulchre
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, … Read more

    Reformulations and Algorithms for the Optimization of Switching Decisions in Nonlinear Optimal Control

  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , ,

    In model-based nonlinear optimal control switching decisions that can be optimized often play an important role. Prominent examples of such hybrid systems are gear switches for transport vehicles or valves in chemical engineering. Optimization algorithms need to take the discrete nature of the variables that model these switching decisions into account. Unnecessarily, for many applications … Read more

    Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Projected Formulations

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing variables $Y_{ij}$ to represent each of the products $x_i x_j$ of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can … Read more

    Proximal-like contraction methods for monotone variational inequalities in a unified framework

  • Bingsheng He
  • Lizhi Liao
  • Xiang Wang
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Convex Optimization Tags , ,

    Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. To solve the subproblems of these algorithms, the projection method takes the iteration in form of $u^{k+1} = P_{\Omega}[u^k-\alpha_k d^k]$. Interestingly, many of them can be paired such that $%\exists \tilde{u}^k, \tilde{u}^k = P_{\Omega}[u^k – \beta_kF(v^k)] = … Read more

    Proximal Methods for Nonlinear Programming: Double Regularization and Inexact Subproblems

  • Jonathan Eckstein
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , ,

    This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that … Read more

    Nonlinear Stepsize Control, Trust Regions and Regularizations for Unconstrained Optimization

  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    A general class of algorithms for unconstrained optimization is introduced, which subsumes the classical trust-region algorithm and two of its newer variants, as well as the cubic and quadratic regularization methods. A unified theory of global convergence to first-order critical points is then described for this class. An extension to projection-based trust-region algorithms for nonlinear … Read more

    A second derivative SQP method: theoretical issues

  • Nicholas I. M. Gould
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    Sequential quadratic programming (SQP) methods form a class of highly efficient algorithms for solving nonlinearly constrained optimization problems. Although second derivative information may often be calculated, there is little practical theory that justifies exact-Hessian SQP methods. In particular, the resulting quadratic programming (QP) subproblems are often nonconvex, and thus finding their global solutions may be … Read more

    Second-order analysis of optimal control problems with control and initial-final state constraints

  • Joseph Frédéric Bonnans
  • Nikolai Osmolovskii
    • Categories Systems governed by Differential Equations Optimization Tags , , , ,

    This paper provides an analysis of Pontryagine mimina satisfying a quadratic growth condition, for optimal control problems of ordinary differential equations with constraints on initial-final state, as well as control constraints satisfying the uniform positive linear independence condition. CitationRapport de Recherche INRIA 6707, Oct. 2008.ArticleDownload View PDF