Quadrature Formulas for Multivariate Convex Functions

We study optimal quadrature formulas for convex functions in several variables. In particular, we answer the following two questions: Are adaptive methods better than nonadaptive ones?, and are randomized (or Monte Carlo) methods better than deterministic methods?     

On the Representation of Approximate Subdifferentials for a Class of Generalized Convex Functions

Given a family of real-valued functions defined in a normed vector space X, we study a class of -convex functions having a simpler representation for the --subdifferential. The case =X^* with X being a Banach space (the Fenchel case) is particularly analysed, and we find that the sublinear lower semicontinuous functions satisfy the simpler representation with respect to X^*. As a side result, we provide various new subdifferential-type charaterizations of positively homogeneous functions among those which are lower semicontinuous and convex. In addition, we also discuss that family related to the the so-called prox-bounded functions. In this more general framework our simpler representation may give rise to a new notion of enlargement of the subdifferential.Mathematics Subject Classifications (2000) 47H05, 46B99, 47H17.This work is based on research material supported in part by CONICYT-Chile through FONDECYT 101-0116 and FONDAP-Matemáticas Aplicadas II.     

Restricted Weak Upper Semi-continuity of Subdifferentials of Convex Functions on Banach Spaces

Let X be a Banach space and f a continuous convex function on X. Suppose that for each x ∈ X and each weak neighborhood V of zero in X ^* there exists δ > 0 such that $$\partial f(y)\subset\partial f(x)+V\;\;{\rm for\;all}\;y\in X\;{\rm with}\;\|y-x\|<\delta. $$ Then every continuous convex function g with $g \leqslant f$ on X is generically Fréchet differentiable. If, in addition, $\lim\limits_{\|x\|\rightarrow\infty}f(x)=\infty$ , then X is an Asplund space.     

Robust Duality in Parametric Convex Optimization

Modelling of convex optimization in the face of data uncertainty often gives rise to families of parametric convex optimization problems. This motivates us to present, in this paper, a duality framework for a family of parametric convex optimization problems. By employing conjugate analysis, we present robust duality for the family of parametric problems by establishing strong duality between associated dual pair. We first show that robust duality holds whenever a constraint qualification holds. We then show that this constraint qualification is also necessary for robust duality in the sense that the constraint qualification holds if and only if robust duality holds for every linear perturbation of the objective function. As an application, we obtain a robust duality theorem for the best approximation problems with constraint data uncertainty under a strict feasibility condition.     

Mazur Intersection Properties and Differentiability of Convex Functions in Banach Spaces

It is proved that the dual of a Banach space with the Mazurintersection property is almost weak* Asplund. Analogously,the predual of a dual space with the weak* Mazur intersectionproperty is almost Asplund. Through the use of these arguments,it is found that, in particular, almost all (in the Baire sense)equivalent norms on l₁() and l() are Fréchet differentiableon a dense G subset. Necessary conditions for Mazur intersectionproperties in terms of convex sets satisfying a Krein–Milmantype condition are also discussed. It is also shown that, ifa Banach space has the Mazur intersection property, then everysubspace of countable codimension can be equivalently renormedto satisfy this property.     

函数的次微分性质

本文给出了函数的Fenchel次微分、Frechet次微分,Hadamard次微分,Gateaux次微分的一些重要性质,并对函数的性质尤其是凸性给出其次微分刻画。     

Generalized Fenchel’s Conjugation Formulas and Duality for Abstract Convex Functions

In this paper, we present a generalization of Fenchel’s conjugation and derive infimal convolution formulas, duality and subdifferential (and ε-subdifferential) sum formulas for abstract convex functions. The class of abstract convex functions covers very broad classes of nonconvex functions. A nonaffine global support function technique and an extended sum-epiconjugate technique of convex functions play a crucial role in deriving the results for abstract convex functions. An additivity condition involving global support sets serves as a constraint qualification for the duality. Work of Z.Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

Exact Matrix Completion via Convex Optimization

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $m\ge C\,n^{1.2}r\log n$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.     

Continuous Outer Subdifferentials in Nonsmooth Optimization

The theory of subdifferentials provides adequate methods and tools to put descent methods for nonsmooth optimization problems into practice. However, in applications it is often difficult to decide on a suitable subdifferential concept to construct a descent method. Therefore, we introduce subdifferentials in terms of their properties to indicate a selection of subdifferentials worth considering. This initials the first part of the construction of a continuous outer subdifferential (COS). Typically, methods based on e.g. the Clarke subdifferential are non-convergent without assumptions like semismoothness on the objective function. In cases in which only supersets of the Clarke subdifferential are known, semismoothness cannot be proved or is even violated. Therefore, in the second part of the construction, a previously selected subdifferential will be expanded to a continuous mapping, if necessary. This is also practicable for upper bounds of the subdifferential of current interest. Finally, based on COS we present a methodology for solving nonsmooth optimization problems. From a theoretical point of view, convergence is established through the construction of COS.

     

Solving Equations of Random Convex Functions via Anchored Regression

Foundations of Computational Mathematics - We consider the question of estimating a solution to a system of equations that involve convex nonlinearities, a problem that is common in machine...     

光滑Banach空间上扩张值函数的Frechet次微分

首先证明了Frechet光滑Banach空间上齐次函数的次微分的一个有用定理,然后利用下半连续函数和的次微分规则把Clarke-Ledyaev多方向中值不等式推广到多个函数的情形.     

两个凸多面体的差及几种次微分之间的关系

给出两种两个凸多面体差的表达式,利用这些表达式,可以具体计算这两种凸多面体的差,做为应用讨论了利用拟微分计算Penot微分和Clarke广义梯度,特别讨论了一类非光滑函数,极大值函数的光滑复合。     

On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals

Convex and concave envelopes play important roles in various types of optimization problems. In this article, we present a result that gives general guidelines for constructing convex and concave envelopes of functions of two variables on bounded quadrilaterals. We show how one can use this result to construct convex and concave envelopes of bilinear and fractional functions on rectangles, parallelograms and trapezoids. Applications of these results to global optimization are indicated.     

Mean Curvature Flow via Convex Functions on Grassmannian Manifolds

Using the convex functions on Grassmannian manifolds, the authors obtain the interior estimates for the mean curvature flow of higher codimension. Confinable properties of Gauss images under the mean curvature flow have been obtained, which reveal that if the Gauss image of the initial submanifold is contained in a certain sublevel set of the v-function, then all the Gauss images of the submanifolds under the mean curvature flow are also contained in the same sublevel set of the v-function. Under such restrictions, curvature estimates in terms of v-function composed with the Gauss map can be carried out.     

Convex Semi-Infinite Parametric Programming: Uniform Convergence of the Optimal Value Functions of Discretized Problems

The continuity of the optimal value function of a parametric convex semi-infinite program is secured by a weak regularity condition that also implies the convergence of certain discretization methods for semi-infinite problems. Since each discretization level yields a parametric program, a sequence of optimal value functions occurs. The regularity condition implies that, with increasing refinement of the discretization, this sequence converges uniformly with respect to the parameter to the optimal value function corresponding to the original semi-infinite problem. Our result is applicable to the convergence analysis of numerical algorithms based on parametric programming, for example, rational approximation and computation of the eigenvalues of the Laplacian.     

Limit Superior of Subdifferentials of Uniformly Convergent Functions

In this paper we show that the – subdifferential of a lower semicontinuous function is contained in the limit superior of the – subdifferential of lower semicontinuous uniformly convergent family to this function. It happens that this result is equivalent to the corresponding normal cones formulas for family of sets which converges in the sense of the bounded Hausdorff distance. These results extend to the infinite dimensional case those of Ioffe for – functions and of Benoist for Clarkes normal cone. As an application we characterize the subdifferential of any function which is bounded from below by a negative quadratic form in terms of its Moreau–Yosida proximal approximation.     

Subdifferentials of Distance Functions, Approximations and Enlargements

In this work, we study some subdifferentials of the distance function to a nonempty nonconvex closed subset of a general Banach space. We relate them to the normal cone of the enlargements of the set which can be considered as regularizations of the set.     

Global Optimization of Marginal Functions with Applications to Economic Equilibrium

We discuss the applicability of the cutting angle method to global minimization of marginal functions. The search of equilibrium prices in the exchange model can be reduced to the global minimization of certain functions, which include marginal functions. This problem has been approximately solved by the cutting angle method. Results of numerical experiments are presented and discussed.