A First-Order Stochastic Primal-Dual Algorithm with Correction Step

In this article, we investigate the convergence properties of a stochastic primal-dual splitting algorithm for solving structured monotone inclusions involving the sum of a cocoercive operator and a composite monotone operator. The proposed method is the stochastic extension to monotone inclusions of a proximal method studied in the literature for saddle point problems. It consists in a forward step determined by the stochastic evaluation of the cocoercive operator, a backward step in the dual variables involving the resolvent of the monotone operator, and an additional forward step using the stochastic evaluation of the cocoercive operator introduced in the first step. We prove weak almost sure convergence of the iterates by showing that the primal-dual sequence generated by the method is stochastic quasi-Fejér-monotone with respect to the set of zeros of the considered primal and dual inclusions. Additional results on ergodic convergence in expectation are considered for the special case of saddle point models.     

A primal-dual augmented Lagrangian

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ ₁ linearly constrained Lagrangian (pdℓ ₁LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

A simple proof of a primal affine scaling method

In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF.     

A primal–dual interior point method for nonlinear semidefinite programming

This paper is concerned with a primal–dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal–dual barrier function, a new primal–dual merit function is proposed. We prove the global convergence property of our method. Finally some numerical experiments are given.     

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.     

On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.     

A class of convergent primal-dual subgradient algorithms for decomposable convex programs

In this paper we develop a primal-dual subgradient algorithm for preferably decomposable, generally nondifferentiable, convex programming problems, under usual regularity conditions. The algorithm employs a Lagrangian dual function along with a suitable penalty function which satisfies a specified set of properties, in order to generate a sequence of primal and dual iterates for which some subsequence converges to a pair of primal-dual optimal solutions. Several classical types of penalty functions are shown to satisfy these specified properties. A geometric convergence rate is established for the algorithm under some additional assumptions. This approach has three principal advantages. Firstly, both primal and dual solutions are available which prove to be useful in several contexts. Secondly, the choice of step sizes, which plays an important role in subgradient optimization, is guided more determinably in this method via primal and dual information. Thirdly, typical subgradient algorithms suffer from the lack of an appropriate stopping criterion, and so the quality of the solution obtained after a finite number of steps is usually unknown. In contrast, by using the primal-dual gap, the proposed algorithm possesses a natural stopping criterion.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

Theoretical convergence of large-step primal—dual interior point algorithms for linear programming

This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.Part of the research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contracts N00014-87-C-0820 and N00014-91-C-0026 is acknowledged.     

Analysis of some interior point continuous trajectories for convex programming

In this paper, we analyse three interior point continuous trajectories for convex programming with general linear constraints. The three continuous trajectories are derived from the primal–dual path-following method, the primal–dual affine scaling method and the central path, respectively. Theoretical properties of the three interior point continuous trajectories are fully studied. The optimality and convergence of all three interior point continuous trajectories are obtained for any interior feasible point under some mild conditions. In particular, with proper choice of some parameters, the convergence for all three interior point continuous trajectories does not require the strict complementarity or the analyticity of the objective function. These results are new in the literature.     

An implementation of linear and nonlinear multicommodity network flows

This work presents a new code for solving the multicommodity network flow problem with a linear or nonlinear objective function considering additional linear side constraints that link arcs of the same or different commodities. For the multicommodity network flow problem through primal partitioning the code implements a specialization of Murtagh and Saunders' strategy of dividing the set of variables into basic, nonbasic and superbasic. Several tests are reported, using random problems obtained from different network generators and real problems arising from the fields of long and short-term hydrothermal scheduling of electricity generation and traffic assignment, with sizes of up to 150000 variables and 45 000 constraints The performance of the code developed is compared to that of alternative methodologies for solving the same problems: a general purpose linear and nonlinear constrained optimization code, a specialised linear multicommodity network flow code and a primal-dual interior point code.     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization

This paper proposes a primal-dual interior point method for solving large scale nonlinearly constrained optimization problems. To solve large scale problems, we use a trust region method that uses second derivatives of functions for minimizing the barrier-penalty function instead of line search strategies. Global convergence of the proposed method is proved under suitable assumptions. By carefully controlling parameters in the algorithm, superlinear convergence of the iteration is also proved. A nonmonotone strategy is adopted to avoid the Maratos effect as in the nonmonotone SQP method by Yamashita and Yabe. The method is implemented and tested with a variety of problems given by Hock and Schittkowskis book and by CUTE. The results of our numerical experiment show that the given method is efficient for solving large scale nonlinearly constrained optimization problems.Acknowledgement The authors would like to thank anonymous referees for their valuable comments to improve the paper.     

Local analysis of the feasible primal-dual interior-point method

In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are kept strictly feasible with respect to the inequality constraints. It is shown under the classical conditions that the rate is q-quadratic when the functions associated to the binding inequality constraints are concave. In general, the q-quadratic rate is achieved provided the step in the primal variables does not become asymptotically orthogonal to any of the gradients of the binding inequality constraints.     

THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS

Abstract

In this paper we study the welldefinedness of the central path associated to a nonlinear convex semidefinite programming problem with smooth objective and constraint functions. Under standard assumptions, we prove that the existence of the central path is equivalent to the nonemptiness and boundedness of the optimal set. Other equivalent conditions are given, such as the existence of a strictly dual feasible point or the existence of a single central point. The monotonic behavior of the primal and dual logarithmic barriers and of the primal and dual objective functions along the trajectory is also discussed. The existence and optimality of cluster points is established and finally, under the additional assumption of analyticity of the data functions, the convergence of the primal-dual trajectory is proved.     

非线性等式约束优化问题的仿射信赖域方法

提出非线性等式和有界约束优化问题的结合非单调技术的仿射信赖域方法. 结合信赖域方法和内点回代线搜索技术, 每一步迭代转到由一般信赖域子问题产生的回代步中且满足严格内点可行条件. 在合理的假设条件下, 证明了算法的整体收敛性和局部超线性收敛速率. 最后, 数值结果表明了所提供的算法具有有效性.     

A control reduced primal interior point method for a class of control constrained optimal control problems

A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparatively coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples. Supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin. This paper appeared as ZIB Report 04-38.     

非线性规划的QP-free方法

该文提出一种QP-free可行域方法用来解满足光滑不等式约束的最优化问题.此方法把QP-free方法和3-1线性互补函数相结合一个等价于原约束问题的一阶KKT条件的方程组,并在此基础上给出解这个方程组的迭代算法. 这个方法的每一步迭代都可以看作是对求KKT条件解的牛顿或拟牛顿迭代的扰动,且在该方法中每一步的迭代均具有可行性. 该方法是可实行的且具有全局性, 且不需要严格互补条件、聚点的孤立性和积极约束函数梯度的线性独立等假设. 在与文献[2]中相同的适当条件下,此方法还具有超线性收敛性. 数值检验结果表示,该文提出的QP-free可行域方法是切实有效的方法.     

The empirical performance of a polynomial algorithm for constrained nonlinear optimization

In [6], a polynomial algorithm based on successive piecewise linear approximation was described. The algorithm is polynomial for constrained nonlinear (convex or concave) optimization, when the constraint matrix has a polynomial size subdeterminant. We propose here a practical adaptation of that algorithm with the idea of successive piecewise linear approximation of the objective on refined grids, and the testing of the gap between lower and upper bounds. The implementation uses the primal affine interior point method at each approximation step. We develop special features to speed up each step and to evaluate the gap. Empirical study of problems of size up to 198 variables and 99 constraints indicates that the procedure is very efficient and all problems tested were terminated after 171 interior point iterations. The procedure used in the implementation is proved to converge when the objective is strongly convex.Supported in part by the Office of Naval Research under Grant No. N00014-88-K-0377 and Grant No. ONR N00014-91-J-1241.