A note on error bounds for convex and nonconvex programs. (English) Zbl 1040.90546

Bertsekas, Dimitri P.

Comput. Optim. Appl. 12, No. 1-3, 41-51 (1999).

Summary: Given a single feasible solution \(x_F\) and a single infeasible solution \(x_I\) of a mathematical program, we provide an upper bound to the optimal dual value. We assume that \(x_F\) satisfies a weakened form of the Slater condition. We apply the bound to convex programs and we discuss its relation to Hoffman-like bounds. As a special case, we recover a bound due to O. L. Mangasarian [Math. Program. 83A, 187–194 (1998; Zbl 0920.90119)] on the distance of a point to a convex set specified by inequalities.

MSC:

90C31	Sensitivity, stability, parametric optimization
90C25	Convex programming
49K40	Sensitivity, stability, well-posedness

Keywords:

convex programming; optimization duality; error bounds

Citations:

Zbl 0920.90119