Nonconvex quadratic problems and games with separable constraints

Resumen

Quadratic programs are generally hard and difficult to solve, where many instances are known to be NP-hard.
However, there are some few cases in which the quadratic problem has some hidden convexity and there are methods to solve the problems optimally in polynomial time.
When this occurs, we say that strong duality holds, and that the primal problem has zero gap with its dual counterpart.
We study this property in nonconvex quadratic problems with separable constraints.

We exploit the disjoint structure of the constraints to analyze when strong duality may occur.
We consider problems that may have both inequality or equality quadratic constraints, and we provide sufficient conditions that guarantee zero duality gap.
Our results consider any number of constraints as long as they do not overlap between each other.

In addition to these results, we propose two distributed algorithms that aim to solve the quadratic problem optimally whenever the strong duality holds.
The first proposal uses a dual formulation and convergence relies on gradient or subgradient methods, depending on the nature of the problem.
The second proposal uses a modern decomposition technique from the literature called NOVA and uses successive convex approximations to converge to the optimal solution, which is generally considered faster than first order methods.

We then study two localization problems with ranged measurements.
We reformulate them as nonconvex quadratic problems with quadratic constraints and explore their solutions.
We refer to the first one as target localization and propose several distributed methods based on primal descent as well as dual ascent methods.

On the one hand, descent methods assume the nonconvexity of the localization problem and may converge to local solutions if the number of measuring nodes is small.
They are however fast and require little communication.
On the other hand, dual ascent methods aim to solve the localization problem optimally assuming that there is zero duality gap between the primal and dual problem.

The second localization problem we consider is the sensor network localization problem in which a set of nodes try to locate themselves having distance measurements between each other.
This is a harder problem, and as before, we propose both distributed methods based on descent techniques as well as based in a dual decomposition.

Finally, we also study the connection of nonconvex quadratic optimization with Nash equilibria in game theory.
In order to do so, we propose a robust demand-side management problem in a smart grid, where the agents try to minimize their monetary expenditure.
Because there is uncertainty in the real-time energy demand, the cost of energy is prone to variations and a robust model that attends to a worst-case scenario is proposed.
This formulation is presented as a min-max game where the maximization game is nonconvex and where the agents have coupled constraints.
We study this game and propose a distributed scheme with convergence guarantees to the NE of the game.
We also study the game model under a real-time energy market where prices have been set on a day-ahead robust optimization.