Worst-case analyses, linear programming and the bin-packing problem

In this paper we consider the familiar bin-packing problem and its associated set-partitioning formulation. We show that the optimal solution to the bin-packing problem can be no larger than 4/3 ⌈Z _LP⌉, whereZ _LP is the optimal solution value of the linear programming relaxation of the set-partitioning formulation. An example is provided to show that the bound is tight. A by-product of our analysis is a new worst-case bound on the performance of the well studied First Fit Decreasing and Best Fit Decreasing heuristics. This research was supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, and NSF Contracts DDM-8922712 and DDM-9322828.     

Convergence results for a nonlinear parabolic control problem

We investigate a general control problem for a class of nonlinear parabolic evolution equations. Applications are related to solid-solid and solid-liquid phase transitions.

We prove compactness of the solution operators, existence of optimal controls and show convergence of the finite-dimensional approximate control problem to the original one.     

An Isotonic Regression Problem for Infinite-Dimensional Parameters

We consider an infinite-dimensional isotonic regression problem which is an extension of the suitably revised classical isotonic regression problem. Given p-summable data, for p finite and at least one, there exists an optimal estimator to our problem. For p greater than one, this estimator is unique and is the limit in the p-norm of the sequence of unique estimators in canonical finite-dimensional truncations of our problem. However, for p equal to one, our problem, as well as the finite-dimensional truncations, admit multiple optimal estimators in general. In this case, the sequence of optimal estimator sets to the truncations converges to the optimal estimator set of the infinite problem in the sense of Kuratowski. Moreover, the selection of natural best optimal estimators to the truncations converges in the 1-norm to an optimal estimator of the infinite problem.     

Discrete approximation of linear two–stage stochastic programming problem

This paper describes a possibility for approximate solution of stochastic programming problems with complete recourse. We replace the static form of linear problem in L^p-space by a sequence of discretized problems in finite-dimensional spaces. We present conditions that guarantee the convergence of optimal values of discretized problems to the optimal value of the initial problem.     

A D.C. optimization method for single facility location problems

The single facility location problem with general attraction and repulsion functions is considered. An algorithm based on a representation of the objective function as the difference of two convex (d.c.) functions is proposed. Convergence to a global solution of the problem is proven and extensive computational experience with an implementation of the procedure is reported for up to 100,000 points. The procedure is also extended to solve conditional and limited distance location problems. We report on limited computational experiments on these extensions.This research was supported in part by the National Science Foundation Grant DDM-91-14489.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

Finite-dimensional stabilization of stationary Navier-Stokes systems

We consider the stabilization problem for an unstable solution of an operator equation of Navier-Stokes type. We show that one can exponentially stabilize this solution by treating it as the unique solution of a stationary variational inequality; the stabilizing operator has finite-dimensional range.     

A new method for interpolating in a convex subset of a Hilbert space

In this paper, interpolating curve or surface with linear inequality constraints is considered as a general convex optimization problem in a Reproducing Kernel Hilbert Space. The aim of the present paper is to propose an approximation method in a very general framework based on a discretized optimization problem in a finite-dimensional Hilbert space under the same set of constraints. We prove that the approximate solution converges uniformly to the optimal constrained interpolating function. Numerical examples are provided to illustrate this result in the case of boundedness and monotonicity constraints in one and two dimensions.     

Convergence behavior of interior-point algorithms

We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.Research supported in part by NSF Grant DDM-8922636, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

Optimal control of self-adjoint nonlinear operator equations in Hilbert spaces

In this paper, we formulate and study a general optimal control problem governed by nonlinear operator equations described by unbounded self-adjoint operators in Hilbert spaces. This problem extends various particular control models studied in the literature, while it has not been considered before in such a generality. We develop an efficient way to construct a finite-dimensional subspace extension of the given self-adjoint operator that allows us to design the corresponding adjoint system and finally derive an appropriate counterpart of the Pontryagin Maximum Principle for the constrained optimal control problem under consideration by using the obtained increment formula for the cost functional and needle type variations of optimal controls.     

Solving binary cutting stock problems by column generation and branch-and-bound

We present an algorithm for the binary cutting stock problem that employs both column generation and branch-and-bound to obtain optimal integer solutions. We formulate a branching rule that can be incorporated into the subproblem to allow column generation at any node in the branch-and-bound tree. Implementation details and computational experience are discussed.This research was supported by NSF and AFOSR grant DDM-9115768     

Optimal control of the multidimensional diffusion equation

The existence and numerical estimation of a boundary control for then-dimensional linear diffusion equation is considered. The problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures. The existence of an optimal measure corresponding to the above problem is shown, and the optimal measure is approximated by a finite convex combination of atomic measures. This construction gives rise to a finite-dimensional linear programming problem, whose solution can be used to construct the combination of atomic measures, and thus a piecewise-constant control function which approximates the action of the optimal measure, so that the final state corresponding to the above control function is close to the desired final state, and the value it assigns to the performance criterion is close to the corresponding infimum. A numerical procedure is developed for the estimation of these controls, entailing the solution of large, finite-dimensional linear programming problems. This procedure is illustrated by several examples.     

Monotonicity of optimal flow control for failure-prone production systems

In this paper, we consider the problem of the optimal flow control for a production system with one machine which is subject to failures and produces one part type. In most previous work, it has been assumed that the machine has exponential up and down times, i.e., its state process is a Markov process. The system considered in our study has general machine up and down times. Our main result is establishing monotone properties for the optimal control policy.This work was partially supported by the National Science Foundation under Grants DDM-9215368 and EDI-9212122. The authors thank two anonymous reviewers for helpful comments and suggestions.     

Min-cut clustering

We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This research was supported by NSF grants DMS-8719128 and DDM-9115768, and by an IBM grant to the Computational Optimization Center, Georgia Institute of Technology.     

First-order conditions for isolated locally optimal solutions

There are well-known first-order sufficient conditions for a pointx ₀ to be a strict locally optimal solution of a nonlinear programming problem. In this paper, we show that these conditions also guarantee thatx ₀ is an isolated stationary point of the considered program provided a constraint qualification holds. This result has an interesting application to finite convergence of algorithms along the lines suggested by Al-Khayyal and Kyparisis.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

Approximation of optimal feedback control: a dynamic programming approach

We consider the general continuous time finite-dimensional deterministic system under a finite horizon cost functional. Our aim is to calculate approximate solutions to the optimal feedback control. First we apply the dynamic programming principle to obtain the evolutive Hamilton–Jacobi–Bellman (HJB) equation satisfied by the value function of the optimal control problem. We then propose two schemes to solve the equation numerically. One is in terms of the time difference approximation and the other the time-space approximation. For each scheme, we prove that (a) the algorithm is convergent, that is, the solution of the discrete scheme converges to the viscosity solution of the HJB equation, and (b) the optimal control of the discrete system determined by the corresponding dynamic programming is a minimizing sequence of the optimal feedback control of the continuous counterpart. An example is presented for the time-space algorithm; the results illustrate that the scheme is effective.     

Superlinear convergence of the affine scaling algorithm

In this paper we show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that 2/3 is a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical explanation for why 2/3 is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates. The work of this author was based on research supported by the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan, 1992. The work of this author was based on research supported by the National Science Foundation (NSF) under grant DDM-9109404 and the Office of Naval Research (ONR) under grant N00014-93-1-0234. This work was done while the second author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Solutions to Constrained Optimal Control Problems with Linear Systems

This paper is devoted to present solutions to constrained finite-horizon optimal control problems with linear systems, and the cost functional of the problem is in a general form. According to the Pontryagin’s maximum principle, the extremal control of such problem is a function of the costate trajectory, but an implicit function. We here develop the canonical backward differential flows method and then give the extremal control explicitly with the costate trajectory by canonical backward differential flows. Moreover, there exists an optimal control if and only if there exists a unique extremal control. We give the proof of the existence of the optimal solution for this optimal control problem with Green functions.     

Approximation of variational eigenvalue problems

A variational eigenvalue problem in an infinite-dimensional Hilbert space is approximated by a problem in a finite-dimensional subspace. We analyze the convergence and accuracy of the approximate solutions. The general results are illustrated by a scheme of the finite element method with numerical integration for a one-dimensional second-order differential eigenvalue problem. For this approximation, we obtain optimal estimates for the accuracy of the approximate solutions.     

The turnpike property in finite-dimensional nonlinear optimal control

Turnpike properties have been established long time ago in finite-dimensional optimal control problems arising in econometry. They refer to the fact that, under quite general assumptions, the optimal solutions of a given optimal control problem settled in large time consist approximately of three pieces, the first and the last of which being transient short-time arcs, and the middle piece being a long-time arc staying exponentially close to the optimal steady-state solution of an associated static optimal control problem. We provide in this paper a general version of a turnpike theorem, valuable for nonlinear dynamics without any specific assumption, and for very general terminal conditions. Not only the optimal trajectory is shown to remain exponentially close to a steady-state, but also the corresponding adjoint vector of the Pontryagin maximum principle. The exponential closedness is quantified with the use of appropriate normal forms of Riccati equations. We show then how the property on the adjoint vector can be adequately used in order to initialize successfully a numerical direct method, or a shooting method. In particular, we provide an appropriate variant of the usual shooting method in which we initialize the adjoint vector, not at the initial time, but at the middle of the trajectory.