On convex hulls of epigraphs of QCQPs

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such … Read more

Relative-error inertial-relaxed inexact versions of Douglas-Rachford and ADMM splitting algorithms

This paper derives new inexact variants of the Douglas-Rachford splitting method for maximal monotone operators and the alternating direction method of multipliers (ADMM) for convex optimization. The analysis is based on a new inexact version of the proximal point algorithm that includes both an inertial step and overrelaxation. We apply our new inexact ADMM method … Read more

On Relaxation of Some Customized Proximal Point Algorithms for Convex Minimization: From Variational Inequality Perspective

The proximal point algorithm (PPA) is a fundamental method for convex programming. When PPA applied to solve linearly constrained convex problems, we may prefer to choose an appropriate metric matrix to define the proximal regularization, so that the computational burden of the resulted PPA can be reduced, and in most cases, even admit closed form … Read more

Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

Partial Relaxation of Equality-constrained Programs

This paper presents a reformulation that is a natural “by-product” of the ‘variable endogenization’ process for equality-constrained programs. The method results a partial relaxation of the constraints which in turn confers some computational advantages. A fully-annotated example illustrates the technique and presents some comparative numerical results. Citation Siwale, I.: Partial Relaxation of Equality-constrained Programs. Technical … Read more

Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method

Optimization problems with cardinality constraints are very dicult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in … Read more

Approaches to a real-world train timetabling problem in a railway node

We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a … Read more

Transmission Expansion Planning Using an AC Model: Formulations and Possible Relaxations

Transmission expansion planning (TEP) is a rather complicated process which requires extensive studies to determine when, where and how many transmission facilities are needed. A well planned power system will not only enhance the system reliability, but also tend to contribute positively to the overall system operating efficiency. Starting with two mixed-integer nonlinear programming (MINLP) … Read more

Sensitivity analysis for relaxed optimal control problems with final-state constraints

In this article, we compute a second-order expansion of the value function of a family of relaxed optimal control problems with final-state constraints, parameterized by a perturbation variable. The sensitivity analysis is performed for controls that we call R-strong solutions. They are optimal solutions with respect to the set of feasible controls with a uniform … Read more

Containment problems for polytopes and spectrahedra

We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more