Strong Formulations of Robust Mixed 0–1 Programming

We introduce strong formulations for robust mixed 0–1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint' for allowed uncertainty in the objective coefficients. We show that for a robust 0–1 problem, there is an α–tight linear programming formulation with size polynomial in the size of an α–tight linear programming formulation for the nominal 0–1 problem. We give extensions to robust mixed 0–1 programming and present computational experiments with the proposed formulations.     

Predictor-corrector algorithm for solvingP *(κ)-matrix LCP from arbitrary positive starting points

A new predictor-corrector algorithm is proposed for solvingP _*(κ)-matrix linear complementarity problems. If the problem is solvable, then the algorithm converges from an arbitrary positive starting point (x ⁰,s ⁰). The computational complexity of the algorithm depends on the quality of the starting point. If the starting point is feasible or close to being feasible, it has -iteration complexity, whereρ ₀ is the ratio of the smallest and average coordinate ofX ⁰ s ⁰. With appropriate initialization, a modified version of the algorithm terminates in O((1+κ)²(n/ρ ₀)L) steps either by finding a solution or by determining that the problem has no solution in a predetermined, arbitrarily large, region. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also propose an extension of a recent algorithm of Mizuno toP _*(κ)-matrix linear complementarity problems such that it can start from arbitrary positive points and has superlinear convergence without a strictly complementary condition. The work of this author was supported in part by NSF, Grant DMS 9305760 and by an Oberman fellowship from the University of Iowa Center for Advanced Studies.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

Sufficiency and duality for multiobjective control problems under generalized (<Emphasis Type="Italic">B</Emphasis>, <Emphasis Type="Italic">ρ</Emphasis>)-type I functions

In this paper, we introduce the classes of (B, ρ)-type I and generalized (B, ρ)-type I, and derive various sufficient optimality conditions and mixed type duality results for multiobjective control problems under (B, ρ)-type I and generalized (B, ρ)-type I assumptions.     

Optimality Conditions and Duality in Nondifferentiable Minimax Fractional Programming with Generalized Convexity

We establish sufficient optimality conditions for a class of nondifferentiable minimax fractional programming problems involving (F, α, ρ, d)-convexity. Subsequently, we apply the optimality conditions to formulate two types of dual problems and prove appropriate duality theorems. The authors thank the referee for valuable suggestions improving the presentation of the paper.     

Optimality Conditions and Duality for?Nondifferentiable Multiobjective Fractional Programming Problems with?(C,α,ρ,d)-convexity

The purpose of this paper is to consider a class of nondifferentiable multiobjective fractional programming problems in which every component of the objective function contains a term involving the support function of a compact convex set. Based on the (C,α,ρ,d)-convexity, sufficient optimality conditions and duality results for weakly efficient solutions of the nondifferentiable multiobjective fractional programming problem are established. The results extend and improve the corresponding results in the literature.     

Nondifferentiable Minimax Fractional Programming Problems with (C, α, ρ, d)-Convexity

In this paper, we present necessary optimality conditions for nondifferentiable minimax fractional programming problems. A new concept of generalized convexity, called (C, α, ρ, d)-convexity, is introduced. We establish also sufficient optimality conditions for nondifferentiable minimax fractional programming problems from the viewpoint of the new generalized convexity. When the sufficient conditions are utilized, the corresponding duality theorems are derived for two types of dual programs. This research was partially supported by NSF and Air Force grants     

Robustness and nondegenerateness for linear complementarity problems

In this paper the main focus is on a stability concept for solutions of a linear complementarity problem. A solution of such a problem is robust if it is stable against slight perturbations of the data of the problem. Relations are investigated between the robustness, the nondegenerateness and the isolatedness of solutions. It turns out that an isolated nondegenerate solution is robust and also that a robust nondegenerate solution is isolated. Since the class of linear complementarity problems with only robust solutions or only nondegenerate solutions is not an open set, attention is paid to Garcia's classG _n of linear complementarity problems. The nondegenerate problems inG _n form an open set.     

Adjustable robust solutions of uncertain linear programs

We consider linear programs with uncertain parameters, lying in some prescribed uncertainty set, where part of the variables must be determined before the realization of the uncertain parameters (``non-adjustable variables'), while the other part are variables that can be chosen after the realization (``adjustable variables'). We extend the Robust Optimization methodology ([1, 3-6, 9, 13, 14]) to this situation by introducing the Adjustable Robust Counterpart (ARC) associated with an LP of the above structure. Often the ARC is significantly less conservative than the usual Robust Counterpart (RC), however, in most cases the ARC is computationally intractable (NP-hard). This difficulty is addressed by restricting the adjustable variables to be affine functions of the uncertain data. The ensuing Affinely Adjustable Robust Counterpart (AARC) problem is then shown to be, in certain important cases, equivalent to a tractable optimization problem (typically an LP or a Semidefinite problem), and in other cases, having a tight approximation which is tractable. The AARC approach is illustrated by applying it to a multi-stage inventory management problem.Research was partially supported by the Israeli Ministry of Science grant #0200-1-98, the Israel Science Foundation founded by The Israel Academy of Sciences and Humanities, grant #683/99-10.0, and the Fund for Promotion of Research at the Technion.     

On the embedding problem with non-Abelian kernel of orderp 4. IV

In the present paper, the embedding problem is considered for number fields with p-groups whose kernel is either of two groups with two generators α and β and with the following relations: (1) α^ρ=1, α^ρ=1, [α,β,β]=1, [α,β,α,α]=1, or (2) α^ρ=[α, β α], β^ρ=1, [α,β,β]=1. It is shown that for the solvability of the original embedding problem it is necessary and sufficient to have the solvability of the associated Abelian and local problems for all completions of the base fields. Bibliography: 7 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 211, 1994, pp. 120–126. Translated by V. V. Ishkhanov.     

Sufficiency and Duality in Multiobjective Variational Problems with Generalized Type I Functions

Recently Hachimi and Aghezzaf introduced the notion of (F,α,ρ,d)-type I functions, a new class of functions that unifies several concepts of generalized type I functions. Here, we extend the concepts of (F,α,ρ,d)-type I and generalized (F,α,ρ, d)-type I functions to the continuous case and we use these concepts to establish various sufficient optimality conditions and mixed duality results for multiobjective variational problems. Our results apparently generalize a fairly large number of sufficient optimality conditions and duality results previously obtained for multiobjective variational problems.     

On a class of stochastic partial differential equations related to turbulent transport

Summary. We consider the Cauchy problem for the mass density ρ of particles which diffuse in an incompressible fluid. The dynamical behaviour of ρ is modeled by a linear, uniformly parabolic differential equation containing a stochastic vector field. This vector field is interpreted as the velocity field of the fluid in a state of turbulence. Combining a contraction method with techniques from white noise analysis we prove an existence and uniqueness result for the solution ρ∈C ^1,2([0,T]×ℝ ^d ,(S)^*), which is a generalized random field. For a subclass of Cauchy problems we show that ρ actually is a classical random field, i.e. ρ(t,x) is an L ²-random variable for all time and space parameters (t,x)∈[0,T]×ℝ ^d . Received: 27 March 1995 / In revised form: 15 May 1997     

Constructing Restricted Patterson Measures for Geometrically Infinite Kleinian Groups

In this paper, we study exhaustions, referred to as p-restrictions, of arbitrary nonelementary Kleinian groups with at most finitely many bounded parabolic elements. Special emphasis is put on the geometrically infinite case, where we obtain that the limit set of each of these Kleinian groups contains an infinite family of closed subsets, referred to as p-restricted limit sets, such that there is a Poincaré series and hence an exponent of convergence δp, canonically associated with every element in this family. Generalizing concepts which are well known in the geometrically finite case, we then introduce the notion of p-restricted Patterson measure, and show that these measures are non-atomic, δp-harmonic, δp-subconformal on special sets and δp-conformal on very special sets. Furthermore, we obtain the results that each p-restriction of our Kleinian group is of δp-divergence type and that the Hausdorff dimension of the p-restricted limit set is equal to δp.     

On 2-stage robust LP with RHS uncertainty: complexity results and applications

We investigate here the class—denoted R-LP-RHSU—of two-stage robust linear programming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain task durations); robust maximum flow (with uncertain arc capacities); robust network capacity expansion problems; robust inventory management; some robust production planning problems in the context of power production/distribution systems. It is shown that such problems can be formulated as large scale linear programs with associated nonconvex separation subproblem. A formal proof of strong NP-hardness for the general case is then provided, and polynomially solvable subclasses are exhibited. Differences with other previously described robust LP problems (featuring row-wise uncertainty instead of column wise uncertainty) are highlighted.     

LMI-Based Robust <Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> Control of Uncertain Neutral Systems with State and Input Delays

Robust stabilization and robust H_∞ control problems for a class of uncertain neutral system with state and input delays are considered. By choosing a Lyapunov-Krasovskii functional, an alternative delay-dependent sufficient condition for the existence of a controller is derived in terms of linear matrix inequalities. Furthermore, a convex optimization problem can be formulated to obtain an H_∞ controller which minimizes an upper H_∞ norm bound of the closed-loop state-input delayed system.     

Equivalence of the Generalized Vertical Block Linear Complementarity Problems and Linear Complementarity Problems

In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices, one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property.     

A coordinate gradient descent method for <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript>-regularized convex minimization

In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing ℓ ₁-regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) to solve the more general ℓ ₁-regularized convex minimization problems, i.e., the problem of minimizing an ℓ ₁-regularized convex smooth function. We establish a Q-linear convergence rate for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving large-scale ℓ ₁-regularized linear least squares problems arising in compressed sensing and image deconvolution as well as large-scale ℓ ₁-regularized logistic regression problems for feature selection in data classification. Comparison with several state-of-the-art algorithms specifically designed for solving large-scale ℓ ₁-regularized linear least squares or logistic regression problems suggests that an efficiently implemented CGD method may outperform these algorithms despite the fact that the CGD method is not specifically designed just to solve these special classes of problems.     

Frequency domain criteria for robust stability of a family of linear difference equations 1

We provide necessary and sufficient conditions for stability of solutions to linear difference equations with coefficients in a prescribed set. The conditions encompass classes of uncertainty such as interval familiesl^p families, affine families.     

On linear programs with linear complementarity constraints

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ ₀ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.