Robustsolutionstoleast-squaresproblemswithuncertaindata.pdf资源-CSDN文库

需积分: 10 53 浏览量 2020-11-19 08:22:09 上传评论收藏 682KB PDF 举报

在本文“Robust Solutions to Least-Squares Problems with Uncertain Data”中，作者Laurent El Ghaoui和Hervé Lebret探讨了处理带有不确定数据的最小二乘问题的稳健方法。最小二乘问题通常涉及寻找一个解向量，使得误差（即实际观测值与模型预测值之间的差异）的平方和最小。然而，在现实世界的应用中，数据往往存在不确定性，这可能由于测量误差、噪声或其他不可控因素导致。文章的核心是提出了一种基于凸二次锥规划（Second-Order Cone Programming, SOCP）的稳健解决方案。SOCP是一种优化技术，可以用来在矩阵A和向量b存在不确定性的情况下最小化最坏情况下的残差误差。这种方法的复杂度与对矩阵A进行一次奇异值分解相当，这意味着它在计算效率上是可接受的。通过SOCP，不仅可以找到最优解，而且还能精确地评估解的稳健性，以及提供一种严谨的方法来计算正则化参数。作者将这种方法与Tikhonov正则化进行了对比，Tikhonov正则化是通过添加一个正则项来避免过拟合，但SOCP的优势在于它能提供解的稳健性边界，并且能够准确地计算出正则化参数。此外，当不确定性具有已知结构（如Toeplitz结构）时，可以通过半定规划（Semidefinite Programming, SDP）在多项式时间内求解相同的问题。这在处理某些特定类型的不确定性时尤其有用，因为SDP能够有效地处理这类问题。论文还讨论了当系数矩阵A和向量b是未知但有界扰动向量的有理函数时的情况。作者展示了如何通过SDP来最小化最优最坏情况残差的上界。论文提供了数值例子，包括来自鲁棒识别和鲁棒插值问题的例子，以证明这些方法的有效性。这些应用领域强调了在面对不确定性时，稳健的最小二乘解决方案对于数据建模和分析的重要性。在数学符号方面，文章使用了一些标准的矩阵和向量范数，如最大奇异值（最大范数）、Frobenius范数和无穷范数。还提到了Moore-Penrose伪逆、对称正半定矩阵的平方根以及与之相关的范数定义。这篇文章为处理不确定数据的最小二乘问题提供了一种新的稳健方法，利用SOCP和SDP等工具，可以在保证计算效率的同时，提供对解稳健性的深刻理解和控制。这对于解决现实世界中的许多工程和科学问题，尤其是在信号处理、控制系统和数据分析等领域，具有重要的理论和实践价值。

资源推荐

资源详情

资源评论

ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH

UNCERTAIN DATA

∗

LAURENT EL GHAOUI

†

AND HERV

E LEBRET

†

SIAM J. M

ATRIX ANAL. APPL.



1997 Society for Industrial and Applied Mathematics

Vol. 18, No. 4, pp. 1035–1064, October 1997 015

Abstract. We consider least-squares problems where the coeﬃcient matrices A, b are unknown

but bounded. We minimize the worst-case residual error using (convex) second-order cone program-

ming, yielding an algorithm with complexity similar to one singular value decomposition of A. The

method can be interpreted as a Tikhonov regularization procedure, with the advantage that it pro-

vides an exact bound on the robustness of solution and a rigorous way to compute the regularization

parameter. When the perturbation has a known (e.g., Toeplitz) structure, the same problem can be

solved in polynomial-time using semideﬁnite programming (SDP). We also consider the case when

A, b are rational functions of an unknown-but-bounded perturbation vector. We show how to mini-

mize (via SDP) upper bounds on the optimal worst-case residual. We provide numerical examples,

including one from robust identiﬁcation and one from robust interpolation.

Key words. least-squares problems, uncertainty, robustness, second-order cone programming,

semideﬁnite programming, ill-conditioned problem, regularization, robust identiﬁcation, robust in-

terpolation

AMS subject classiﬁcations. 15A06, 65F10, 65F35, 65K10, 65Y20

PII. S0895479896298130

Notation. For a matrix X, kXk denotes the largest singular value and kXk

the Frobenius norm. If x is a vector, max

| is denoted by kxk

∞

. For a matrix A,

†

denotes the Moore–Penrose pseudoinverse of A. For a square matrix S, S ≥ 0

(resp., S>0) means S is symmetric and positive semideﬁnite (resp., deﬁnite). For

S ≥ 0, S

1/2

denotes the symmetric square root of S.ForS>0, and given vector

x, we deﬁne kxk

= kS

−1/2

xk. The notation I

denotes the p × p identity matrix;

sometimes the subscript is omitted when it can be inferred from context. For given

matrices X, Y, the notation X ⊕ Y refers to the block-diagonal matrix with X, Y as

diagonal blocks.

1. Introduction. Consider the problem of ﬁnding a solution x to an overdeter-

mined set of equations Ax ' b, where the data matrices A ∈ R

n×m

, b ∈ R

are

given. The least squares (LS) ﬁt minimizes the residual k∆bk subject to Ax = b +∆b,

resulting in a consistent linear model of the form (A, b +∆b) that is closest to the

original one (in the Euclidean norm sense). The total least squares (TLS) solution

described by Golub and Van Loan [17] ﬁnds the smallest error k[∆A ∆b]k

subject to

the consistency equation (A +∆A)x= b+∆b. The resulting closest consistent linear

model (A +∆A, b +∆b) is even more accurate than the LS one, since modiﬁcations

of A are allowed.

Accuracy is the primary aim of LS and TLS, so it is not surprising that both

solutions may exhibit very sensitive behavior to perturbations in the data matrices

(A, b). Detailed sensitivity analyses for the LS and TLS problems may be found

in [12, 18, 2, 44, 22, 14]. Many regularization methods have been proposed to decrease

sensitivity and make LS and TLS applicable. Most regularization schemes for LS,

including Tikhonov regularization [43], amount to solve a weighted LS problem for

∗

Received by the editors February 7, 1996; accepted for publication (in revised form) by S. Van

Huﬀel November 4, 1996.

http://www.siam.org/journals/simax/18-4/29813.html

†

Ecole Nationale Sup´erieure de Techniques Avanc´ees, 32, Bd. Victor, 75739 Paris C´edex 15,

France (elghaoui@ensta.fr, lebret@ensta.fr).

1035

1036 LAURENT EL GHAOUI AND HERV

E LEBRET

an augmented system. As pointed out in [18], the choice of weights (or regularization

parameter) is usually not obvious and application dependent. Several criteria for

optimizing the regularization parameter(s) have been proposed (see, e.g., [23, 11,

15]). These criteria are chosen according to some additional a priori information, of

deterministic or stochastic nature. The extensive surveys [31, 8, 21] discuss these

problems and some applications.

In contrast with the extensive work on sensitivity and regularization, relatively

little has been done on the subject of deterministic robustness of LS problems in which

the perturbations are deterministic and unknown but bounded (not necessarily small).

Some work has been done on a qualitative analysis of the problem, where entries of

(A, b) are unspeciﬁed except for their sign [26, 39]. In many papers mentioning least

squares and robustness, the latter notion is understood in some stochastic sense; see,

e.g., [20, 47, 37]. A notable exception concerns the ﬁeld of identiﬁcation, where the

subject has been explored using a framework used in control system analysis [40, 9],

or using regularization ideas combined with additional a priori information [34, 42].

In this paper, we assume that the data matrices are subject to (not necessarily

small) deterministic perturbations. First, we assume that the given model is not a

single pair (A, b) but a family of matrices (A+∆A, b+∆b), where ∆ = [∆A ∆b]isan

unknown-but-bounded matrix; precisely, k∆k≤ρ, where ρ ≥ 0isgiven.Forxﬁxed,

we deﬁne the worst-case residual as

r(A, b, ρ, x)

∆

= max

k∆A ∆bk

≤ρ

k(A +∆A)x−(b+∆b)k.(1)

We say that x is a robust least squares (RLS) solution if x minimizes the worst-case

residual r(A, b, ρ, x). The RLS solution trades accuracy for robustness at the expense

of introducing bias. In our paper, we assume that the perturbation bound ρ is known,

but in section 3.5 we also show that TLS can be used as a preliminary step to obtain

a value of ρ that is consistent with data matrices A, b.

In many applications, the perturbation matrices ∆A,∆bhave a known structure.

For instance, ∆A might have a Toeplitz structure inherited from A. In this case, the

worst-case residual (1) might be a very conservative estimate. We are led to consider

the following structured RLS (SRLS) problem. Given A

,...,A

∈R

n×m

, b

,...,b

∈R

, we deﬁne, for every δ ∈ R

A(δ)

∆

= A

i=1

, b(δ)

∆

= b

i=1

.(2)

For ρ ≥ 0andx∈R

, we deﬁne the structured worst-case residual as

(A, b,ρ,x)

∆

= max

kδk≤ρ

kA(δ)x − b(δ)k.(3)

We say that x is an SRLS solution if x minimizes the worst-case residual r

(A, b,ρ,x).

Our main contribution is to show that we can compute the exact value of the

optimal worst-case residuals using convex, second-order cone programming (SOCP)

or semideﬁnite programming (SDP). The consequence is that the RLS and SRLS

problems can be solved in polynomial time and with great practical eﬃciency using,

e.g., recent interior-point methods [33, 46]. Our exact results are to be contrasted with

those of Doyle et al. [9], who also use SDP to compute upper bounds on the worst-

case residual for identiﬁcation problems. In the preliminary draft [5] sent to us shortly

ROBUST LEAST SQUARES 1037

after submission of this paper, the authors provide a solution to an (unstructured)

RLS problem, which is similar to that given in section 3.2.

Another contribution is to show that the RLS solution is continuous in the data

matrices A, b. RLS can thus be interpreted as a (Tikhonov) regularization technique

for ill-conditioned LS problems: the additional a priori information is ρ (the per-

turbation level), and the regularization parameter is optimal for robustness. Similar

regularity results hold for the SRLS problem.

We also consider a generalization of the SRLS problem, referred to as the linear-

fractional SRLS problem in what follows, in which the matrix functions A(δ), b(δ)

in (2) depend rationally on the parameter vector δ. (We describe a robust interpo-

lation problem that falls in this class in section 7.6.) Using the framework of [9], we

show that the problem is NP-complete in this case, but we may compute and optimize

upper bounds on the worst-case residual using SDP. In parallel with RLS, we interpret

our solution as one of a weighted LS problem for an augmented system, the weights

being computed via SDP.

The paper’s outline is as follows. The next section is devoted to some technical

lemmas. Section 3 is devoted to the RLS problem. In section 4, we consider the SRLS

problem. Section 5 studies the linear-fractional SRLS problem. Regularity results are

given in section 6. Section 7 shows numerical examples.

2. Preliminary results.

2.1. Semideﬁnite and second-order cone programs. We brieﬂy recall some

important results on semideﬁnite programs (SDPs) and second-order cone programs

(SOCPs). These results can be found, e.g., in [4, 33, 46].

A linear matrix inequality is a constraint on a vector x ∈ R

of the form

F(x)=F

i=1

≥ 0,(4)

where the symmetric matrices F

= F

∈ R

N×N

, i =0,...,m, are given. The

minimization problem

minimize c

x subject to F(x) ≥ 0,

(5)

where c ∈ R

, is called an SDP. SDPs are convex optimization problems and can be

solved in polynomial time with, e.g., primal-dual interior-point methods [33, 45].

The problem dual to problem (5) is

maximize −TrF

subject to Z≥0, TrF

Z = c

,i=1,...,m,

(6)

where Z is a symmetric N ×N matrix and c

is the ith coordinate of vector c. When

both problems are strictly feasible (that is, when there exists x, Z which satisfy the

constraints strictly), the existence of optimal points is guaranteed [33, Thm. 4.2.1],

and both problems have equal optimal objectives. In this case, the optimal primal-

dual pairs (x, Z) are those pairs (x, Z) such that x is feasible for the primal problem,

Z is feasible for the dual one, and F(x)Z =0.

An SOCP problem is one of the form

minimize c

subject to kC

x + d

k≤e

x+f

,i=1,...,L,

(7)

ROBUST LEAST SQUARES 1039

Proof.IfT

or T

equal zero, the result is obvious. Now assume T

6= 0. Then,

(10) implies τ>0, which in turn implies kT

k < 1. Thus, for a given τ , (10) holds if

and only if kT

k < 1, and for every (u, p)wehave

u+2T

p)−τ(q

q−p

p)≥0,

where q = T

u + T

p. Since T

6= 0, the constraint q

q ≥ p

p is qualiﬁed, that is,

satisﬁed strictly for some (u

) (choose p

= 0 and u

such that T

6= 0). Using

the S-procedure, we obtain that there exists τ ∈ R such that (10) holds if and only

if kT

k < 1, and for every (u, p) such that q

q ≥ p

p we have u

u +2T

p)≥0.

We end our proof by noting that for every pair (p, q), p =∆

qfor some ∆, k∆k≤1

if and only if p

p ≤ q

The following lemma is a “structured” version of the above, which can be traced

back to [13].

Lemma 2.3. Let T

= T

, T

be real matrices of appropriate size. Let D

be a subspace of R

N×N

and denote by S (resp., G) the set of symmetric (resp., skew-

symmetric) matrices that commute with every element of D. We have det(I −T

∆) 6=

0 and (9) for every ∆ ∈D,k∆k≤1, if there exist S ∈S,G∈Gsuch that



− T

−T

+ T

−T

−GT

S − GT

+ T

G − T



> 0,S>0.

If D = R

N×N

, the condition is necessary and suﬃcient.

Proof. The proof follows the scheme of that of Lemma 2.2, except that p

p ≤ q

is replaced with p

Sp ≤ q

Sq, p

Gq = 0, for given S ∈S,S>0, G ∈G. Note that

for G = 0, the above result is a simple application of Lemma 2.2 to the scaled matrices

, T

−1/2

, S

1/2

, S

1/2

−1/2

2.3. Elimination lemma. The last lemma is proven in [4, 24].

Lemma 2.4 (elimination). Given real matrices W = W

, U, V of appropriate

size, there exists a real matrix X such that

W + UXV

+VX

>0(11)

if and only if

U>0and

V>0,(12)

where

V are orthogonal complements of U, V .IfU, V are full column rank, and (12)

holds, a solution X to the inequality (11) is

X = σ(U

−1

V,(13)

where Q

∆

= W + σV V

, and σ is any scalar such that Q>0(the existence of which

is guaranteed by (12)).

3. Unstructured RLS. In this section, we consider the RLS problem, which is

to compute

φ(A, b, ρ)

∆

=min

max

k∆A ∆bk

≤ρ

k(A +∆A)x−(b+∆b)k.(14)

For ρ = 0, we recover the standard LS problem. For every ρ>0, φ(A, b, ρ)=

ρφ(A/ρ, b/ρ, 1), so we take ρ = 1 in what follows, unless otherwise stated. In the re-

mainder of this paper, φ(A, b) (resp., r(A, b, x)) denotes φ(A, b, 1) (resp., r(A, b, 1,x)).

剩余29页未读，继续阅读

评论收藏

内容反馈

Quant0xff

粉丝: 1w+
资源: 459

Robust solutions to least-squares problems with uncertain data.p...

最新资源

Robust solutions to least-squares problems with uncertain data.p...

Methods fornonlinear least squares problems.pdf

Robust solutions of LP contaminated with uncertain data.pdf

Robust solutions of uncertain linear programs.pdf

Robust anti-synchronization of uncertain chaotic systems based on multiple-kernel least squares support vector machine modeling

robust solutions to multi-objective linear programming with uncertain data.pdf

Optimization with uncertain data.pdf

Worst-Case_Conditional_Value-at-Risk_with_Applicat.pdf

Jamie-Grier-Robust-Stream-Processing-with-Apache-Flink.pdf

mcts70-515_microsoft_trainingkit.pdf

RSA 2018PPT汇总（108份）.zip

演示-Robust Multi-Modality Multi-Object Tracking.pptx

论文研究-ROBUST STABILITY TEST FOR STATE-SPACE MODELS WITH STRUCTURED UNCERTAINTY.pdf

CCDE 400-007-en-unlocked.pdf

BZT52C18S-7-F_datasheet.eeworld.com.cn.pdf

Arduino-arduino-robust-serial.zip

Lerner -- Python Workout. 50 Essential Exercises -- 2020.pdf

GSC ----robust adaptive beamforming.pdf

Graph Neural Networks_ A Review of Methods and Applications----清华大学周杰.pdf

IE598NH-lecture-10-11-CCP.pdf

mems-based-conductivitytemperaturedepth-ctd-sensor-for-hars.pdf

A MATLAB function for robust non-linear least squares.zip

A robust asset-liability man- agement framework.pdf

Min-max robust and CVaR.pdf

个人精心收集的云计算相关论文（共15篇）

Mastering.Cross-Platform.Development.with.Xamarin.2016.3.pdf

最新资源