The Primal-Dual Second-Order Cone Approximations Algorithm for Symmetric Cone Programming

Given any open convex cone K, a logarithmically homogeneous, self-concordant barrier for K, and any positive real number r < 1, we associate, with each direction , a second-order cone containing K. We show that K is the interior of the intersection of the second-order cones , as x ranges over all directions in K. Using these second-order cones as approximations to cones of symmetric, positive definite matrices, we develop a new polynomial-time primal-dual interior-point algorithm for semidefinite programming. The algorithm is extended to symmetric cone programming via the relation between symmetric cones and Euclidean Jordan algebras.     

锥约束多目标规划的二阶对称对偶性质

给出一对锥约束多目标非线性规划的二阶对称对偶问题,以及二阶F凸函数类的概念.在二阶F凸假设下证明了真有效解的对偶性质———弱对偶性、强对偶性及逆对偶性.     

对称锥互补问题

对称锥互补问题是一类均衡优化,包括标准互补问题、二阶锥互补问题和半定互补问题等,近几年,人们借助欧几里德若当代数技术,在对称锥互补问题的研究方面获得了突破性进展并使之逐渐受到重视,本文主要从理论和算法两方面总结和评述这些新成果,同时,列出了相应的重要文献。     

A Primal-dual Interior-point Algorithm for Symmetric Cone Convex Quadratic Programming Based on the Commutative Class Directions

Acta Mathematicae Applicatae Sinica, English Series - In this paper, we present a neighborhood following primal-dual interior-point algorithm for solving symmetric cone convex quadratic programming...     

On Valid Inequalities for Mixed Integer p-Order Cone Programming

We discuss two families of valid inequalities for linear mixed integer programming problems with cone constraints of arbitrary order, which arise in the context of stochastic optimization with downside risk measures. In particular, we extend the results of Atamtürk and Narayanan (Math. Program., 122:1–20, 2010, Math. Program., 126:351–363, 2011), who developed mixed integer rounding cuts and lifted cuts for mixed integer programming problems with second-order cone constraints. Numerical experiments conducted on randomly generated problems and portfolio optimization problems with historical data demonstrate the effectiveness of the proposed methods.     

Central Paths in Semidefinite Programming, Generalized Proximal-Point Method and Cauchy Trajectories in Riemannian Manifolds

The relationships among the central path in the context of semidefinite programming, generalized proximal-point method and Cauchy trajectory in a Riemannian manifolds is studied in this paper. First, it is proved that the central path associated to a general function is well defined. The convergence and characterization of its limit point is established for functions satisfying a certain continuity property. Also, the generalized proximal-point method is considered and it is proved that the correspondingly generated sequence is contained in the central path. As a consequence, both converge to the same point. Finally, it is proved that the central path coincides with the Cauchy trajectory in a Riemannian manifold. This work was supported in part by CNPq Grant 302618/2005-8, by PRONEX(CNPq), CAPES-PICDT and FUNAPE/UFG.     

The <Emphasis Type="Italic">Q</Emphasis> Method for Symmetric Cone Programming

The Q method of semidefinite programming, developed by Alizadeh, Haeberly and Overton, is extended to optimization problems over symmetric cones. At each iteration of the Q method, eigenvalues and Jordan frames of decision variables are updated using Newton’s method. We give an interior point and a pure Newton’s method based on the Q method. In another paper, the authors have shown that the Q method for second-order cone programming is accurate. The Q method has also been used to develop a “warm-starting” approach for second-order cone programming. The machinery of Euclidean Jordan algebra, certain subgroups of the automorphism group of symmetric cones, and the exponential map is used in the development of the Newton method. Finally we prove that in the presence of certain non-degeneracies the Jacobian of the Newton system is nonsingular at the optimum. Hence the Q method for symmetric cone programming is accurate and can be used to “warm-start” a slightly perturbed symmetric cone program.     

On the Curvature of the Central Path of Linear Programming Theory

We prove a linear bound on the average total curvature of the central path of linear programming theory in terms of the number of independent variables of the primal problem, and independent of the number of constraints.     

Primal Newton Method for the Linear Cone Programming Problem

A linear cone programming problem containing among the constraints a second-order cone is considered. For solving this problem, a primal Newton method which is constructed with the help of the optimality conditions is proposed. Local convergence of this method is proven.     

对称锥互补问题的一个惩罚NR函数的水平有界性

建立了一个对称锥互补问题的惩罚自然剩余函数,基于一个若当代数迹不等式,在一个较弱条件下证明了其相应势函数的水平有界性.     

对称锥互补问题的一个惩罚NR函数(英文)

本文建立了一个对称锥互补问题的惩罚自然剩余函数,并且证明了单调情形下其相应势函数的水平有界性.     

On a Commutative Class of Search Directions for Linear Programming over Symmetric Cones

The commutative class of search directions for semidefinite programming was first proposed by Monteiro and Zhang (Ref. 1). In this paper, we investigate the corresponding class of search directions for linear programming over symmetric cones, which is a class of convex optimization problems including linear programming, second-order cone programming, and semidefinite programming as special cases. Complexity results are established for short-step, semilong-step, and long-step algorithms. Then, we propose a subclass of the commutative class for which we can prove polynomial complexities of the interior-point method using semilong steps and long steps. This subclass still contains the Nesterov–Todd direction and the Helmberg–Rendl–Vanderbei–Wolkowicz/Kojima–Shindoh–Hara/Monteiro direction. An explicit formula to calculate any member of the class is also given.     

多目标规划锥有效解的最优性条件

该文提出了广义锥凸向量函数以及向量函数关于锥八的下降、不变、非升、非降方向集等概念．在讨论它们的性质和判别条件的基础上，给出了决策可行集中的点为锥八一有效解的一系列充分必要条件．     

Stochastic Second-Order Cone Programming in Mobile Ad Hoc Networks

We propose a two-stage stochastic second-order cone programming formulation of the semidefinite stochastic location-aided routing (SLAR) model, described in Ariyawansa and Zhu (Q. J. Oper. Res. 4(3), 239–253, 2006). The aim is to provide a sender node S with an algorithm for optimally determining a region that is expected to contain a destination node D (the expected zone). The movements of the destination node are represented by ellipsoid scenarios, randomly generated by uniform and normal distributions in a neighborhood of the starting position of the destination node. By using a second-order cone model, we are able to solve problems with a much larger number of scenarios (20250) than it is possible with the semidefinite model (500). The use of a larger number of scenarios allows for the computation of a new expected zone, that may be very effective in practical applications, and for obtaining stability results for the optimal first-stage solutions and the optimal cost function values.     

非线性规划问题的二阶对称对偶性

本文讨论了二阶凸和二阶凹条件下的二阶对称对偶问题,并利用有效性和真有效性概念证明了弱对偶、强对偶、逆对偶及自对偶定理。     

Homogeneous Self-dual Algorithms for Stochastic Second-Order Cone Programming

Jin et al. (in J. Optim. Theory Appl. 155:1073–1083, 2012) proposed homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. In this paper, we utilize their work to derive homogeneous self-dual algorithms for stochastic second-order cone programs with finite event space. We also show how the structure in the stochastic second-order cone programming problems may be exploited so that the algorithms developed for these problems have less complexity than the algorithms developed for stochastic semidefinite programs mentioned above.     

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

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