A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Global Convergence of a Robust Smoothing SQP Method for Semi-Infinite Programming

The semi-infinite programming (SIP) problem is a program with infinitely many constraints. It can be reformulated as a nonsmooth nonlinear programming problem with finite constraints by using an integral function. Due to the nondifferentiability of the integral function, gradient-based algorithms cannot be used to solve this nonsmooth nonlinear programming problem. To overcome this difficulty, we present a robust smoothing sequential quadratic programming (SQP) algorithm for solving the nonsmooth nonlinear programming problem. At each iteration of the algorthm, we need to solve only a quadratic program that is always feasible and solvable. The global convergence of the algorithm is established under mild conditions. Numerical results are given. Communicated by F. Giannessi His work was supported by the Hong Kong Research Grant Council His work was supported by the Australian Research Council.     

解非线性约束方程的拉格朗日全局投影方法

基于最优化方法求解约束非线性方程组的一个突出困难是计算 得到的仅是该优化问题的稳定点或局部极小点,而非方程组的解点.由此引出的问题是如何从一个稳定点出发得到一个相对于方程组解更好的点. 该文采用投影型算法,推广了Nazareth-Qi$^{[8,9]}$ 求解无约束非线性方程组的拉格朗日全局算法(Lagrangian Global-LG)于约束方程上; 理论上证明了从优化问题的稳定点出发,投影LG方法可寻找到一个更好的点. 数值试验证明了LG方法的有效性.     

Nonsmooth equations approach to a constrained minimax problem

An equivalent model of nonsmooth equations for a constrained minimax problem is derived by using a KKT optimality condition. The Newton method is applied to solving this system of nonsmooth equations. To perform the Newton method, the computation of an element of the b-differential for the corresponding function is developed.This work has been supported by Shanghai Education Committee (04EA01).This revised version was published online in April 2005 with a corrected missing date string.     

A Gradient-based Continuous Method for Large-scale Optimization Problems

In this paper, we study a gradient-based continuous method for large-scale optimization problems. By converting the optimization problem into an ODE, we are able to show that the solution trajectory of this ODE tends to the set of stationary points of the original optimization problem. We test our continuous method on large-scale problems available in the literature. The simulation results are very attractive.This research was supported in part by Grants FRG/99-00/II-23 and FRG/00-0l/II-63 of Hong Kong Baptist University and the Research Grant Council of Hong Kong.     

Convexification of Nonsmooth Monotone Functions<Superscript>1</Superscript>

We consider a convexification method for a class of nonsmooth monotone functions. Specifically, we prove that a semismooth monotone function can be converted into a convex function via certain convexification transformations. The results derived in this paper lay a theoretical base to extend the reach of convexification methods in monotone optimization to nonsmooth situations. Communicated by X. Q. Yang This research was partially supported by the National Natural Science Foundation of China under Grants 70671064 and 60473097 and by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E.     

Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

A verified inexact implicit Runge–Kutta method for nonsmooth ODEs

Structural pounding and oscillations have been extensively investigated by using ordinary differential equations (ODEs). In many applications, force functions are defined by piecewise continuously differentiable functions and the ODEs are nonsmooth. Implicit Runge–Kutta (IRK) methods for solving the nonsmooth ODEs are numerically stable, but involve systems of nonsmooth equations that cannot be solved exactly in practice. In this paper, we propose a verified inexact IRK method for nonsmooth ODEs which gives a global error bound for the inexact solution. We use the slanting Newton method to solve the systems of nonsmooth equations, and interval method to compute the set of matrices of slopes for the enclosure of solution of the systems. Numerical experiments show that the algorithm is efficient for verification of solution of systems of nonsmooth equations in the inexact IRK method. We report numerical results of nonsmooth ODEs arising from simulation of the collapse of the Tacoma Narrows suspension bridge, steel to steel impact experiment, and pounding between two adjacent structures in 27 ground motion records for 12 different earthquakes. This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science and a scholarship from Egyptian Government.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.     

An Inexact Newton Method Derived from Efficiency Analysis

We consider solving an unconstrained optimization problem by Newton-PCG like methods in which the preconditioned conjugate gradient method is applied to solve the Newton equations. The main question to be investigated is how efficient Newton-PCG like methods can be from theoretical point of view. An algorithmic model with several parameters is established. Furthermore, a lower bound of the efficiency measure of the algorithmic model is derived as a function of the parameters. By maximizing this lower bound function, the parameters are specified and therefore an implementable algorithm is obtained. The efficiency of the implementable algorithm is compared with Newtons method by theoretical analysis and numerical experiments. The results show that this algorithm is competitive.Mathematics Subject Classification: 90C30, 65K05.This work was supported by the National Science Foundation of China Grant No. 10371131, and Hong Kong Competitive Earmarked Research Grant CityU 1066/00P from Hong Kong University Grant Council     

On the coupling of regularization techniques and the boundary element method for a hemivariational inequality modelling a delamination problem

In this paper, we couple regularization techniques of nondifferentiable optimization with the h‐version of the boundary element method (h‐BEM) to solve nonsmooth variational problems arising in contact mechanics. As a model example, we consider the delamination problem. The variational formulation of this problem leads to a hemivariational inequality with a nonsmooth functional defined on the contact boundary. This problem is first regularized and then discretized by an h‐BEM. We prove convergence of the h‐BEM Galerkin solution of the regularized problem in the energy norm, provide an a priori error estimate and give a numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

Multi-level spectral galerkin method for the navier-stokes problem I : spatial discretization

A multi-level spectral Galerkin method for the two-dimensional non-stationary Navier-Stokes equations is presented. The method proposed here is a multiscale method in which the fully nonlinear Navier-Stokes equations are solved only on a low-dimensional space subsequent approximations are generated on a succession of higher-dimensional spaces j=2, . . . ,J, by solving a linearized Navier-Stokes problem around the solution on the previous level. Error estimates depending on the kinematic viscosity 0<ν<1 are also presented for the J-level spectral Galerkin method. The optimal accuracy is achieved when We demonstrate theoretically that the J-level spectral Galerkin method is much more efficient than the standard one-level spectral Galerkin method on the highest-dimensional space . The work of this author was supported in part by the NSF of China 10371095, City University of Hong Kong Research Project 7001093 Hong Kong and the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 1084/02P)     

Matrix decomposition algorithms for the finite element Galerkin method with piecewise Hermite cubics

Matrix decomposition algorithms (MDAs) employing fast Fourier transforms are developed for the solution of the systems of linear algebraic equations arising when the finite element Galerkin method with piecewise Hermite bicubics is used to solve Poisson’s equation on the unit square. Like their orthogonal spline collocation counterparts, these MDAs, which require O(N ²logN) operations on an N×N uniform partition, are based on knowledge of the solution of a generalized eigenvalue problem associated with the corresponding discretization of a two-point boundary value problem. The eigenvalues and eigenfunctions are determined for various choices of boundary conditions, and numerical results are presented to demonstrate the efficacy of the MDAs. Weiwei Sun was supported in part by a grant from City University of Hong Kong (Project No. CityU 7002110).     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

非线性互补约束均衡问题的一个滤子SQP算法

提出了—个求解非线性互补约束均衡问题的滤子SQP算法.借助Fischer-Burmeister函数把均衡约束转化为—个非光滑方程组,然后利用逐步逼近和分裂思想,给出—个与原问题近似的一般的约束优化.引入滤子思想,避免了罚函数法在选择罚因子上的困难.在适当的条件下证明了算法的全局收敛性,部分的数值结果表明算法是有效的.     

Duality and Penalization in Optimization via an Augmented Lagrangian Function with Applications

This paper aims to establish duality and exact penalization results for the primal problem of minimizing an extended real-valued function in a reflexive Banach space in terms of a valley-at-0 augmented Lagrangian function. It is shown that every weak limit point of a sequence of optimal solutions generated by the valley-at-0 augmented Lagrangian problems is a solution of the original problem. A zero duality gap property and an exact penalization representation between the primal problem and the valley-at-0 augmented Lagrangian dual problem are obtained. These results are then applied to an inequality and equality constrained optimization problem in infinite-dimensional spaces and variational problems in Sobolev spaces, respectively. The first author was supported by the Research Committee of Hong Kong Polytechnic University, by Grant 10571174 from the National Natural Science Foundation of China and Grant 08KJB11009 from the Jiangsu Education Committee of China. The second author was supported by Grant BQ771 from the Research Grants Council of Hong Kong. We are grateful to the referees for useful suggestions which have contributed to the final presentation of the paper.     

The Superconvergence of the Composite Trapezoidal Rule for Hadamard Finite Part Integrals

The composite trapezoidal rule has been well studied and widely applied for numerical integrations and numerical solution of integral equations with smooth or weakly singular kernels. However, this quadrature rule has been less employed for Hadamard finite part integrals due to the fact that its global convergence rate for Hadamard finite part integrals with (p+1)-order singularity is p-order lower than that for the Riemann integrals in general. In this paper, we study the superconvergence of the composite trapezoidal rule for Hadamard finite part integrals with the second-order and the third-order singularity, respectively. We obtain superconvergence estimates at some special points and prove the uniqueness of the superconvergence points. Numerical experiments confirm our theoretical analysis and show that the composite trapezoidal rule is efficient for Hadamard finite part integrals by noting the superconvergence phenomenon. The work of this author was partially supported by the National Natural Science Foundation of China(No.10271019), a grant from the Research Grants Council of the Hong Kong Special Administractive Region, China (Project No. City 102204) and a grant from the Laboratory of Computational Physics The work of this author was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 102204).     

Boundedness and Regularity Properties of Semismooth Reformulations of Variational Inequalities

The Karush-Kuhn-Tucker (KKT) system of the variational inequality problem over a set defined by inequality and equality constraints can be reformulated as a system of semismooth equations via an nonlinear complementarity problem (NCP) function. We give a sufficient condition for boundedness of the level sets of the norm function of this system of semismooth equations when the NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function is the minimum function. Nonsingularity properties identified by Facchinei, Fischer and Kanzow, 1998, SIAM J. Optim. 8, 850–869, for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function, which is an irrational regular pseudo-smooth NCP function, hold for the reformulation based on other regular pseudo-smooth NCP functions. We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent to the minimum NCP function. When it is used to the generalized Newton method for solving the variational inequality problem, an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers only. This work is supported by the Research Grant Council of Hong Kong This paper is dedicated to Alex Rubinov on the occasion of his 65th Birthday     

Z-eigenvalue methods for a global polynomial optimization problem

As a global polynomial optimization problem, the best rank-one approximation to higher order tensors has extensive engineering and statistical applications. Different from traditional optimization solution methods, in this paper, we propose some Z-eigenvalue methods for solving this problem. We first propose a direct Z-eigenvalue method for this problem when the dimension is two. In multidimensional case, by a conventional descent optimization method, we may find a local minimizer of this problem. Then, by using orthogonal transformations, we convert the underlying supersymmetric tensor to a pseudo-canonical form, which has the same E-eigenvalues and some zero entries. Based upon these, we propose a direct orthogonal transformation Z-eigenvalue method for this problem in the case of order three and dimension three. In the case of order three and higher dimension, we propose a heuristic orthogonal transformation Z-eigenvalue method by improving the local minimum with the lower-dimensional Z-eigenvalue methods, and a heuristic cross-hill Z-eigenvalue method by using the two-dimensional Z-eigenvalue method to find more local minimizers. Numerical experiments show that our methods are efficient and promising. This work is supported by the Research Grant Council of Hong Kong and the Natural Science Foundation of China (Grant No. 10771120).     

CALCULATING AN ELEMENT OF B-DIFFERENTIAL FOR A VECTOR-VALUED MAXIMUM FUNCTION*

In this paper, we propose a method of calculating an element of B-differential, also an element of Clarke generalized Jacobian, for a vector-valued maximum function. This calculation is required in many existing numerical methods for the solution of nonsmooth equations and for the nonsmooth optimization. The generalization of our method to a vector-valued smooth composition of maximum functions is also discussed. Particularly, we propose a method of obtaining the set of B-differential for a vector-valued maximum of affine functions.