A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov–Todd step

In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, , where N denotes the number of second-order cones in the problem formulation and ε the desired accuracy.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

Long-step strategies in interior-point primal-dual methods

In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods on nonlinear conic problems. We demonstrate that most interior-point methods with efficiency estimate can be considered as different strategies of minimizing aconvex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate for a pure primal-dual potential reduction method, which can be considered as an implementation of apenalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem.     

On a Commutative Class of Search Directions for Linear Programming over Symmetric Cones

The commutative class of search directions for semidefinite programming was first proposed by Monteiro and Zhang (Ref. 1). In this paper, we investigate the corresponding class of search directions for linear programming over symmetric cones, which is a class of convex optimization problems including linear programming, second-order cone programming, and semidefinite programming as special cases. Complexity results are established for short-step, semilong-step, and long-step algorithms. Then, we propose a subclass of the commutative class for which we can prove polynomial complexities of the interior-point method using semilong steps and long steps. This subclass still contains the Nesterov–Todd direction and the Helmberg–Rendl–Vanderbei–Wolkowicz/Kojima–Shindoh–Hara/Monteiro direction. An explicit formula to calculate any member of the class is also given.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

The Nesterov–Todd Direction and Its Relation to Weighted Analytic Centers

The subject of this paper concerns differential-geometric properties of the Nesterov–Todd search direction for linear optimization over symmetric cones. In particular, we investigate the rescaled asymptotics of the associated flow near the central path. Our results imply that the Nesterov–Todd direction arises as the solution of a Newton system defined in terms of a certain transformation of the primal-dual feasible domain. This transformation has especially appealing properties which generalize the notion of weighted analytic centers for linear programming.     

A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r^5/4log ?^?1) for the Nesterov-Todd direction, and 𝒪(r^7/4log ?^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r^3/4. Some preliminary numerical results are provided as well.     

Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for ``infinite-dimensional second-order cone programs.' We consider as an example a long-step primal-dual algorithm based on the Nesterov-Todd direction. It is shown that this algorithm can be generalized along with complexity estimates to the infinite-dimensional situation under consideration. An application is given to an important problem of control theory: multi-criteria analytic design of the linear regulator. The calculation of the Nesterov-Todd direction requires in this case solving one matrix differential Riccati equation plus solving a finite-dimensional system of linear algebraic equations on each iteration. The number of equations and unknown variables of this algebraic system is m+1, where m is a number of quadratic performance criteria. Key words.polynomial-time primal-dual interior-point methods – JB-algebras – infinite-dimensional problems – optimal control problemsThis author was supported in part by DMS98-03191 and DMS01-02698.This author was supported in part by the Grant-in-Aid for Scientific Research (C) 11680463 of the Ministry of Education, Culture, Sports, Science and Technology of Japan.Mathematics Subject Classification (1991):90C51, 90C48, 34H05, 49N05     

A lower bound on the number of iterations of long-step primal-dual linear programming algorithms

Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn ^1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550.This author is supported in part by NSF Grant DDM-9207347. Part of thiw work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Approximate factorizations with S/P consistently ordered M-factors

The behaviour of PCG methods for solving a finite difference or finite element positive definite linear systemAx=b with a (pre)conditioning matrixB=U ^TP^–1 U (whereU is upper triangular andP=diag(U)) obtained from a modified incomplete factorization, isunpredictable in the present status of knowledge whenever the upper triangular factor is not strictly diagonally dominant and 2P –D, whereD=diag(A), is not symmetric positive definite. The origin of this rather surprising shortcoming of the theory is that all upper bounds on the associated spectral condition number (B ^–1 A) obtained so far require either the strict diagonal dominance of the upper triangular factor or the strict positive definiteness of 2P –D. It is our purpose here to improve the theory in this respect by showing that, when the triangular factors are S/P consistently orderedM-matrices, nonstrict diagonal dominance is generally a sufficient requirement, without additional condition on 2P –D. As a consequence, the new analysis does not require diagonal perturbations (otherwise needed to keep control of the diagonal dominance ofU or of the positive definiteness of 2P –D). Further, the bounds obtained here on (B ^–1 A) are independent of the lower spectral bound ofD ^–1 A meaning that quasi-singular problems can be solved at the same speed as regular ones, an unexpected result.     

Extension of primal-dual interior point algorithms to symmetric cones

 In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions. Received: April 2000 / Accepted: May 2002 Published online: March 28, 2003 RID="⋆" ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational Optimization at Columbia University. RID="⋆⋆" ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research contract number N00014-96-1-0704.     

Deadbeat control: A special inverse eigenvalue problem

In this paper we give a numerical method to construct a rankm correctionBF (where then ×m matrixB is known and them ×n matrixF is to be found) to an ×n matrixA, in order to put all the eigenvalues ofA +BF at zero. This problem is known in the control literature as deadbeat control. Our method constructs, in a recursive manner, a unitary transformation yielding a coordinate system in which the matrixF is computed by merely solving a set of linear equations. Moreover, in this coordinate system one easily constructs the minimum norm solution to the problem. The coordinate system is related to the Krylov sequenceA ^–1 B,A ^–2 B,A ^–3 B, .... Partial results of numerical stability are also obtained.Dedicated to Professor Germund Dahlquist: on the occasion of his 60th birthday     

Some positive cotes numbers for the chebyshev weight function

We show that, for the Chebyshev weight function (1–x ²)^–1/2, the Cotes numbers for the quadrature rule with nodes at the zeros of the ultraspherical polynomialP _n ^/() are nonnegative if and only if –1/2<1.     

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.     

How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds

By refining a variant of the Klee–Minty example that forces the central path to visit all the vertices of the Klee–Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is , we prove that solving this n-dimensional linear optimization problem requires at least 2 ⁿ −1 iterations. Dedicated to Professor Emil Klafszky on the occasion of his 70th birthday.     

Asymptotic Estimates for a Variational Problem Involving a Quasilinear Operator in the Semi-Classical Limit

Let be a domain of ^N . We study the infimum ₁(h) of the functional |u| ^p +h ^–p V(x)|u| ^p dx in W ^1,p () for ||u|| _LP()= 1 where h > 0 tends to zero and V is a measurable function on . When V is bounded, we describe the behaviour of ₁(h), in particular when V is radial and 'slowly' decaying to zero. We also study the limit of ₁(h) when h 0 for more general potentials and show a necessary and sufficient condition for ₁(h) to be bounded. A link with the tunelling effect is established. We end with a theorem of existence for a first eigenfunction related to ₁(h).     

Applications of shortest path algorithms to matrix scalings

Summary A symmetric scaling of a nonnegative, square matrixA is a matrixXAX ^–1, whereX is a nonsingular, nonnegative diagonal matrix. By associating a family of weighted directed graphs with the matrixA we are able to adapt the shortest path algorithms to compute an optimal scaling ofA, where we call a symmetric scalingA ofA optimal if it minimizes the maximum of the ratio of non-zero elements.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthdayThe first author was partially supported by the Deutsche Forschungsgemeinschaft under grant GO 270/3, the second author by the U.S. National Science Foundation under grand MCS-8026132     

On a lower bound for the perron eigenvalue

A lower boundn ^–1 _i,k a_ik for the Perron eigenvalue of a symmetric non-negative irreducible matrixA=(a _ik) is studied and compared with certain other lower bounds.     

Well-posedness of the Cauchy problem for the fractional power dissipative equation in critical Besov spaces

In this paper we study the Cauchy problem for the semilinear fractional power dissipative equation u_t+(−Δ)^αu=F(u) for the initial data u₀ in critical Besov spaces with , where α>0, F(u)=P(D)u^b+1 with P(D) being a homogeneous pseudo-differential operator of order d[0,2α) and b>0 being an integer. Making use of some estimates of the corresponding linear equation in the frame of mixed time–space spaces, the so-called “mono-norm method” which is different from the Kato's “double-norm method,” Fourier localization technique and Littlewood–Paley theory, we get the well-posedness result in the case .     

Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.