Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

Convexification procedures and decomposition methods for nonconvex optimization problems

In order for primal-dual methods to be applicable to a constrained minimization problem, it is necessary that restrictive convexity conditions are satisfied. In this paper, we consider a procedure by means of which a nonconvex problem is convexified and transformed into one which can be solved with the aid of primal-dual methods. Under this transformation, separability of the type necessary for application of decomposition algorithms is preserved. This feature extends the range of applicability of such algorithms to nonconvex problems. Relations with multiplier methods are explored with the aid of a local version of the notion of a conjugate convex function.This work was carried out at the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, and was supported by the National Science Foundation under Grant ENG 74-19332.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

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

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.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).基于这三种核函数设计了新的求解半正定规划问题的原始对内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming

We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central pathH _P (XS) [PXSP ^–1 + (PXSP ^–1) ^T ]/2 = I, introduced by Zhang. At an iterate (X,S), we choose a scaling matrixP from the class of nonsingular matricesP such thatPXSP ^–1 is symmetric. This class of matrices includes the three well-known choices, namely:P = S ^1/2 andP = X ^–1/2 proposed by Monteiro, and the matrixP corresponding to the Nesterov—Todd direction. We show that within the class of algorithms studied in this paper, the one based on the Nesterov—Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This author's research is supported in part by the National Science Foundation under grants INT-9600343 and CCR-9700448 and the Office of Naval Research under grant N00014-94-1-0340.This author's research was supported in part by DOE DE-FG02-93ER25171-A001.     

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition, if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can be false when the perturbation parameter goes to zero quadratically.      

AnO(\sqrt n L) iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.     

An inexact algorithm for composite nondifferentiable optimization

We describe an inexact version of Fletcher's QL algorithm with second-order corrections for minimizing composite nonsmooth functions. The method is shown to retain the global and local convergence properties of the original version, if the parameters are chosen appropriately. It is shown how the inexact method can be implemented, for the case in which the function to be minimized is an exact penalty function arising from the standard nonlinear programming problem. The method can also be applied to the problems of nonlinearl ₁ - andl -approximation.This research supported in part by the National Science Foundation under Grant DMS-8619903, and by the Air Force Office of Scientific Research under Grant AFOSR-ISSA-870092.     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

Feasible direction method for large-scale nonconvex programs: Decomposition approach

In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by dual decomposition. Results are extended for dynamical problems which include distributed delays and constraints both in state and control variables. The approach is compared with other feasible-direction approaches, and the method is applied to a power generation problem. Some computational results are included.This work was supported by the Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, Brasilia, Brasil, and by the Fundaçao de Amparo a Pesquisa do Estado de Sao Paulo, Sao Paulo, Brazil.On leave from UNICAMP, Campinas, Brazil.     

A trust region algorithm for equality constrained optimization

A trust region algorithm for equality constrained optimization is proposed that employs a differentiable exact penalty function. Under certain conditions global convergence and local superlinear convergence results are proved.     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

A regularized stochastic decomposition algorithm for two-stage stochastic linear programs

In this paper a regularized stochastic decomposition algorithm with master programs of finite size is described for solving two-stage stochastic linear programming problems with recourse. In a deterministic setting cut dropping schemes in decomposition based algorithms have been used routinely. However, when only estimates of the objective function are available such schemes can only be properly justified if convergence results are not sacrificed. It is shown that almost surely every accumulation point in an identified subsequence of iterates produced by the algorithm, which includes a cut dropping scheme, is an optimal solution. The results are obtained by including a quadratic proximal term in the master program. In addition to the cut dropping scheme, other enhancements to the existing methodology are described. These include (i) a new updating rule for the retained cuts and (ii) an adaptive rule to determine when additional reestimation of the cut associated with the current solution is needed. The algorithm is tested on problems from the literature assuming both descrete and continuous random variables.A majority of this work is part of the author's Ph.D. dissertation prepared at the University of Arizona in 1990.     

Asymptotic convergence in a generalized predictor-corrector method

The asymptotic convergence properties of a generalized predictor-corrector method are analyzed. This method is based on making a sequence of corrections to the primal-dual affine scaling (predictor) direction. It is shown that a method makingr corrections to a predictor direction has theQ-order convergence of orderr+2. It is also shown that asymptotically the problem can be solved by only computing corrections to the predictor direction. Supported in part by a grant from the GTE Laboratories and by the grant CCR-9019469 from the National Science Foundation.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

Thevenin decomposition and large-scale optimization

The Thevenin theorem, one of the most celebrated results of electric circuit theory, provides a two-parameter characterization of the behavior of an arbitrarily large circuit, as seen from two of its terminals. We interpret the theorem as a sensitivity result in an associated minimum energy/network flow problem, and we abstract its main idea to develop a decomposition method for convex quadratic programming problems with linear equality constraints, of the type arising in a variety of contexts such as the Newton method, interior point methods, and least squares estimation. Like the Thevenin theorem, our method is particularly useful in problems involving a system consisting of several subssystems, connected to each other with a small number of coupling variables.This research was supported by NSF under Grant CCR-91-03804.     

Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems

In this paper we deal with the study of the polynomial complexity and numerical implementation for a short-step primal-dual interior point algorithm for monotone linear complementarity problems LCP. The analysis is based on a new class of search directions used by the author for convex quadratic programming (CQP) [M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics 25 (1) (2006) 97-110]. Here, we show that this algorithm enjoys the best theoretical polynomial complexity namely , iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems.     

An approximate subgradient algorithm for unconstrained nonsmooth,nonconvex optimization

In this paper a new algorithm for minimizing locally Lipschitz functions is developed. Descent directions in this algorithm are computed by solving a system of linear inequalities. The convergence of the algorithm is proved for quasidifferentiable semismooth functions. We present the results of numerical experiments with both regular and nonregular objective functions. We also compare the proposed algorithm with two different versions of the subgradient method using the results of numerical experiments. These results demonstrate the superiority of the proposed algorithm over the subgradient method.