Approximating optimization problems over convex functions

DOI10.1007/S00211-008-0176-4MaRDI QIDQ957934zbMATH OpenOpenAlexFDO

Publication date 1 December 2008

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.1693, http://hdl.handle.net/11336/84142

Abstract: Many problems of theoretical and practical interest involve finding an optimum over a family of convex functions. For instance, finding the projection on the convex functions in

H^{k} (O m e g a)

, and optimizing functionals arising from some problems in economics. In the continuous setting and assuming smoothness, the convexity constraints may be given locally by asking the Hessian matrix to be positive semidefinite, but in making discrete approximations two difficulties arise: the continuous solutions may be not smooth, and functions with positive semidefinite discrete Hessian need not be convex in a discrete sense. Previous work has concentrated on non-local descriptions of convexity, making the number of constraints to grow super-linearly with the number of nodes even in dimension 2, and these descriptions are very difficult to extend to higher dimensions. In this paper we propose a finite difference approximation using positive semidefinite programs and discrete Hessians, and prove convergence under very general conditions, even when the continuous solution is not smooth, working on any dimension, and requiring a linear number of constraints in the number of nodes. Using semidefinite programming codes, we show concrete examples of approximations to problems in two and three dimensions.

Review text

The authors give a theoretical framework for approximating many optimization problems on convex functions using a finite differences scheme which imposes a positive semidefinite constraint on a discretization of the Hessian matrix. Positive semidefinite programs and discrete Hessians to a finite difference approximation are used. Here the semidefinite program is an optimization problem of the form: \[ \min c.x\text{ subject to }x_1A_1 + \cdots x_nA_n-A_0 \succeq 0,\quad x\in R^n, \] where \(c \in \mathbb R^n\), \(A_0, A_1 \ldots A_n\) are symmetric \( m \times m\) matrices, and \(A (A \succeq 0)\) is the symmetric positive semidefinite matrix. Different characterizations of smooth convex functions of continuous variables, which allow to extend the definition of the Hessian to \(C^1\) functions in terms of averages, are proposed. Main result: In order to have a good definition of discrete convexity, the authors show that any convex function of continuous variables may be approximated by its counterparts, and conversely, that a converging sequence (in a suitable norm) of discrete convex functions will do so to a convex function of continuous variables. It is proved that the approximation of the discrete functions to the limit \(u\) is uniform in \(u\) and its derivatives if \(u\) is smooth, and uniform in \(u\) over compact subsets of \(\Omega\), if \(u\) is merely convex and bounded (and hence continuous). If a sequence of discrete functions converges to a function which is not \(C^2\) or even \(C^1\), still convexity of the limit function is guaranteed. A general structure for optimization problems on convex functions which fits the presented results, any may be applied to several important problems, is posed. Concrete examples of approximations to problems in two and three dimensions (using semidefinite programming codes) are shown.

Recommendations

Cites work

Cited in

(23)

Describes a project that uses

Uses Software

This page was built for publication: Approximating optimization problems over convex functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957934)