A Bregman projection method for approximating fixed points of quasi-Bregman nonexpansive mappings

We introduce an abstract algorithm that aims to find the Bregman projection onto a closed convex set. As an application, the asymptotic behavior of an iterative method for finding a fixed point of a quasi-Bregman nonexpansive mapping with the fixed-point closedness property is analyzed. We also show that our result is applicable to Bregman subgradient projectors.     

Subgradient Projectors: Extensions,Theory, and Characterizations

Subgradient projectors play an important role in optimization and for solving convex feasibility problems. For every locally Lipschitz function, we can define a subgradient projector via generalized subgradients even if the function is not convex. The paper consists of three parts. In the first part, we study basic properties of subgradient projectors and give characterizations when a subgradient projector is a cutter, a local cutter, or a quasi-nonexpansive mapping. We present global and local convergence analyses of subgradent projectors. Many examples are provided to illustrate the theory. In the second part, we investigate the relationship between the subgradient projector of a prox-regular function and the subgradient projector of its Moreau envelope. We also characterize when a mapping is the subgradient projector of a convex function. In the third part, we focus on linearity properties of subgradient projectors. We show that, under appropriate conditions, a linear operator is a subgradient projector of a convex function if and only if it is a convex combination of the identity operator and a projection operator onto a subspace. In general, neither a convex combination nor a composition of subgradient projectors of convex functions is a subgradient projector of a convex function.     

A storm of feasibility pumps for nonconvex MINLP

One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed-Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pump algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pump algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pump algorithms is that, unlike most previous successive projection methods from the literature, projection is ??naturally?? taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performance of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm.     

Minibatch stochastic subgradient-based projection algorithms for feasibility problems with convex inequalities

In this paper we consider convex feasibility problems where the feasible set is given as the intersection of a collection of closed convex sets. We assume that each set is specified algebraically as a convex inequality, where the associated convex function is general (possibly non-differentiable). For finding a point satisfying all the convex inequalities we design and analyze random projection algorithms using special subgradient iterations and extrapolated stepsizes. Moreover, the iterate updates are performed based on parallel random observations of several constraint components. For these minibatch stochastic subgradient-based projection methods we prove sublinear convergence results and, under some linear regularity condition for the functional constraints, we prove linear convergence rates. We also derive sufficient conditions under which these rates depend explicitly on the minibatch size. To the best of our knowledge, this work is the first deriving conditions that show theoretically when minibatch stochastic subgradient-based projection updates have a better complexity than their single-sample variants when parallel computing is used to implement the minibatch. Numerical results also show a better performance of our minibatch scheme over its non-minibatch counterpart.

     

Differential evolution with generalized differentials

In this paper, we study the mutation operation of the differential evolution (DE) algorithm. In particular, we propose the differential of scaled vectors, called the ‘generalized differential’, as opposed to the existing scaled differential vector in the mutation of DE. We derive the probability distribution of points generated by the mutation with ‘generalized differentials’. We incorporate a vector-projection-based exploratory method within the new mutation scheme. The vector projection is not mandatory and it is only invoked if trial points continue to be unsuccessful. An algorithm is then proposed which implements the mutation strategy based on the difference of the scaled vectors as well as the vector projection technique. A numerical study is carried out using a set of 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the new algorithm is superior to DE.     

A smoothing homotopy method for variational inequality problems on polyhedral convex sets

In this paper, based on the Robinson’s normal equation and the smoothing projection operator, a smoothing homotopy method is presented for solving variational inequality problems on polyhedral convex sets. We construct a new smoothing projection operator onto the polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with only finite coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, which is a weaker condition than several well-known ones, the existence and global convergence of a smooth homotopy path from almost any starting point in $R^n$ are proven. The global convergence condition of the proposed homotopy method is same with that of the homotopy method based on the equivalent KKT system, but the starting point of the proposed homotopy method is not necessarily an interior point, and the efficiency is more higher. Preliminary test results show that the proposed method is practicable, effective and robust.     

Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs

Probabilistically constrained quadratic programming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation.     

Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications

We address the solution of constrained nonlinear systems by new linesearch quasi-Newton methods. These methods are based on a proper use of the projection map onto the convex constraint set and on a derivative-free and nonmonotone linesearch strategy. The convergence properties of the proposed methods are presented along with a worst-case iteration complexity bound. Several implementations of the proposed scheme are discussed and validated on bound-constrained problems including gas distribution network models. The results reported show that the new methods are very efficient and competitive with an existing affine-scaling procedure.     

A primal-dual subgradient method for time staged capacity expansion planning

We model capacity expansion problems as nondifferentiable convex programs. A dual to this problem is also formulated as a nondifferentiable convex program. The solution methodology we utilize is a primal-dual subgradient approach. Here the primal-dual pair is utilized in step length determination. The special structure of these capacity expansion problems also results in other simplifications. In particular, unlike the application of subgradient optimization for general convex programs, the test for feasibility in certain capacity expansion problems is straightforward. Further, quadratic programs associated with projection operators are also avoided by using the special problem structure. The algorithm is shown to be convergent. In order to illustrate the applicability of our methodology, we discuss its application to a time dynamic power generation capacity planning problem. Computational results with this application is also provided.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

Regularization of ill-posed constrained minimization problems by iteration methods

The ill-posed minimization problems in Hilbert space with quadratic objective function and closed convex constraint set are considered. For the compact set the regularization methods for such problems are well understood [1, 2] The regularizing properties of some Iteration projection methods for noncompact constraint set are the main issues of this paper. We are looking the gradient projection method for the sphere.     

Minimum L1-Distance Projection onto the Boundary of a Convex Set: Simple Characterization

We show that the minimum distance projection in the L ₁-norm from an interior point onto the boundary of a convex set is achieved by a single, unidimensional projection. Application of this characterization when the convex set is a polyhedron leads to either an elementary minmax problem or a set of easily solved linear programs, depending upon whether the polyhedron is given as the intersection of a set of half spaces or as the convex hull of a set of extreme points. The outcome is an easier and more straightforward derivation of the special case results given in a recent paper by Briec (Ref. 1).     

An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results which indicate that by using our strengthened formulations, instances that are considerably larger than have been considered before can be solved to optimality.     

基于修正拟牛顿方程的两阶段非单调稀疏对角变尺度梯度投影算法

基于修正拟牛顿方程,利用Goldstein-Levitin-Polyak(GLP)投影技术,建立了求解带凸集约束的优化问题的两阶段步长非单调变尺度梯度投影算法,证明了算法的全局收敛性和一定条件下的Q超线性收敛速率.数值结果表明新算法是有效的,适合求解大规模问题.     

Conditional subgradient optimization — Theory and applications

We generalize the subgradient optimization method for nondifferentiable convex programming to utilize conditional subgradients. Firstly, we derive the new method and establish its convergence by generalizing convergence results for traditional subgradient optimization. Secondly, we consider a particular choice of conditional subgradients, obtained by projections, which leads to an easily implementable modification of traditional subgradient optimization schemes. To evaluate the subgradient projection method we consider its use in three applications: uncapacitated facility location, two-person zero-sum matrix games, and multicommodity network flows. Computational experiments show that the subgradient projection method performs better than traditional subgradient optimization; in some cases the difference is considerable. These results suggest that our simply modification may improve subgradient optimization schemes significantly. This finding is important as such schemes are very popular, especially in the context of Lagrangean relaxation.     

Applying oracles of on-demand accuracy in two-stage stochastic programming – A computational study

Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the aggregate and the disaggregate version. In this study we report our experiments with a special convex programming method applied to the aggregate master problem. The convex programming method is of the type that uses an oracle with on-demand accuracy. We use a special form which, when applied to two-stage stochastic programming problems, is shown to integrate the advantages of the traditional variants while avoiding their disadvantages. On a set of 105 test problems, we compare and analyze parallel implementations of regularized and unregularized versions of the algorithms. The results indicate that solution times are significantly shortened by applying the concept of on-demand accuracy.     

Extended Lorentz cones and mixed complementarity problems

In this paper we extend the notion of a Lorentz cone in a Euclidean space as follows: we divide the index set corresponding to the coordinates of points in two disjoint classes. By definition a point belongs to an extended Lorentz cone associated with this division, if the coordinates corresponding to one class are at least as large as the norm of the vector formed by the coordinates corresponding to the other class. We call a closed convex set isotone projection set with respect to a pointed closed convex cone if the projection onto the set is isotone (i.e., order preserving) with respect to the partial order defined by the cone. We determine the isotone projection sets with respect to an extended Lorentz cone. In particular, a Cartesian product between an Euclidean space and any closed convex set in another Euclidean space is such a set. We use this property to find solutions of general mixed complementarity problems recursively.     

Reduction of a Minimization Problem of a Separable Convex Function Under Linear Constraints to a Fixed Point Problem

The paper is devoted to studying a constrained nonlinear optimization problem of a special kind. The objective functional of the problem is a separable convex function whose minimum is sought for on a set of linear constraints in the form of equalities. It is proved that, for this type of optimization problems, the explicit form can be obtained of a projection operator based on a generalized projection matrix. The projection operator allows us to represent the initial problem as a fixed point problem. The explicit form of the fixed point problem makes it possible to run a process of simple iteration. We prove the linear convergence of the obtained iterative method and, under rather natural additional conditions, its quadratic convergence. It is shown that an important application of the developed method is the flow assignment in a network of an arbitrary topology with one pair of source and sink.     

约束优化问题的修正共轭梯度投影算法

对闭凸集约束的非线性规划问题构造了一个修正共轭梯度投影下降算法,在去掉迭代点列有界的条件下,分析了算法的全局收敛性.新算法与共轭梯度参数结合,给出了三类结合共轭梯度参数的修正共轭梯度投影算法.数值例子表明算法是有效的.     

A new inertial-type hybrid projection-proximal algorithm for monotone inclusions

This paper investigates an enhanced proximal algorithm with interesting practical features and convergence properties for solving non-smooth convex minimization problems, or approximating zeroes of maximal monotone operators, in Hilbert spaces. The considered algorithm involves a recent inertial-type extrapolation technique, the use of enlargement of operators and also a recently proposed hybrid strategy, which combines inexact computation of the proximal iteration with a projection. Compared to other existing related methods, the resulting algorithm inherits the good convergence properties of the inertial-type extrapolation and the relaxed projection strategy. It also inherits the relative error tolerance of the hybrid proximal-projection method. As a special result, an update of inexact Newton-proximal method is derived and global convergence results are established.