Controlled dual perturbations for l p -programming

l _p -programming is a common generalization of linear programming, quadratically constrained quadratic programming,l _p -constrainedl _p -approximation, and multiple criteria compromise programming. It is a type of convex programming with objective function and inequality constraints expressed by means ofl _p -norms. The dual program established by Peterson and Ecker is a maximization problem with a concave, upper-semicontinuous objective function over a set of constraints that are essentially linear. In developing a dual method for this problem, we face two major difficulties. One is the non-differentiability of the dual objective function and the other one is an efficient dual-to-primal conversion.In this paper, we introduce a mechanism to construct a suitably perturbed dual program with a differentiable concave objective function over linear constraints. Solving this well-constructed perturbed dual program, we can obtain an-optimal dual solution for an arbitrarily small number. Moreover, we show a way of constructing a linear program based on this dual solution. Then an-optimal primal solution can be obtained by solving the dual of this simple linear program.

---

Zusammenfassung Diel _p -Optimierung ist eine Verallgemeinerung, die die lineare Optimierung, quadratische Optimierung mit quadratischen Restriktionen,l _p -Approximation mitl _p -Restriktionen, wie auch Vektoroptimierung umfaßt. Es handelt sich dabei um konvexe Optimierungsaufgaben, bei denen Zielfunktions- und Ungleichungsrestriktionen mittelsl _p -Normen ausgedrückt werden. Das duale Problem nach Peterson and Eckert ist ein Maximierungsproblem mit einer konkaven oberhalb-halbstetigen Zielfunktion über einer Menge von im wesentlichen linearen Restrictionen. Bei der Entwicklung einer dualen Lösungsmethode treten zwei Hauptschwierigkeiten auf: Die eine ist die Nicht-Differenzierbarkeit der dualen Zielfunktion, die andere besteht darin, eine effiziente Übertragung der dualen Lösung in eine primale zu finden.In dieser Arbeit führen wir eine Methode ein, die es gestattet, ein entsprechendes gestörtes duales Programm mit differenzierbarer konkaver Zielfunktion und linearen Restriktion aufzustellen. Bei der Lösung dieses wohl-strukturierten, gestörten dualen Problems erhalten wir eine-optimale Duallösung für beliebig kleines. Ferner zeigen wir einen Weg auf, wie, basierend auf dieser Duallösung, ein lineares Programm formuliert werden kann. Löst man das Dualproblem dieses einfachen linearen Programms, so erhält man eine-optimale Lösung für das Ausgangsproblem.

     

A Tauberian Theorem for Ergodic Averages,Spectral Decomposability,and the Dominated Ergodic Estimate for Positive Invertible Operators

Suppose that (,) is a -finite measure space, and 1 < p < . Let T:L^p( L ^p() be a bounded invertible linear operator such that T and T ^–1 are positive. Denote by _n(T) the nth two-sided ergodic average of T, taken in the form of the nth (C,1) mean of the sequence {T^j+T^–j}_{j =1} . Martín-Reyes and de la Torre have shown that the existence of a maximal ergodic estimate for T is characterized by either of the following two conditions: (a) the strong convergence of E_n(T)_n=1 ; (b) a uniform A _p p estimate in terms of discrete weights generated by the pointwise action on of certain measurable functions canonically associated with T. We show that strong convergence of the (C,2) means of {T^j+T^–j}_j=1 already implies (b). For this purpose the (C,2) means are used to set up an `averaged' variant of the requisite uniform A _p weight estimates in (b). This result, which can be viewed as a Tauberian-Type replacement of (C,1) means by (C,2) means in (a), leads to a spectral-theoretic characterization of the maximal ergodic estimate by application of a recent result of the authors establishing the strong convergence of the (C,2)-weighted ergodic means for all trigonometrically well-bounded operators. This application also serves to equate uniform boundedness of the rotated Hilbert averages of T with the uniform boundedness of the ergodic averages E_n(T)_{n = 1} .