The Descriptor Continuous-Time Algebraic Riccati Equation. Numerical Solutions and Some Direct Applications

  • Claudiu Dinicu
    • Categories Applications - Science and Engineering, Robust Optimization Tags , , ,

    We investigate here the numerical solution of a special type of descriptor continuous-time Riccati equation which is involved in solving several key problems in robust control, formulated under very general hypotheses. We also give necessary and sufficient existence conditions together with computable formulas for both stabilizing and antistabilizing solutions in terms of the associated matrix … Read more

    Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs

  • Jérôme Bolte
  • Edouard Pauwels
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , , , , , , ,

    In view of solving nonsmooth and nonconvex problems involving complex constraints (like standard NLP problems), we study general maximization-minimization procedures produced by families of strongly convex sub-problems. Using techniques from semi-algebraic geometry and variational analysis –in particular Lojasiewicz inequality– we establish the convergence of sequences generated by this type of schemes to critical points. The … Read more

    Efficient First-Order Methods for Linear Programming and Semidefinite Programming

  • James Renegar
    • Categories Linear Programming, Semi-definite Programming Tags , , ,

    We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally “smoothed,” thereby allowing most first-order … Read more

    Relative Entropy Relaxations for Signomial Optimization

  • Venkat Chandrasekaran
  • Parikshit Shah
    • Categories Convex and Nonsmooth Optimization, Global Optimization

    Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are non convex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain … Read more

    Integer programming formulations for the elementary shortest path problem

  • Leonardo Taccari
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Polyhedra Tags , , ,

    Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this … Read more

    Approximation algorithms for the Transportation Problem with Market Choice and related models

  • Karen I. Aardal
  • Pierre Le Bodic
    • Categories Approximation Algorithms Tags , ,

    Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated … Read more

    A Gentle, Geometric Introduction to Copositive Optimization

  • Samuel Burer
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more

    Convergence Analysis of Primal-Dual Based Methods for Total Variation Minimization with Finite Element Approximation

  • Wenyi Tian
  • Xiao-Ming Yuan
    • Categories Applications - Science and Engineering Tags , , , ,

    We consider the total variation minimization model with consistent finite element discretization. It has been shown in the literature that this model can be reformulated as a saddle-point problem and be efficiently solved by the primal-dual method. The convergence for this application of the primal-dual method has also been analyzed. In this paper, we focus … Read more

    A Tight Lower Bound for the Adjacent Quadratic Assignment Problem

  • Pietro Belotti
  • Federico Malucelli
  • Borzou Rostami
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , ,

    In this paper we address the Adjacent Quadratic Assignment Problem (AQAP) which is a variant of the QAP where the cost coefficient matrix has a particular structure. Motivated by strong lower bounds obtained by applying Reformulation Linearization Technique (RLT) to the classical QAP, we propose two special RLT representations for the problem. The first is … Read more

    Lower Bounds for the Quadratic Minimum Spanning Tree Problem Based on Reduced Cost Computation

  • Federico Malucelli
  • Borzou Rostami
    • Categories Combinatorial Optimization, Quadratic Programming Tags , , , , ,

    The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MST whose cost considers also the interaction between every pair … Read more