Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.     

A NEW TRUST-REGION ALGORITHM FOR NONLINEAR CONSTRAINED OPTIMIZATION

We propose a new trust region algorithm for nonlinear constrained optimization problems. In each iteration of our algorithm, the trial step is computed by minimizing a quadratic approximation to the augmented Lagrange function in the trust region. The augmented Lagrange function is also used as a merit function to decide whether the trial step should be accepted. Our method extends the traditional trust region approach by combining a filter technique into the rules for accepting trial steps so that a trial step could still be accepted even when it is rejected by the traditional rule based on merit function reduction. An estimate of the Lagrange multiplier is updated at each iteration, and the penalty parameter is updated to force sufficient reduction in the norm of the constraint violations. Active set technique is used to handle the inequality constraints. Numerical results for a set of constrained problems from the CUTEr collection are also reported.     

对称锥规划的Mehrotra型预估-矫正算法的多项式复杂性（英文）

We establish polynomial complexity bounds of the Mehrotra-type predictorcorrector algorithms for linear programming over symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al[18]. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O(r log ε-1) iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

A INTERIOR POINT ALGORITHM FOR CONVEX NONLINEAR PROGRAMMING PROBLEMS

This paper describes a primal-dual interior paint algorithm for convex nonlinear programming problems subject to linear constraints. The algorithm is based on the path following idea. Each iteration updates a penalty parameter and finds a Newton step associated with the simplified Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap if reduced at each iteration by a factor of (1 - δ / n~(1/n) ), where S is positive and depends on some parameters associated with the objective function.     

ON AUGMENTED LAGRANGIAN METHODS FOR SADDLE-POINT LINEAR SYSTEMS WITH SINGULAR OR SEMIDEFINITE （1, 1） BLOCKS

An effective algorithm for solving large saddle-point linear systems, presented by Krukier et al., is applied to the constrained optimization problems. This method is a modification of skew-Hermitian triangular splitting iteration methods. We consider the saddle-point linear systems with singular or semidefinite （1, 1） blocks. Moreover, this method is applied to precondition the GMRES. Numerical results have confirmed the effectiveness of the method and showed that the new method can produce high-quality preconditioners for the Krylov subspace methods for solving large sparse saddle-point linear systems.     

Global optimization method for linear multiplicative programming

In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming(LMP). The problem(LMP) is firstly converted into an equivalent programming problem(LMP(H))by introducing p auxiliary variables. Then by exploiting structure of(LMP(H)), a linear relaxation programming(LP(H)) of(LMP(H)) is obtained with a problem(LMP) reduced to a sequence of linear programming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems(LP(H)). The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

On affine scaling and semi-infinite programming

We consider an extension of the affine scaling algorithm for linear programming problems with free variables to problems having infinitely many constraints, and explore the relationship between this algorithm and the finite affine scaling method applied to a discretization of the problem.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR 89-0410.     

An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption

In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.     

A trust region affine scaling method for bound constrained optimization

We study a new trust region affine scaling method for general bound constrained optimization problems. At each iteration, we compute two trial steps. We compute one along some direction obtained by solving an appropriate quadratic model in an ellipsoidal region. This region is defined by an affine scaling technique. It depends on both the distances of current iterate to boundaries and the trust region radius. For convergence and avoiding iterations trapped around nonstationary points, an auxiliary step is defined along some newly defined approximate projected gradient. By choosing the one which achieves more reduction of the quadratic model from the two above steps as the trial step to generate next iterate, we prove that the iterates generated by the new algorithm are not bounded away from stationary points. And also assuming that the second-order sufficient condition holds at some nondegenerate stationary point, we prove the Q-linear convergence of the objective function values. Preliminary numerical experience for problems with bound constraints from the CUTEr collection is also reported.     

Limiting behavior of the affine scaling continuous trajectories for linear programming problems

We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called centered optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm.     

Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones

This paper presents an extension of the variant of Mehrotra’s predictor–corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646–658, 2006) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra’s original predictor–corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov–Todd direction, we show that the iteration-complexity bound of the proposed algorithm is , where r is the rank of the associated Euclidean Jordan algebras and ε>0 is the required precision.     

A simplified global convergence proof of the affine scaling algorithm

This paper presents a simplified and self-contained global convergence proof for the affine scaling algorithm applied to degenerate linear programming problems. Convergence of the sequence of dual estimates to the center of the optimal dual face is also proven. In addition, we give a sharp rate of convergence result for the sequence of objective function values. All these results are proved with respect to the long step version of the affine scaling algorithm in which we move a fraction , where (0,2/3), of the step to the boundary of the feasible region.This research was supported by the National Science Foundation (NSF) under Grant No. DDM-9109404 and the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

A Note on Mascarenhas' Counterexample about Global Convergence of the Affine Scaling Algorithm

Mascarenhas gave an instance of linear programming problems to show that the long-step affine scaling algorithm can fail to converge to an optimal solution with the step-size λ=0.999 . In this note, we give a simple and clear geometrical explanation for this phenomenon in terms of the Newton barrier flow induced by projecting the homogeneous affine scaling vector field conically onto a hyperplane where the objective function is constant. Based on this interpretation, we show that the algorithm can fail for "any" λ greater than about 0.91 (a more precise value is 0.91071), which is considerably shorter than λ = 0.95 and 0.99 recommended for efficient implementations. Accepted 17 February 1998