互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数-对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

凸二次-线性双层规划的共轭对偶及其性质

研究具有一般形式的凸二次-线性双层规划问题。讨论了这类双层规划问题的DC规划等价形式,利用DC规划共轭对偶理论,提出了凸二次-线性双层规划的共轭对偶规划,并给出相应的对偶性质。     

关于对偶问题及对偶性质

本文考虑非可微凸规划的一个对偶问题，它使用目标函数的扰动函数的次微分及外法向量锥，它不同于已知结果．我们给出相应的对偶性质．     

求最优权对集的一个对偶算法

1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。     

一类特殊DC规划的对偶性

根据共轭函数和DC规划的性质，给出一类特殊DC规划的共轭对偶并讨论其对偶规划的特殊性质，然后利用该性质，把对这类特殊DC规划的求解转化为对一个凸规划的求解。     

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

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

区间数互补判断矩阵的性质及相关问题研究

研究了区间数互补判断矩阵的性质问题。利用区间数互反判断矩阵与区间数互补判断矩阵之间的转换关系，给出了乘性一致性与加性一致性区间数互补判断矩阵的定义，并研究了一致性区间数判断矩阵的一些特殊性质；同时给出了区间数互补判断矩阵满意一致性的一个简单的判断方法与算法。文章的最后，通过一个例子来说明这个算法的有效性。     

单位球上的对偶Toeplitz算子

本文研究了单位球Bergman空间的直交补上的对偶Toeplitz算子的代数性质,首先我们给出了对偶Toeplitz算子的有界性和紧性的完全刻画,然后给出对偶Toeplitz算子的谱性质,最后证明了不存在以有界全纯或者反全纯函数为符号的拟正规对偶Toeplitz算子.     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

Parallel bundle-based decomposition for large-scale structured mathematical programming problems

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.     

Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

Using the parametric approach to solve the continuous-time linear fractional max–min problems

A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm.     

Conic approximation to quadratic optimization with linear complementarity constraints

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

Efficient algorithms for buffer space allocation

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms.     

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.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

The exact penalty map for nonsmooth and nonconvex optimization

Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets.