Approximating optimization problems over convex functions (Q957934)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximating optimization problems over convex functions |
scientific article |
Statements
Approximating optimization problems over convex functions (English)
0 references
1 December 2008
0 references
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.
0 references
approximation
0 references
optimization problem
0 references
discrete convex function
0 references
positive semidefinite discrete Hessian
0 references
Hessian matrix
0 references
finite difference approximation
0 references
semidefinite programming codes
0 references
\(L^2(L^1)\) projection
0 references
space \(H^K (\Omega)\)
0 references
spaces \(H^K (\Omega)\), \(L^2 (\Omega)\), \(L^1 (\Omega)\), \(L^\infty (\Omega)\)
0 references
sequence
0 references
norm
0 references
convergence
0 references
0 references
0 references
0 references