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.     

New Complexity Analysis of the Primal—Dual Newton Method for Linear Optimization

We deal with the primal–dual Newton method for linear optimization (LO). Nowadays, this method is the working horse in all efficient interior point algorithms for LO, and its analysis is the basic element in all polynomiality proofs of such algorithms. At present there is still a gap between the practical behavior of the algorithms and the theoretical performance results, in favor of the practical behavior. This is especially true for so-called large-update methods. We present some new analysis tools, based on a proximity measure introduced by Jansen et al., in 1994, that may help to close this gap. This proximity measure has not been used in the analysis of large-update methods before. The new analysis does not improve the known complexity results but provides a unified way for the analysis of both large-update and small-update methods.     

Equivalent Conditions for Jacobian Nonsingularity in Linear Symmetric Cone Programming

In this paper we consider the linear symmetric cone programming (SCP). At a Karush-Kuhn-Tucker (KKT) point of SCP, we present the important conditions equivalent to the nonsingularity of Clarke’s generalized Jacobian of the KKT nonsmooth system, such as primal and dual constraint nondegeneracy, the strong regularity, and the nonsingularity of the B-subdifferential of the KKT system. This affirmatively answers an open question by Chan and Sun (SIAM J. Optim. 19:370–396, 2008).     

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.     

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 New Interior Path Following Method for Nonconvex Nonlinear Programming

Consider the following nonlinear programming problem:where f, gi's are sufficiently smooth functions in R~n. LetIt is well known that if x~*∈Ω is a solution of (1) then there exists λ~*=(λ_I~*,…,λ_m~*)∈R~m such that(x~*,λ~*) is a solution of the K-K-T system     

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms

We propose a new first-order splitting algorithm for solving jointly the primal and dual formulations of large-scale convex minimization problems involving the sum of a smooth function with Lipschitzian gradient, a nonsmooth proximable function, and linear composite functions. This is a full splitting approach, in the sense that the gradient and the linear operators involved are applied explicitly without any inversion, while the nonsmooth functions are processed individually via their proximity operators. This work brings together and notably extends several classical splitting schemes, like the forward–backward and Douglas–Rachford methods, as well as the recent primal–dual method of Chambolle and Pock designed for problems with linear composite terms.     

Primal—Dual Constraint Aggregation with Application to Stochastic Programming

The special constraint structure and large dimension are characteristic for multistage stochastic optimization. This results from modeling future uncertainty via branching process or scenario tree. Most efficient algorithms for solving this type of problems use certain decomposition schemes, and often only a part of the whole set of scenarios is taken into account in order to make the problem tractable.We propose a primal–dual method based on constraint aggregation, which constructs a sequence of iterates converging to a solution of the initial problem. At each iteration, however, only a reduced sub-problem with smaller number of aggregate constraints has to be solved. Number of aggregates and their composition are determined by the user, and the procedure for calculating aggregates can be parallelized. The method provides a posteriori estimates of the quality of the current solution approximation in terms of the objective function value and the residual.Results of numerical tests for a portfolio allocation problem with quadratic utility function are presented.     

A modified Primal–Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

The aim of solving the Optimal Power Flow problem is to determine the optimal state of an electric power transmission system, that is, the voltage magnitude and phase angles and the tap ratios of the transformers that optimize the performance of a given system, while satisfying its physical and operating constraints. The Optimal Power Flow problem is modeled as a large-scale mixed-discrete nonlinear programming problem. This paper proposes a method for handling the discrete variables of the Optimal Power Flow problem. A penalty function is presented. Due to the inclusion of the penalty function into the objective function, a sequence of nonlinear programming problems with only continuous variables is obtained and the solutions of these problems converge to a solution of the mixed problem. The obtained nonlinear programming problems are solved by a Primal–Dual Logarithmic-Barrier Method. Numerical tests using the IEEE 14, 30, 118 and 300-Bus test systems indicate that the method is efficient.     

A Full Nesterov–Todd Step Infeasible Interior-Point Method for Second-Order Cone Optimization

After a brief introduction to Jordan algebras, we present a primal–dual interior-point algorithm for second-order conic optimization that uses full Nesterov–Todd steps; no line searches are required. The number of iterations of the algorithm coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization to second-order conic optimization. As usual for infeasible interior-point methods, the starting point depends on a positive number. The algorithm either finds a solution in a finite number of iterations or determines that the primal–dual problem pair has no optimal solution with vanishing duality gap.     

Symmetric Duality and Self-duality for Nonsmooth Mathematical Programming

Ｓｙｍｍｅｔｒｉｃ　Ｄｕａｌｉｔｙ　ａｎｄ　Ｓｅｌｆ－ｄｕａｌｉｔｙ　ｆｏｒ　Ｎｏｎｓｍｏｏｔｈ　Ｍａｔｈｅｍａｔｉｃａｌ　ＰｒｏｇｒａｍｍｉｎｇＤｏｎｇＪｉａｌｉ（董加礼）（ＤｅｐａｒｔｍｅｎｔｏｆａｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓａ，Ｊｉｌｉｎ...     

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.     

A Method for Non-Lipschitz Programming via an Exact Penalry Function

A descent algorithm for Non-Lipschitz Programming is presented in the paper. The algorithm employs a strict convex programming to obtain a search direction and an exact penalty function to determine step lenth. The convergence is proved and two numerical results are given, in which the objective functions are discontinuous.     

A New Method for Computing Reproducing Kernels

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＡｓｙｓｔｅｍａｔｉｃｒｅｓｅａｒｃｈｔｏｔｈｅｔｈｅｏｒｙｏｆｒｅｐｒｏｄｕｃｉｎｇｋｅｒｎｅｌｗａｓｆｉｒｓｔｍａｄｅｂｙＡｒｏｎｓｚａｊｎａｎｄＢｅｒｇｍａｎ［１］．Ｔｈｅｙｇａｖｅａｓｕｆｉｃｉｅｎｔａｎｄｎｅｃ...