Convex and Nonsmooth Optimization

On smoothness properties of optimal value functions at the boundary of their domain under complete convexity

  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This article studies continuity and directional differentiability properties of optimal value functions, in particular at boundary points of their domain. We extend and complement standard continuity results from W.W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, Vol. 15 (1973), 591-603, for abstract feasible set mappings under complete convexity as well as standard differentiability results … Read more

    Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems

  • Euhanna Ghadimi
  • Mikael Johansson
  • Iman Shames
  • André Teixeira
    • Categories Convex Optimization, Quadratic Programming Tags , ,

    The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm … Read more

    One condition for all: solution uniqueness and robustness of l1-synthesis and l1-analysis minimizations

  • Ming Yan
  • Wotao Yin
  • Hui Zhang
    • Categories Convex and Nonsmooth Optimization, Statistics Tags , , , , ,

    The l1-synthesis and l1-analysis models recover structured signals from their undersampled measurements. The solution of the former model is often a sparse sum of dictionary atoms, and that of the latter model often makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We … Read more

    A branch and bound approach for convex semi-infinite programming

  • Le Thi Hoai An
  • Mohand Ouanes
  • A. Ismael F. Vaz
    • Categories Convex Optimization, Semi-infinite Programming

    In this paper we propose an efficient approach for globally solving a class of convex semi-infinite programming (SIP) problems. Under the objective function and constraints (w.r.t. the variables to be optimized) convexity assumption, and appropriate differentiability, we propose a branch and bound exchange type method for SIP. To compute a feasible point for a SIP … Read more

    KKT Reformulation and Necessary Conditions for Optimality in Nonsmooth Bilevel Optimization

  • Stephan Dempe
  • Alain Zemkoho
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    For a long time, the bilevel programming problem has essentially been considered as a special case of mathematical programs with equilibrium constraints (MPECs), in particular when the so-called KKT reformulation is in question. Recently though, this widespread believe was shown to be false in general. In this paper, other aspects of the difference between both … Read more

    A variable fixing version of the two-block nonlinear constrained Gauss-Seidel algorithm for ℓ1-regularized least-squares

  • Margherita Porcelli
  • Francesco Rinaldi
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    The problem of finding sparse solutions to underdetermined systems of linear equations is very common in many fields as e.g. in signal/image processing and statistics. A standard tool for dealing with sparse recovery is the ℓ1-regularized least-squares approach that has recently attracted the attention of many researchers. In this paper, we describe a new version … Read more

    Forward-Backward and Tseng’s Type Penalty Schemes for Monotone Inclusion Problems

  • Radu Ioan Bot
  • Ernö Robert Csetnek
    • Categories Convex Optimization Tags , , , , , , , ,

    We deal with monotone inclusion problems of the form $0\in Ax+Dx+N_C(x)$ in real Hilbert spaces, where $A$ is a maximally monotone operator, $D$ a cocoercive operator and $C$ the nonempty set of zeros of another cocoercive operator. We propose a forward-backward penalty algorithm for solving this problem which extends the one proposed by H. Attouch, … Read more

    Facially exposed cones are not always nice

  • Vera Roshchina
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We address the conjecture proposed by Gabor Pataki that every facially exposed cone is nice. We show that the conjecture is true in the three-dimensional case, however, there exists a four-dimensional counterexample of a cone that is facially exposed but is not nice. Citation CRN, University of Ballarat Article Download View Facially exposed cones are … Read more

    The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    This paper considers a general class of iterative optimization algorithms, referred to as linear-optimization-based convex programming (LCP) methods, for solving large-scale convex programming (CP) problems. The LCP methods, covering the classic conditional gradient (CG) method (a.k.a., Frank-Wolfe method) as a special case, can only solve a linear optimization subproblem at each iteration. In this paper, … Read more

    New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more