A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

随机支付型未定权益的风险最小套期保值

讨论了具有随机支付型未定权益的风险最小套期问题.假定市场中存在两类具有不同市场信息的投资者,对于一个预先给定的随机支付流未定权益,利用Galtchouk-Kunita-Watanabe分解和L2空间投影定理证明了风险最小策略的存在性和唯一性,并给出了风险最小策略的构造方法.     

Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions. Received: December 1999 / Accepted: January 2001?Published online March 22, 2001     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

A Log-Barrier method with Benders decomposition for solving two-stage stochastic linear programs

An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time. Received: August 1998 / Accepted: August 2000?Published online April 12, 2001     

Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

Primal and dual convergence of a proximal point exponential penalty method for linear programming

We consider the diagonal inexact proximal point iteration where f(x,r)=c ^T x+r∑exp[(A _i x-b _i )/r] is the exponential penalty approximation of the linear program min{c ^T x:Ax≤b}. We prove that under an appropriate choice of the sequences λ _k , ε _k and with some control on the residual ν ^k , for every r _k →0⁺ the sequence u ^k converges towards an optimal point u ^∞ of the linear program. We also study the convergence of the associated dual sequence μ _i ^k =exp[(A _i u ^k -b _i )/r _k ] towards a dual optimal solution. Received: May 2000 / Accepted: November 2001?Published online June 25, 2002     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Robustness of posynomial geometric programming optima

Received April 2, 1998 / Revised version received July 8, 1998 Published online November 24, 1998     

Approximating quadratic programming with bound and quadratic constraints

Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998     

A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality. Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

Nonlinear programming algorithms using trust regions and augmented Lagrangians with nonmonotone penalty parameters

The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998     

The many facets of linear programming

We examine the history of linear programming from computational, geometric, and complexity points of view, looking at simplex, ellipsoid, interior-point, and other methods. Received: June 22, 2000 / Accepted: April 4, 2001?Published online October 2, 2001     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

On consistency of stochastic dominance and mean–semideviation models

We analyze relations between two methods frequently used for modeling the choice among uncertain outcomes: stochastic dominance and mean–risk approaches. New necessary conditions for stochastic dominance are developed. These conditions compare values of a certain functional, which contains two components: the expected value of a random outcome and a risk term represented by the central semideviation of the corresponding degree. If the weight of the semideviation in the composite objective does not exceed the weight of the expected value, maximization of such a functional yields solutions which are efficient in terms of stochastic dominance. The results are illustrated graphically. Received: September 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

On sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Metric regularity and quantitative stability in stochastic programs with probabilistic constraints

Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998