An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming

We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:1–19, 1993) holds.     

Additive Schwarz Methods for Elliptic Mortar Finite Element Problems

Summary. Two variants of the additive Schwarz method for solving linear systems arising from the mortar finite element discretization on nonmatching meshes of second order elliptic problems with discontinuous coefficients are designed and analyzed. The methods are defined on subdomains without overlap, and they use special coarse spaces, resulting in algorithms that are well suited for parallel computation. The condition number estimate for the preconditioned system in each method is proportional to the ratio H/h, where H and h are the mesh sizes, and it is independent of discontinuous jumps of the coefficients. For one of the methods presented the choice of the mortar (nonmortar) side is independent of the coefficients.This work has been supported in part by the Norwegian Research Council, grant 113492/420This work has been supported in part by the National Science Foundation, grant NSF-CCR-9732208 and in part by the Polish Science Foundation, grant 2P03A02116 Mathematics Subject Classification (2000):65N55     

A quadratically convergent predictor—corrector method for solving linear programs from infeasible starting points

A predictor—corrector method for solving linear programs from infeasible starting points is analyzed. The method is quadratically convergent and can be combined with Ye's finite termination scheme under very general assumptions. If the starting points are large enough then the algorithm hasO(nL) iteration complexity. If the ratio between feasibility and optimality at the starting points is small enough then the algorithm has O( ) iteration complexity. For feasible starting points the algorithm reduces to the Mizuno—Todd—Ye predictor—corrector method.This work was supported by an interdisciplinary research grant from the Institute for Advanced Studies of the University of Iowa.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

An implicit shift bidiagonalization algorithm for ill-posed systems

Iterative methods based on Lanczos bidiagonalization with full reorthogonalization (LBDR) are considered for solving large-scale discrete ill-posed linear least-squares problems of the form min _x Ax–b₂. Methods for regularization in the Krylov subspaces are discussed which use generalized cross validation (GCV) for determining the regularization parameter. These methods have the advantage that no a priori information about the noise level is required. To improve convergence of the Lanczos process we apply a variant of the implicitly restarted Lanczos algorithm by Sorensen using zero shifts. Although this restarted method simply corresponds to using LBDR with a starting vector (AA ^T) ^p b, it is shown that carrying out the process implicitly is essential for numerical stability. An LBDR algorithm is presented which incorporates implicit restarts to ensure that the global minimum of the CGV curve corresponds to a minimum on the curve for the truncated SVD solution. Numerical results are given comparing the performance of this algorithm with non-restarted LBDR.This work was partially supported by DARPA under grant 60NANB2D1272 and by the National Science Foundation under grant CCR-9209349.     

Inexact non-interior continuation method for monotone semidefinite complementarity problems

Chen and Tseng (Math Program 95:431?C474, 2003) extended non-interior continuation methods for solving linear and nonlinear complementarity problems to semidefinite complementarity problems (SDCP), in which a system of linear equations is exactly solved at each iteration. However, for problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a version of one of the non-interior continuation methods for monotone SDCP presented by Chen and Tseng that incorporates inexactness into the linear system solves. Only one system of linear equations is inexactly solved at each iteration. The global convergence and local superlinear convergence properties of the method are given under mild conditions.     

A globally and quadratically convergent affine scaling method for linearℓ 1 problems

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this interior point philosophy can be adapted to the linear ₁ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.This paper was presented at the Third SIAM Conference on Optimization, in Boston, April 1989.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University, and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration     

The polynomial hierarchy and a simple model for competitive analysis

The multi-level linear programs of Candler, Norton and Townsley are a simple class of sequenced-move games, in which players are restricted in their moves only by common linear constraints, and each seeks to optimize a fixed linear criterion function in his/her own continuous variables and those of other players. All data of the game and earlier moves are known to a player when he/she is to move. The one-player case is just linear programming.We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players.For three players, the games allow reduction of the ₂ and ₂ levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with (p + 1) players allow reductions of _p and _p in the hierarchy.An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.The author's work has been supported by the Alexander von Humboldt Foundation and the Institut fur Okonometrie und Operations Research of the University of Bonn, Federal Republic of Germany; grant ECS8001763 of the National Science Foundation, USA; and a grant from the Georgia Tech Foundation.     

D.c. sets,d.c. functions and nonlinear equations

Ad.c. set is a set which is the difference of two convex sets. We show that any set can be viewed as the image of a d.c. set under an appropriate linear mapping. Using this universality we can convert any problem of finding an element of a given compact set in ⁿ into one of finding an element of a d.c. set. On the basis of this approach a method is developed for solving a system of nonlinear equations—inequations. Unlike Newton-type methods, our method does not require either convexity, differentiability assumptions or an initial approximate solution.The revision of this paper was produced during the author's stay supported by a Sophia lecturing-research grant at Sophia University (Tokyo, Japan).     

Solution of sparse rectangular systems using LSQR and CRAIG

We examine two iterative methods for solving rectangular systems of linear equations: LSQR for over-determined systemsAx b, and Craig's method for under-determined systemsAx = b. By including regularization, we extend Craig's method to incompatible systems, and observe that it solves the same damped least-squares problems as LSQR. The methods may therefore be compared on rectangular systems of arbitrary shape.Various methods for symmetric and unsymmetric systems are reviewed to illustrate the parallels. We see that the extension of Craig's method closes a gap in existing theory. However, LSQR is more economical on regularized problems and appears to be more reliable if the residual is not small.In passing, we analyze a scaled augmented system associated with regularized problems. A bound on the condition number suggests a promising direct method for sparse equations and least-squares problems, based on indefiniteLDL ^T factors of the augmented matrix.Dedicated to Professor Åke Björck in honor of his 60th birthdayPresented at the 12th Householder Symposium on Numerical Algebra, Lake Arrowhead, California, June 1993.Partially supported by Department of Energy grant DE-FG03-92ER25117, National Science Foundation grant DMI-9204208, and Office of Naval Research grant N00014-90-J-1242.     

Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

Spline approximation methods for multidimensional periodic pseudodifferential equations

We investigate several numerical methods for solving the pseudodifferential equationAu=f on the n-dimensional torusT ⁿ . We examine collocation methods as well as Galerkin-Petrov methods using various periodical spline functions. The considered spline spaces are subordinated to a uniform rectangular or triangular grid. For given approximation method and invertible pseudodifferential operatorA we compute a numerical symbol ^C , resp. ^G , depending onA and on the approximation method. It turns out that the stability of the numerical method is equivalent to the ellipticity of the corresponding numerical symbol. The case of variable symbols is tackled by a local principle. Optimal error estimates are established.The second author has been supported by a grant of Deutsche Forschungsgemeinschaft under grant namber Ko 634/32-1.     

An interior point algorithm ofO(\sqrt m \left| {\ln \varepsilon } \right|) iterations forC 1-convex programming

We present a theoretical result on a path-following algorithm for convex programs. The algorithm employs a nonsmooth Newton subroutine. It starts from a near center of a restricted constraint set, performs a partial nonsmooth Newton step in each iteration, and converges to a point whose cost is within accuracy of the optimal cost in iterations, wherem is the number of constraints in the problem. Unlike other interior point methods, the analyzed algorithm only requires a first-order Lipschitzian condition and a generalized Hessian similarity condition on the objective and constraint functions. Therefore, our result indicates the theoretical feasibility of applying interior point methods to certainC ¹-optimization problems instead ofC ²-problems. Since the complexity bound is unchanged compared with similar algorithms forC ²-convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.This author's work is supported in part by the National Science Foundation of the USA under grant DDM-8721709.This author's work is supported in part by the Australian Research Council.     

A characterization of Denniston's maximal arcs

Our main result is the following characterization of Denniston's maximal arcs: If a maximal arcK in PG(2,q),q even, is invariant under a linear collineation group of PG(2,q) which is cyclic and has orderq+1, thenK is a Denniston's maximal arc.This work was partially supported by a grant of M.P.I. (Research project Strutture geometriche combinatorie e loro applicazioni).     

A note on positively invariant cones

Given a closed convex pointed cone which is positively invariant with respect to motions of the differential equation (A being a real (n × n) matrix), it is proven that a necessary and sufficient condition for asymptotic stability of (and therefore of the linear span of) is In case, this result yields a known equivalence from the theory ofM-matrices.This research was supported by the Natural Sciences and Engineering Council Canada under grant A4641.     

Scattered subsets of\mathbb{Q}

A linear order isscattered if it contains no copy of the rationals. The scattered subsets of form a better quasi-order under embeddability via order automorphisms.Research supported by NSERC grant #9848.     

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds

We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an activity set. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, 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.Corresponding author.     

Linear forward-backward stochastic differential equations with random coefficients

Solvability of linear forward-backward stochastic differential equations (FBSDEs, for short) with random coefficients is studied. A decoupling reduction method is introduced via which a large class of linear FBSDEs with random or deterministic time-varying coefficients is proved to be solvable. On the other hand, by means of Four Step Scheme, a Riccati backward stochastic equation (BSDE, for short) for (m×n) matrix-valued processes is derived. Global solvability of such Riccati BSDEs is discussed for some special (but nontrivial) cases, which leads to the solvability of the corresponding linear FBSDEs. This work is supported in part by the NSFC, under grant 10131030, the Chinese Education Ministry Science Foundation under grant 2000024605, the Cheung Kong Scholars Programme, and Shanghai Commission of Science and Technology under grant 02DJ14063.