Genericity Results in Linear Conic Programming: A Tour d’Horizon

Mirjam Dür, Bolor Jargalsaikhan, Georg J. Still

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances.
In this paper, we survey known results and present new ones. In particular we give an easy proof of the fact that Slater’s condition holds generically in linear conic programming. We further discuss the problem of stability of uniqueness, nondegeneracy, and strict complementarity. We also comment on the fact that in general, a conic program cannot be treated as a smooth problem and that techniques from nonsmooth geometric measure theory are needed.
Original languageEnglish
Pages (from-to)77
Number of pages94
JournalMathematics of operations research
Volume42
Issue number1
DOIs
Publication statusPublished - 1 Feb 2017

Fingerprint

Conic Programming
Genericity
Linear programming
Strict Complementarity
Nondegeneracy
Uniqueness
Geometric Measure Theory
Generic Property
Strong Duality
Optimal Solution
Subset
Complementarity

Keywords

  • conic optimization
  • generic properties
  • Slater’s condition
  • uniqueness and nondegeneracy of optimal solutions
  • strict complementarity
  • stability

Cite this

Dür, Mirjam ; Jargalsaikhan, Bolor ; Still, Georg J. / Genericity Results in Linear Conic Programming : A Tour d’Horizon. In: Mathematics of operations research. 2017 ; Vol. 42, No. 1. pp. 77.
@article{23b872787f5d4b929d12a12e72ff87a0,
title = "Genericity Results in Linear Conic Programming: A Tour d’Horizon",
abstract = "This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances.In this paper, we survey known results and present new ones. In particular we give an easy proof of the fact that Slater’s condition holds generically in linear conic programming. We further discuss the problem of stability of uniqueness, nondegeneracy, and strict complementarity. We also comment on the fact that in general, a conic program cannot be treated as a smooth problem and that techniques from nonsmooth geometric measure theory are needed.",
keywords = "conic optimization, generic properties, Slater’s condition, uniqueness and nondegeneracy of optimal solutions, strict complementarity, stability",
author = "Mirjam D{\"u}r and Bolor Jargalsaikhan and Still, {Georg J.}",
note = "Finally, they gratefully acknowledge support of the Netherlands Organisation for Scientific Research [Vici Grant 639.033.907].",
year = "2017",
month = "2",
day = "1",
doi = "10.1287/moor.2016.0793",
language = "English",
volume = "42",
pages = "77",
journal = "Mathematics of operations research",
issn = "0364-765X",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "1",

}

Genericity Results in Linear Conic Programming : A Tour d’Horizon. / Dür, Mirjam; Jargalsaikhan, Bolor; Still, Georg J.

In: Mathematics of operations research, Vol. 42, No. 1, 01.02.2017, p. 77.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Genericity Results in Linear Conic Programming

T2 - A Tour d’Horizon

AU - Dür, Mirjam

AU - Jargalsaikhan, Bolor

AU - Still, Georg J.

N1 - Finally, they gratefully acknowledge support of the Netherlands Organisation for Scientific Research [Vici Grant 639.033.907].

PY - 2017/2/1

Y1 - 2017/2/1

N2 - This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances.In this paper, we survey known results and present new ones. In particular we give an easy proof of the fact that Slater’s condition holds generically in linear conic programming. We further discuss the problem of stability of uniqueness, nondegeneracy, and strict complementarity. We also comment on the fact that in general, a conic program cannot be treated as a smooth problem and that techniques from nonsmooth geometric measure theory are needed.

AB - This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances.In this paper, we survey known results and present new ones. In particular we give an easy proof of the fact that Slater’s condition holds generically in linear conic programming. We further discuss the problem of stability of uniqueness, nondegeneracy, and strict complementarity. We also comment on the fact that in general, a conic program cannot be treated as a smooth problem and that techniques from nonsmooth geometric measure theory are needed.

KW - conic optimization

KW - generic properties

KW - Slater’s condition

KW - uniqueness and nondegeneracy of optimal solutions

KW - strict complementarity

KW - stability

U2 - 10.1287/moor.2016.0793

DO - 10.1287/moor.2016.0793

M3 - Article

VL - 42

SP - 77

JO - Mathematics of operations research

JF - Mathematics of operations research

SN - 0364-765X

IS - 1

ER -