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

    A strongly convergent proximal bundle method for convex minimization in Hilbert spaces

  • Yunier Bello-Cruz
  • Welington de Oliveira
  • Wim van Ackooij
    • Categories Convex and Nonsmooth Optimization

    A key procedure in proximal bundle methods for convex minimization problems is the definition of stability centers, which are points generated by the iterative process that successfully decrease the objective function. In this paper we study a different stability-center classification rule for proximal bundle methods. We show that the proposed bundle variant has three particularly … Read more

    Approximation of the Quadratic Knapsack Problem

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead an edge weighted graph G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the … Read more

    Polynomial time algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

  • Dong Li
  • Dolores Romero Morales
    • Categories Production and Logistics, Robust Optimization Tags , , ,

    We study the Minimax Regret Uncapacitated Lot Sizing (MRULS) model, where the production cost function and the demand are subject to uncertainty. We propose a polynomial time algorithm which solves the MRULS model in O(n^6) time. We improve this running time to O(n^5) when only the demand is uncertain, and to O(n^4) when only the … Read more

    A Revisit to Quadratic Programming with One Inequality Quadratic Constraint via Matrix Pencil

  • Lin Gang-Xuan
  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Global Optimization Theory, Quadratic Programming Tags , , , , ,

    The quadratic programming over one inequality quadratic constraint (QP1QC) is a very special case of quadratically constrained quadratic programming (QCQP) and attracted much attention since early 1990’s. It is now understood that, under the primal Slater condition, (QP1QC) has a tight SDP relaxation (PSDP). The optimal solution to (QP1QC), if exists, can be obtained by … Read more

    Reactive Power Management using Firefly and Spiral Optimization under Static and Dynamic Loading Conditions

  • Ripunjoy Phukan
    • Categories Applications - Science and Engineering, Global Optimization Applications, Stochastic Programming Tags , , , ,

    Power System planning encompasses the concept of minimization of transmission losses keeping in mind the voltage stability and system reliability. Voltage profile decides the state of a system and its control is dependent on Generator source voltage, shunt/series injection, transformer taps etc. Optimal parameter setting in system level is needed for managing the available resources … Read more

    Optimal control modeling of cell division

  • Robin J. Evans
  • Musa Mammadov
  • Cameron Wellard
    • Categories Biomedical Applications, Control Applications

    This paper investigates the population dynamics of a system of identically prepared B cells whose proliferation trajectories have been individually tracked using live-cell imaging techniques. The main goal is to investigate whether the system behavior can be determined using an optimality criterion. In order to achieve this goal we assume the existence of an intracellular … Read more

    Turnpike theorems for convex problems with undiscounted integral functionals

  • Musa Mammadov
    • Categories Control Applications

    In this paper the turnpike property is established for convex optimal control problems, involving undiscounted utility function and differential inclusions defined by multi-valued mapping having convex graph. Utility function is concave but not necessarily strictly concave. The turnpike theorem is proved under the main assumption that over any given line segment, either multi-valued mapping is … Read more

    Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity

  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Global Optimization Theory, Quadratic Programming

    The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (T_m), have drawn much attention recently. The question as to whether Problem ( T_m) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T_1) has an exact SOCP/SDP reformulation and thus … Read more

    Memory-Aware Parallelized RLT3 for Solving Quadratic Assignment Problems

  • Monique Guignard
  • Peter M. Hahn
  • Amir Roth
  • Matthew Saltzman
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Parallel Algorithms Tags , ,

    We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) … Read more