Deciding robust feasibility and infeasibility using a set containment approach: An application to stationary passive gas network operations

Denis Aßmann, Frauke Liers, Michael Stingl, J. C. Vera

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented---one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient.
Original languageEnglish
Pages (from-to)2489-2517
JournalSIAM Journal on Optimization
Volume28
Issue number3
DOIs
Publication statusPublished - Sep 2018

Fingerprint

Infeasibility
Polynomials
Polynomial
Gases
Absolute value
Value Function
Uncertainty
Semidefinite Program
Tree Networks
Feasible region
Linear programming
Sum of squares
Topology
Gas
Arc of a curve
Linearly
Projection
Sufficient
Optimization Problem
Cycle

Keywords

  • Polynomial optimization
  • Robust optimization
  • Natural gas transport

Cite this

@article{ab36c81378394d3f8ec59e67955fcbd4,
title = "Deciding robust feasibility and infeasibility using a set containment approach: An application to stationary passive gas network operations",
abstract = "In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented---one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient.",
keywords = "Polynomial optimization, Robust optimization, Natural gas transport",
author = "Denis A{\ss}mann and Frauke Liers and Michael Stingl and Vera, {J. C.}",
year = "2018",
month = "9",
doi = "10.1137/17M112470X",
language = "English",
volume = "28",
pages = "2489--2517",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Deciding robust feasibility and infeasibility using a set containment approach : An application to stationary passive gas network operations. / Aßmann, Denis; Liers, Frauke; Stingl, Michael; Vera, J. C.

In: SIAM Journal on Optimization, Vol. 28, No. 3, 09.2018, p. 2489-2517.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Deciding robust feasibility and infeasibility using a set containment approach

T2 - An application to stationary passive gas network operations

AU - Aßmann, Denis

AU - Liers, Frauke

AU - Stingl, Michael

AU - Vera, J. C.

PY - 2018/9

Y1 - 2018/9

N2 - In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented---one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient.

AB - In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding whether the uncertainty set is contained within the projection of the feasible region onto the uncertainty-space. Moreover, the considered sets are assumed to be described by polynomials. For answering this question, two very general approaches using methods from polynomial optimization are presented---one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares (SOS) polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a nonconvex feasibility problem where the feasible set is described by a composition of polynomials with the absolute value function. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, the problem can be decided by eliminating the absolute value functions and solving the resulting linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. It turns out that for instances where robust feasibility or infeasibility can be decided successfully, level 2 or level 3 of the Lasserre relaxation hierarchy typically is sufficient.

KW - Polynomial optimization

KW - Robust optimization

KW - Natural gas transport

U2 - 10.1137/17M112470X

DO - 10.1137/17M112470X

M3 - Article

VL - 28

SP - 2489

EP - 2517

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -