带锥约束多目标规划问题的高阶Wolfe逆对偶

本文对带锥约束多目标规划问题提出一个新的高阶Wolfe逆对偶定理,该结果克服了Kim等(2010)的文章中高阶Wolfe逆对偶定理的缺陷.     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

群体多目标最优化的Lagrange对偶性

本文建立了目标和约束为不对称的群体多目标最优化问题的Lagrange对偶规划，在问题的联合弱有效解意义下，得到群体多目标最优化Lagrange型的弱对偶定理、基本对偶定理、直接对偶定理和逆对偶定理。     

一类锥约束多目标优化问题的高阶对偶研究

在一类锥约束单目标优化问题的一阶对偶模型基础之上,建立了锥约束多目标优化问题的二阶和高阶对偶模型.在广义凸性假设下,给出了弱对偶定理,在Kuhn-Tucker约束品性下,得到了强对偶定理.最后,在弱对偶定理的基础上,利用Fritz-John型必要条件建立了逆对偶定理.     

半无限规划与方向导数

本文对半无限凸规划提出一个用方向导数表述的对偶问题，其对偶间隙为零．     

二阶锥线性互补问题内点法的复杂性

本文提出一个二阶锥线性互补问题的长步原始对偶内点法,搜索方向由一个一般的核函数来定义.如果给出初始的严格内点,可以得到本算法的复杂性为O((1+2k)llog(lμ0/ε)).     

关于分次自对偶

本文讨论非交换分次环上的纲性分次自对偶与其初始子环上的自对偶之间的关系.     

机器学习中的最优化模型与对偶

数学最优化是以数学的方式来刻画和找出问题最优解的一门学科.机器学习利用数据构造预测方法,并对这些方法进行研究.介绍了机器学习中与支持向量机和稀疏重构相关的最优化模型.在此基础上,给出了三个典型最优化模型的对偶问题,并详细地讨论了对偶在求解这些问题中的应用.     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

存贮问题的优化算法

本文根据经济模型的特殊结构,利用对偶线性规划的理论和其它技巧,简化求解过程,有利于模型的普及应用.     

Using a Conic Formulation for Finding Steiner Minimal Trees

We present a new mathematical programming formulation for the Steiner minimal tree problem. We relax the integrality constraints on this formulation and transform the resulting problem (which is convex, but not everywhere differentiable) into a standard convex programming problem in conic form. We consider an efficient computation of an ε-optimal solution for this latter problem using an interior-point algorithm.     

解新锥模型信赖域子问题的折线法

本文以新锥模型信赖域子问题的最优性条件为理论基础,认真讨论了新子问题的锥函数性质,分析了此函数在梯度方向及与牛顿方向连线上的单调性.在此基础上本文提出了一个求解新锥模型信赖域子问题折线法,并证明了这一子算法保证解无约束优化问题信赖域法全局收敛性要满足的下降条件.本文获得的数值实验表明该算法是有效的.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

A new approach to the weighted peak-constrained least-square error FIR digital filter optimal design problem

This paper deals with the design of linear-phase finite impulse response (FIR) digital filters using weighted peak-constrained least-squares (PCLS) optimization. The PCLS error design problem is formulated as a quadratically constrained quadratic semi-infinite programming problem. An exchange algorithm with a new exchange rule is proposed to solve the problem. The algorithm provides the approximate optimal solution after a finite number of iterations. In particular, the subproblem solved at each iteration is a quadratically constrained quadratic programming. We can rewrite it as a conic optimization problem solvable in polynomial time. For illustration, numerical examples are solved using the proposed algorithm.     

Cascading: an adjusted exchange method for robust conic programming

It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust conic problem.      

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.     

Analysis of a smoothing method for symmetric conic linear programming

This paper proposes a smoothing method for symmetric conic linear programming (SCLP). We first characterize the central path conditions for SCLP problems with the help of Chen-Harker-Kanzow-Smale smoothing function. A smoothing-type algorithm is constructed based on this characterization and the global convergence and locally quadratic convergence for the proposed algorithm are demonstrated.     

Facial Reduction Algorithms for Conic Optimization Problems

In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems.