Refinement of Lagrangian bounds in optimization problems

Lagrangian constraint relaxation and the corresponding bounds for the optimal value of an original optimization problem are examined. Techniques for the refinement of the classical Lagrangian bounds are investigated in the case where the complementary slackness conditions are not fulfilled because either the original formulation is nonconvex or the Lagrange multipliers are nonoptimal. Examples are given of integer and convex problems for which the modified bounds improve the classical Lagrangian bounds.     

Lagrangian bounds in multiextremal polynomial and discrete optimization problems

Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

Logarithmic sample bounds for Sample Average Approximation with capacity- or budget-constraints

Sample Average Approximation (SAA) is used to approximately solve stochastic optimization problems. In practice, SAA requires much fewer samples than predicted by existing theoretical bounds that ensure the SAA solution is close to optimal. Here, we derive new sample-size bounds for SAA that, for certain problems, are logarithmic (existing bounds are polynomial) in problem dimension. Notably, our new bounds provide a theoretical explanation for the success of SAA for many capacity- or budget-constrained optimization problems.     

Using dual network bounds in algorithms for solving generalized set packing partitioning problems

This article deals with a method to compute bounds in algorithms for solving the generalized set packing/partitioning problems. The problems under investigation can be solved by the branch and bound method. Linear bounds computed by the simplex method are usually used. It is well known that this method breaks down on some occasions because the corresponding linear programming problems are degenerate. However, it is possible to use the dual (Lagrange) bounds instead of the linear bounds. A partial realization of this approach is described that uses a network relaxation of the initial problem. The possibilities for using the dual network bounds in the approximation techniques to solve the problems under investigation are described.     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Lower Bounds for Fixed Spectrum Frequency Assignment

Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time.     

Improved bounds for queues with delayed arrivals

Improved bounds are developed for a queue where arrivals are delayed by a fixed time. For moderate to heavy traffic, a simple improved upper bound is obtained which only uses the first two moments of the service time distribution. We show that our approach can be extended to obtain bounds for other types of delayed arrival queues. For very light traffic, asymptotically tight bounds can be obtained using more information about the service time distribution. While an improved upper bound can be obtained for light to moderate traffic it is not particularly easy to apply. This revised version was published online in June 2006 with corrections to the Cover Date.     

Error bounds and strong upper semicontinuity for monotone affine variational inequalities

Global error bounds for possibly degenerate or nondegenerate monotone affine variational inequality problems are given. The error bounds are on an arbitrary point and are in terms of the distance between the given point and a solution to a convex quadratic program. For the monotone linear complementarity problem the convex program is that of minimizing a quadratic function on the nonnegative orthant. These bounds may form the basis of an iterative quadratic programming procedure for solving affine variational inequality problems. A strong upper semicontinuity result is also obtained which may be useful for finitely terminating any convergent algorithm by periodically solving a linear program.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grants CCR-9101801 and CCR-9157632.     

A regularized projection method for complementarity problems with non-Lipschitzian functions

We consider complementarity problems involving functions which are not Lipschitz continuous at the origin. Such problems arise from the numerical solution for differential equations with non-Lipschitzian continuity, e.g. reaction and diffusion problems. We propose a regularized projection method to find an approximate solution with an estimation of the error for the non-Lipschitzian complementarity problems. We prove that the projection method globally and linearly converges to a solution of a regularized problem with any regularization parameter. Moreover, we give error bounds for a computed solution of the non-Lipschitzian problem. Numerical examples are presented to demonstrate the efficiency of the method and error bounds.

     

New improved error bounds for the linear complementarity problem

New local and global error bounds are given for both nonmonotone and monotone linear complementarity problems. Comparisons of various residuals used in these error bounds are given. A possible candidate for a best error bound emerges from our comparisons as the sum of two natural residuals.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

Some non‐standard problems in viscous flow

Energy bounds are derived for Dirichlet type boundary value problems for the Navier–Stokes and Stokes equations when a combination of the solution values initially and at a later time is prescribed. The bounds are obtained by means of a differential inequality and imply uniqueness and continuous data dependence of the solutions for a range of values of the parameter in the non‐standard auxiliary condition. Copyright © 2004 John Wiley & Sons, Ltd.     

Optimization of Stability Robustness Bounds for Linear Discrete-Time Systems

In this paper, existing stability robustness measures for the perturbation of both continuous-time and discrete-time systems are reviewed. Optimized robustness bounds for discrete-time systems are derived. These optimized bounds are obtained reducing the conservatism of existing bounds by (a) using the structural information on the perturbation and (b) changing the system coordinates via a properly chosen similarity transformation matrix. Numerical examples are used to illustrate the proposed reduced conservatism bounds.     

Comparison of Two Sets of First-Order Conditions as Bases of Interior-Point Newton Methods for Optimization with Simple Bounds

In this paper, we compare the behavior of two Newton interior-point methods derived from two different first-order necessary conditions for the same nonlinear optimization problem with simple bounds. One set of conditions was proposed by Coleman and Li; the other is the standard KKT set of conditions. We discuss a perturbation of the CL conditions for problems with one-sided bounds and the difficulties involved in extending this to problems with general bounds. We study the numerical behavior of the Newton method applied to the systems of equations associated with the unperturbed and perturbed necessary conditions. Preliminary numerical results for convex quadratic objective functions indicate that, for this class of problems, the Newton method based on the perturbed KKT formulation appears to be the more robust.     

A dynamic bounding algorithm for approximating multi-state two-terminal reliability

This paper modifies Jane and Laih’s (2008) exact and direct algorithm to provide sequences of upper bounds and lower bounds that converge to the NP-hard multi-state two-terminal reliability. Advantages of the modified algorithm include (1) it does not require a priori the lower and/or upper boundary points of the network, (2) it derives a series of increasing lower bounds and a series of decreasing upper bounds simultaneously, guaranteed to enclose the exact reliability value, and (3) trade-off between accuracy and execution time can be made to ensure an exact difference between the upper and lower bounds within an acceptable time. Examples are analyzed to illustrate the bounding algorithm, and to compare the bounding algorithm with existing algorithms. Computational experiments on a large network are conducted to realize the performance of the bounding algorithm.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

Solution Bounds of the Continuous and Discrete Lyapunov Matrix Equations

A unified approach is proposed to solve the estimation problem for the solution of continuous and discrete Lyapunov equations. Upper and lower matrix bounds and corresponding eigenvalue bounds of the solution of the so-called unified algebraic Lyapunov equation are presented in this paper. From the obtained results, the bounds for the solutions of continuous and discrete Lyapunov equations can be obtained as limiting cases. It is shown that the eigenvalue bounds of the unified Lyapunov equation are tighter than some parallel results and that the lower matrix bounds of the continuous Lyapunov equation are more general than the majority of those which have appeared in the literature.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.