First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems

First-order and second-order necessary and sufficient optimality conditions are given for infinite-dimensional programming problems with constraints defined by arbitrary closed convex cones. The necessary conditions are immediate generalizations of those known for the finite-dimensional case. However, this does not hold for the sufficient conditions as illustrated by a counterexample. Here, to go from finite to infinite dimensions, causes an essential change in the proof-techniques and the results. We present modified sufficient conditions of first-order and of second-order which are based on a strengthening of the usual assumptions on the derivative of the objective function and on the second derivative of the Lagrangian.     

求解非线性规划的序列有理规划SRP方法

基于分子、分母皆线性的两点有理逼近，本文对于非线性规划提出了序列有理规划ＳＲＰ方法，按两种情况进行了研究。第一种为ＳＲＰ－Ｌ方法，将原问题化为等效的ＬＰ问题求解；第二种为ＳＲＰ－Ｑ方法，将原问题化为等效的ＱＰ问题求解。本文的工作说明，两点有理逼近函数对于改进优化方法是有益的。     

A strongly polynomial algorithm for the minimum maximum flow degree problem

Let us consider a network flow respecting arc capacities and flow conservation constraints. The flow degree of a node is sum of the flow entering and leaving it. We study the problem of determining a flow that minimizes the maximum flow degree of a node. We show how to solve it in strongly polynomial time with linear programming.     

分式规划模糊投资组合模型的遗传算法求解

将预期收益率表示为模糊数,以E-SV风险测度为基础给出了组合证券投资决策的效用函数,并建立了基于分式规划的模糊投资组合选择模型,考虑到模型求解的复杂性,我们利用遗传算法构造罚函数对模型进行了求解,并通过实例,验证了该模型解法的可行性和有效性.     

On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty

We present a model for optimizing a mean-risk function of the terminal wealth for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. Some logical constraints are considered to be satisfied by the assets portfolio. Uncertainty is represented by a scenario tree and is dealt with by a multistage stochastic mixed 0-1 model with complete recourse. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. A Branch-and-Fix Coordination approach for the multistage 0–1 program solving is proposed. Some computational experience is reported.      

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

SOLUTION OF OPTIMAL TRANSPORTATION PROBLEMS USING A MULTIGRID LINEAR PROGRAMMING APPROACH

We compute and visualize solutions to the Optimal Transportation (OT) problem for a wide class of cost functions. The standard linear programming (LP) discretization of the continuous problem becomes intractable for moderate grid sizes. A grid refinement method results in a linear cost algorithm. Weak convergence of solutions is established and barycentric projection of transference plans is used to improve the accuracy of solutions. Optimal maps between nonconvex domains, partial OT free boundaries, and high accuracy barycenters are presented.     

A modified Gauss-Seidel-algorithm with exclusion of suboptimal actions for A class of semi-Markovian decision problems

In this paper it is shown that a modified Gauss-Seidel-Algorithm with exclusion of suboptimai actions can be used for approximative solving a continuously discounted Semi-Markovian decision problem. Moreover it is proved that the overrelaxation factor of the algorithm introduced in [5] can be improved. If the sojourn times are constant and the overrelaxation factor is independent of states and actions one obtains results of Reetz [6,7] for (discrete) discounted Markovian decision problems. Finally, an example illustrates this method including exclusion of suboptimai actions     

Finite-stage stochastic decision processes with recursive reward structure I: optimality equations and deterministic strategies

In this paper we examine an N-stage stochastic decision model with a recursive reward structure whose state and action spaces are standard Borel ones. The central results relate to the validity of the optimality equations and to the sufficiency of deterministic strategies. The results expand statements known for classical dynamic programming problems with additive total rewards to a wide class of recursive reward functions under certain monotonicity and continuity assumptions. The existence of an expected utility representation of the total rewards is generally not presupposed     

A method for globally minimizing concave functions over convex sets

A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the original function over successively tighter polytopes enclosing the feasible region. The algorithm does not involve cuts of the feasible region, requires only simplex pivot operations and univariate search computations to be performed, allows the objective function to be lower semicontinuous and nonseparable, and is guaranteed to converge to the global solution. Computational aspects of the algorithm are discussed.