Solving semidefinite programming problems via alternating direction methods

In this paper, we consider an alternating direction algorithm for the solution of semidefinite programming problems (SDP). The main idea of our algorithm is that we reformulate the complementary conditions in the primal–dual optimality conditions as a projection equation. By using this reformulation, we only need to make one projection and solve a linear system of equation with reduced dimension in each iterate. We prove that the generated sequence converges to the solution of the SDP under weak conditions.     

Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this article an iterative algorithm is studied in connection with an implicit complementarity problem. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by isotone projection cones, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

Smoothing SQP algorithm for semismooth equations with box constraints

In this paper, in order to solve semismooth equations with box constraints, we present a class of smoothing SQP algorithms using the regularized-smooth techniques. The main difference of our algorithm from some related literature is that the correspondent objective function arising from the equation system is not required to be continuously differentiable. Under the appropriate conditions, we prove the global convergence theorem, in other words, any accumulation point of the iteration point sequence generated by the proposed algorithm is a KKT point of the corresponding optimization problem with box constraints. Particularly, if an accumulation point of the iteration sequence is a vertex of box constraints and additionally, its corresponding KKT multipliers satisfy strictly complementary conditions, the gradient projection of the iteration sequence finitely terminates at this vertex. Furthermore, under local error bound conditions which are weaker than BD-regular conditions, we show that the proposed algorithm converges superlinearly. Finally, the promising numerical results demonstrate that the proposed smoothing SQP algorithm is an effective method.     

Finding solutions of implicit complementarity problems by isotonicity of the metric projection

Isac and Németh [G. Isac and A. B. Németh, Projection method, isotone projection cones and the complementarity problem, J. Math. Anal. App., 153, 258-275(1990)] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this paper, the notion of *-isotone projection cones is employed and an iterative algorithm is presented in connection with an implicit complementarity problem on *-isotone projection cones. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by *-isotone projection cones. The question of finding nonzero solutions of these problems is also studied.     

A derivative-free three-term projection algorithm involving spectral quotient for solving nonlinear monotone equations

ABSTRACT

In this paper, we develop a three-term conjugate gradient method involving spectral quotient, which always satisfies the famous Dai-Liao conjugacy condition and quasi-Newton secant equation, independently of any line search. This new three-term conjugate gradient method can be regarded as a variant of the memoryless Broyden-Fletcher-Goldfarb-Shanno quasi-Newton method with regard to spectral quotient. By combining this method with the projection technique proposed by Solodov and Svaiter in 1998, we establish a derivative-free three-term projection algorithm for dealing with large-scale nonlinear monotone system of equations. We prove the global convergence of the algorithm and obtain the R-linear convergence rate under some mild conditions. Numerical results show that our projection algorithm is effective and robust, and is more competitive with the TTDFP algorithm proposed Liu and Li [A three-term derivative-free projection method for nonlinear monotone system of equations. Calcolo. 2016;53:427–450].     

Error analysis of a fully discrete projection method for magnetohydrodynamic system

In this paper, we develop and analyze a finite element projection method for magnetohydrodynamics equations in Lipschitz domain. A fully discrete scheme based on Euler semi-implicit method is proposed, in which continuous elements are used to approximate the Navier–Stokes equations and H ( curl ) conforming Nédélec edge elements are used to approximate the magnetic equation. One key point of the projection method is to be compatible with two different spaces for calculating velocity, which leads one to obtain the pressure by solving a Poisson equation. The results show that the proposed projection scheme meets a discrete energy stability. In addition, with the help of a proper regularity hypothesis for the exact solution, this paper provides a rigorous optimal error analysis of velocity, pressure and magnetic induction. Finally, several numerical examples are performed to demonstrate both accuracy and efficiency of our proposed scheme.     

Visibility of the higher-dimensional central projection into the projective sphere

We can describe higher-dimensional classical spaces by analytical projective geometry, if we embed the d-dimensional real space onto a d + 1-dimensional real projective metric vector space. This method allows an approach to Euclidean, hyperbolic, spherical and other geometries uniformly [8]. To visualize d-dimensional solids, it is customary to make axonometric projection of them. In our opinion the central projection gives more information about these objects, and it contains the axonometric projection as well, if the central figure is an ideal point or an s-dimensional subspace at infinity. We suggest a general method which can project solids into any picture plane (space) from any central figure, complementary to the projection plane (space). Opposite to most of the other algorithms in the literature, our algorithm projects higher-dimensional solids directly into the two-dimensional picture plane (especially into the computer screen), it does not use the three-dimensional space for intermediate step. Our algorithm provides a general, so-called lexicographic visibility criterion in Definition and Theorem 3.4, so it determines an extended visibility of the d-dimensional solids by describing the edge framework of the two-dimensional surface in front of us. In addition we can move the central figure and the image plane of the projection, so we can simulate the moving position of the observer at fixed objects on the computer screen (see first our figures in reverse order). Supported by DAAD 2008 Multimedia Technology for Mathematics and Computer Science Education.     

A Projection Method for the Integer Quadratic Knapsack Problem

In this paper we present a new branch and bound algorithm for solving a class of integer quadratic knapsack problems. A previously published algorithm solves the continuous variable subproblems in the branch and bound tree by performing a binary search over the breakpoints of a piecewise linear equation resulting from the Kuhn-Tucker conditions. Here, we first present modifications to a projection method for solving the continuous subproblems. Then we implement the modified projection method in a branch and bound framework and report computational results indicating that the new branch and bound algorithm is superior to the earlier method.     

Factorization of moving-average spectral densities by state-space representations and stacking

To factorize a spectral density matrix of a vector moving average process, we propose a state space representation. Although this state space is not necessarily of minimal dimension, its associated system matrices are simple and most matrix multiplications involved are nothing but index shifting. This greatly reduces the complexity of computation. Moreover, in this article we stack every q consecutive observations of the original process MA(q) and generate a vector MA(1) process. We consider a similar state space representation for the stacked process. Consequently, the solution hinges on a surprisingly compact discrete algebraic Riccati equation (DARE), which involves only one Toeplitz and one Hankel block matrix composed of autocovariance functions. One solution to this equation is given by the so-called iterative projection algorithm. Each iteration of the stacked version is equivalent to q iterations of the unstacked one. We show that the convergence behavior of the iterative projection algorithm is characterized by the decreasing rate of the partial correlation coefficients for the stacked process. In fact, the calculation of the partial correlation coefficients via the Whittle algorithm, which takes a very simple form in this case, offers another solution to the problem. To achieve computational efficiency, we apply the general Newton procedure given by Lancaster and Rodman to the DARE and obtain an algorithm of quadratic convergence rate. One immediate application of the new algorithms is polynomial stabilization. We also discuss various issues such as check of positivity and numerical implementation.     

A GENERALIZED GRADIENT PROJECTION METHOD FOR OPTIMIZATION PROBLEMS WITH EQUALITY AND INEQUALITY CONSTRAINTS ABOUT ARBITRARY INITIAL POINT

ＧＡＯＺＩＹＯＵ（高自友）（ＮｏｒｔｈｅｒｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００４４，Ｃｈｉｎａ）ＬＡＩＹＡＮＬＩＡＮ（赖炎连）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏ...     

Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

互补约束规划问题的一个广义梯度投影算法

本文研究了一类均衡约束最优化问题.利用广义梯度投影法,结合罚函数思想,得到了一个初始点可以任意的广义梯度投影算法.在较弱的条件下,证明了算法的全局收敛性.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

A smoothing Newton algorithm for weighted linear complementarity problem

In this paper, we present a new smoothing Newton method for solving monotone weighted linear complementarity problem (WCP). Our algorithm needs only to solve one linear system of equation and performs one line search per iteration. Any accumulation point of the iteration sequence generated by our algorithm is a solution of WCP. Under suitable conditions, our algorithm has local quadratic convergence rate. Numerical experiments show the feasibility and efficiency of the algorithm.     

Special conformal groups of a Riemannian manifold and Lie point symmetries of the nonlinear Poisson equation

We obtain a complete group classification of the Lie point symmetries of nonlinear Poisson equations on generic (pseudo) Riemannian manifolds M. Using this result we study their Noether symmetries and establish the respective conservation laws. It is shown that the projection of the Lie point symmetries on M are special subgroups of the conformal group of M. In particular, if the scalar curvature of M vanishes, the projection on M of the Lie point symmetry group of the Poisson equation with critical nonlinearity is the conformal group of the manifold. We illustrate our results by applying them to the Thurston geometries.     

A Constrained Optimization Approach for LCP

In this paper, LCP is converted to an equivalent nonsmooth nonlinear equation system H(x,y) = 0 by using the famous NCP function-Fischer-Burmeister function. Note that some equations in H(x, y) = 0 are nonsmooth and nonlinear hence difficult to solve while the others are linear hence easy to solve. Then we further convert the nonlinear equation system H(x, y) = 0 to an optimization problem with linear equality constraints. After that we study the conditions under which the K-T points of the optimization problem are the solutions of the original LCP and propose a method to solve the optimization problem. In this algorithm, the search direction is obtained by solving a strict convex programming at each iterative point, However, our algorithm is essentially different from traditional SQP method. The global convergence of the method is proved under mild conditions. In addition, we can prove that the algorithm is convergent superlinearly under the conditions: M is P0 matrix and the limit point is a strict complementarity solution of LCP. Preliminary numerical experiments are reported with this method.     

A half-space projection method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method.     

A Direct convolution algorithm for image reconstruction

In image reconstruction algorithms, the choices of filter functions and interpolating functions are very important for the computational speed and the quality of the image reconstructed, especially, for fan-beam geometry, the occurrence of the singular integral operator may lead tosome great oscillations compared to the original image. In this paper we will give a direct convolu-tion algorithm which needs not the complex computations occuring in the Fourier transform, then using a circle integral we obtain a stable computational program. Different from all other previouswindow functions used by many pioneer researchers, in our algorithm we choose a window func tion similar to Gabor‘s window function e-x^2/2 , which can be regarded as the approximation to the inverse Fourier transform of a locally integrable frequency function. Also we point out that such reconstruction algorithm procedures can be used to deal with the SPECT projection data with constant attenuation.     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

Algorithms for vector field generation in mass consistent models

Diagnostic models in meteorology are based on the fulfillment of some time independent physical constraints as, for instance, mass conservation. A successful method to generate an adjusted wind field, based on mass conservation equation, was proposed by Sasaki and leads to the solution of an elliptic problem for the multiplier. Here we study the problem of generating an adjusted wind field from given horizontal initial velocity data, by two ways. The first one is based on orthogonal projection in Hilbert spaces and leads to the same elliptic problem but with natural boundary conditions for the multiplier. We derive from this approach the so called E–algorithm. An innovative alternative proposal is obtained from a second approach where we consider the saddle–point formulation of the problem—avoiding boundary conditions for the multiplier— and solving this problem by iterative conjugate gradient methods. This leads to an algorithm that we call the CG–algorithm, which is inspired from Glowinsk's approach to solve Stokes–like problems in computational fluid dynamics. Finally, the introduction of new boundary conditions for the multiplier in the elliptic problem generates better adjusted fields than those obtained with the original boundary conditions. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010