Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces

Computational Optimization and Applications - We develop a globalized Proximal Newton method for composite and possibly non-convex minimization problems in Hilbert spaces. Additionally, we impose...     

A descent algorithm for solving monotone variational inequalities and monotone complementarity problems

The paper provides a descent algorithm for solving certain monotone variational inequalities and shows how this algorithm may be used for solving certain monotone complementarity problems. Convergence is proved under natural monotonicity and smoothness conditions; neither symmetry nor strict monotonicity is required.The author is grateful to two anonymous referees for their very valuable comments on an earlier draft of this paper.     

一个新的求解半正定规划问题的原始对偶内点算法

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.Bai等针对线性规划提出三种核函数,并给出求解线性规划的大步迭代复杂界,但未给出数值算例验证算法的实际效果(Bai Y Q,Xie W,Zhang J.New parameterized kernel functions for linear optimization.J Global Optim,2012.DOI 10.1007/s10898-012-9934-z).基于这三种核函数设计了新的求解半正定规划问题的原始对内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.     

A smoothing Newton algorithm for solving the monotone second-order cone complementarity problems

In this paper, a new smoothing function is given by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this function, a smoothing Newton algorithm is proposed for solving the monotone second-order cone complementarity problems. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Numerical results indicate that the proposed algorithm is effective.     

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.     

An improved SQP algorithm for solving minimax problems

In this work, an improved SQP method is proposed for solving minimax problems, and a new method with small computational cost is proposed to avoid the Maratos effect. In addition, its global and superlinear convergence are obtained under some suitable conditions.     

An algorithm for solving linearly constrained optimization problems

An algorithm for minimization of functions of many variables, subject possibly to linear constraints on the variables, is described. In it a subproblem is solved in which a quadratic approximation is made to the object function and minimized over a region in which the approximation is valid. A strategy for deciding when this region should be expanded or contracted is given. The quadratic approximation involves estimating the hessian of the object function by a matrix which is updated at each iteration by a formula recently reported by Powell [6]. This formula enables convergence of the algorithm from any feasible point to be proved. Use of such an approximation, as against using exact second derivatives, also enables a reduction of about 60% to be made in the number of operations to solve the subproblem. Numerical evidence is reported showing that the algorithm is efficient in the number of function evaluations required to solve well known test problems.This paper was presented at the 7th International Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

A quadratically convergent primal-dual algorithm with global convergence properties for solving optimization problems with equality constraints

This paper presents a globally convergent multiplier method which utilizes an explicit formula for the multiplier. The algorithm solves finite dimensional optimization problems with equality constraints. A unique feature of the algorithm is that it automatically calculates a value for the penalty coefficient, which, under certain assumptions, leads to global convergence.Research sponsored by the Joint Services Electronics Program, Contract F44620-71-C-0087 and the National Science Foundation, Grant GK-37672.     

Iterative splitting methods for solving time-dependent problems

There is increasing motivation for solving time-dependent differential equations with iterative splitting schemes. While Magnus expansion has been intensively studied and widely applied for solving explicitly time-dependent problems, the combination with iterative splitting schemes can open up new areas. The main problems with the Magnus expansion are the exponential character and the difficulty of deriving practical higher order algorithms. An alternative method is based on iterative splitting methods that take into account a temporally inhomogeneous equation. In this work, we show that the ideas derived from the iterative splitting methods can be used to solve time-dependent problems. Examples are discussed.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

An adaptive membrane algorithm for solving combinatorial optimization problems

Membrane algorithms (MAs), which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The empirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural network and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.     

An efficient algorithm for solving fifth-order boundary value problems

In this paper, we apply the homotopy perturbation method for solving the fifth-order boundary value problems. The analytical results of the equations have been obtained in terms of convergent series with easily computable components. Several examples are given to illustrate the efficiency and implementation of the homotopy perturbation method. Comparisons are made to confirm the reliability of the method.     

A splitting algorithm for dual monotone inclusions involving cocoercive operators

We consider the problem of solving dual monotone inclusions involving sums of composite parallel-sum type operators. A feature of this work is to exploit explicitly the properties of the cocoercive operators appearing in the model. Several splitting algorithms recently proposed in the literature are recovered as special cases.     

An inertial subgradient-type method for solving single-valued variational inequalities and fixed point problems

In this paper, we introduce an inertial subgradient-type algorithm to find the common element of fixed point set of a family of nonexpansive mappings and the solution set of the single-valued variational inequality problem. Under the assumption that the mapping is monotone and Lipschitz continuous, we show that the sequence generated by our algorithm converges strongly to some common element of the fixed set and the solution set. Moreover, preliminary numerical experiments are also reported.     

A splitting algorithm for finding fixed points of nonexpansive mappings and solving equilibrium problems

We consider the problem of finding a fixed point of a nonexpansive mapping, which is also a solution of a pseudo-monotone equilibrium problem, where the bifunction in the equilibrium problem is the sum of two ones. We propose a splitting algorithm combining the gradient method for equilibrium problem and the Mann iteration scheme for fixed points of nonexpansive mappings. At each iteration of the algorithm, two strongly convex subprograms are required to solve separately, one for each of the component bifunctions. Our main result states that, under paramonotonicity property of the given bifunction, the algorithm converges to a solution without any Lipschitz-type condition as well as Hölder continuity of the bifunctions involved.     

An algorithm for solving global optimization problems with nonlinear constraints

In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.     

An adaptive algorithm for solving stochastic multi-point boundary value problems

In this paper, we present an adaptive multiple-shooting method to solve stochastic multi-point boundary value problems. We first analyze the strong order of convergence of the underlying multiple shooting method. We then proceed to describe the proposed strategy to adaptively choose the location of shooting points. We analyze the effect of method parameters on the performance of the overall scheme using a benchmark linear two-point stochastic boundary value problem. We illustrate the effectiveness of this approach on several (one and two dimensional) test problems by comparing our results with other non-adaptive alternative techniques proposed in the literature.     

Two algorithms for solving systems of inclusion problems

The goal of this paper is to present two algorithms for solving systems of inclusion problems, with all components of the systems being a sum of two maximal monotone operators. The algorithms are variants of the forward-backward splitting method and one being a hybrid with the alternating projection method. They consist of approximating the solution sets involved in the problem by separating half-spaces which is a well-studied strategy. The schemes contain two parts, the first one is an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. The second part is the projection step, this being the main difference between the algorithms. While the first algorithm computes the projection onto the intersection of the separating half-spaces, the second chooses one component of the system and projects onto the separating half-space of this case. In the iterative process, the forward-backward operator is computed once per inclusion problem, representing a relevant computational saving if compared with similar algorithms in the literature. The convergence analysis of the proposed methods is given assuming monotonicity of all operators, without Lipschitz continuity assumption. We also present some numerical experiments.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

A primal-dual interior-point algorithm for nonlinear least squares constrained problems

This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty parameter that ensures descent directions along the iterative process. Computational results are included for a variety of least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient in practice.