First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

Average number of iterations of some polynomial interior-point ——Algorithms for linear programming

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above byO(n ^1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

A path to the Arrow–Debreu competitive market equilibrium

We present polynomial-time interior-point algorithms for solving the Fisher and Arrow–Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic operation complexity bound of )) for computing an -equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O(n ⁴ L) which is in line with the best complexity bound for linear programming of the same dimension and size. This is a significant improvement over the previously best bound )) for approximating the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations, efficient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the Arrow–Debreu equilibrium, similar to the central path developed for linear programming interior-point methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixed-point theorem. The defining equations are bilinear and possess some primal-dual structure for the application of the Newton-based path-following method. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday. This author was supported in part by NSF Grants DMS-0306611 and DMS-0604513. The author would like to thank Curtis Eaves, Osman Güler, Kamal Jain and Mike Todd for insightful discussions on this subject, especially on their mathematical references and economic interpretations of the fixed-point model presented in this paper.     

Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results

 In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems. Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002 RID="⋆" ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan. Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05     

Combining search directions using gradient flows

 The efficient combination of directions is a significant problem in line search methods that either use negative curvature, or wish to include additional information such as the gradient or different approximations to the Newton direction. In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm. Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction of negative curvature, if it exists. We also show that the procedure is well-defined, and it has reasonable theoretical properties regarding the rate of convergence of the method. We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the CUTE collection. Received: November 2000 / Accepted: October 2002 Published online: February 14, 2003 Key Words. negative curvature – primal-dual methods – interior-point methods – nonconvex optimization – line searches Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹ (0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion. Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003 Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Quick Max-flow Algorithm

Determining of a maximal network flow is a classic problem in discrete optimization with many applications. In this paper, a new algorithm based on the Dinic’s method is presented. Algorithms of the Dinic’s method work evidently faster than theoretical bounds for a randomized network. This paper presents a parameterized and easy to implement family of algorithms of finding a saturating flow in a layered network. Although their common complexity is poor O(V ² L) where L is the number of layers, three particular members are proved to be O(V ²). Furthermore, there is a particularly interesting “balanced” member of the family for which a calculated upper bound on complexity is still O(V ² L) but there is known no example of a layered network that needs more than O(E + V ^(3/2)) time to resolve. All the considered members work really quickly for randomized examples of a layered network. Starting from the above family, three algorithms which find maximal flow in a network in O(V ³) worst case time have been constructed, while the respective “balanced” algorithm is theoretically O(V ⁴). All the algorithms do not extend O(V ²) time in experimental, i.e. randomized, cases.      

A simple GAP-canceling algorithm for the generalized maximum flow problem

We give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (GAPs). We use ideas of Wallacher (A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms, 1991) to find GAPs that have a good trade-off between the gain of the GAP and the residual capacity of its arcs; our algorithm may be viewed as a special case of Wayne’s algorithm for the generalized minimum-cost circulation problem (Wayne in Math Oper Res 27:445–459, 2002). Most previous algorithms for the generalized maximum flow problem are dual-based; the few previous primal algorithms (including Wayne in Math Oper Res 27:445–459, 2002) require subroutines to test the feasibility of linear programs with two variables per inequality (TVPIs). We give an O(mn) time algorithm for finding negative-cost GAPs which can be used in place of the TVPI tester. This yields an algorithm with O(m log(mB/ε)) iterations of O(mn) time to compute an ε-optimal flow, or O(m ² log (mB)) iterations to compute an optimal flow, for an overall running time of O(m ³ nlog(mB)). The fastest known running time for this problem is , and is due to Radzik (Theor Comput Sci 312:75–97, 2004), building on earlier work of Goldfarb et al. (Math Oper Res 22:793–802, 1997). David P. Williamson is supported in part by an IBM Faculty Partnership Award and NSF grant CCF-0514628.     

On some interior-point algorithms for nonconvex quadratic optimization

 Recently, interior-point algorithms have been applied to nonlinear and nonconvex optimization. Most of these algorithms are either primal-dual path-following or affine-scaling in nature, and some of them are conjectured to converge to a local minimum. We give several examples to show that this may be untrue and we suggest some strategies for overcoming this difficulty. Received: June 26, 2000 / Accepted: April 2002 Published online: September 5, 2002 Key words. Nonconvex quadratic optimization – local minimum – interior-point algorithms – trust region – branch-and-cut This research is supported by the National Science Foundation Grant CCR-9731273 and DMS-9703490.     

The Graver Complexity of Integer Programming

In this article we establish an exponential lower bound on the Graver complexity of integer programs. This provides new type of evidence supporting the presumable intractability of integer programming. Specifically, we show that the Graver complexity of the incidence matrix of the complete bipartite graph K ₃,m satisfies g(m) = Ω(2 ^m ), with g(m) ≥ 17·2 ^m−3 –7 for every m > 3.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Large deviations and continuum limit in the 2D Ising model

Summary. We study the 2D Ising model in a rectangular box Λ _L of linear size O(L). We determine the exact asymptotic behaviour of the large deviations of the magnetization ∑ _t∈ΛL σ(t) when L→∞ for values of the parameters of the model corresponding to the phase coexistence region, where the order parameter m ^* is strictly positive. We study in particular boundary effects due to an arbitrary real-valued boundary magnetic field. Using the self-duality of the model a large part of the analysis consists in deriving properties of the covariance function <σ(0)σ(t)>, as |t|→∞, at dual values of the parameters of the model. To do this analysis we establish new results about the high-temperature representation of the model. These results are valid for dimensions D≥2 and up to the critical temperature. They give a complete non-perturbative exposition of the high-temperature representation. We then study the Gibbs measure conditioned by {|∑ _t∈ΛL σ(t) −m|Λ _L ||≤|Λ _L |L ^{− c} }, with 0<c<1/4 and −m ^*<m<m ^*. We construct the continuum limit of the model and describe the limit by the solutions of a variational problem of isoperimetric type. Received: 17 October 1996 / In revised form: 7 March 1997     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

Dimension of Maximal Attractors for the m-dimensional Cahn-Hilliard System

On the basis of the existence of the maximal attractor of the m-dimensional Cahn-Hilliard system in the product spaces （L2（Ω））^m and （H2（Ω））^m, in this paper, its Hausdorff dimension is estimated by calculating the orthogonal projection of the linear variational operator of the system.     

Higher order Poincaré inequalities associated with linear operators on stratified groups and applications

 This paper considers the dual of anisotropic Sobolev spaces on any stratified groups 𝔾. For 0≤k<m and every linear bounded functional T on anisotropic Sobolev space W ^m−k,p (Ω) on Ω⊂𝔾, we derive a projection operator L from W ^m,p (Ω) to the collection 𝒫 _k+1 of polynomials of degree less than k+1 such that T(X ^I (Lu))=T(X ^I u) for all uW ^m,p (Ω) and multi-index I with d(I)≤k. We then prove a general Poincaré inequality involving this operator L and the linear functional T. As applications, we often choose a linear functional T such that the associated L is zero and consequently we can prove Poincaré inequalities of special interests. In particular, we obtain Poincaré inequalities for functions vanishing on tiny sets of positive Bessel capacity on stratified groups. Finally, we derive a Hedberg-Wolff type characterization of measures belonging to the dual of the fractional anisotropic Sobolev spaces W ^α,p 𝔾. Received: 25 March 2002; in final form: 10 September 2002 / Published online: 1 April 2003 Mathematics Subject Classification (1991): 46E35, 41A10, 22E25 The second author was supported partly by U.S NSF grant DMS99-70352 and the third author was supported partly by NNSF grant of China.