Nonlinear Optimization

Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

  • Mario A. T. Figueiredo
  • Stephen Wright
  • Robert Nowak
    • Categories Applications - Science and Engineering, Bound-constrained Optimization Tags ,

    Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard approach consists in minimizing an objective function which includes a quadratic (squared $\ell_2$) error term combined with a sparseness-inducing ($\ell_1$) regularization term.{\it Basis pursuit}, the {\it least absolute shrinkage and selection operator} (LASSO), … Read more

    Explicit reformulations for robust optimization problems with general uncertainty sets

  • Igor Averbakh
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Robust Optimization Tags ,

    We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be equivalently reformulated as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty … Read more

    A primal-dual interior point method for nonlinear semidefinite programming

  • Kouhei Harada
  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. By combining the primal barrier penalty function and the primal-dual barrier function, a new primal-dual merit function is proposed within the framework of the line search strategy. We show the global convergence property of our method. Finally some numerical … Read more

    A globally convergent trust-region SQP method without a penalty function for nonlinearly constrained optimization

  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we propose a new trust-region SQP method, which uses no penalty function, for solving nonlinearly constrained optimization problem. Our method consists of alternate two phases. Specifically, we alternately proceed the feasibility restoration phase and the objective function minimization phase. The global convergence property of the proposed method is shown. CitationCooperative Research Report … Read more

    Developments of NEWUOA for unconstrained minimization without derivatives

  • M.J.D. Powell
    • Categories Bound-constrained Optimization, Unconstrained Optimization Tags , , , , ,

    The NEWUOA software is described briefly, with some numerical results that show good efficiency and accuracy in the unconstrained minimization without derivatives of functions of up to 320 variables. Some preliminary work on an extension of NEWUOA that allows simple bounds on the variables is also described. It suggests a variation of a technique in … Read more

    Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

  • Jesús A. De Loera
  • Jon Lee
  • Susan Margulies
  • Shmuel Onn
    • Categories Combinatorial Optimization, Integer Programming, Nonlinear Optimization Tags ,

    Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more

    Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

  • Hande Benson
  • Arun Sen
  • David F. Shanno
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more

    A view of algorithms for optimization without derivatives

  • M.J.D. Powell
    • Categories Unconstrained Optimization Tags , , , ,

    Let the least value of a function of many variables be required. If its gradient is available, then one can tell whether search directions are downhill, and first order conditions help to identify the solution. It seems in practice, however, that the vast majority of unconstrained calculations do not employ any derivatives. A view of … Read more

    An implicit trust-region method on Riemannian manifolds

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • C. G. Baker
    • Categories Constrained Nonlinear Optimization Tags , ,

    We propose and analyze an “implicit” trust-region method in the general setting of Riemannian manifolds. The method is implicit in that the trust-region is defined as a superlevel set of the ratio of the actual over predicted decrease in the objective function. Since this method potentially requires the evaluation of the objective function at each … Read more

    A polynomial predictor-corrector trust-region algorithm for linear programming

  • Guanghui Lan
  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Nonlinear Optimization Tags , , , ,

    In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more