Higher-Order Duality in Nondifferentiable Minimax Programming with Generalized Type I Functions

A unified higher-order dual for a nondifferentiable minimax programming problem is formulated. Weak, strong and strict converse duality theorems are discussed involving generalized higher-order (F,α,ρ,d)-Type I functions. The research of second author was supported by the Department of Atomic Energy, Government of India, under the NBHM Post Doctoral Fellowship Program 40/9/2005-R&D II/2398.     

Duality for Semi-Infinite Minimax Fractional Programming Problem Involving Higher-Order (Φ, ρ)-V-Invexity

In this paper, we introduce the concept of higher-order (Φ, ρ)-V-invexity and present two types of higher-order dual models for a semi-infinite minimax fractional programming problem. Weak, strong, and strict converse duality theorems are discussed under the assumptions of higher-order (Φ, ρ)-V-invexity to establish a relation between the primal and dual problems.     

Higher-Order Duality in Nondifferentiable Multiobjective Programming

A new generalized class of higher-order (F, α, ρ, d)–type I functions is introduced, and a general Mond–Weir type higher-order dual is formulated for a nondifferentiable multiobjective programming problem. Based on the concepts introduced, various higher-order duality results are established. At the end, some special cases are also discussed.     

Finding and identifying optimal inventory levels for systems with common components

In this article, we consider the problem of finding the optimal inventory level for components in an assembly system where multiple products share common components in the presence of random demand. Previously, solution procedures that identify the optimal inventory levels for components in a component commonality problem have been considered for two product or one common component systems. We will here extend this to a three products system considering any number of common components. The inventory problem considered is modeled as a two stage stochastic recourse problem where the first stage is to set the inventory levels to maximize expected profit while the second stage is to allocate components to products after observing demand. Our main contribution, and the main focus of this paper, is the outline of a procedure that finds the gradient for the stochastic problem, such that an optimal solution can be identified and a gradient based search method can be used to find the optimal solution.     

On higher-order proto-differentiability of perturbation maps

This paper is concerned with higher-order sensitivity analysis in parametric vector optimization problems. Firstly, higher-order proto-differentiability of a set-valued mapping from one Euclidean space to another is defined. Then, we prove that the perturbation map/the proper perturbation map/the weak perturbation map of a parameterized vector optimization problem are higher-order proto-differentiable under some suitable qualification conditions.

     

Dynamic lot-sizing in sequential online retail auctions

Retailers often conduct non-overlapping sequential online auctions as a revenue generation and inventory clearing tool. We build a stochastic dynamic programming model for the seller’s lot-size decision problem in these auctions. The model incorporates a random number of participating bidders in each auction, allows for any bid distribution, and is not restricted to any specific price-determination mechanism. Using stochastic monotonicity/stochastic concavity and supermodularity arguments, we present a complete structural characterization of optimal lot-sizing policies under a second order condition on the single-auction expected revenue function. We show that a monotone staircase with unit jumps policy is optimal and provide a simple inequality to determine the locations of these staircase jumps. Our analytical examples demonstrate that the second order condition is met in common online auction mechanisms. We also present numerical experiments and sensitivity analyses using real online auction data.     

On Higher-Order Sensitivity Analysis in Nonsmooth Vector Optimization

We propose the notion of higher-order radial-contingent derivative of a set-valued map, develop some calculus rules and use them directly to obtain optimality conditions for several particular optimization problems. Then we employ this derivative together with contingent-type derivatives to analyze sensitivity for nonsmooth vector optimization. Properties of higher-order contingent-type derivatives of the perturbation and weak perturbation maps of a parameterized optimization problem are obtained.     

Some results on sensitivity analysis in set-valued optimization

In the paper, the higher-order contingent derivative of a parametrized set-valued inclusion is first established. For its applications, we obtain sensitivity analysis of solution map in the decision variable space for a parametrized constrained set-valued optimization problem in terms of higher-order contingent derivatives.     

Heuristic and lower bound for a stochastic location-routing problem

In this article a stochastic location-routing problem is defined and cast as a two-stage model. In a first stage the set of plants and a family of routes are determined; in a second stage a recourse action is applied to adapt these routes to the actual set of customers to visit, once they are known. A two-phase heuristic is developed. An initial feasible solution is built by solving a sequence of subproblems, and an improvement phase is then applied. A lower bound based on bounding separately different parts of the cost of any feasible solution is also developed. Computational results are reported.     

Weak and strong stationarity in generalized bilevel programming and bilevel optimal control

In this article, we consider a general bilevel programming problem in reflexive Banach spaces with a convex lower level problem. In order to derive necessary optimality conditions for the bilevel problem, it is transferred to a mathematical program with complementarity constraints (MPCC). We introduce a notion of weak stationarity and exploit the concept of strong stationarity for MPCCs in reflexive Banach spaces, recently developed by the second author, and we apply these concepts to the reformulated bilevel programming problem. Constraint qualifications are presented, which ensure that local optimal solutions satisfy the weak and strong stationarity conditions. Finally, we discuss a certain bilevel optimal control problem by means of the developed theory. Its weak and strong stationarity conditions of Pontryagin-type and some controllability assumptions ensuring strong stationarity of any local optimal solution are presented.     

On Higher-Order Sensitivity Analysis of Parametric Henig Set-Valued Equilibrium Problems

Abstract

In the article, we discuss sensitivity analysis of a parametric Henig set-valued equilibrium problem. In detail, relationships between the higher-order contingent derivative of the solution map of this problem and those of objective and constraint maps are established. Finally, applications to parametric set-valued optimization problems are given.     

Higher-order optimality conditions in set-valued optimization using radial sets and radial derivatives

We propose higher-order radial sets and corresponding derivatives of a set-valued map and prove calculus rules for sums and compositions, which are followed by direct applications in discussing optimality conditions for several particular optimization problems. Our main results are both necessary and sufficient higher-order conditions for weak efficiency in a general set-valued vector optimization problem without any convexity assumptions. Many examples are provided to explain advantages of our results over a number of existing ones in the literature.     

The full-information best-choice problem with uniform or gamma horizons

A decision-maker has to choose one from among a Poisson stream of i.i.d. bids, with no recall. The stream stops at a random time with a uniform (in the first case) or Erlang (in the second case) distribution. We solve the problem explicitly for maximal expected gain for bids that may take on any finite number of values. A fast procedure to solve the problem for fixed horizon is presented as well.     

New algorithms for constrained minimax optimization

A constrained minimax problem is converted to minimization of a sequence of unconstrained and continuously differentiable functions in a manner similar to Morrison's method for constrained optimization. One can thus apply any efficient gradient minimization technique to do the unconstrained minimization at each step of the sequence. Based on this approach, two algorithms are proposed, where the first one is simpler to program, and the second one is faster in general. To show the efficiency of the algorithms even for unconstrained problems, examples are taken to compare the two algorithms with recent methods in the literature. It is found that the second algorithm converges faster with respect to the other methods. Several constrained examples are also tried and the results are presented.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities

Extending our work on second-order cover cuts [F. Glover, H.D. Sherali, Second-order cover cuts, Mathematical Programming (ISSN: 0025-5610 1436-4646) (2007), doi:10.1007/s10107-007-0098-4. (Online)], we introduce a new class of higher-order cover cuts that are derived from the implications of a knapsack constraint in concert with supplementary two-sided inequalities that bound the sums of sets of variables. The new cuts can be appreciably stronger than the second-order cuts, which in turn dominate the classical knapsack cover inequalities. The process of generating these cuts makes it possible to sequentially utilize the second-order cuts by embedding them in systems that define the inequalities from which the higher-order cover cuts are derived. We characterize properties of these cuts, design specialized procedures to generate them, and establish associated dominance relationships. These results are used to devise an algorithm that generates all non-dominated higher-order cover cuts, and, in particular, to formulate and solve suitable separation problems for deriving a higher-order cut that deletes a given fractional solution to an underlying continuous relaxation. We also discuss a lifting procedure for further tightening any generated cut, and establish its polynomial-time operation for unit-coefficient cuts. A numerical example is presented that illustrates these procedures and the relative strength of the generated non-redundant, non-dominated higher-order cuts, all of which turn out to be facet-defining for this example. Some preliminary computational results are also presented to demonstrate the efficacy of these cuts in comparison with lifted minimal cover inequalities for the underlying knapsack polytope.     

Multiple centrality corrections in a primal-dual method for linear programming

A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.Supported by the Fonds National de la Recherche Scientifique Suisse, Grant #12-34002.92.     

Sensitivity analysis framework for variational inequalities

In this paper a sensitivity analysis framework is developed for variational inequalities. The perturbed solution to a parametric variational inequality problem is shown to be continuous and directionally differentiable under appropriate second order and regularity assumptions. Moreover, this solution is once continuously differentiable if strict complementarity also holds.     

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.     

Connectivity-and-hop-constrained design of electricity distribution networks

This paper addresses the problem of designing the configuration of an interconnected electricity distribution network, so as to maximize the minimum power margin over the feeders. In addition to the limitation of feeder power capacity, the distance (as hop count) between any customer and its allocated feeder is also limited for preventing power losses and voltage drops. Feasibility conditions are studied and a complexity analysis is performed before introducing a heuristic algorithm and two integer linear programming formulations for addressing the problem. A cutting-plane algorithm relying on the generation of two classes of cuts for enforcing connectivity and distance requirements respectively is proposed for solving the second integer linear programming formulation. All the approaches are then compared on a set of 190 instances before discussing their performances.