A Note on the Dual Treatment of Higher-Order Regularization Functionals

In this paper, we apply the dual approach developed by A. Chambolle for the Rudin-Osher-Fatemi model to regularization functionals with higher order derivatives. We emphasize the linear algebra point of view by consequently using matrix-vector notation. Numerical examples demonstrate the differences between various second order regularization approaches.     

An Optimal Algorithm for Bound and Equality Constrained Quadratic Programming Problems with Bounded Spectrum

An implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for solving the large convex bound and equality constrained quadratic programming problems is considered. It is proved that if the algorithm is applied to the class of problems with uniformly bounded spectrum of the Hessian matrix, then the algorithm finds an approximate solution at O(1) matrix-vector multiplications. The optimality results are presented that do not depend on conditioning of the matrix which defines the equality constraints. Theory covers also the problems with dependent constraints. Theoretical results are illustrated by numerical experiments.     

On the Quadratic Convergence of the Levenberg-Marquardt Method without Nonsingularity Assumption

Recently, Yamashita and Fukushima [11] established an interesting quadratic convergence result for the Levenberg-Marquardt method without the nonsingularity assumption. This paper extends the result of Yamashita and Fukushima by using _k=||F(x_k)||, where [1,2], instead of _k=||F(x_k)||² as the Levenberg-Marquardt parameter. If ||F(x)|| provides a local error bound for the system of nonlinear equations F(x)=0, it is shown that the sequence {x_k} generated by the new method converges to a solution quadratically, which is stronger than dist(x_k,X^*)0 given by Yamashita and Fukushima. Numerical results show that the method performs well for singular problems.     

Global Convergence of a Class of Collinear Scaling Algorithms with Inexact Line Searches on Convex Functions

Ariyawansa [2] has presented a class of collinear scaling algorithms for unconstrained minimization. A certain family of algorithms contained in this class may be considered as an extension of quasi-Newton methods with the Broyden family [11] of approximants of the objective function Hessian. Byrd, Nocedal and Yuan [7] have shown that all members except the DFP [11] method of the Broyden convex family of quasi-Newton methods with Armijo [1] and Goldstein [12] line search termination criteria are globally and q-superlinearly convergent on uniformly convex functions. Extension of this result to the above class of collinear scaling algorithms of Ariyawansa [2] has been impossible because line search termination criteria for collinear scaling algorithms were not known until recently. Ariyawansa [4] has recently proposed such line search termination criteria. In this paper, we prove an analogue of the result of Byrd, Nocedal and Yuan [7] for the family of collinear scaling algorithms of Ariyawansa [2] with the line search termination criteria of Ariyawansa [4]. Received: May 8, 1996; revised January 27, 1999     

An exterior simplex type algorithm for the Minimum Cost Network Flow Problem

In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex algorithm. The main idea of the algorithm is to compute two flows. One flow is basic but not always feasible and the other is feasible but not always basic. A complete proof of correctness for the proposed algorithm is also presented. Moreover, the computational behavior of NEPSA is shown by an empirical study carried out for randomly generated sparse instances created by the well-known GRIDGEN network problem generator.     

Variational Methods on the Space of Functions of Bounded Hessian for Convexification and Denoising

In this paper we investigate variational principles on the space of functions of bounded Hessian for denoising, for numerical calculation of convex envelopes and for approximation by convex functions.     

Models for Image Interpolation Based on the Optical Flow

Optical flow is the 2D motion that needs to be recovered from a video sequence. In this paper we study variational principles for the generation of interpolating sequences between two images. The basic assumption is that there exists an underlying video sequence that solves the optic flow equation and interpolates the two images. The numerical solution of the interpolation problem is reduced to the solution of a system of coupled partial differential equations. Some numerical simulations are presented. Received June 29, 2000; revised November 29, 2000     

Validation and enclosure of solutions of linear complementarity problems

An inclusion condition is presented to guarantee the existence of the solution of the linear complementarity problem in a given domain. The condition can be tested numerically with very small computational cost. Based on the condition algorithms are designed to compute an interval to enclose the unknown solution. Numerical results are reported to support the theoretical analysis in the paper.     

Locating repair shops in a stochastic environment

In this paper, we consider a repair shop location problem with uncertainties in demand. New repair shops have to be opened at a number of locations. At these local repair shops, customers arrive with broken, but repairable, items. Customers go to the nearest open repair shop. Since they want to leave as soon as possible, an inventory of working items is kept at the repair shops. A customer immediately receives a working item from stock, provided that the stock is not empty. If a stockout occurs, the customer has to wait for a working item. The broken items are repaired in the shop and then put in stock. Sometimes, however, a broken item cannot be fixed at the local repair shop, and it has to be sent to a central repair shop. At the central repair shop the same policy with inventory and repair is used.     

Polynomial root finding by means of continuation

In this paper we deal with the problem of locating all the zeros of a given polynomialp(x) and approximating them to any degree of precision: by combining classical iterative methods with homotopy path tracking techniques, we introduce a new algorithm for polynomial root finding, prove its convergence and estimate its computational cost.     

Identifying the coefficient of first-order in parabolic equation from final measurement data

This paper studies an inverse problem of recovering the first-order coefficient in parabolic equation when the final observation is given. Such problem has important application in a large field of applied science. The original problem is transformed into an optimal control problem by the optimization theory. The existence, uniqueness and necessary condition of the minimum for the control functional are established. By an elliptic bilateral variational inequality which is deduced from the necessary condition, an algorithm and some numerical experiments are proposed in the paper. The numerical results show that the proposed method is an accurate and stable method to determine the coefficient of first-order in the inverse parabolic problems.     

Numerical optimal control of the wave equation: optimal boundary control of a string to rest in finite time

In many real-life applications of optimal control problems with constraints in form of partial differential equations (PDEs), hyperbolic equations are involved which typically describe transport processes. Since hyperbolic equations usually propagate discontinuities of initial or boundary conditions into the domain on which the solution lives or can develop discontinuities even in the presence of smooth data, problems of this type constitute a severe challenge for both theory and numerics of PDE constrained optimization.     

A Semi-smooth Newton Method for Regularized State-constrained Optimal Control of the Navier-Stokes Equations

In this paper, we study semi-smooth Newton methods for the numerical solution of regularized pointwise state-constrained optimal control problems governed by the Navier-Stokes equations. After deriving an appropriate optimality system for the original problem, a class of Moreau-Yosida regularized problems is introduced and the convergence of their solutions to the original optimal one is proved. For each regularized problem a semi-smooth Newton method is applied and its local superlinear convergence verified. Finally, selected numerical results illustrate the behavior of the method and a comparison between the max-min and the Fischer-Burmeister as complementarity functionals is carried out.     

A New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

Recursive modeling and control of multi-link manipulators with vacuum grippers

Manipulators equipped with vacuum grippers are a new and flexible element in innovative material-flow solutions. The limited holding forces of vacuum grippers require elaborate strategies of control to prevent the contact between gripper and load from breaking off especially in time optimal motion. Mathematically this can be modeled as a constraint on internal forces of a multi-link manipulator. A Maximum Principle based approach is presented for the accurate solution of the control problem. Not only the equations of motion of the manipulator, but the complete optimal control problem is modeled recursively. By this, the structural properties of the control problem are revealed. Direct access becomes possible to all information necessary to restrict internal forces efficiently.     

Approximation algorithms for facility location problems with a special class of subadditive cost functions

In this article we focus on approximation algorithms for facility location problems with subadditive costs. As examples of such problems, we present three facility location problems with stochastic demand and exponential servers, respectively inventory. We present a (1+ε,1)$(1+\epsilon ,1)$-reduction of the facility location problem with subadditive costs to the soft capacitated facility location problem, which implies the existence of a 2(1+ε)$2(1+\epsilon )$-approximation algorithm. For a special subclass of subadditive functions, we obtain a 2-approximation algorithm by reduction to the linear cost facility location problem.     

Denoising of Smooth Images Using L 1-Fitting

In this paper, denoising of smooth (H¹₀-regular) images is considered. The purpose of the paper is basically twofold. First, to compare the denoising methods based on L¹- and L²-fitting. Second, to analyze and realize an active-set method for solving the non-smooth optimization problem arising from the former approach. More precisely, we formulate the algorithm, proof its convergence, and give an efficient numerical realization. Several numerical experiments are presented, where the convergence of the proposed active-set algorithm is studied and the denoising properties of the methods based on L¹- and L²-fitting are compared. Also a heuristic method for determining the regularization parameter is presented and tested.     

Multigrid optimization methods for linear and bilinear elliptic optimal control problems

Summary Multigrid optimization schemes that solve elliptic linear and bilinear optimal control problems are discussed. For the solution of these problems, the multigrid for optimization (MGOPT) method and the collective smoothing multigrid (CSMG) method are developed and compared. It is shown that though these two methods are formally similar, they provide different approaches to computational optimization with partial differential equations.      

换热器热焓控制系统的研究与实现

若换热器出口物料是汽、液混合相,则温度与热焓之间没有单值关系,应采用热焓控制.根据蒸汽加热器的热量衡算式,分析确定蒸汽加热器出口物料的热焓控制方案,讨论基于GE 90-30 PLC的热焓控制系统的硬件配置、主要组态策略,上位机组态软件选用美国GE Fanuc自动化公司的自动化监控软件CIMPLICITY HMI实现热焓调节器组件的组态设计.系统实用表明,该控制方案可保证能量平衡的精确控制,避免能量损耗,实现换热器整体操作的最优化,提高企业经济效益.