A full-Newton step interior-point algorithm based on modified Newton direction

The central path plays a very important role in interior-point methods. By an equivalent reformulation of the central path, we obtain a new search direction which targets at a small neighborhood of the central path. For a full-Newton step interior-point algorithm based on this search direction, the complexity bound of the algorithm is the best known for linear optimization.     

An infeasible interior-point algorithm with full-Newton step for linear optimization

Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained.      

Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming

We present an analysis of the full-Newton step infeasible interior-point algorithm for semidefinite optimization, which is an extension of the algorithm introduced by Roos [C. Roos, A full-Newton step 𝒪(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), pp. 1110–1136] for the linear optimization case. We use the proximity measure σ(V)?=?‖I???V ²‖ to overcome the difficulty of obtaining an upper bound of updated proximity after one full-Newton step, where I is an identity matrix and V is a symmetric positive definite matrix. It turns out that the complexity analysis of the algorithm is simplified and the iteration bound obtained is improved slightly.     

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.     

A new primal-dual path-following interior-point algorithm for semidefinite optimization

In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov-Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, , which is as good as the linear analogue.     

An SQP algorithm with cautious updating criteria for nonlinear degenerate problems

An efficient SQP algorithm for solving nonlinear degenerate problems is proposed in the paper. At each iteration of the algorithm, a quadratic programming subproblem, which is always feasible by introducing a slack variable, is solved to obtain a search direction. The steplength along this direction is computed by employing the 1∞ exact penalty function through Armijo-type line search scheme. The algorithm is proved to be convergent globally under mild conditions.     

An interior-point method for fractional programs with convex constraints

We present an interior-point method for a class of fractional programs with convex constraints. The proposed algorithm converges at a polynomial rate, similarly as in the case of a convex problem, even though fractional programs are only pseudo-convex. Here, the rate of convergence is measured in terms of the area of two-dimensional convex setsC _k containing the origin and certain projections of the optimal points, and the area ofC _k is reduced by a constant factorc < 1 at each iteration. The factorc depends only on the self-concordance parameter of a barrier function associated with the feasible set. We present an outline of a practical implementation of the proposed method, and we report results of some preliminary numerical experiments.Corresponding author.     

An efficient approach to updating simplex multipliers in the simplex algorithm

The simplex algorithm computes the simplex multipliers by solving a system (or two triangular systems) at each iteration. This note offers an efficient approach to updating the simplex multipliers in conjunction with the Bartels–Golub and Forrest–Tomlin updates for LU factors of the basis. It only solves one triangular system. The approach was implemented within and tested against MINOS 5.51 on 129 problems from Netlib, Kennington and BPMPD. Computational results show that the new approach improves simplex implementations. Project 10371017 supported by National Natural Science Foundation of China.     

An optimal adaptive algorithm for the approximation of concave functions

Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case. This work was partially supported by NSERC (Canada) and FCAR (Québec).     

An adaptive block Lanczos algorithm

A generalization of the block Lanczos algorithm will be given, which allows the block size to be increased during the iteration process. In particular, the algorithm can be implemented with the block size chosen adaptively according to clustering of Ritz values. In this way, multiple and clustered eigenvalues can be found and the difficulty of choosing the block size is eased. Residual bounds for clustered eigenvalues are given. Numerical examples are presented to illustrate the adaptive algorithm.Research supported by a grant from Natural Sciences and Engineering Research Council of Canada.     

A modified gradient based algorithm for solving Sylvester equations

In this paper a modified gradient based algorithm for solving Sylvester equations is presented. Different from the gradient based method introduced by Ding and Chen [7] and the relaxed gradient based algorithm proposed by Niu et al. [18], the information generated in the first half-iterative step is fully exploited and used to construct the approximate solution. Theoretical analysis shows that the new method converges under certain assumptions. Numerical results are given to verify the efficiency of the new method.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

An interior-point method for the single-facility location problem with mixed norms using a conic formulation

We consider the single-facility location problem with mixed norms, i.e. the problem of minimizing the sum of the distances from a point to a set of fixed points in , where each distance can be measured according to a different p-norm. We show how this problem can be expressed into a structured conic format by decomposing the nonlinear components of the objective into a series of constraints involving three-dimensional cones. Using the availability of a self-concordant barrier for these cones, we present a polynomial-time algorithm (a long-step path-following interior-point scheme) to solve the problem up to any given accuracy. Finally, we report computational results for this algorithm and compare with standard nonlinear optimization solvers applied to this problem. This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The first author acknowledges support by an FSR grant from Université Catholique de Louvain and a FRIA grant from Fonds de la Recherche Scientifique-FNRS. The scientific responsibility rests with its authors.     

An adaptive Newton algorithm based on numerical inversion: Regularization as postconditioner

Summary We examine a class of approximate inversion processes, satisfying estimates similar to those defined by finite element or truncated spectral approximations; these are to be used as approximate right inverses for Newton iteration methods. When viewed at the operator level, these approximations introduce a defect, or loss of derivatives, of order one or more. Regularization is introduced as a form of defect correction. A superlinearly convergent, approximate Newton iteration is thereby obtained by using the numerical inversion adaptively, i.e., with spectral or grid parameters correlated to the magnitude of the current residual in an intermediate norm defined by the defect. This adaptive choice makes possible ascribing an order to the convergent process, and this is identified as essentially optimal for elliptic problems, relative to complexity. The design of the algorithm involves multi-parameter selection, thereby opening up interesting avenues for elliptic problems, relative to complexity. This applies also to the regularization which may be carried out in the Fourier transform space, and is band-limited in the language of Whittaker-Shannon sampling theory. The norms employed in the analysis are of Hölder space type; the iteration is an adaptation of Nash-Moser interation; and, the complexity studies use Vitukin's theory of information processing. Computational experience is described in the final section.Research supported by National Science Foundation grant MCS-8218041. This is the second part of work in progress during the author's visit to the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, USA     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

An adaptive truncation criterion,for linesearch-based truncated Newton methods in large scale nonconvex optimization

Starting from the paper by Nash and Sofer (1990), we propose a heuristic adaptive truncation criterion for the inner iterations within linesearch-based truncated Newton methods. Our aim is to possibly avoid “over-solving” of the Newton equation, based on a comparison between the predicted reduction of the objective function and the actual reduction obtained. A numerical experience on unconstrained optimization problems highlights a satisfactory effectiveness and robustness of the adaptive criterion proposed, when a residual-based truncation criterion is selected.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.