Vector Variational Inequalities Involving Set-valued Mappings via Scalarization with Applications to Error Bounds for Gap Functions

In this paper, by using the scalarization approach of Konnov, several kinds of strong and weak scalar variational inequalities (SVI and WVI) are introduced for studying strong and weak vector variational inequalities (SVVI and WVVI) with set-valued mappings, and their gap functions are suggested. The equivalence among SVVI, WVVI, SVI, WVI is then established under suitable conditions and the relations among their gap functions are analyzed. These results are finally applied to the error bounds for gap functions. Some existence theorems of global error bounds for gap functions are obtained under strong monotonicity and several characterizations of global (respectively local) error bounds for the gap functions are derived.     

Gap functions for vector variational inequalities

In this article, we intend to study several scalar-valued gap functions for Stampacchia and Minty-type vector variational inequalities. We first introduce gap functions based on a scalarization technique and then develop a gap function without any scalarizing parameter. We then develop its regularized version and under mild conditions develop an error bound for vector variational inequalities with strongly monotone data. Further, we introduce the notion of a partial gap function which satisfies all, but one of the properties of the usual gap function. However, the partial gap function is convex and we provide upper and lower estimates of its directional derivative.     

On duality in multiobjective semi-infinite optimization

Abstract

In this paper, we consider multiobjective semi-infinite optimization problems which are defined in a finite-dimensional space by finitely many objective functions and infinitely many inequality constraints. We present duality results both for the convex and nonconvex case. In particular, we show weak, strong and converse duality with respect to both efficiency and weak efficiency. Moreover, the property of being a locally properly efficient point plays a crucial role in the nonconvex case.     

Regularized gap functions and error bounds for split mixed vector quasivariational inequality problems

In this paper, we consider a class of split mixed vector quasivariational inequality problems in real Hilbert spaces and establish new gap functions by using the method of the nonlinear scalarization function. Further, we obtain some error bounds for the underlying split mixed vector quasivariational inequality problems in terms of regularized gap functions. Finally, we give some examples to illustrate our results. The results obtained in this paper are new.     

Equivalent Optimization Formulations and Error Bounds for Variational Inequality Problems

We investigate whether some merit functions for variational inequality problems (VIP) provide error bounds for the underlying VIP. Under the condition that the involved mapping F is strongly monotone, but not necessarily Lipschitz continuous, we prove that the so-called regularized gap function provides an error bound for the underlying VIP. We give also an example showing that the so-called D-gap function might not provide error bounds for a strongly monotone VIP.This research was supported by United College and by a direct grant of the Chinese University of Hong Kong. The authors thank the referees for helpful comments and suggestions.     

Gap functions and error bounds for weak vector variational inequalities

In this article, by using the image space analysis, a gap function for weak vector variational inequalities is obtained. Its lower semicontinuity is also discussed. Then, these results are applied to obtain the error bounds for weak vector variational inequalities. These bounds provide effective estimated distances between a feasible point and the solution set of the weak vector variational inequalities.     

Relaxing support vectors for classification

We introduce a novel modification to standard support vector machine (SVM) formulations based on a limited amount of penalty-free slack to reduce the influence of misclassified samples or outliers. We show that free slack relaxes support vectors and pushes them towards their respective classes, hence we use the name relaxed support vector machines (RSVM) for our method. We present theoretical properties of the RSVM formulation and develop its dual formulation for nonlinear classification via kernels. We show the connection between the dual RSVM and the dual of the standard SVM formulations. We provide error bounds for RSVM and show it to be stable, universally consistent and tighter than error bounds for standard SVM. We also introduce a linear programming version of RSVM, which we call RSVMLP. We apply RSVM and RSVMLP to synthetic data and benchmark binary classification problems, and compare our results with standard SVM classification results. We show that relaxed influential support vectors may lead to better classification results. We develop a two-phase method called RSVM² for multiple instance classification (MIC) problems, where RSVM formulations are used as classifiers. We extend the two-phase method to the linear programming case and develop RSVMLP². We demonstrate the classification characteristics of RSVM² and RSVMLP², and report our classification results compared to results obtained by other SVM-based MIC methods on public benchmark datasets. We show that both RSVM² and RSVMLP² are faster and produce more accurate classification results.     

Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations

We derive bounds on the expectation of a class of periodic functions using the total variations of higher-order derivatives of the underlying probability density function. These bounds are a strict improvement over those of Romeijnders et al. (Math Program 157:3–46, 2016b), and we use them to derive error bounds for convex approximations of simple integer recourse models. In fact, we obtain a hierarchy of error bounds that become tighter if the total variations of additional higher-order derivatives are taken into account. Moreover, each error bound decreases if these total variations become smaller. The improved bounds may be used to derive tighter error bounds for convex approximations of more general recourse models involving integer decision variables.     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.     

Distributed subgradient method for multi‐agent optimization with quantized communication

This paper focuses on a distributed optimization problem associated with a time‐varying multi‐agent network with quantized communication, where each agent has local access to its convex objective function, and cooperatively minimizes a sum of convex objective functions of the agents over the network. Based on subgradient methods, we propose a distributed algorithm to solve this problem under the additional constraint that agents can only communicate quantized information through the network. We consider two kinds of quantizers and analyze the quantization effects on the convergence of the algorithm. Furthermore, we provide explicit error bounds on the convergence rates that highlight the dependence on the quantization levels. Finally, some simulation results on a l₁‐regression problem are presented to demonstrate the performance of the algorithm. Copyright © 2016 John Wiley & Sons, Ltd.     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

Gap functions and global error bounds for set-valued variational inequalities

The set-valued variational inequality problem is very useful in economics theory and nonsmooth optimization. In this paper, we introduce some gap functions for set-valued variational inequality problems under suitable assumptions. By using these gap functions we derive global error bounds for the solution of the set-valued variational inequality problems. Our results not only generalize the previously known results for classical variational inequalities from single-valued case to set-valued, but also present a way to construct gap functions and derive global error bounds for set-valued variational inequality problems.     

A second-order dynamical system with Hessian-driven damping and penalty term associated to variational inequalities

Abstract

We consider the minimization of a convex objective function subject to the set of minima of another convex function, under the assumption that both functions are twice continuously differentiable. We approach this optimization problem from a continuous perspective by means of a second-order dynamical system with Hessian-driven damping and a penalty term corresponding to the constrained function. By constructing appropriate energy functionals, we prove weak convergence of the trajectories generated by this differential equation to a minimizer of the optimization problem as well as convergence for the objective function values along the trajectories. The performed investigations rely on Lyapunov analysis in combination with the continuous version of the Opial Lemma. In case the objective function is strongly convex, we can even show strong convergence of the trajectories.     

From error bounds to the complexity of first-order descent methods for convex functions

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-?ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Hölderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple method: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form \(O(q^{k})\) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with \(\ell ^1\) regularization.     

General logical metatheorems for functional analysis

In this paper we prove general logical metatheorems which state that for large classes of theorems and proofs in (nonlinear) functional analysis it is possible to extract from the proofs effective bounds which depend only on very sparse local bounds on certain parameters. This means that the bounds are uniform for all parameters meeting these weak local boundedness conditions. The results vastly generalize related theorems due to the second author where the global boundedness of the underlying metric space (resp. a convex subset of a normed space) was assumed. Our results treat general classes of spaces such as metric, hyperbolic, CAT(0), normed, uniformly convex and inner product spaces and classes of functions such as nonexpansive, Hölder-Lipschitz, uniformly continuous, bounded and weakly quasi-nonexpansive ones. We give several applications in the area of metric fixed point theory. In particular, we show that the uniformities observed in a number of recently found effective bounds (by proof theoretic analysis) can be seen as instances of our general logical results.

     

Quantifying the error of convex order bounds for truncated first moments

The concepts of convex order and comonotonicity have become quite popular in risk theory, essentially since Kaas et al. [Kaas, R., Dhaene, J., Goovaerts, M.J., 2000. Upper and lower bounds for sums of random variables. Insurance: Math. Econ. 27, 151-168] constructed bounds in the convex order sense for a sum S of random variables without imposing any dependence structure upon it. Those bounds are especially helpful, if the distribution of S cannot be calculated explicitly or is too cumbersome to work with. This will be the case for sums of lognormally distributed random variables, which frequently appear in the context of insurance and finance.In this article we quantify the maximal error in terms of truncated first moments, when S is approximated by a lower or an upper convex order bound to it. We make use of geometrical arguments; from the unknown distribution of S only its variance is involved in the computation of the error bounds. The results are illustrated by pricing an Asian option. It is shown that under certain circumstances our error bounds outperform other known error bounds, e.g. the bound proposed by Nielsen and Sandmann [Nielsen, J.A., Sandmann, K., 2003. Pricing bounds on Asian options. J. Financ. Quant. Anal. 38, 449-473].     

On the role of convexity in isoperimetry,spectral gap and concentration

We show that for convex domains in Euclidean space, Cheeger’s isoperimetric inequality, spectral gap of the Neumann Laplacian, exponential concentration of Lipschitz functions, and the a-priori weakest requirement that Lipschitz functions have arbitrarily slow uniform tail-decay, are all quantitatively equivalent (to within universal constants, independent of the dimension). This substantially extends previous results of Maz’ya, Cheeger, Gromov–Milman, Buser and Ledoux. As an application, we conclude a sharp quantitative stability result for the spectral gap of convex domains under convex perturbations which preserve volume (up to constants) and under maps which are “on-average” Lipschitz. We also provide a new characterization (up to constants) of the spectral gap of a convex domain, as one over the square of the average distance from the “worst” subset having half the measure of the domain. In addition, we easily recover and extend many previously known lower bounds on the spectral gap of convex domains, due to Payne–Weinberger, Li–Yau, Kannan–Lovász–Simonovits, Bobkov and Sodin. The proof involves estimates on the diffusion semi-group following Bakry–Ledoux and a result from Riemannian Geometry on the concavity of the isoperimetric profile. Our results extend to the more general setting of Riemannian manifolds with density which satisfy the CD(0,∞) curvature-dimension condition of Bakry-émery. Supported by NSF under agreement #DMS-0635607.     

Monotone and cash-invariant convex functions and hulls

This paper provides some useful results for convex risk measures. In fact, we consider convex functions on a locally convex vector space E which are monotone with respect to the preference relation implied by some convex cone and invariant with respect to some numeraire (‘cash’). As a main result, for any function f, we find the greatest closed convex monotone and cash-invariant function majorized by f. We then apply our results to some well-known risk measures and problems arising in connection with insurance regulation.     

Error bound results for convex inequality systems via conjugate duality

The aim of this paper is to implement some new techniques, based on conjugate duality in convex optimization, for proving the existence of global error bounds for convex inequality systems. First of all, we deal with systems described via one convex inequality and extend the achieved results, by making use of a celebrated scalarization function, to convex inequality systems expressed by means of a general vector function. We also propose a second approach for guaranteeing the existence of global error bounds of the latter, which meanwhile sharpens the classical result of Robinson.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002