A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , ,

    It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant … Read more

    E. Lieb convexity inequalities and noncommutative Bernstein inequality in Jordan-algebraic setting

  • Leonid Faybusovich
    • Categories Generalized Convexity/Monoticity, Other Topics Tags , ,

    We describe a Jordan-algebraic version of E. Lieb convexity inequalities. A joint convexity of Jordan-algebraic version of quantum entropy is proven. SA spectral theory on semi-simple complex Jordan algebras is used as atool to prove the convexity results. Possible applications to optimization and statistics are indicated CitationPreprint, University of Notre Dame, August 2014ArticleDownload View PDF

    Fast Algorithms for the Minimum Volume Estimator

  • Selin Damla Ahipasaoglu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Statistics Tags , ,

    The MVE estimator is an important tool in robust regression and outlier detection in statistics. We develop fast and efficient algorithms for the MVE estimator problem and discuss how they can be implemented efficiently. The novelty of our approach stems from the recent developments in the first-order algorithms for solving the related Minimum Volume Enclosing … Read more

    A branch-cut-and-price algorithm for the energy minimization vehicle routing problem

  • Ricardo Fukasawa
  • Qie He
  • Yongjia Song
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming

    We study a variant of the capacitated vehicle routing problem where the cost over each arc is defined as the product of the arc length and the weight of the vehicle when it traverses that arc. We propose two new mixed integer linear programming formulations for the problem: an arc-load formulation and a set partitioning … Read more

    Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , , , ,

    The alternating direction method of multipliers (ADMM) is a benchmark for solving a linearly constrained convex minimization model with a two-block separable objective function; and it has been shown that its direct extension to a multiple-block case where the objective function is the sum of more than two functions is not necessarily convergent. For the … Read more

    Self Equivalence of the Alternating Direction Method of Multipliers

  • Ming Yan
  • Wotao Yin
    • Categories Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADM or ADMM) breaks a complex optimization problem into much simpler subproblems. The ADM algorithms are typically short and easy to implement yet exhibit (nearly) state-of-the-art performance for large-scale optimization problems. To apply ADM, we first formulate a given problem into the “ADM-ready” form, so the final algorithm depends … Read more

    Block stochastic gradient iteration for convex and nonconvex optimization

  • Yangyang Xu
  • Wotao Yin
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Approaches Tags , ,

    The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by updating them one at a time; when the blocks … Read more

    On efficiency of nonmonotone Armijo-type line searches

  • Masoud Ahookhosh
  • Susan Ghaderi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    Monotonicity and nonmonotonicity play a key role in studying the global convergence and the efficiency of iterative schemes employed in the field of nonlinear optimization, where globally convergent and computationally efficient schemes are explored. This paper addresses some features of descent schemes and the motivation behind nonmonotone strategies and investigates the efficiency of an Armijo-type … Read more

    A proximal point algorithm for DC functions on Hadamard manifolds

  • Paulo Roberto Oliveira
  • João Carlos Souza
    • Categories Other Topics, Unconstrained Optimization Tags

    An extension of a proximal point algorithm for difference of two convex functions is presented in the context of Riemannian manifolds of nonposite sectional curvature. If the sequence generated by our algorithm is bounded it is proved that every cluster point is a critical point of the function (not necessarily convex) under consideration, even if … Read more

    Robust risk adjustment in health insurance

  • Aurelie Thiele
  • Tengjiao Xiao
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , ,

    Risk adjustment is used to calibrate payments to health plans based on the relative health status of insured populations and helps keep the health insurance market competitive. Current risk adjustment models use parameter estimates obtained via regression and are thus subject to estimation error. This paper discusses the impact of parameter uncertainty on risk scoring, … Read more