24 citations · 78 across the 15 of their papers we have counts for
11 papers · 1 filter
On relaxations of the max -cut problem formulations
Ramin Fakhimi, Hamidreza Validi, Illya V. Hicks +2
A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max -cut problem is a…
Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition
Javier Peña, Juan C. Vera, Luis F. Zuluaga
We provide new insight into the convergence properties of the Douglas-Rachford algorithm for the problem , where and are convex functions. Our approac…
Reducing non-negativity over general semialgebraic sets to non-negativity over simple sets
Olga Kuryatnikova, Juan C. Vera, Luis F. Zuluaga
A non-negativity certificate (NNC) is a way to write a polynomial so that its non-negativity on a semialgebraic set becomes evident. Positivstellensätze (Psätze) guarantee the exis…
Equivalence and invariance of the chi and Hoffman constants of a matrix
Javier F. Pena, Juan C. Vera, Luis F. Zuluaga
We show that the following two condition measures of a full column rank matrix are identical: the chi constant and a signed Hoffman constant. This id…
New characterizations of Hoffman constants for systems of linear constraints
Javier Pena, Juan Vera, Luis Zuluaga
We give a characterization of the Hoffman constant of a system of linear constraints in {\em relative} to a {\em reference polyhedron} . The reference polyhe…
An algorithm to compute the Hoffman constant of a system of linear constraints
Javier Pena, Juan Vera, Luis Zuluaga
We propose a combinatorial algorithm to compute the Hoffman constant of a system of linear equations and inequalities. The algorithm is based on a characterization of the Hoffman c…
Positive polynomials on unbounded domains
Javer Pena, Juan C. Vera, Luis F. Zuluaga
Certificates of non-negativity such as Putinar's Positivstellensatz have been used to obtain powerful numerical techniques to solve polynomial optimization (PO) problems. Putinar's…
Pricing in non-convex markets with quadratic deliverability costs
Xiaolong Kuang, Alberto J. Lamadrid, Luis F. Zuluaga
The problem of obtaining market-clearing prices for markets with non-convexities has been widely studied in the literature. This is particularly the case in electricity markets, wh…
Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization
Xiaolong Kuang, Luis F. Zuluaga
Completely positive (CP) tensors, which correspond to a generalization of CP matrices, allow to reformulate or approximate a general polynomial optimization problem (POP) with a co…
Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques
Wei Xia, Juan Vera, Luis F. Zuluaga
Quadratic programming (QP) is a well-studied fundamental NP-hard optimization problem which optimizes a quadratic objective over a set of linear constraints. In this paper, we refo…
Alternative SDP and SOCP Approximations for Polynomial Optimization
Xiaolong Kuang, Bissan Ghaddar, Joe Naoum-Sawaya +1
In theory, hierarchies of semidefinite programming (SDP) relaxations based on sum of squares (SOS) polynomials have been shown to provide arbitrarily close approximations for a gen…