Search

In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most O(n2log(x°}T s° /e) iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to O(nlog(x°}T s° /e). To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider numerical simulation to a class of constrained dynamic problems where the overall dynamics are determined by the interactions between two sub-systems. We present an iterative algorithm that naturally decouples the computation of the two sub-systems and that ensures an accurate and efficient solution procedure. We conduct rigorous error analysis for the convergence of the iterative algorithm, and verify the analytical results through careful numerical tests. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new penalty-free-type method for nonlinear equality constrained problems. The new algorithm uses trust region framework and feasibility safeguarding technique. Moreover, it has no choice of penalty parameter and penalty function as a merit function, and it does not use the filter technique to avoid the penalty function either. We analyze the global convergence of the main algorithm under the standard assumptions. The preliminary numerical tests are reported. [Copyright &y& Elsevier]

Abstract: In this paper, an active set limited BFGS algorithm is proposed for bound constrained optimization. The global convergence will be established under some suitable conditions. Numerical results show that the given method is effective. [Copyright &y& Elsevier]

Abstract: A directed searching optimization algorithm (DSO) is proposed to solve constrained optimization problems in this paper. The proposed algorithm includes two important operations — position updating and genetic mutation. Position updating enables the non-best solution vectors to mimic the best one, which is beneficial to the convergence of the DSO; genetic mutation can increase the diversity of individuals, which is beneficial to preventing the premature convergence of the DSO. In addition, we adopt the penalty function method to balance objective and constraint violations. We can obtain satisfactory solutions for constrained optimization problems by combining the DSO and the penalty function method. Experimental results indicate that the proposed algorithm can be an efficient alternative on solving constrained optimization problems. [Copyright &y& Elsevier]

Abstract: In this paper, a nonmonotone trust region algorithm for unconstrained optimization problems is presented. In the algorithm, a kind of nonmonotone technique, which is evidently different from Grippo, Lampariello and Lucidi’s approach, is used. Under mild conditions, global and local convergence results of the algorithm are established. Preliminary numerical results show that the new algorithm is efficient. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to incorporate the preconditioned gradient path in a nonmonotone stabilization algorithm for unconstrained optimization. The global convergence and locally superlinear convergence are established for this class of algorithms. Finally, we report in details the numerical results which show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We present an algorithm for large-scale equality constrained optimization. The method is based on a characterization of inexact sequential quadratic programming (SQP) steps that can ensure global convergence. Inexact SQP methods are needed for large-scale applications for which the iteration matrix cannot be explicitly formed or factored and the arising linear systems must be solved using iterative linear algebra techniques. We address how to determine when a given inexact step makes sufficient progress toward a solution of the nonlinear program, as measured by an exact penalty function. The method is globalized by a line search. An analysis of the global convergence properties of the algorithm and numerical results are presented. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a kind of nonlinear optimization problems with nonlinear inequality constraints are discussed, and a new SQP feasible descent algorithm for solving the problems is presented. At each iteration of the new algorithm, a convex quadratic program (QP) which always has feasible solution is solved and a master direction is obtained, then, an improved (feasible descent) direction is yielded by updating the master direction with an explicit formula, and in order to avoid the Maratos effect, a height-order correction direction is computed by another explicit formula of the master direction and the improved direction. The new algorithm is proved to be globally convergent and superlinearly convergent under mild conditions without the strict complementarity. Furthermore, the quadratic convergence rate of the algorithm is obtained when the twice derivatives of the objective function and constrained functions are adopted. Finally, some numerical tests are reported. [Copyright &y& Elsevier]

We introduce a new method for solving a class of non-smooth unconstrained optimization problems. The method constructs a sequencex k in ℝ n , and at the kth iteration, a search direction h k is considered, where h k is a solution to a variational inequality problem. A convergence theorem for our algorithm model and its discrete version can be easily proved. Furthermore, preliminary computational results show that the new method performs quite well and can compete with other methods. [ABSTRACT FROM AUTHOR]

In 2004, Graña Drummond and Iusem proposed an extension of the projected gradient method for constrained vector optimization problems. Using this method, an Armijo-like rule, implemented with a backtracking procedure, was used in order to determine the step lengths. The authors just showed stationarity of all cluster points and, for another version of the algorithm (with exogenous step lengths), under some additional assumptions, they proved convergence to weakly efficient solutions. In this work, first we correct a slight mistake in the proof of a certain continuity result in that 2004 article, and then we extend its convergence analysis. Indeed, under some reasonable hypotheses, for convex objective functions with respect to the ordering cone, we establish full convergence to optimal points of any sequence produced by the projected gradient method with an Armijo-like rule, no matter how poor the initial guesses may be. [ABSTRACT FROM PUBLISHER]

Numerous scientific applications across a variety of fields depend on box-constrained convex optimization. Box-constrained problems therefore continue to attract research interest. We address box-constrained (strictly convex) problems by deriving two new quasi-Newton algorithms. Our algorithms are positioned between the projected-gradient [J. B. Rosen, J. SIAM, 8 (1960), pp. 181-217] and projected-Newton [D. P. Bertsekas, SIAM J. Control Optim., 20 (1982), pp. 221- 246] methods. We also prove their convergence under a simple Armijo step-size rule. We provide experimental results for two particular box-constrained problems: nonnegative least squares (NNLS), and nonnegative Kullback-Leibler (NNKL) minimization. For both NNLS and NNKL our algorithms perform competitively as compared to well-established methods on medium-sized problems; for larger problems our approach frequently outperforms the competition. [ABSTRACT FROM AUTHOR]