Conical Algorithm in Global Optimization for Optimizing over Efficient Sets

The problem of optimizing some contiuous function over the efficient set of a multiple objective programming problem can be formulated as a nonconvex global optimization problem with special structure. Based on the conical branch and bound algorithm in global optimization, we establish an algorithm for optimizing over efficient sets and discuss about the implementation of this algorithm for some interesting special cases including the case of biobjective programming problems.     

An L-ribbon for large underdetermined linear discrete ill-posed problems

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side vector, which is contaminated by errors of unknown size. However, for large problems, the computation of the L-curve can be quite expensive, because the determination of a point on the L-curve requires that both the norm of the regularized approximate solution and the norm of the corresponding residual vector be available. Recently, an approximation of the L-curve, referred to as the L-ribbon, was introduced to address this difficulty. The present paper discusses how to organize the computation of the L-ribbon when the matrix of the linear system of equations has many more columns than rows. Numerical examples include an application to computerized tomography.     

关于一类半线性退化椭圆方程的存在性结果

本文研究下列半线性退化椭圆Ｄｉｒｉｃｈｌｅｔ问题：这里Ｘ＝｛Ｘ１，…，Ｘｍ｝是一组满足Ｈｏｒｍａｎｄｅｒ条件的实光滑向量场．假设它们在区域的边界附近还满足一些附加条件，以及ｆ∈Ｃ∞〔Ω×Ｒ×Ｒｍ），并且　ｚｆ（ｘ，ｚ，ξ）≥０，ｓｉｇｎＸｆ（ｘ，ｚ，０）≥μ＞－∞，ｃ（ｘ）≥ｃ０＞０和ｆ（ｘ，ｚ，ξ）关于变量ξ满足一定的增长条件．我们证明了当边界是无穷可微时，上述岸线性Ｄｉｒｉｃｈｌｅｔ问题的光滑解的存在性和唯一性．     

Stefan－Signorini问题的均匀化

本文讨论了一维Ｓｔｅｆａｎ－Ｓｉｇｎｏｒｉｎｉ问题的均匀化．利用一个关于未知函数的变换，将原问题转化为一个等价问题，然后利用一些估计和分析技巧对后者进行均匀化．这部分地回答Ｊ．Ｒ．Ｒｏｄｒｉｓｕｅｓ提出的一个问题．     

Numerical methods and asymptotic error expansions for the Emden-Fowler equations

In the present paper we analyse a numerical method for computing the solution of some boundary-value problems for the Emden-Fowler equations. The differential equations are discretized by a finite-difference method and we derive asymptotic expansions for the discretization error. Based on these asymptotic expansions, we use an extrapolation algorithm to accelerate the convergence of the numerical method.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).     

Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming

Many problems faced by decision makers are characterized by a multistage decision process with uncertainty about the future and some decisions constrained to take on values of either zero or one (for example, either open a facility at a location or do not open it). Although some mathematical theory exists concerning such problems, no general-purpose algorithms have been available to address them. In this article, we introduce the first implementation of general purpose methods for finding good solutions to multistage, stochastic mixed-integer (0, 1) programming problems. The solution method makes use of Rockafellar and Wets' progressive hedging algorithm that averages solutions rather than data. Solutions to the induced quadratic (0,1) mixed-integer subproblems are obtained using a tabu search algorithm. We introduce the notion of integer convergence for progressive hedging. Computational experiments verify that the method is effective. The software that we have developed reads standard (SMPS) data files.     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.