Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J. Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximities for linear optimization (LO) problems. They also extended the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this kernel function, both with large- and small-updates. The complexity bounds are and , respectively, which are as good as those in the linear case. Mathematics Subject Classifications (2000) 90C22, 90C31.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

一个求解半正定规划问题的新原始一对偶内点算法

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O（√n log n log n/c）和O（√n log n/ε）,这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。     

A New Infeasible Interior-Point Method Based on a Non-Coercive Kernel Function with Improved Centering Steps for Second-Order Cone Optimization

In this article, we present a new full Nesterov-Todd step infeasible interior-point method for second-order cone optimization based on a non-coercive kernel function. The main iteration consists of a so-called feasibility step and one centering step, whereas the earlier versions, in [4 S. Bouali and S. Kabbaj ( 2014 ). Full-NT step infeasible interior-point method for SOCO based on a specific kernel function . Afr. Mat. 25 : 549 – 565 .[Crossref] , [Google Scholar], 21 M. Zangiabadi , G. Gu , and C. Roos ( 2013 ). A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization . J. Optim. Theory Appl. 158 : 816 – 858 .[Crossref], [Web of Science ®] , [Google Scholar]], needed two additional centering steps. We use a kernel function to induce the feasibility step. The new algorithm reduces the searching steps in each iteration and tenders an interesting analysis for complexity bound.     

基于局部self-concordant障碍函数的全牛顿步多项式时间算法

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

二阶锥规划两个新的预估-校正算法

基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法．其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴．算法对于迭代点可行或不可行的情形都适用．主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键．在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数．数值实验结果表明提出的两个算法是有效的．     

线性二阶锥规划的一个光滑化方法及其收敛性

首先讨论了用Chen-Harker-Kanzow-Smale光滑函数刻画线性二阶锥规划的中心路径条件;基于此,提出了求解线性二阶锥规划的一个光滑化算法,然后分析了该算法的全局及其局部二次收敛性质.     

Research Article: On Extending Primal-Dual Interior-Point Method for Linear Optimization to Convex Quadratic Symmetric Cone Optimization

Disjoint frames are interesting frames in Hilbert spaces, which were introduced by Han and Larson in [4 D. Han and D. R. Larson ( 2000 ). Frames, Basis and Group Representations . Memoirs of the American Mathematical Society, No. 679. AMS, Providence, RI.  [Google Scholar]]. In this article, we use disjoint frames to construct frames. In particular, we obtain some conditions for the linear combinations of frames to be frames where the coefficients in the combination may be operators. Our results generalize the corresponding results obtained by Han and Larson. Finally, we provide some examples to illustrate our constructions.     

New Interior-Point Algorithm for Symmetric Optimization Based on a Positive-Asymptotic Barrier Function

Abstract

We define a new interior-point method (IPM), which is suitable for solving symmetric optimization (SO) problems. The proposed algorithm is based on a new search direction. In order to obtain this direction, we apply the method of algebraically equivalent transformation on the centering equation of the central path. We prove that the associated barrier cannot be derived from a usual kernel function. Therefore, we introduce a new notion, namely the concept of the positive-asymptotic kernel function. We conclude that this algorithm solves the problem in polynomial time and has the same complexity as the best known IPMs for SO.     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm.     

求解二阶锥规划问题的VU分解方法

给出解决二阶锥规划(SOCP)问题的VU-分解方法.问题首先被转化为非线性规划,并给出相应的精确罚函数的Clarke次微分结构及VU-空间分解．在某种条件下,可以计算出一个二阶连续可微的轨道,进而得到目标函数f在其上的二阶展开．最后给出一个具有超线性收敛速度的概念型算法．     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

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.     

Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term

In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization(SDO) problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 q2 1, the algorithm has O((q1 + 1) nq1+1/2(q1-q2)logn/ε)and O((q1 + 1)3q1-2q2+1/2(q1-q2)n~1/2 logn/ε) complexity results for large- and small-update methods, respectively.     

A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r^5/4log ?^?1) for the Nesterov-Todd direction, and 𝒪(r^7/4log ?^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r^3/4. Some preliminary numerical results are provided as well.     

New Modified Function Method for Global Optimization

In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073.     

证券投资组合优化问题的强健性的锥优化方法(英文)

本文研究了具有强健性的证券投资组合优化问题.模型以最差条件在值风险为风险度量方法,并且考虑了交易费用对收益的影响.当投资组合的收益率概率分布不能准确确定但是在有界的区间内,尤其是在箱型区间结构和椭球区域结构内时,我们可以把具有强健性的证券投资组合优化问题的模型分别转化成线性规划和二阶锥规划形式.最后,我们用一个真实市场数据的算例来验证此方法.     

Convergence of the Augmented Lagrangian Method for Nonlinear Optimization Problems over Second-Order Cones

The paper analyzes the rate of local convergence of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Under the constraint nondegeneracy condition and the strong second order sufficient condition, we demonstrate that the sequence of iterate points generated by the augmented Lagrangian method locally converges to a local minimizer at a linear rate, whose ratio constant is proportional to 1/τ with penalty parameter τ not less than a threshold . Importantly and interestingly enough, the analysis does not require the strict complementarity condition. Supported by the National Natural Science Foundation of China under Project 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.