Comparative analysis of affine scaling algorithms based on simplifying assumptions

We analyze several affine potential reduction algorithms for linear programming based on simplifying assumptions. We show that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be with high probability, compared to the guaranteed(1). ( 2n is a parameter in the potential function andn is the number of variables.) Under the same assumption, we further show that the objective reduction rate of Dikin's affine scaling algorithm is with high probability, compared to no guaranteed convergence rate.Research supported in part by NSF Grant DDM-8922636.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

On the validity of the counterpoise correction for the basis set superposition error including the fragment relaxation terms

It is demonstrated that relatively large geometrical changes make Emsley et al.'s assumption (J Am Chem Soc (1978) 100:3303) on the counterpoise correction for the basis set superposition error including the fragment relaxation terms unacceptable. Received: 23 September 1997 / Accepted: 31 October 1997     

基于遗传算法的PTP1B抑制剂的二维定量构效关系研究

利用遗传算法,并结合线性回归和交叉验证方法,对一系列43个苯并呋喃/噻吩联二苯类PTP1B抑制剂作了二维定量构效关系的研究.计算得到了一组效果较好的定量构效关系模型.模型不仅具有好的回归能力,而且还具有很好的预测能力.同时,通过分析在遗传优化过程中参数在精华种群中所占的比例,还得到了可能对活性影响较大的成分.计算结果表明,分子的4个参数:lgP(分配系数)、Area（表面积）、MW（分子量）以及Dip（偶极距）是影响化合物活性的最重要的参数,这对抑制剂的设计和改造提供了指导.     

Decentralized operation strategies for an integrated building energy system using a memetic algorithm

The emerging technology in net-zero building and smart grids drives research moving from centralized operation decisions on a single building to decentralized decisions on a group of buildings, termed a building cluster which shares energy resources locally and globally. However, current research has focused on developing an accurate simulation of single building energy usage which limits its application to building clusters as scenarios such as energy sharing and competition cannot be modeled and studied. We hypothesize that the study of energy usage for a group of buildings instead of one single building will result in a cost effective building system which in turn will be resilient to power disruption. To this end, this paper develops a decision model based on a building cluster simulator with each building modeled by energy consumption, storage and generation sub modules. Assuming each building is interested in minimizing its energy cost, a bi-level operation decision framework based on a memetic algorithm is proposed to study the tradeoff in energy usage among the group of buildings. Two additional metrics, measuring the comfort level and the degree of dependencies on the power grid are introduced for the analysis. The experimental result demonstrates that the proposed framework is capable of deriving the Pareto solutions for the building cluster in a decentralized manner. The Pareto solutions not only enable multiple dimensional tradeoff analysis, but also provide valuable insight for determining pricing mechanisms and power grid capacity.     

A finite volume cell‐centered Lagrangian hydrodynamics approach for solids in general unstructured grids

A finite volume cell‐centered Lagrangian hydrodynamics approach, formulated in Cartesian frame, is presented for solving elasto‐plastic response of solids in general unstructured grids. Because solid materials can sustain significant shear deformation, evolution equations for stress and strain fields are solved in addition to mass, momentum, and energy conservation laws. The total stress is split into deviatoric shear stress and dilatational components. The dilatational response of the material is modeled using the Mie‐Grüneisen equation of state. A predicted trial elastic deviatoric stress state is evolved assuming a pure elastic deformation in accordance with the hypo‐elastic stress‐strain relation. The evolution equations are advanced in time by constructing vertex velocity and corner traction force vectors using multi‐dimensional Riemann solutions erected at mesh vertices. Conservation of momentum and total energy along with the increase in entropy principle are invoked for computing these quantities at the vertices. Final state of deviatoric stress is effected via radial return algorithm based on the J‐2 von Mises yield condition. The scheme presented in this work is second‐order accurate both in space and time. The suitability of the scheme is evinced by solving one‐ and two‐dimensional benchmark problems both in structured grids and in unstructured grids with polygonal cells. Copyright © 2013 John Wiley & Sons, Ltd.     

Reconstruction of n-dimensional convex bodies from surface tensors

In this paper, we derive uniqueness and stability results for surface tensors. Further, we develop two algorithms that reconstruct shape of n-dimensional convex bodies. One algorithm requires knowledge of a finite number of surface tensors, whereas the other algorithm is based on noisy measurements of a finite number of harmonic intrinsic volumes. The derived stability results ensure consistency of the two algorithms. Examples that illustrate the feasibility of the algorithms are presented.