A New Full Nesterov–Todd Step Primal–Dual Path-Following Interior-Point Algorithm for Symmetric Optimization

In this paper, we generalize a primal–dual path-following interior-point algorithm for linear optimization to symmetric optimization by using Euclidean Jordan algebras. The proposed 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 steps. Moreover, we derive the currently best known iteration bound for the small-update method. This unifies the analysis for linear, second-order cone, and semidefinite optimizations.     

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions , we propose a combined homotopy infeasible interior-point method (CHIIP) for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.     

New Complexity Analysis of the Primal–Dual Method for Semidefinite Optimization Based on the Nesterov–Todd Direction

Interior-point methods for semidefinite optimization have been studied intensively in recent times, due to their polynomial complexity and practical efficiency. In this paper, first we present some technical results about symmetric matrices. Then, we apply these results to give a unified analysis for both large update and small update interior-point methods for SDP based on the Nesterov–Todd (NT) direction.     

A Damped Gauss-Newton Method for the Second-Order Cone Complementarity Problem

We investigate some properties related to the generalized Newton method for the Fischer-Burmeister (FB) function over second-order cones, which allows us to reformulate the second-order cone complementarity problem (SOCCP) as a semismooth system of equations. Specifically, we characterize the B-subdifferential of the FB function at a general point and study the condition for every element of the B-subdifferential at a solution being nonsingular. In addition, for the induced FB merit function, we establish its coerciveness and provide a weaker condition than Chen and Tseng (Math. Program. 104:293–327, 2005) for each stationary point to be a solution, under suitable Cartesian P-properties of the involved mapping. By this, a damped Gauss-Newton method is proposed, and the global and superlinear convergence results are obtained. Numerical results are reported for the second-order cone programs from the DIMACS library, which verify the good theoretical properties of the method. S. Pan’s work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. J.-S. Chen is member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. J.-S. Chen’s work is partially supported by National Science Council of Taiwan.     

A Revised Pascoletti–Serafini Scalarization Method for Multiobjective Optimization Problems

The presented study deals with the scalarization techniques for solving multiobjective optimization problems. The Pascoletti–Serafini scalarization technique is considered, and it is attempted to sidestep two weaknesses of this method, namely the inflexibility of the constraints and the difficulties of checking proper efficiency. To this end, two modifications for the Pascoletti–Serafini scalarization technique are proposed. First, by including surplus variables in the constraints and penalizing the violations in the objective function, the inflexibility of the constraints is resolved. Moreover, by including slack variables in the constraints, easy-to-check statements on proper efficiency are obtained. Thereafter, the two proposed modifications are combined to obtain the revised Pascoletti–Serafini scalarization method. Theorems are provided on the relation of (weakly, properly) efficient solutions of the multiobjective optimization problem and optimal solutions of the proposed scalarized problems. All the provided results are established with no convexity assumption. Moreover, the capability of the proposed approaches is demonstrated through numerical examples.     

A New Wide Neighborhood Primal–Dual Infeasible-Interior-Point Method for Symmetric Cone Programming

We present a new infeasible-interior-point method, based on a wide neighborhood, for symmetric cone programming. The convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the xs and sx directions. Moreover, we derive the complexity bound of the wide neighborhood infeasible interior-point methods that coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm.     

A new interior-point algorithm based on modified Nesterov–Todd direction for symmetric cone linear complementarity problem

We present a new primal-dual path-following interior-point algorithm for linear complementarity problem over symmetric cones. The algorithm is based on a reformulation of the central path for finding the search directions. For a full Nesterov–Todd step feasible interior-point algorithm based on the search directions, the complexity bound of the algorithm with the small update approach is the best available.     

An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity

Infeasible interior point methods have been very popular and effective. In this paper, we propose a predictor–corrector infeasible interior point algorithm for convex quadratic programming, and we prove its convergence and analyze its complexity. The algorithm has the polynomial numerical complexity with O(nL)-iteration.     

A Filter-Based Pattern Search Method for Unconstrained Optimization

We discuss a filter-based pattern search method for unconstrained optimization in this paper. For the purpose to broaden the search range we use both filter technique and frames, which are fragments of grids, to provide a new criterion of iterate acceptance. The convergence can be ensured under some conditions. The numerical result shows that this method is practical and efficient.     

Primal–Dual–Infeasible Newton Approach for the Analytic Center Deep-Cutting Plane Method

The convergence and complexity of a primal–dual column generation and cutting plane algorithm from approximate analytic centers for solving convex feasibility problems defined by a deep cut separation oracle is studied. The primal–dual–infeasible Newton method is used to generate a primal–dual updating direction. The number of recentering steps is O(1) for cuts as deep as half way to the deepest cut, where the deepest cut is tangent to the primal–dual variant of Dikin's ellipsoid.     

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 full Nesterov–Todd step infeasible-interior-point algorithm for Cartesian P*(κ) horizontal linear complementarity problems over symmetric cones

Euclidean Jordan algebra is a commonly used tool in designing interior-point algorithms for symmetric cone programs. In this paper, we present a full Nesterov–Todd (NT) step infeasible interior-point algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones. Since the algorithm uses only full-NT feasibility and centring steps, it has the advantage that no line searches are needed. The complexity result obtained here for symmetric cones using NT directions coincides with the best bound obtained for horizontal linear complementarity problems.     

Optimization Problem Coupled with Differential Equations: A Numerical Algorithm Mixing an Interior-Point Method and Event Detection

The numerical analysis of a dynamic constrained optimization problem is presented. It consists of a global minimization problem that is coupled with a system of ordinary differential equations. The activation and the deactivation of inequality constraints induce discontinuity points in the time evolution. A numerical method based on an operator splitting scheme and a fixed point algorithm is advocated. The ordinary differential equations are approximated by the Crank-Nicolson scheme, while a primal-dual interior-point method with warm-starts is used to solve the minimization problem. The computation of the discontinuity points is based on geometric arguments, extrapolation polynomials and sensitivity analysis. Second order convergence of the method is proved when an inequality constraint is activated. Numerical results for atmospheric particles confirm the theoretical investigations.