Stochastic programming with incomplete information:a surrey of results on postoptimization and sensitivity analysis

The possibility of successful applications of stochastic programming decision models has been limited by the assumed complete knowledge of the distribution Fof the random parameters as well as by the limited scope of the existing numerical procedures.

We shall give a survey of selected methods which can be used to deal with the incomplete knowledge of the distribution F, namely to study robustness of the optimal solution and the optimal value of the objective function relative to small changes of the underlying distribution and to get error bounds in approximation schemes.     

On Martos' and Chaehes-Coopeb's approach vis-a-vis

In this paper a linear fractional programming problem is studied in presence of “singular-points”. It is proved that “singular points”, if present, exist at an extreme point of S: = {x ? R ⁿ | Ax = b, x ≧0}

It is also shown that a “singular point” is adjacent to an optimal point of S and a characterization of a non-basic vector is obtained, whose entry into the optimal basis in Martos' approach yields the “singular point”.     

A bibliography on outranking approaches (1988-1982)

A linear optimization problem with parameters as right-hand sides of the restrictions and as coefficients of the objective function is considered. In some special cases one can discern stability domains from an explicit optimal simplex tableau. Furthermore it is proved that the set of vertices of the solvability cone is a stability domain.     

Efficient sample sizes in stochastic nonlinear programming

We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is specified in terms of a fractional reduction of the initial cost error. We show that such an approximate solution can be found by approximately solving a sequence of sample average approximations. The key issue in this approach is the determination of the required sequence of sample average approximations as well as the number of iterations to be carried out on each sample average approximation in this sequence. We show that one can express this requirement as an idealized optimization problem whose cost function is the computing work required to obtain the required error reduction. The specification of this idealized optimization problem requires the exact knowledge of a few problems and algorithm parameters. Since the exact values of these parameters are not known, we use estimates, which can be updated as the computation progresses. We illustrate our approach using two numerical examples from structural engineering design.     

One-sided stability and convergence of the Nessyahu–Tadmor scheme

Non-oscillatory schemes are widely used in numerical approximations of nonlinear conservation laws. The Nessyahu–Tadmor (NT) scheme is an example of a second order scheme that is both robust and simple. In this paper, we prove a new stability property of the NT scheme based on the standard minmod reconstruction in the case of a scalar strictly convex conservation law. This property is similar to the One-sided Lipschitz condition for first order schemes. Using this new stability, we derive the convergence of the NT scheme to the exact entropy solution without imposing any nonhomogeneous limitations on the method. We also derive an error estimate for monotone initial data.     

A family of variable metric proximal methods

We consider conceptual optimization methods combining two ideas: the Moreau—Yosida regularization in convex analysis, and quasi-Newton approximations of smooth functions. We outline several approaches based on this combination, and establish their global convergence. Then we study theoretically the local convergence properties of one of these approaches, which uses quasi-Newton updates of the objective function itself. Also, we obtain a globally and superlinearly convergent BFGS proximal method. At each step of our study, we single out the assumptions that are useful to derive the result concerned.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

Relations between stochastic and parametric programming for decision problems with a random objective function

In this paper we study the relation between the general concept for an optimal solution for stochastic programming problems with a random objective function-the concept of an £-efficient solution-and the associated parametric problem, We show that it is possible under certain assumptions to obtain some or even all £-efficient solutions of the stochastic problem by solving the parametric problem with respect to a certain parameter set.     

On the finite extension of the marginal function arising in decomposition algorithms 1

We consider the problem how a convex optimal-value function arising in primal decomposition can be finitely continued beyond its domain. By a suitable presentation of the exact penalty method an implementable continuation can be obtained which does not change the set of optimal solutions. If the problem has separability and partially linearity properties we manage to obtain a complete continuation of the optimal-value function.     

Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems

We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size.     

Minimal curves with limited curvature in cases of cost depending on location

Find a connection of two points in the plane with minimal cost, the cost per length unit depending on the location, and the curvature of the curve being limited. For simple cases, as a necessary condition, the known optical law of refraction is supplemented by a “circular law of refraction”.

For the general case, a practicable numerical procedure is developed on the foundation of graph theory. This procedure is able to additionally take into consideration the given directions of the curve in the end points. Several examples demonstrate fundamental solution structures for classical basic problems and also solutions for routing problems in planning traffic ways.     

On the lower semicontinuity of optimal solution sets

We study the lower semicontinuity of the optimal solution set of a parametric optimization problem. Our results sharpen the main results of Zhao (1997, The lower semicontinuity of optimal solution sets. Journal of Mathematical Analysis and Applications, 207, 240–254. Ref. ). Namely, it is shown that the conclusion of Theorem 1 of is still valid under weaker assumptions, and the conditions on “ε-nontriviality” and uniform continuity of the objective function in Theorems 2 and 3 of can be omitted.     

The circumpolygon with maximal area

The convex circumpolygon with maximal area to a given convex polygon can be determined by means of dynamic programming. The effort of this method increases cubically with respect to the number of sides. It is further shown that the optimal circum-polygon can be constructed with ruler and circle. The applied version of dynamic programming can be also used for solving Steiner's problem of the inpoiygon with minimal circumference but it demands a higher effort than Phú's method.     

A semidefinite programming approach for solving fractional optimal control problems

This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method.     

Zur bestimmung aller elementarkreise in gerichteten graphen

New algorithms for enumerating all circuits of a directed graph are presented. These algorithms are backtrack algorithms, by which we intended to avoid fruitless computations. The best results give algorithms involving heuristic rules.

To receive numerical comparisons additionally the algorithms of DÖRFLER/MÜHL-BACHER, TIERNAN/SYSLO and BJELKINA were programmed and tested in FORTRAN (CDC 3300) and (or) ALGOL (ICL 4130).     

Duality in geometric vector optimization

The purpose of the present paper is to handle a special class of vector optimization problems, denoted as geometrical vector optimization problems, and to establish a duality approach for seeking efficient and properly efficient points of such problems.     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

Distribution sensitivity in stochastic programming

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.This research was presented in parts at the 4th International Conference on Stochastic Programming held in Prague in September 1986.