Convex Optimization

Target following algorithms for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Semi-definite Programming

    We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic … Read more

    Mosco stability of proximal mappings in reflexive Banach spaces

  • Dan Butnariu
  • Elena Resmerita
    • Categories Convex Optimization Tags , , , , , ,

    In this paper we establish criteria for the stability of the proximal mapping \textrm{Prox} $_{\varphi }^{f}=(\partial \varphi +\partial f)^{-1}$ associated to the proper lower semicontinuous convex functions $\varphi $ and $f$ on a reflexive Banach space $X.$ We prove that, under certain conditions, if the convex functions $\varphi _{n}$ converge in the sense of Mosco … Read more

    Proximal Point Methods for Quasiconvex and Convex Functions With Bregman Distances

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Convex Optimization, Generalized Convexity/Monoticity Tags ,

    This paper generalizes the proximal point method using Bregman distances to solve convex and quasiconvex optimization problems on noncompact Hadamard manifolds. We will proved that the sequence generated by our method is well defined and converges to an optimal solution of the problem. Also, we obtain the same convergence properties for the classical proximal method, … Read more

    Numerical Experiments with universal barrier functions for cones of Chebyshev systems

  • Leonid Faybusovich
  • Takashi Tsuchiya
  • Thanasak Mouktonglang
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-infinite Programming Tags ,

    Based on previous explicit computations of universal barrier functions, we describe numerical experiments for solving certain classes of convex optimization problems. The comparison is given of the performance of the classical affine-scaling algorithm with similar algorithm based upon the universal barrier function Citation To appear in “Computational Optimization and Applications” Article Download View Numerical Experiments … Read more

    Generating and Measuring Instances of Hard Semidefinite Programs, SDP

  • Hua Wei
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

    Steplength Selection in Interior-Point Methods for Quadratic Programming

  • Frank E. Curtis
  • Jorge Nocedal
    • Categories Convex Optimization Tags , , , ,

    We present a new strategy for choosing primal and dual steplengths in a primal-dual interior-point algorithm for convex quadratic programming. Current implementations often scale steps equally to avoid increases in dual infeasibility between iterations. We propose that this method can be too conservative, while safeguarding an unequally-scaled steplength approach will often require fewer steps toward … Read more

    The multiple-sets split feasibility problem and its applications for inverse problems

  • Thomas Bortfeld
  • Yair Censor
  • Tommy Elfving
  • Nirit Kopf
    • Categories Applications - Science and Engineering, Biomedical Applications, Convex Optimization

    The multiple-sets split feasibility problem requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. It can be a model for many inverse problems where constraints are … Read more

    On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more

    Computational acceleration of projection algorithms for the linear best approximation problem

  • Yair Censor
    • Categories Convex Optimization

    This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches … Read more

    Fast Moreau Envelope Computation I: Numerical Algorithms

  • Yves Lucet
    • Categories Convex Optimization, Nonsmooth Optimization, Problem Solving Environments Tags , , , , , ,

    The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, … Read more