Statistical approximations for recourse constrained stochastic programs

The two stage stochastic program with recourse is known to have numerous applications in financial planning, energy modeling, telecommunications systems etc. Notwithstanding its applicability, the two stage stochastic program is limited in its ability to incorporate a decision maker's attitudes towards risk. In this paper we present an extension via the inclusion of a recourse constraint. This results in a convex integrated chance constraint (ICC), which inherits the convexity properties of two stage programs. However, it also inherits some of the difficulties associated with the evaluation of recourse functions. This motivates our study of conditions that may be applicable to algorithms using statistical approximations of such ICC. We present a set of sufficient conditions that these approximations may satisfy in order to assure convergence. Our conditions are satisfied by a wide range of statistical approximations, and we demonstrate that these approximations can be generated within standard algorithmic procedures.This work was supported in part by Grant No. NSF-DDM-9114352 from the National Science Foundation.     

On the Quasiconcave Bilevel Programming Problem

Bilevel programming involves two optimization problems where the constraint region of the first-level problem is implicitly determined by another optimization problem. In this paper, we consider the case in which both objective functions are quasiconcave and the constraint region common to both levels is a polyhedron. First, it is proved that this problem is equivalent to minimizing a quasiconcave function over a feasible region comprised of connected faces of the polyhedron. Consequently, there is an extreme point of the polyhedron that solves the problem. Finally, it is shown that this model includes the most important case where the objective functions are ratios of concave and convex functions     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

A continuation method for monotone variational inequalities

This paper presents a continuation method for monotone variational inequality problems based on a new smooth equation formulation. The existence, uniqueness and limiting behavior of the path generated by the method are analyzed.This work was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by a grant from the Burlington Northern Railroad.     

The long-step method of analytic centers for fractional problems

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t ₀ |t ₀ B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial “centering” phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds. The research was partly supported by the Israeli-American Binational Science Foundation (BSF).     

Coal bank scheduling using a mathematical programming model

Coals are extracted from mines and upgraded on the surface for customers. The upgraded coals must be aged at least four weeks in a bank before being supplied to customers. Different sizes of banks are required for different lengths of time at different points in time. Bigger banks increase the floor space capacity and reduce handling costs. The proper location of banks reduces the total space requirement and bank movement after building. In this paper, we address the bank size and location problem and solve it by using a mathematical programming approach.     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

Generalized quasiconvexities,cone saddle points,and minimax theorem for vector-valued functions

We establish the following theorems: (i) an existence theorem for weak type generalized saddle points; (ii) an existence theorem for strong type generalized saddle points; (iii) a generalized minimax theorem for a vector-valued function. These theorems are generalizations and extensions of the author's recent results. For such extensions, we propose new concepts of convexity and continuity of vector-valued functions, which are weaker than ordinary ones. Some of the proofs are based on a few key observations and also on the Browder coincidence theorem or the Tychonoff fixed-point theorem. Also, the minimax theorem follows from the existence theorem for weak type generalized saddle points. The main spaces with mathematical structures considered are real locally convex spaces and real ordered topological vector spaces.This paper is dedicated to Professor Kensuke Tanaka on his sixtieth birthday.This paper was written when the author was a visitor at the Department of Mathematical Science, Graduate School of Science and Technology, Niigata University, Niigata, Japan. The author is indebted to Prof. K. Tanaka for suggesting this work.The author is very grateful to Prof. P. L. Yu for his useful encouragement and suggestions and to the referees for their valuable suggestions and comments.     

Introducing oblique norms into multiple criteria programming

We propose to use block norms to generate nondominated solutions of multiple criteria programs and introduce the new concept of the oblique norm that is specially tailored to handle general problems. We prove the equivalence of finding the properly nondominated solutions of a multiple criteria program and solving its scalarization by means of oblique norms.     

A nonsmooth Newton method for variational inequalities,I: Theory

This paper presents a modified damped Newton algorithm for solving variational inequality problems based on formulating this problem as a system of equations using the Minty map. The proposed modified damped-Newton method insures convergence and locally quadratic convergence under the assumption of regularity. Under the assumption ofweak regularity and some mild conditions, the modified algorithm is shown to always create a descent direction and converge to the solution. Hence, this new algorithm is often suitable for many applications where regularity does not hold. Part II of this paper presents the results of extensive computational testing of this new method.Corresponding author.