On integrality in semidefinite programming for discrete optimization

It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … Read more

On the Number of Pivots of Dantzig’s Simplex Methods for Linear and Convex Quadratic Programs

Refining and extending works by Ye and Kitahara-Mizuno, this paper presents new results on the number of pivots of simplex-type methods for solving linear programs of the Leontief kind, certain linear complementarity problems of the P kind, and nonnegative constrained convex quadratic programs. Our results contribute to the further understanding of the complexity and efficiency … Read more

Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations

We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. … Read more

On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints

\(\) Globally optimizing a nonconvex quadratic over the intersection of \(m\) balls in \(\mathbb{R}^n\) is known to be polynomial-time solvable for fixed \(m\). Moreover, when \(m=1\), the standard semidefinite relaxation is exact, and when \(m=2\), it has recently been shown that an exact relaxation can be constructed via a disjunctive semidefinite formulation based on essentially two copies of the \(m=1\) case. … Read more

Force-Controlled Pose Optimization and Trajectory Planning for Chained Stewart Platforms

We study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs) that we call an “Assembler” Robot. These chained SPs are parallel mechanisms that are stronger, stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. Linking these units in … Read more

A classification method based on a cloud of spheres

\(\) In this article we propose a binary classification model to distinguish a specific class that corresponds to a characteristic that we intend to identify (fraud, spam, disease). The classification model is based on a cloud of spheres that circumscribes the points of the class to be identified. It is intended to build a model … Read more

Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part II

Abstract. This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products and extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT), applying a sophisticated discretization to both … Read more

The Jordan algebraic structure of the rotated quadratic cone

In this paper, we look into the rotated quadratic cone and analyze its algebraic structure. We construct an algebra associated with this cone and show that this algebra is a Euclidean Jordan algebra (EJA) with a certain inner product. We also demonstrate some spectral and algebraic characteristics of this EJA. The rotated quadratic cone is … Read more

Joint MSE Constrained Hybrid Beamforming and Reconfigurable Intelligent Surface

In this paper, the symbol detection mean squared error (MSE) constrained hybrid analog and digital beamforming is proposed in millimeter wave (mmWave) system, and the reconfigurable intelligent surface (RIS) is proposed to assist the mmWave system. The inner majorization-minimization (iMM) method is proposed to obtain analog transmitter, RIS and analog receivers, and the alternating direction … Read more