A primal projective interior point method for linear programming

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

A primal interior point method for the linear semidefinite programming problem

The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved.     

Theoretical convergence of large-step primal—dual interior point algorithms for linear programming

This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.Part of the research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contracts N00014-87-C-0820 and N00014-91-C-0026 is acknowledged.     

Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming

We introduce and study two-stage stochastic symmetric programs with recourse to handle uncertainty in data defining (deterministic) symmetric programs in which a linear function is minimized over the intersection of an affine set and a symmetric cone. We present a Benders’ decomposition-based interior point algorithm for solving these problems and prove its polynomial complexity. Our convergence analysis proved by showing that the log barrier associated with the recourse function of stochastic symmetric programs behaves a strongly self-concordant barrier and forms a self-concordant family on the first stage solutions. Since our analysis applies to all symmetric cones, this algorithm extends Zhao’s results [G. Zhao, A log barrier method with Benders’ decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001) 507–536] for two-stage stochastic linear programs, and Mehrotra and Özevin’s results [S. Mehrotra, M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (1) (2007) 206–222] for two-stage stochastic semidefinite programs.     

An O(n 3 L) primal interior point algorithm for convex quadratic programming

We present a primal interior point method for convex quadratic programming which is based upon a logarithmic barrier function approach. This approach generates a sequence of problems, each of which is approximately solved by taking a single Newton step. It is shown that the method requires iterations and O(n ^3.5 L) arithmetic operations. By using modified Newton steps the number of arithmetic operations required by the algorithm can be reduced to O(n ³ L).This research was supported in part by NSF Grant DMS-85-12277 and ONR Contract N-00014-87-K0214. It was presented at the Meeting on Mathematische Optimierung, Mathematisches Forschungsinstitut, Oberwolfach, West Germany, January 3–9, 1988.     

Stability of multistage stochastic programming

In this paper, we study the stability of multistage stochastic programming with recourse in a way that is different from that used in studying stability of two-stage stochastic programs. Here, we transform the multistage programs into mathematical programs in the space ⁿ ×L _p with a simple objective function and multistage stochastic constraints. By investigating the continuity of the multistage multifunction defined by the multistage stochastic constraints and applying epi-convergence theory we obtain stability results for linear and linear-quadratic multistage stochastic programs.Project supported by the National Natural Science Foundation of China.     

Partially observable multistage stochastic programming

We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the stochastic dual dynamic programming method.     

Stability in multistage stochastic programming

Multistage stochastic programs are regarded as mathematical programs in a Banach spaceX of summable functions. Relying on a result for parametric programs in Banach spaces, the paper presents conditions under which linearly constrained convex multistage problems behave stably when the (input) data process is subjected to (small) perturbations. In particular, we show the persistence of optimal solutions, the local Lipschitz continuity of the optimal value and the upper semicontinuity of optimal sets with respect to the weak topology inX. The linear case with deterministic first-stage decisions is studied in more detail.This research has been supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

Test problems in stochastic multistage programming

This paper provides a set of stochastic multistage programs where the evolvement of uncertain factors is given by stochastic processes. We treat a practical problem statement within the field of managing fixed-income securities. Detailed information on the used parameter values in various interest rate models is given. Barycentric approximation is applied to obtain computational results; different measures of the achieved goodness of approximation are indicated     

An interior point method for nonlinear programming

Summary In this paper an interior point method is presented for nonlinear programming problems with inequality constraints. On defining a modified distance function the original problem is solved sequentially by using a method of feasible directions. At each iteration a usable feasible direction can be determined explicitly. Under certain assumptions it can be shown that every accumulation point of the sequence of points constructed by the proposed algorithm satisfies the Kuhn-Tucker conditions.

---

Zusammenfassung Im vorliegenden Beitrag wird eine Innere-Punkt-Methode zur Lösung nichtlinearer Optimierungsprobleme mit Ungleichungsrestriktionen vorgestellt. Mit dem Begriff der modifizierten Distanzfunktion und mit Hilfe einer Methode der zulässigen Richtungen wird das ursprüngliche Problem sequentiell gelöst. Bei jeder Iteration kann eine brauchbare zulässige Richtung explizit angegeben werden. Unter geeigneten Voraussetzungen wird gezeigt, daß jeder Häufungspunkt der Folgenpunkte, die durch den dargestellten Algorithmus konstruiert werden, die Kuhn-Tucker-Bedingungen erfüllt.

     

A multistage linear stochastic programming model for optimal corporate debt management

Large corporations fund their capital and operational expenses by issuing bonds with a variety of indexations, denominations, maturities and amortization schedules. We propose a multistage linear stochastic programming model that optimizes bond issuance by minimizing the mean funding cost while keeping leverage under control and insolvency risk at an acceptable level. The funding requirements are determined by a fixed investment schedule with uncertain cash flows. Candidate bonds are described in a detailed and realistic manner. A specific scenario tree structure guarantees computational tractability even for long horizon problems. Based on a simplified example, we present a sensitivity analysis of the first stage solution and the stochastic efficient frontier of the mean-risk trade-off. A realistic exercise stresses the importance of controlling leverage. Based on the proposed model, a financial planning tool has been implemented and deployed for Brazilian oil company Petrobras.     

A globally convergent interior point algorithm for non-convex nonlinear programming

In this paper, a new algorithm for tracing the combined homotopy path of the non-convex nonlinear programming problem is proposed. The algorithm is based on the techniques of β$\beta$-cone neighborhood and a combined homotopy interior point method. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the β$\beta$-cone neighborhood to be included in the interior part of the feasible region. The global convergence and polynomial complexity are established under some hypotheses.     

A unified view of interior point methods for linear programming

The paper shows how various interior point methods for linear programming may all be derived from logarithmic barrier methods. These methods include primal and dual projective methods, affine methods, and methods based on the method of centers. In particular, the paper demonstrates that Karmarkar's algorithm is equivalent to a classical logarithmic barrier method applied to a problem in standard form.Invited paper presented at the Workshop on Supercomputers in Optimization, Minneapolis, Minn., May 1988.The work of this author was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USA, under Grants AFOSR-87-0215 and AFOSR-85-0271. The US Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright notation thereon.     

A primal-dual interior point method for parametric semidefinite programming problems

1.IntroductionSemidefiniteprogrammingunifiesquiteanumberofstandardmathematicalprogrammingproblems,suchaslinearprogrammingproblems,quadraticminimizationproblemswithconvexquadraticconstraints.Italsofindsmanyapplicationsinengineering,control,andcombinatorialoptimization[l,2].Inthepastfewyears,aquitenumberofresearchworkbasedoninteriorpointmethodsgaveattentiontoparametricsemidefiniteprogrammingproblems[3,4]fwherediscussionsaremostlyrelatedtopostoptimalandparametricanalysis.Inthispapergwefocusoureff…     

Inference of statistical bounds for multistage stochastic programming problems

We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal (minimum) value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. We also indicate that fixing a feasible first-stage solution and then solving the sampling approximation of the corresponding (T–1)-stage problem, does not give a valid statistical upper bound for the optimal value of the true problem.Supported, in part, by the National Science Foundation under grant DMS-0073770.     

Parallel decomposition of multistage stochastic programming problems

A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.     

Minimax and risk averse multistage stochastic programming

In this paper we study relations between the minimax, risk averse and nested formulations of multistage stochastic programming problems. In particular, we discuss conditions for time consistency of such formulations of stochastic problems. We also describe a connection between law invariant coherent risk measures and the corresponding sets of probability measures in their dual representation. Finally, we discuss a minimax approach with moment constraints to the classical inventory model.