This note presents a theoretical analysis of disjunctive constraints featuring unbounded variables. In this framework, classical modeling techniques, including big-M approaches, are not applicable. We introduce a lifted second-order cone formulation of such on/off constraints and discuss related constraint qualification issues. A solution is proposed to avoid solvers’ failure. CitationH. L. Hijazi and L.Liberti “Constraint … Read more
Kitahara and Mizuno get new bounds for the number of distinct solutions generated by the simplex method for linear programming (LP). In this paper, we combine results of Kitahara and Mizuno and Tardos’s strongly polynomial algorithm, and propose an algorithm for solving a standard form LP problem. The algorithm solves polynomial number of artificial LP … Read more
We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular we study relationships between this cone and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative … Read more
Although it is easy to prove the sufficient conditions for optimality of a linear program, the necessary conditions pose a pedagogical challenge. A widespread practice in deriving the necessary conditions is to invoke Farkas’ lemma, but proofs of Farkas’ lemma typically involve “nonlinear” topics such as separating hyperplanes between disjoint convex sets, or else more … Read more
Infinite-dimensional linear conic formulations are described for nonlinear optimal control problems. The primal linear problem consists of finding occupation measures supported on optimal relaxed controlled trajectories, whereas the dual linear problem consists of finding the largest lower bound on the value function of the optimal control problem. Various approximation results relating the original optimal control … Read more
Suppose that we are given a feasible conic program with a finite optimal value and with strong duality failing. It is known that there are small perturbations of the problem data that lead to relatively big changes in the optimal value. We quantify the notion of big change in the case of a semidefinite program … Read more
Let $p_n$ denote the largest possible cp-rank of an $n\times n$ completely positive matrix. This matrix parameter has its significance both in theory and applications, as it sheds light on the geometry and structure of the solution set of hard optimization problems in their completely positive formulation. Known bounds for $p_n$ are $s_n=\binom{n+1}2-4$, the current … Read more
In this paper we provide a unified treatment of general two-term disjunctions on cross-sections of the second-order cone. We derive a closed-form expression for a convex inequality that is valid for such a disjunctive set and show that this inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and … Read more
In semidefinite programming (SDP), unlike in linear programming, Farkas’ lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system … Read more
A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l – x_j)(x_j – u) \le 0$ with $l < u$, equals the intersection ... Read more