求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

NONDESCENT SUBGRADIENT METHOD FOR NONSMOOTH CONSTRAINED MINIMIZATION

A kind of nondecreasing subgradient algorithm with appropriate stopping rule has been proposed for nonsmooth constrained minimization problem. The dual theory is invoked in dealing with the stopping rule and general global minimiizing algorithm is employed as a subroutine of the algorithm. The method is expected to tackle a large class of nonsmooth constrained minimization problem.     

A proximal point algorithm revisit on the alternating direction method of multipliers

The alternating direction method of multipliers(ADMM)is a benchmark for solving convex programming problems with separable objective functions and linear constraints.In the literature it has been illustrated as an application of the proximal point algorithm(PPA)to the dual problem of the model under consideration.This paper shows that ADMM can also be regarded as an application of PPA to the primal model with a customized choice of the proximal parameter.This primal illustration of ADMM is thus complemental to its dual illustration in the literature.This PPA revisit on ADMM from the primal perspective also enables us to recover the generalized ADMM proposed by Eckstein and Bertsekas easily.A worst-case O(1/t)convergence rate in ergodic sense is established for a slight extension of Eckstein and Bertsekas’s generalized ADMM.     

Adaptive Wavelet Solution to the Stokes Problem

This paper deals with the design and analysis of adaptive wavelet method for the Stokes problem. First, the limitation of Richardson iteration is explained and the multiplied matrix M0 in the paper of Bramble and Pasciak is proved to be the simplest possible in an appropiate sense. Similar to the divergence operator, an exact application of its dual is shown; Second, based on these above observations, an adaptive wavelet algorithm for the Stokes problem is designed. Error analysis and computational complexity are given; Finally, since our algorithm is mainly to deal with an elliptic and positive definite operator equation, the last section is devoted to the Galerkin solution of an elliptic and positive definite equation. It turns out that the upper bound for error estimation may be improved.     

Parametric estimation of discretely sampled Gamma-OU processes

The stationary Gamma-OU processes are recommended to be the volatility of the financial assets. A parametric estimation for the Gamma-OU processes based on the discrete observations is considered in this paper. The estimator of an intensity parameter A and its convergence result are given, and the simulations show that the estimation is quite accurate. Assuming that the parameter A is estimated, the maximum likelihood estimation of shape parameter c and scale parameter a, whose likelihood function is not explicitly computable, is considered. By means of the Gaver-Stehfest algorithm, we construct an explicit sequence of approximations to the likelihood function and show that it converges the true (but unkown) one. Maximizing the sequence results in an estimator that converges to the true maximum likelihood estimator and the approximation shares the asymptotic properties of the true maximum likelihood estimator. Some simulation experiments reveal that this method is still quite accurate in most of rational situations for the background of volatility.     

SOURCE TERM IDENTIFICATION WITH DISCONTINUOUS DUAL RECIPROCITY APPROXIMATION AND QUASI-NEWTON METHOD FROM BOUNDARY OBSERVATIONS

This paper deals with discontinuous dual reciprocity boundary element method for solving an inverse source problem.The aim of this work is to determine the source term in elliptic equations for nonhomogenous anisotropic media,where some additional boundary measurements are required.An equivalent formulation to the primary inverse problem is established based on the minimization of a functional cost,where a regularization term is employed to eliminate the oscillations of the noisy data.Moreover,an efficient algorithm is presented and tested for some numerical examples.     

Convergence analysis of a nonlinear Lagrange algorithm for general nonlinear constrained optimization problems

The convergence analysis of a nonlinear Lagrange algorithm for solving nonlinear constrained optimization problems with both inequality and equality constraints is explored in detail. The estimates for the derivatives of the multiplier mapping and the solution mapping of the proposed algorithm are discussed via the technique of the singular value decomposition of matrix. Based on the estimates, the local convergence results and the rate of convergence of the algorithm are presented when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions. Furthermore, the condition number of the Hessian of the nonlinear Lagrange function with respect to the decision variables is analyzed, which is closely related to efficiency of the algorithm. Finally, the preliminary numericM results for several typical test problems are reported.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

THE PRIMAL—DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI—DEFINITE PROGRAMMING

In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.     

ANALYSING FAULT EQUIVALENCE IN LOGIC NETWORKS WITH STATE VARIABLE STAR ALGORITHM

In this paper the State Variable Star Algoritnm(SVSALG) is briefly introduced. The identification of equivalent faults in logic networks is treated with the algorithm.It is shown that SVSALG is an efficient means to analyse fault equivalence. Based on the algorithm, the conception on a particular type of equivalence fault classes, the strongly connectivé equivalence fault class, is presented. The properties of the. equivalence class and its importance for multiple fault analysis are discussed in detail.     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

The convergence of a dual algorithm for nonlinear programming

A dual algorithm based on the smooth function proposed by Polyak (1988) is constructed for solving nonlinear programming problems with inequality constraints. It generates a sequence of points converging locally to a Kuhn-Tucker point by solving an unconstrained minimizer of a smooth potential function with a parameter. We study the relationship between eigenvalues of the Hessian of this smooth potential function and the parameter, which is useful for analyzing the effectiveness of the dual algorithm.     

Alternating direction method of multiplier for the unilateral contact problem with an automatic penalty parameter selection

We propose an alternating direction method of multiplier (ADMM) for the unilateral (frictionless) contact problem with an optimal parameter selection. We first introduce an auxiliary unknown to seprate the linear elasticity subproblem from the unilateral contact condition. Then an alternating direction is applied to the corresponding augmented Lagrangian. By eliminating the primal and auxiliary unknowns, at the discrete level, we derive a pure dual algorithm, starting point for the convergence analysis and the optimal parameter approximation. Numerical experiments are proposed to illustrate the efficiency of the proposed (optimal) penalty parameter selection method.     

A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

求解约束规划的一个非线性Lagrange函数

本文提出了一个求解不等式约束优化问题的非线性Lagrange函数,并构造了基于该函数的对偶算法.证明了当参数σ小于某一阈值σ_0时,由算法生成的原始-对偶点列是局部收敛的,并给出了原始-对偶解的误差估计.此外,建立了基于该函数的对偶理论.最后给出了算法的数值结果.     

On the choice of parameters for power-series interior point algorithms in linear programming

In this paper we study higher-order interior point algorithms, especially power-series algorithms, for solving linear programming problems. Since higher-order differentials are not parameter-invariant, it is important to choose a suitable parameter for a power-series algorithm. We propose a parameter transformation to obtain a good choice of parameter, called ak-parameter, for general truncated powerseries approximations. We give a method to find ak-parameter. This method is applied to two powerseries interior point algorithms, which are built on a primal—dual algorithm and a dual algorithm, respectively. Computational results indicate that these higher-order power-series algorithms accelerate convergence compared to first-order algorithms by reducing the number of iterations. Also they demonstrate the efficiency of thek-parameter transformation to amend an unsuitable parameter in power-series algorithms.Work supported in part by the DFG Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung.     

Geometric Algorithm for Multiparametric Linear Programming

We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems.     

Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization

Active constraint set invariancy sensitivity analysis is concerned with finding the range of parameter variation so that the perturbed problem has still an optimal solution with the same support set that the given optimal solution of the unperturbed problem has. However, in an optimization problem with inequality constraints, active constraint set invariancy sensitivity analysis aims to find the range of parameter variation, where the active constraints in a given optimal solution remains invariant.For the sake of simplicity, we consider the primal problem in standard form and consequently its dual may have an optimal solution with some active constraints. In this paper, the following question is answered: “what is the range of the parameter, where for each parameter value in this range, a dual optimal solution exists with exactly the same set of positive slack variables as for the current dual optimal solution?”. The differences of the results between the linear and convex quadratic optimization problems are highlighted too.     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.