Centered solutions for uncertain linear equations

Jianzhe Zhen, Dick den Hertog

Research output: Contribution to journalArticleScientificpeer-review

45 Downloads (Pure)

Abstract

Our contribution is twofold. Firstly, for a system of uncertain linear equations where the uncertainties are column-wise and reside in general convex sets, we derive convex representations for united and tolerable solution sets. Secondly, to obtain centered solutions for uncertain linear equations, we develop a new method based on adjustable robust optimization (ARO) techniques to compute the maximum size inscribed convex body (MCB) of the set of the solutions. In general, the obtained MCB is an inner approximation of the solution set, and its center is a potential solution to the system. We use recent results from ARO to characterize for which convex bodies the obtained MCB is optimal. We compare our method both theoretically and numerically with an existing method that minimizes the worst-case violation. Applications to the input–output model, Colley’s Matrix Rankings and Article Influence Scores demonstrate the advantages of the new method.
Original languageEnglish
Pages (from-to)585-610
JournalComputational Management Science
Volume14
Issue number4
DOIs
Publication statusPublished - Oct 2017

Fingerprint

Linear equations
Uncertainty
Robust optimization

Keywords

  • interval linear systems
  • Uncertain linear equations
  • (Adjustable)Robust optimization
  • Maximum volume inscribed ellipsoid
  • Robust least-squares

Cite this

@article{e625bf4d40d24a94be666a767746d61c,
title = "Centered solutions for uncertain linear equations",
abstract = "Our contribution is twofold. Firstly, for a system of uncertain linear equations where the uncertainties are column-wise and reside in general convex sets, we derive convex representations for united and tolerable solution sets. Secondly, to obtain centered solutions for uncertain linear equations, we develop a new method based on adjustable robust optimization (ARO) techniques to compute the maximum size inscribed convex body (MCB) of the set of the solutions. In general, the obtained MCB is an inner approximation of the solution set, and its center is a potential solution to the system. We use recent results from ARO to characterize for which convex bodies the obtained MCB is optimal. We compare our method both theoretically and numerically with an existing method that minimizes the worst-case violation. Applications to the input–output model, Colley’s Matrix Rankings and Article Influence Scores demonstrate the advantages of the new method.",
keywords = "interval linear systems, Uncertain linear equations, (Adjustable)Robust optimization , Maximum volume inscribed ellipsoid, Robust least-squares",
author = "Jianzhe Zhen and {den Hertog}, Dick",
year = "2017",
month = "10",
doi = "10.1007/s10287-017-0290-9",
language = "English",
volume = "14",
pages = "585--610",
journal = "Computational Management Science",
issn = "1619-697X",
publisher = "Springer Verlag",
number = "4",

}

Centered solutions for uncertain linear equations. / Zhen, Jianzhe; den Hertog, Dick.

In: Computational Management Science, Vol. 14, No. 4, 10.2017, p. 585-610.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Centered solutions for uncertain linear equations

AU - Zhen, Jianzhe

AU - den Hertog, Dick

PY - 2017/10

Y1 - 2017/10

N2 - Our contribution is twofold. Firstly, for a system of uncertain linear equations where the uncertainties are column-wise and reside in general convex sets, we derive convex representations for united and tolerable solution sets. Secondly, to obtain centered solutions for uncertain linear equations, we develop a new method based on adjustable robust optimization (ARO) techniques to compute the maximum size inscribed convex body (MCB) of the set of the solutions. In general, the obtained MCB is an inner approximation of the solution set, and its center is a potential solution to the system. We use recent results from ARO to characterize for which convex bodies the obtained MCB is optimal. We compare our method both theoretically and numerically with an existing method that minimizes the worst-case violation. Applications to the input–output model, Colley’s Matrix Rankings and Article Influence Scores demonstrate the advantages of the new method.

AB - Our contribution is twofold. Firstly, for a system of uncertain linear equations where the uncertainties are column-wise and reside in general convex sets, we derive convex representations for united and tolerable solution sets. Secondly, to obtain centered solutions for uncertain linear equations, we develop a new method based on adjustable robust optimization (ARO) techniques to compute the maximum size inscribed convex body (MCB) of the set of the solutions. In general, the obtained MCB is an inner approximation of the solution set, and its center is a potential solution to the system. We use recent results from ARO to characterize for which convex bodies the obtained MCB is optimal. We compare our method both theoretically and numerically with an existing method that minimizes the worst-case violation. Applications to the input–output model, Colley’s Matrix Rankings and Article Influence Scores demonstrate the advantages of the new method.

KW - interval linear systems

KW - Uncertain linear equations

KW - (Adjustable)Robust optimization

KW - Maximum volume inscribed ellipsoid

KW - Robust least-squares

U2 - 10.1007/s10287-017-0290-9

DO - 10.1007/s10287-017-0290-9

M3 - Article

VL - 14

SP - 585

EP - 610

JO - Computational Management Science

JF - Computational Management Science

SN - 1619-697X

IS - 4

ER -