On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

The well-known result stating that any non-convex quadratic problem over the nonnegative orthant with some additional linear and binary constraints can be rewritten as linear problem over the cone of completely positive matrices (Burer, 2009) is generalized by replacing the nonnegative orthant with an arbitrary closed convex cone. This set-semidefinite representation result implies new semidefinite … Read more

Formulations for Dynamic Lot Sizing with Service Levels

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more

Time consistency and risk averse dynamic decision models: Definition, interpretation and practical consequences

Categories Finance and Economics, Stochastic Programming Tags , , , ,

This paper aims at resolving a major obstacle to practical usage of time-consistent risk-averse decision models. The recursive objective function, generally used to ensure time consistency, is complex and has no clear/direct interpretation. Practitioners rather choose a simpler and more intuitive formulation, even though it may lead to a time inconsistent policy. Based on rigorous … Read more

Time consistency and risk averse dynamic decision models: Definition, interpretation and practical consequences

Categories Finance and Economics, Stochastic Programming Tags , , , ,

This paper aims at resolving a major obstacle to practical usage of time-consistent risk-averse decision models. The recursive objective function, generally used to ensure time consistency, is complex and has no clear/direct interpretation. Practitioners rather choose a simpler and more intuitive formulation, even though it may lead to a time inconsistent policy. Based on rigorous … Read more

On Computation of Performance Bounds of Optimal Index Assignment

Categories Applications - Science and Engineering, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more

From convergence principles to stability and optimality conditions

Categories Nonsmooth Optimization Tags , , , , ,

We show in a rather general setting that Hoelder and Lipschitz stability properties of solutions to variational problems can be characterized by convergence of more or less abstract iteration schemes. Depending on the principle of convergence, new and intrinsic stability conditions can be derived. Our most abstract models are (multi-) functions on complete metric spaces. … Read more

Numerical estimation of the relative entropy of entanglement

Categories Applications - Science and Engineering, Basic Sciences Applications Tags , , ,

We propose a practical algorithm for the calculation of the relative entropy of entanglement(REE), defined as the minimum relative entropy between a state and the set of states with positive partial transpose. Our algorithm is based on a practical semi-definite cutting plane approach. In low dimensions the implementation of the algorithm in MATLAB provides an … Read more

A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality

Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

The principle underlying this paper is the basic observation that the problem of simultaneously solving a large class of composite monotone inclusions and their duals can be reduced to that of finding a zero of the sum of a maximally monotone operator and a linear skew-adjoint operator. An algorithmic framework is developed for solving this … Read more

A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming

Categories Linear Programming Tags , , ,

In this paper, ellipse is used to approximate the central path of the linear programming. An interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows … Read more

A Polynomial Arc-Search Interior-Point Algorithm for Convex Quadratic Programming

Categories Linear Programming Tags , ,

Arc-search is developed for linear programming in \cite{yang09, yang10}. The algorithms search for optimizers along an ellipse that are approximations of the central path. In this paper, the arc-search method is applied to primal-dual path-following interior-point method for convex quadratic programming. A simple algorithm with iteration complexity $O(\sqrt{n}\log(1/\epsilon))$ is devised. Several improvements on the simple … Read more