Nonlinear Optimization

Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

  • V. Jeyakumar
  • Guoyin Li
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more

    On the use of iterative methods in cubic regularization for unconstrained optimization

  • Tommaso Bianconcini
  • Giampaolo Liuzzi
  • Benedetta Morini
  • Marco Sciandrone
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we consider the problem of minimizing a smooth function by using the Adaptive Cubic Regularized framework (ARC). We focus on the computation of the trial step as a suitable approximate minimizer of the cubic model and discuss the use of matrix-free iterative methods. Our approach is alternative to the implementation proposed in … Read more

    An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization

  • Richard H. Byrd
  • Jorge Nocedal
  • Figen Oztoprak
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags ,

    We study a Newton-like method for the minimization of an objective function $\phi$ that is the sum of a smooth convex function and an $\ell_1$ regularization term. This method, which is sometimes referred to in the literature as a proximal Newton method, computes a step by minimizing a piecewise quadratic model $q_k$ of the objective … Read more

    Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization

  • Cong D. Dang
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper, we present a new stochastic algorithm, namely the stochastic block mirror descent (SBMD) method for solving large-scale nonsmooth and stochastic optimization problems. The basic idea of this algorithm is to incorporate the block-coordinate decomposition and an incremental block averaging scheme into the classic (stochastic) mirror-descent method, in order to significantly reduce the … Read more

    On the Incomplete Oblique Projections Method for Solving Box Constrained Least Squares Problems

  • N. Echebest
  • MT Guardarucci
  • HD Scolnik
    • Categories Bound-constrained Optimization, Nonlinear Systems and Least-Squares Tags , ,

    The aim of this paper is to extend the applicability of the incomplete oblique projections method (IOP) previously introduced by the authors for solving inconsistent linear systems to the box constrained case. The new algorithm employs incomplete projections onto the set of solutions of the augmented system Ax-r= b, together with the box constraints, based … Read more

    Inexact Coordinate Descent: Complexity and Preconditioning

  • Jacek Gondzio
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. … Read more

    The Euclidean distance degree of an algebraic variety

  • Jan Draisma
  • Emil Horobet
  • Giorgio Ottaviani
  • Bernd Sturmfels
  • Rekha R. Thomas
    • Categories Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational … Read more

    A new formulation of protein evolutionary models that account for structural constraints

  • Andrew J. Bordner
  • Hans D Mittelmann
    • Categories Biomedical Applications, Constrained Nonlinear Optimization Tags , , , ,

    Despite the importance of a thermodynamically stable structure with a conserved fold for protein function, almost all evolutionary models neglect site-site correlations that arise from physical interactions between neighboring amino acid sites. This is mainly due to the difficulty in formulating a computationally tractable model since rate matrices can no longer be used. Here we … Read more

    String-Averaging Projected Subgradient Methods for Constrained Minimization

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , ,

    We consider constrained minimization problems and propose to replace the projection onto the entire feasible region, required in the Projected Subgradient Method (PSM), by projections onto the individual sets whose intersection forms the entire feasible region. Specifically, we propose to perform such projections onto the individual sets in an algorithmic regime of a feasibility-seeking iterative … Read more

    A Flexible Inexact Restoration Method and Application to Optimization with Multiobjective Constraints under Weighted-Sum Scalarization

  • Luís Felipe Bueno
  • Gabriel Haeser
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization

    We introduce a new flexible Inexact-Restoration (IR) algorithm and an application to problems with multiobjective constraints (MOCP) under the weighted-sum scalarization approach. In IR methods each iteration has two phases. In the first phase one aims to improve the feasibility and, in the second phase, one minimizes a suitable objective function. This is done in … Read more