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

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

一类二层凸规划的对偶二层规划

本文讨论上层目标函数以下层子系统目标函数的最优值作为反馈的一类二层凸规划的对偶规划问题 ,在构成函数满足凸连续可微等条件的假设下 ,建立了二层凸规划的 Lagrange对偶二层规划 ,并证明了基本对偶定理 .     

一类反凸规划的全局新算法

§1.引言 到目前为止,大多数非线性规划的有效算法都是寻求它的局部最优解,由于很难判断一个局部解是否就是一个全局解,全局规划的研究是个困难问题,反凸规划由于其可行域的非凸性甚至非连通性,目前有效算法更少。 [1]已经指出很容易把D.C.规划(即目标函数和约束函数均为二个凸函数之差)转化成为一个目标函数为线性的反凸规划:     

由方向导数表述的对偶问题

本文利用扰动函数的方向导数引进凸规划的一个新的对偶问题，并证明了相应的对偶性．     

混凝土重力坝多参数弹性位移反演分析不唯一性理论探讨

反演分析是现场监测⁃反演分析⁃工程实践检验⁃正演分析及预测的闭环系统的重要环节,而参数反分析是工程实践中研究最多的反分析问题.针对混凝土重力坝多参数反演分析是否具有唯一性,基于均质地基上重力坝在水压力作用下的位移解析解建立目标函数,进而以目标函数和非空凸集构建一个凸规划问题,然后通过分析目标函数的Hesse矩阵是否是正定矩阵,验证目标函数是否是严格凸函数,从而辨识构建的凸规划问题是否具有唯一全局极小点.对坝体和岩基弹性参数的不同组合方案分析表明,当采用理论值与实测值的差值的l1范数作为目标函数时,目标函数的Hesse矩阵均不能保证为正定矩阵,即混凝土重力坝多参数弹性位移反演分析凸规划问题不具有唯一全局极小点,反演分析不唯一.     

B-(p,γ)-不变凸规划的最优性条件及混合型对偶

函数的广义凸性在数学规划及数学规划的对偶理论中起着非常重要的作用.在一种函数的广义凸性-关于n和b的B-(p,γ)-不变凸性的假设下,讨论了一类含有无穷多分式函数的约束广义分式规划及其对偶的某些问题:首先,给出并证明了这类约束广义分式规划的一个最优性充分条件,接着,针对这一类广义分式规划,提出了它的一个混合型对偶,然后又在适当的条件下,进一步给出并证明了相应的弱对偶定理,强对偶定理以及严格逆对偶定理.     

求解凸随机规划的Monte Carlo模拟方法

基于对目标函数和约束函数的同时抽样,给出求解凸随机规划的Monte CaLrlo模拟的算法及其收敛性.将得到的结果和算法应用到以半偏差为约束的投资组合优化问题,并且给出相应的数值试验.     

凸二次半定规划一个长步原始对偶路径跟踪算法

本文基于Nesterov-Todd方向,并引进中心路径测量函数以及原始对偶对数障碍函数,建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O(n|lnε|)次可得到一个ε最优解.论文最后报告了初步的数值试验结果.     

E凸规划问题解集的刻画

考虑一类重要的广义凸规划问题E凸规划. 在E凸集中定义了关于E凸函数的E-Gateaux微分概念, 证明了E凸函数 的E-Gateaux微分的几个特征性质,并利用这些特征性质,提出了E凸规划问题解集的等价刻画. 在赋范向量空间中,对于一个目标函数在最优解处E-Gateaux可微的E凸规划问题而言,它的解集是由位于超平面内的可行解组成的,这些可行解的法向量就是目标函数在给定最优解处的E-Gateaux微分.     

一致不变凸多目标规划的有效性条件和对偶性

作者对多目标规划引进一致不变凸的概念,用来综合规划所涉及函数的不变凸性,而不是用单个函数的不变凸性.考虑了涉及这样函数的多目标规划解的有效性和Mond-Weir对偶性.     

A sufficient condition for self-concordance,with application to some classes of structured convex programming problems

Recently a number of papers were written that present low-complexity interior-point methods for different classes of convex programs. The goal of this article is to show that the logarithmic barrier function associated with these programs is self-concordant. Hence the polynomial complexity results for these convex programs can be derived from the theory of Nesterov and Nemirovsky on self-concordant barrier functions. We also show that the approach can be applied to some other known classes of convex programs.This author's research was supported by a research grant from SHELL.On leave from the Eötvös University, Budapest, Hungary. This author's research was partially supported by OTKA No. 2116.     

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 New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

Limiting behavior of the affine scaling continuous trajectories for linear programming problems

We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called centered optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Sequential convexification in reverse convex and disjunctive programming

This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.The research underlying this report was supported by Grant ECS-8601660 of The National Science Foundation and Contract N00014-85-K-0198 with the Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.On leave from the University of Aarhus, Denmark.     

A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.     

Line Search Techniques for the Logarithmic Barrier Function in Quadratic Programming

In this paper, we propose a line-search procedure for the logarithmic barrier function in the context of an interior point algorithm for convex quadratic programming. Preliminary testing shows that the proposed procedure is superior to some other line-search methods developed specifically for the logarithmic barrier function in the literature.     

Penalty and Barrier Methods for Convex Semidefinite Programming

In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.     

凸二次交叉规划的等价形式

利用参数规划逆问题考虑凸二次交叉规划与多目标规划的关系 ,把交叉规划转变为同变量规划组 ,再把同变量规划组变为多目标规划 ,证明了凸二次交叉规划的均衡解与多目标规划的最优解的关系。