Convex and Nonsmooth Optimization

Iterative Reweighted Linear Least Squares for Exact Penalty Subproblems on Product Sets

  • James V. Burke
  • Frank E. Curtis
  • Hao Wang
  • Jiashan Wang
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

    We present two matrix-free methods for solving exact penalty subproblems on product sets that arise when solving large-scale optimization problems. The first approach is a novel iterative reweighting algorithm (IRWA), which iteratively minimizes quadratic models of relaxed subproblems while automatically updating a relaxation vector. The second approach is based on alternating direction augmented Lagrangian (ADAL) … Read more

    On local convergence of the method of alternating projections

  • Dominikus Noll
  • Aude Rondepierre
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    The method of alternating projections is a classical tool to solve feasibility problems. Here we prove local convergence of alternating projections between subanalytic sets A,B under a mild regularity hypothesis on one of the sets. We show that the speed of convergence is O$(k^{-\rho})$ for some $\rho\in(0,\infty)$. CitationUniversité de Toulouse, Institut de Mathématiques, december 19, … Read more

    Equivalence and Strong Equivalence between Sparsest and Least $\ell_1hBcNorm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Applications - Science and Engineering, Convex Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Convex Optimization, Global Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    The inexact projected gradient method for quasiconvex vector optimization problems

  • Yunier Bello-Cruz
  • Glaydston Bento
  • Gemayqzel Bouza
  • R.F.B. Costa
    • Categories Generalized Convexity/Monoticity, Multi-Criteria Optimization, Nonlinear Optimization

    Vector optimization problems are a generalization of multiobjective optimization in which the preference order is related to an arbitrary closed and convex cone, rather than the nonnegative octant. Due to its real life applications, it is important to have practical solution approaches for computing. In this work, we consider the inexact projected gradient-like method for … Read more

    A Relaxed-Projection Splitting Algorithm for Variational Inequalities in Hilbert Spaces

  • Yunier Bello-Cruz
  • R. Diaz Millan
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    We introduce a relaxed-projection splitting algorithm for solving variational inequalities in Hilbert spaces for the sum of nonsmooth maximal monotone operators, where the feasible set is defined by a nonlinear and nonsmooth continuous convex function inequality. In our scheme, the orthogonal projections onto the feasible set are replaced by projections onto separating hyperplanes. Furthermore, each … Read more

    Active Set Methods with Reoptimization for Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags , ,

    We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm … Read more

    An inexact block-decomposition method for extra large-scale conic semidefinite programming

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    In this paper, we present an inexact block-decomposition (BD) first-order method for solving standard form conic semidefinite programming (SDP) which avoids computations of exact projections onto the manifold defined by the affine constraints and, as a result, is able to handle extra large SDP instances. The method is based on a two-block reformulation of the … Read more

    On the Convergence of Alternating Minimization for Convex Programming with Applications to Iteratively Reweighted Least Squares and Decomposition Schemes

  • Amir Beck
    • Categories Convex Optimization

    This paper is concerned with the alternating minimization (AM) for solving convex minimization problems where the decision variables vector is split into two blocks. The objective function is a sum of a differentiable convex function and a separable (possible) nonsmooth extended real-valued convex function, and consequently constraints can be incorporated. We analyze the convergence rate … Read more