A Rigorous Lower Bound for the Optimal Value of Convex Optimization Problems

In this paper, we consider the computation of a rigorous lower error bound for the optimal value of convex optimization problems. A discussion of large-scale problems, degenerate problems, and quadratic programming problems is included. It is allowed that parameters, whichdefine the convex constraints and the convex objective functions, may be uncertain and may vary between given lower and upper bounds. The error bound is verified for the family of convex optimization problems which correspond to these uncertainties. It can be used to perform a rigorous sensitivity analysis in convex programming, provided the width of the uncertainties is not too large. Branch and bound algorithms can be made reliable by using such rigorous lower bounds.     

Convex extensions and envelopes of lower semi-continuous functions

 We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms. Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002 RID="*" ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award (DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S. Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization     

Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques

In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.     

The effect of transformations on the approximation of univariate (convex) functions with applications to Pareto curves

In the literature, methods for the construction of piecewise linear upper and lower bounds for the approximation of univariate convex functions have been proposed. We study the effect of the use of transformations on the approximation of univariate (convex) functions. In this paper, we show that these transformations can be used to construct upper and lower bounds for nonconvex functions. Moreover, we show that by using such transformations of the input variable or the output variable, we obtain tighter upper and lower bounds for the approximation of convex functions than without these approximations. We show that these transformations can be applied to the approximation of a (convex) Pareto curve that is associated with a (convex) bi-objective optimization problem.     

The exact extreme response and the confidence extreme response analysis of structures subjected to uncertain-but-bounded excitations

In this study, the methods for computing the exact bounds and the confidence bounds of the dynamic response of structures subjected to uncertain-but-bounded excitations are discussed. Here the Euclidean norm of the nodal displacement is considered as the measurement of the structural response. The problem of calculating the exact lower bound, the confidence (outer) approximation and the inner approximation of the exact upper bound, and the exact upper bound of the dynamic response are modeled as three convex QB (quadratic programming with box constraints) problems and a problem of quadratic programming with bivalent constraints at each time point, respectively. Accordingly, the DCA (difference of convex functions algorithm) and the vertex method are adopted to solve the above convex QB problems and the quadratic programming problem with bivalent constraints, respectively. Based on the inner approximation and the outer approximation of the exact upper bound, the error between the confidence upper bound and the exact upper bound of dynamic response could be yielded. Specially, we also investigate how to obtain the confidence bound of the dynamic response of structures subjected to harmonic excitations with uncertain-but-bounded excitation frequencies. Four examples are given to show the efficiency and accuracy of the proposed method.     

Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value, in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis over the convex hull of the upper-level integer variables.     

Abstract convex optimal antiderivatives

Having studied families of antiderivatives and their envelopes in the setting of classical convex analysis, we now extend and apply these notions and results in settings of abstract convex analysis. Given partial data regarding a c-subdifferential, we consider the set of all c-convex c-antiderivatives that comply with the given data. Under a certain assumption, this set is not empty and contains both its lower and upper envelopes. We represent these optimal antiderivatives by explicit formulae. Some well known functions are, in fact, optimal c-convex c-antiderivatives. In one application, we point out a natural minimality property of the Fitzpatrick function of a c-monotone mapping, namely that it is a minimal antiderivative. In another application, in metric spaces, a constrained Lipschitz extension problem fits naturally the convexity notions we discuss here. It turns out that the optimal Lipschitz extensions are precisely the optimal antiderivatives. This approach yields explicit formulae for these extensions, the most particular case of which recovers the well known extensions due to McShane and Whitney.     

Accelerated reflection projection algorithm and its application to the LMI problem

We discuss accelerated version of the alternating projection method which can be applied to solve the linear matrix inequality (LMI) problem. The alternating projection method is a well-known algorithm for the convex feasibility problem, and has many generalizations and extensions. Bauschke and Kruk proposed a reflection projection algorithm for computing a point in the intersection of an obtuse cone and a closed convex set. We carry on this research in two directions. First, we present an accelerated version of the reflection projection algorithm, and prove its weak convergence in a Hilbert space; second, we prove the finite termination of an algorithm which is based on the proposed algorithm and provide an explicit upper bound for the required number of iterations under certain assumptions. Numerical experiments for the LMI problem are provided to demonstrate the effectiveness and merits of the proposed algorithms.     

Concave-Convex Adaptive Rejection Sampling

We describe a method for generating independent samples from univariate density functions using adaptive rejection sampling without the log-concavity requirement. The method makes use of the fact that many functions can be expressed as a sum of concave and convex functions. Using a concave-convex decomposition, we bound the log-density by separately bounding the concave and convex parts using piecewise linear functions. The upper bound can then be used as the proposal distribution in rejection sampling. We demonstrate the applicability of the concave-convex approach on a number of standard distributions and describe an application to the efficient construction of sequential Monte Carlo proposal distributions for inference over genealogical trees. Computer code for the proposed algorithms is available online.     

Non-euclidean restricted memory level method for large-scale convex optimization

We propose a new subgradient-type method for minimizing extremely large-scale nonsmooth convex functions over simple domains. The characteristic features of the method are (a) the possibility to adjust the scheme to the geometry of the feasible set, thus allowing to get (nearly) dimension-independent (and nearly optimal in the large-scale case) rate-of-convergence results for minimization of a convex Lipschitz continuous function over a Euclidean ball, a standard simplex, and a spectahedron (the set of positive semidefinite symmetric matrices, of given size, with unit trace); (b) flexible handling of accumulated information, allowing for tradeoff between the level of utilizing this information and iterations complexity. We present extensions of the scheme for the cases of minimizing non-Lipschitzian convex objectives, finding saddle points of convex-concave functions and solving variational inequalities with monotone operators. Finally, we report on encouraging numerical results of experiments with test problems of dimensions up to 66,000.This research was supported by the Technion Fund for Promotion of Research     

Lagrange multiplier rules for non-differentiable DC generalized semi-infinite programming problems

This paper aims to study a broad class of generalized semi-infinite programming problems with (upper and lower level) objectives given as the difference of two convex functions, and (lower level) constraints described by a finite number of convex inequalities and a set constraints. First, we are interested in some various lower level constraint qualifications for the problem. Then, the results are used to establish efficient upper estimate of certain subdifferential of value functions. Finally, we apply the obtained subdifferential estimates to derive necessary optimality conditions for the problem.     

Pricing Bounds for Volatility Derivatives via Duality and Least Squares Monte Carlo

Derivatives on the Chicago Board Options Exchange volatility index have gained significant popularity over the last decade. The pricing of volatility derivatives involves evaluating the square root of a conditional expectation which cannot be computed by direct Monte Carlo methods. Least squares Monte Carlo methods can be used, but the sign of the error is difficult to determine. In this paper, we propose a new model-independent technique for computing upper and lower pricing bounds for volatility derivatives. In particular, we first present a general stochastic duality result on payoffs involving convex (or concave) functions. This result also allows us to interpret these contingent claims as a type of chooser options. It is then applied to volatility derivatives along with minor adjustments to handle issues caused by the square root function. The upper bound involves the evaluation of a variance swap, while the lower bound involves estimating a martingale increment corresponding to its hedging portfolio. Both can be achieved simultaneously using a single linear least square regression. Numerical results show that the method works very well for futures, calls and puts under a wide range of parameter choices.     

Some properties of the lower bound of optimal values in interval convex quadratic programming

One of the fundamental problems in interval quadratic programming is to compute the range of optimal values. In this paper, we derive some results on the lower bound of interval convex quadratic programming. We first develop complementary slackness conditions of a quadratic program and its Dorn dual. Then, some interesting and useful characteristics of the lower bound of interval quadratic programming are established based on these conditions. Finally, illustrative examples and remarks are given to get an insight into the problem discussed.     

Intrinsic volumes and successive radii

Motivated by a problem of Teissier to bound the intrinsic volumes of a convex body in terms of the inradius and the circumradius of the body, we give upper and lower bounds for the intrinsic volumes of a convex body in terms of the elementary symmetric functions of the so-called successive inner and outer radii. These results improve on former bounds and, in particular, they also provide bounds for the elementary symmetric functions of the roots of Steiner polynomials in terms of the elementary symmetric functions of these radii.     

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 Constraint Qualifications in Nonsmooth Optimization

We introduce extensions of the Mangasarian-Fromovitz and Abadie constraint qualifications to nonsmooth optimization problems with feasibility given by means of lower-level sets. We do not assume directional differentiability, but only upper semicontinuity of the defining functions. By deriving and reviewing primal first-order optimality conditions for nonsmooth problems, we motivate the formulations of the constraint qualifications. Then, we study their interrelation, and we show how they are related to the Slater condition for nonsmooth convex problems, to nonsmooth reverse-convex problems, to the stability of parametric feasible set mappings, and to alternative theorems for the derivation of dual first-order optimality conditions.In the literature on general semi-infinite programming problems, a number of formally different extensions of the Mangasarian-Fromovitz constraint qualification have been introduced recently under different structural assumptions. We show that all these extensions are unified by the constraint qualification presented here.     

A production-transportation problem with stochastic demand and concave production costs

Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs, at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges, so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand points. The objective function can then be represented as the difference of two convex functions, and is therefore called a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space, then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP]. We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently. Problems up to the size of 100 supply points and 500 demand points are solved. Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998     

Experiments with a new selection criterion in a fast interval optimization algorithm

Usually, interval global optimization algorithms use local search methods to obtain a good upper (lower) bound of the solution. These local methods are based on point evaluations. This paper investigates a new local search method based on interval analysis information and on a new selection criterion to direct the search. When this new method is used alone, the guarantee to obtain a global solution is lost. To maintain this guarantee, the new local search method can be incorporated to a standard interval GO algorithm, not only to find a good upper bound of the solution, but also to simultaneously carry out part of the work of the interval B&B algorithm. Moreover, the new method permits improvement of the guaranteed upper bound of the solution with the memory requirements established by the user. Thus, the user can avoid the possible memory problems arising in interval GO algorithms, mainly when derivative information is not used. The chance of reaching the global solution with this algorithm may depend on the established memory limitations. The algorithm has been evaluated numerically using a wide set of test functions which includes easy and hard problems. The numerical results show that it is possible to obtain accurate solutions for all the easy functions and also for the investigated hard problems.     

A class of problems where dual bounds beat underestimation bounds

We investigate the problem of minimizing a nonconvex function with respect to convex constraints, and we study different techniques to compute a lower bound on the optimal value: The method of using convex envelope functions on one hand, and the method of exploiting nonconvex duality on the other hand. We investigate which technique gives the better bound and develop conditions under which the dual bound is strictly better than the convex envelope bound. As a byproduct, we derive some interesting results on nonconvex duality.     

On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.