Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more

The robust stabilization problem for discrete-time descriptor systems

In this paper the robust stabilization problem for linear discrete-time descriptor systems is investigated. This means that the transfer function matrix of the system at hand is allowed to be improper or even polynomial, as the uncertainty acts on normalized coprime factors. The main results comprising explicit analytical formulas for the maximum stability margin and … Read more

Characterizing and testing subdifferential regularity for piecewise smooth objective functions

Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT … Read more

Weak Stability of $\ell_1hBcminimization Methods in Sparse Data Reconstruction

As one of the most plausible convex optimization methods for sparse data reconstruction, $\ell_1$-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, … Read more

A partial outer convexification approach to control transmission lines

In this paper we derive an efficient optimization approach to calculate optimal controls of electric transmission lines. These controls consist of time-dependent inflows and switches that temporarily disable single arcs or whole subgrids to reallocate the flow inside the system. The aim is then to find the best energy input in terms of boundary controls … Read more

Approximation algorithms for the covering-type k-violation linear program

We study the covering-type k-violation linear program where at most $k$ of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k+1)-approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the … Read more

Probabilistic Variational Formulation of Binary Programming

A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more

Generalized Dual Dynamic Programming for Infinite Horizon Problems in Continuous State and Action Spaces

We describe a nonlinear generalization of dual dynamic programming theory and its application to value function estimation for deterministic control problems over continuous state and action (or input) spaces, in a discrete-time infinite horizon setting. We prove that the result of a one-stage policy evaluation can be used to produce nonlinear lower bounds on the … Read more