A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.     

Operations risk management by optimally planning the qualified workforce capacity

Operational risks are defined as risks of human origin. Unlike financial risks that can be handled in a financial manner (e.g. insurances, savings, derivatives), the treatment of operational risks calls for a “managerial approach”. Consequently, we propose a new way of dealing with operational risk, which relies on the well known aggregate planning model. To illustrate this idea, we have adapted this model to the case of a back office of a bank specializing in the trading of derivative products. Our contribution corresponds to several improvements applied to stochastic programming techniques. First, the model is transformed into a multistage stochastic program in order to take into account the randomness associated with the volume of transaction demand and with the capacity of work provided by qualified and non-qualified employees over the planning horizon. Second, as advocated by Basel II, we calculate the probability distribution based on a Bayesian Network to circumvent the difficulty of obtaining data which characterizes uncertainty in operations. Third, we go a step further by relaxing the traditional assumption in stochastic programming that imposes a strict independence between the decision variables and the random elements. Comparative results show that in general these improved stochastic programming models tend to allocate more human expertise in order to hedge operational risks. Finally, we employ the dual solutions of the stochastic programs to detect periods and nodes that are at risk in terms of the expertise availability.     

On the parallel version of the successive approximation method for quasilinear boundary value problem

The convergence properties of the successive approximation method to solve a quasilinear two points boundary value problem is studied. The successive approximation method is used to solve the parallel/multiple version of the problem. Conditions which assure the convergence of the method and error bound are given.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

An exterior point method for the convex programming problem

This paper gives a proof of convergence of an iterative method for maximizing a concave function subject to inequality constraints involving convex functions. The linear programming problem is an important special case. The primary feature is that each iteration is very simple computationally, involving only one of the constraints. Although the paper is theoretical in nature, some numerical results are included.The author wishes to express his gratitude to Ms. A. Dunham, who provided a great deal of assistance in carrying out the computations presented in this paper.     

The modified method of refined bounds for polyhedral approximation of convex polytopes

The modified method of refined bounds is proposed and experimentally studied. This method is designed to iteratively approximate convex multidimensional polytopes with a large number of vertices. Approximation is realized by a sequence of convex polytopes with a relatively small but gradually increasing number of vertices. The results of an experimental comparison between the modified and the original methods of refined bounds are presented. The latter was designed for the polyhedral approximation of multidimensional convex compact bodies of general type.     

A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

The initial convergence rate of adaptive methods for polyhedral approximation of convex bodies

The convergence rate at the initial stage is analyzed for a previously proposed class of asymptotically optimal adaptive methods for polyhedral approximation of convex bodies. Based on the results, the initial convergence rate of these methods can be evaluated for arbitrary bodies (including the case of polyhedral approximation of polytopes) and the resources sufficient for achieving optimal asymptotic properties can be estimated.     

A successive approximation method for quantum separability

Determining whether a quantum state is separable or inseparable （entangled） is a problem of fundamental importance in quantum science and has attracted much attention since its first recognition by Einstein, Podolsky and Rosen [Phys. Rev., 1935, 47： 777] and SchrSdinger [Naturwissenschaften, 1935, 23： 807-812, 823-828, 844-849]. In this paper, we propose a successive approximation method （SAM） for this problem, which approximates a given quantum state by a so-called separable state： if the given states is separable, this method finds its rank-one components and the associated weights; otherwise, this method finds the distance between the given state to the set of separable states, which gives information about the degree of entanglement in the system. The key task per iteration is to find a feasible descent direction, which is equivalent to finding the largest M-eigenvalue of a fourth-order tensor. We give a direct method for this problem when the dimension of the tensor is 2 and a heuristic cross-hill method for cases of high dimension. Some numerical results and experiences are presented.     

A general framework for multistage mean-variance post-tax optimization

An investor’s decisions affect the way taxes are paid in a general portfolio investment, modifying the net redemption value and the yearly optimal portfolio distribution. We investigate the role of these decisions on multistage mean-variance portfolio allocation model. A number of risky assets grouped in wrappers with special taxation rules is integrated in a multistage financial portfolio optimization problem. The uncertainty on the returns of assets is specified as a scenario tree generated by simulation/clustering based approach. We show the impact of decisions in the yearly reallocation of the investments for three typical cases with an annual fixed withdrawal in a fixed horizon that utilizes completely the option of taper relief offered by banks in UK. Our computational framework can be used as a tool for testing decisions in this context.     

求解线性矩问题的一个逼近方法

给出一种求解线性矩问题的逼近方法，并给出以B样条函数为基的数值例子，证明了该方法的有效性．     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

On the implementation of a log-barrier progressive hedging method for multistage stochastic programs

A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1-24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

Dual support method for solving convex quadratic programs

In this article, we present a new dual method for solving convex (but not strictly convex) quadratic programs (QPs). Our method is the generalization of the dual support method, developed by Gabasov and co-workers in 1981, for solving convex QPs. It proceeds in two phases: the first is to construct the initial support, called coordinator support, for the problem and the second is to achieve the optimality of the problem. Results of numerical experiments are given comparing our approach with the active-set method.     

A bisection/successive approximation method for computing Gittins indices

An iterative method, combining bisections and successive approximations, is proposed for computing intervals containing the Gittins indices. The intervals could be of a specified maximum length, or be merely disjoint. The first option gives approximations of the Gittins indices. The second option gives a ranking of indices, which in many applications is sufficient.Supported by the Royal Norwegian Council for Industrial and Scientific Research and by the National Science Foundation.     

一类二层凸规划的分解法

研究了一类二层凸规划和与之相应的凸规划问题的等价性．并讨论了这类凸规划的对偶性和鞍点问题,最后给出了求解这类二层凸规划的一个分解法．     

A prolog-based decision support system for computer capacity planning

This paper describes a project to implement a decision support system for computer capacity planning. The system provides an intelligent interface to the various models needed for this type of planning by assisting the user in model formulation, data manipulation, model execution, interpretation and manipulation of results. The implementation strategy is based on the integration of relational model and database management with logic. A modified version of a Prolog interpreter is utilized as the vehicle for this integrated strategy.This research was supported by Sandia National Laboratories Grant No. 56-3737. Sandia is managed by AT&T Technologies for the U.S. Department of Energy.     

A logarithmic barrier cutting plane method for convex programming

The paper presents a logarithmic barrier cutting plane algorithm for convex (possibly non-smooth, semi-infinite) programming. Most cutting plane methods, like that of Kelley, and Cheney and Goldstein, solve a linear approximation (localization) of the problem and then generate an additional cut to remove the linear program's optimal point. Other methods, like the central cutting plane methods of Elzinga-Moore and Goffin-Vial, calculate a center of the linear approximation and then adjust the level of the objective, or separate the current center from the feasible set. In contrast to these existing techniques, we develop a method which does not solve the linear relaxations to optimality, but rather stays in the interior of the feasible set. The iterates follow the central path of a linear relaxation, until the current iterate either leaves the feasible set or is too close to the boundary. When this occurs, a new cut is generated and the algorithm iterates. We use the tools developed by den Hertog, Roos and Terlaky to analyze the effect of adding and deleting constraints in long-step logarithmic barrier methods for linear programming. Finally, implementation issues and computational results are presented. The test problems come from the class of numerically difficult convex geometric and semi-infinite programming problems.This work was completed under the support of a research grant of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.