Asymptotic kuhn-tucker conditions in abstract spaces

Asymptotic extensions of the Kuhn-Tucker conditions, in which both the adjoint equation and the complementary slackness condition are solved asymptotically, are given for vector-valued mathematical programming problems in locally convex spaces. Under appropriate hypotheses, the conditions are both necessary and sufficient for optimality. In particular, they characterize optimality for linear programs. An asymptotic dual program is also given.     

On the application of a transportation model for revenue optimization in waste management: a case study

This paper describes an interactive decision support system called Opti-Link which has been developed for a company operating in the area of waste and raw material management. Built around a specific transportation problem, the system is used to maximize the revenue generated by selling waste paper to paper mills. Furthermore, the dual variables of the linear program allow the planner to identify upper bounds for setting bid prices to buy waste paper from waste collection companies. First operational results indicate a significant increase in profit while at the same time the duration of the planning process could be cut by more than half.     

A simple constraint qualification in convex programming

We introduce and characterize a class of differentiable convex functions for which the Karush—Kuhn—Tucker condition is necessary for optimality. If some constraints do not belong to this class, then the characterization of optimality generally assumes an asymptotic form.We also show that for the functions that belong to this class in multi-objective optimization, Pareto solutions coincide with strong Pareto solutions,. This extends a result, well known for the linear case.Research partly supported by the National Research Council of Canada.     

Sufficient conditions for the asymptotic optimality of projection methods as applied to operator equations

Sufficient conditions are found for the asymptotic optimality of projection methods as applied to linear operator equations in Hilbert spaces. The conditions are applicable to a wide class of equations when asymptotically optimal projection methods are sought for their solution. Applications illustrating the result are presented.     

Local Behavior of the Newton Method on Two Equivalent Systems from Linear Programming

Newton's method is a fundamental technique underlying many numerical methods for solving systems of nonlinear equations and optimization problems. However, it is often not fully appreciated that Newton's method can produce significantly different behavior when applied to equivalent systems, i.e., problems with the same solution but different mathematical formulations. In this paper, we investigate differences in the local behavior of Newton's method when applied to two different but equivalent systems from linear programming: the optimality conditions of the logarithmic barrier function formulation and the equations in the so-called perturbed optimality conditions. Through theoretical analysis and numerical results, we provide an explanation of why Newton's method performs more effectively on the latter system.     

Vertex packings: Structural properties and algorithms

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient “local” optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a “good” algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported.     

Asymptotic behaviour and stability to linear non-autonomous neutral delay difference equations

This paper is concerned with the asymptotic behaviour and the stability of a class of linear neutral delay difference equations with variable coefficients and constant delays. Via an appropriate solution of the so-called generalized characteristic equation, an asymptotic criterion and a stability result are established.     

Constraint augmentation in pseudo-singularly perturbed linear programs

In this paper we study a linear programming problem with a linear perturbation introduced through a parameter ε > 0. We identify and analyze an unusual asymptotic phenomenon in such a linear program. Namely, discontinuous limiting behavior of the optimal objective function value of such a linear program may occur even when the rank of the coefficient matrix of the constraints is unchanged by the perturbation. We show that, under mild conditions, this phenomenon is a result of the classical Slater constraint qualification being violated at the limit and propose an iterative, constraint augmentation approach for resolving this problem.     

Stability analysis of positive switched systems via joint linear copositive Lyapunov functions

In this paper, we study the asymptotic stability of continuous-time positive switched linear systems for the case when each subsystem is only stable. By using the so-called “joint linear copositive Lyapunov function” (JLCLF) generalizing the common linear copositive Lyapunov function, we show that the system remains asymptotically stable under appropriate switching if it has a JLCLF. Then, the main result is extended to positive switched linear systems with time delay.     

Asymptotically optimal rate of convergence of smoothed stochastic recursive algorithms

This work is concerned with smoothed stochastic approximation/optimization algorithms. The main emphasis is placed on the asymptotic optimality issues. An algorithm with averaging in both state variables and observations is studied. Under correlated noise processes, it is shown that a scaled sequence of the iterates converges weakly to a Browman motion. As a result the algorithm is asymptotically optimal Numerical experiments are carried out. Comparisons are made among several algorithms for both linear and nonlinear functions. The numerical results yield good agreement with our analytical findings     

On the Coderivative of the Projection Operator onto the Second-order Cone

The limiting (Mordukhovich) coderivative of the metric projection onto the second-order cone $\mathbb{R}^{n}$ is computed. This result is used to obtain a sufficient condition for the Aubin property of the solution map of a parameterized second-order cone complementarity problem and to derive necessary optimality conditions for a mathematical program with a second-order cone complementarity problem among the constraints.     

The b-hull of an integer program

Given a linear integer program: max{cx:Ax=b, x≥0 and integer},A rational, it is known that it can be solved in theory for all values of c, either by testing a finite number of solutions for optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.The main result of this paper is to show that (analogously) the integer program can be solved for all values of b, either by testing a finite number of solutions for feasibility and optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.     

Game options with gradual exercise and cancellation under proportional transaction costs

ABSTRACT

Game (Israeli) options in a multi-asset market model with proportional transaction costs are studied in the case when the buyer is allowed to exercise the option and the seller has the right to cancel the option gradually at a mixed (or randomized) stopping time, rather than instantly at an ordinary stopping time. Allowing gradual exercise and cancellation leads to increased flexibility in hedging, and hence tighter bounds on the option price as compared to the case of instantaneous exercise and cancellation. Algorithmic constructions for the bid and ask prices, and the associated superhedging strategies and optimal mixed stopping times for both exercise and cancellation are developed and illustrated. Probabilistic dual representations for bid and ask prices are also established.     

Design of discrete Dutch auctions with an uncertain number of bidders

The focus of this paper is on Dutch auctions where the bidding prices are restricted to a finite set of values and the number of bidders follows a Poisson distribution. The goal is to determine what the discrete bid levels should be to maximize the auctioneer’s expected revenue, which is the same as the average selling price of the object under consideration. We take a new approach to the problem by formulating the descending-price competitive bidding process as a nonlinear program. The optimal solution indicates that the interval between two successive bids should be wider as the Dutch auction progresses. Moreover, the auctioneer’s maximum expected revenue increases with the number of bid levels to be set as well as the expected number of bidders. Numerical examples are provided to illustrate the key results from this study and their managerial implications are discussed.     

Lower bound for the oracle projection posterior convergence rate

In Babenko and Belitser (2010), a new notion for the posterior concentration rate is proposed, the so-called oracle risk rate, the best possible rate over an appropriately chosen estimators family, which is a local quantity (as compared, e.g., with global minimax rates). The program of oracle estimation and Bayes oracle posterior optimality is fully implemented in the above paper for the Gaussian white noise model and the projection estimators family.In this note, we complement the upper bound results of Babenko and Belitser (2010) on the posterior concentration rate by a lower bound result, namely that the concentration rate of the posterior distribution around the ‘true’ value cannot be faster than the oracle projection rate.     

Structured products equilibria in conic two price markets

A novel equilibrium theory is developed for two price markets permitting investors to trade personally designed structured products. Classical market clearing is enhanced for structured products where the market allows these products to be freely bought at ask prices or sold for bid prices. Competitive pressures lead the market to lower the ask prices and raise the bid prices with the market offering individual investors the widest possible set of acceptable risks provided the aggregate counter cash flow held by the market is consistent with a more conservative prespecified set of acceptable risks. We learn that in equilibrium heterogeneous investors inherit a common hedging objective of maximizing the bid prices of the final structured product sold to market or equivalently minimizing the ask price of what is bought.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

Asymptotic behavior of the solution to a linear stochastic differential equation and almost sure optimality for a controlled stochastic process

The asymptotic behavior of a stochastic process satisfying a linear stochastic differential equation is analyzed. More specifically, the problem is solved of finding a normalizing function such that the normalized process tends to zero with probability 1. The explicit expression found for the function involves the parameters of the perturbing process, and the function itself has a simple interpretation. The solution of the indicated problem makes it possible to considerably improve almost sure optimality results for a stochastic linear regulator on an infinite time interval.     

On the asymptotic properties of multivariate sample autocovariances

We show that if a process can be obtained by filtering an autoregressive process, then the asymptotic distribution of sample autocovariances of the former is the same as the asymptotic distribution of linear combinations of sample autocovariances of the latter. This result is used to show that for small lags the sample autocovariances of the filtered process have the same asymptotic distribution as estimators utilizing more information (observations on the associated autoregression process and knowledge of the parameters of the filter). In particular, for a Gaussian ARMA process the first few sample autocovariances are jointly asymptotically efficient.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.