Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

Confined buckling of inextensible rods by convex difference algorithms

In this Note we present an approach to determine the local minima of a specific class of minimization problems. Attention is focused on the inextensibility condition of flexible rods expressed as a nonconvex constraint. Two algorithms are derived from a special splitting of the Lagrangian into the difference of two convex functions (DC). They are compared to the augmented Lagrangian methods used in this context. These DC formulations are easily extended to contact problems and applied to the determination of confined buckling shapes. To cite this article: P. Alart, S. Pagano, C. R. Mecanique 330 (2002) 819–824.     

k-均值问题的差分隐私算法综述

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息,同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。     

一种基于等距线的碰撞检测算法

碰撞检测是虚拟现实场景模拟中的关键技术之一.文中试图在投影包围盒交集内通过判断等距线与投影线交点个数及位置的方法来构建一种高效优化的碰撞检测算法.该算法在适应虚拟环境的实时性要求的同时,减少了误判的产生.     

The Double Self-Dual Gravity with Cosmological Term and Constraints Under the Double Constant Conformal Transformation

The double constraint equations in the self-dual gravitational theory containing the cosmological term are derived in 3 + 1 gravity. Furthermore, in order to deeply study the Lorentzian and Euclidean reality conditions for this theory, the relations between constraints are discussed by introducing the double constant conformal transformation and the double complex function method.     

Null Space Algorithm and Spanning Trees in Solving Darcy's Equation

A Null Space algorithm is considered to solve the augmented system produced by the mixed finite element approximation of Darcy's Law. The method is based on the combination of a LU factorization technique for sparse matrices with an iterative Krylov solver. The computational efficiency of the method relies on the use of spanning trees to compute the LU factorization without fill-in and on a suitable stopping criterion for the iterative solver. We experimentally investigate its performance on a realistic set of selected application problems.This revised version was published online in October 2005 with corrections to the Cover Date.     

Models for Architectural Power and Power Grid Noise Analysis on Data Bus

The transition activity on a data bus is a time series that determines power consumption on this data bus. The average values of power consumption and power grid voltage drop are proportional to average value of transition activity, i.e., transition probability. The fluctuation of power grid voltage drop appears as noise on power grid and its strength is determined by the second order statistics of transition activity, i.e., variance, auto-correlation function or power spectrum. In this paper, for the first time, simple accurate models for estimating variance and power spectrum of transition activity are proposed. The proposed models are based on linearly modeling spatial-time correlation of bit-level transition activity and result in low computational complexity but very good estimation accuracy. In addition, the dual bit type (DBT) [1, 2] model for estimating average transition activity was further developed. The previous DBT model was made complete with the equation derived in this paper for computing transition probability beyond breakpoint BP ₁. Besides DSP computational architecture and algorithm designs, the proposed simple models are of great significance for power grid noise decoupling and chip floor-planning. Lijun Gao (S’99–M’01) received B.E. and M.E. degrees in Communication & Electronic Systems from Tsinghua University, Beijing, China, in 1986 and 1988, respectively. He received his PhD degree in Elecrical & Computer Engineering from University of Minnesota, Minneapolis, USA, in 2001. He is also an MS degree candidate in Computer & Information Science at University of Minnesota, Minneapolis. Dr. Gao is currently with Medtronic Inc., Minneapolis, MN, and working on DSP design for pacemaker. From 2001 to 2003, he was with Bermai Inc., Minnetonka, MN and working on the design of wireless LAN (802.11a/11b) chipsets. In 2001, he worked in the R & D division of GlobeSpan Semiconductor Inc., Red Bank, NJ. From 1988 to 1991, he was a faculty member with Tsinghua University, Beijing, China. From 1991 to 1996, he was a R & D engineer with the Institute of Software, Chinese Academy of Science, Beijing, China. For the period of 1991 to 1993, he was a visiting R & D engineer at Onflo Computer Co. Hong Kong. Dr. Gao received the Science & Technology awards from the National Education Council, China, in 1994 for his contribution to radar signal processing while he was at Tsinghua University, and from the ministry of Electronic Industry, China, in 1995 for his contribution to the CJK Ideograph Unification in ISO 10646 (Unicode). His current reserach interest includes the algorithm/architecture/ circuit for VLSI design, the computational aspects of digital signal processing (DSP) and programmable DSP processor. Specifically, his focus is on the deep-submicron VLSI design, power estimation/low power design, computer arithmetic, finite field arithmetic, error control coding, cryptography, adaptive filters, equalization, beamformer, special-purpose processors and FPGA/reconfigurable computing. Keshab K. Parhi (S’85-M’88–SM’91-F’96) Keshab K. Parhi received his B.Tech., MSEE, and Ph.D. degrees from the Indian Institute of Technology, Kharagpur, the University of Pennsylvania, Philadelphia, and the University of California at Berkeley, in 1982, 1984, and 1988, respectively. He has been with the University of Minnesota, Minneapolis, since 1988, where he is currently Distinguished McKnight University Professor in the Department of Electrical and Computer Engineering. His research addresses VLSI architecture design and implementation of physical layer aspects of broadband communications systems. He is currently working on error control coders and cryptography architectures, high-speed transceivers, ultra wideband systems, quantum error control coders and quantum cryptography. He has published over 350 papers, has authored the text book VLSI Digital Signal Processing Systems (Wiley, 1999) and coedited the reference book Digital Signal Processing for Multimedia Systems (Marcel Dekker, 1999). Dr. Parhi is the recipient of numerous awards including the 2004 F.E. Terman award by the American Society of Engineering Education, the 2003 IEEE Kiyo Tomiyasu Technical Field Award, the 2001 IEEE W.R.G. Baker prize paper award, and a Golden Jubilee award from the IEEE Circuits and Systems Society in 1999. He has served on the editorial boards of the IEEE TRANSACTIONS ON CAS, CAS-II, VLSI Systems, Signal Processing, Signal Processing Letters, and currently serves on editorial board of the IEEE Signal Processing Magazine, and is the curent Editor-in-Chief of the IEEE Trans. on Circuits and Systems–I (2004–2005 term). He has served as technical program cochair of the 1995 IEEE VLSI Signal Processing workshop and the 1996 ASAP conference, and as the general chair of the 2002 IEEE Workshop on Signal Processing Systems. He was a distinguished lecturer for the IEEE Circuits and Systems society during 1996–1998. He currently serves on the Board of Governors of the IEEE Circuits and Systems Society. He was elected a Fellow of IEEE in 1996.     

A new augmented penalty function technique for optimal control problems

This note presents an extension of the Miele—Cragg-Iyer-Levy augmented function method for finite-dimensional optimization problems to optimal control problems. A numerical study is provided.     

Pseudo-duality and saddle points

Results associated with saddle-type stationary points are described. It is shown that barrier-type functions are pseudo-duals of generalized Lagrangian functions, while augmented Lagrangians are pseudo-duals of the regular Lagrangian function. An application of pseudo-duality to a min-max problem is illustrated, together with several other examples.