向量映射的鞍点和Lagrange对偶问题

本文研究拓扑向量空间广义锥-次类凸映射向量优化问题的鞍点最优性条件和Lagrange对偶问题,建立向量优化问题的Fritz John鞍点和Kuhn-Tucker鞍点的最优性条件及其与向量优化问题的有效解和弱有效解之间的联系。通过对偶问题和向量优化问题的标量化刻画各解之间的关系,给出目标映射是广义锥-次类凸的向量优化问题在其约束映射满足广义Slater约束规格的条件下的对偶定理。     

不具有关于锥的例外簇的映射

给出Hilbert空间到其自身不具有关于锥的例外族的映射条件，利用Hilbert空间可表为闭凸锥与负对偶锥的特点研究映射关于锥的例外簇的特性，证明了可通过映射在某紧凸子集上的性态判断其例外簇的存在与否，并讨论单调和沿射线单调映射的不具例外簇问题。     

The Γ-algorithm and some applications

In this paper the power of the Γ-algorithm for obtaining the dual of a given cone and some of its multiple applications is discussed. The meaning of each sequential tableau appearing during the process is interpreted. It is shown that each tableau contains the generators of the dual cone of a given cone and that the algorithm updates the dual cone when new generators are incorporated. This algorithm, which is based on the duality concept, allows one to solve many problems in linear algebra, such as determining whether or not a vector belongs to a cone, obtaining the minimal representations of a cone in terms of a linear space and an acute cone, obtaining the intersection of two cones, discussing the compatibility of linear systems of inequalities, solving systems of linear inequalities, etc. The applications are illustrated with examples.     

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.     

Space tensor conic programming

Space tensors appear in physics and mechanics. Mathematically, they are tensors in the three-dimensional Euclidean space. In the research area of diffusion magnetic resonance imaging, convex optimization problems are formed where higher order positive semi-definite space tensors are involved. In this short paper, we investigate these problems from the viewpoint of conic linear programming (CLP). We characterize the dual cone of the positive semi-definite space tensor cone, and study the CLP formulation and the duality of positive semi-definite space tensor conic programming.     

向量均衡问题的超有效性的对偶形式

在局部凸空间中引进了向量均衡问题的强超有效解、C-强超有效解、弱超有效解, C-弱超有效解、齐次超有效解、 C-齐次超有效解的概念,并在局部凸空间中用极理论为工具讨论了向量均衡问题的 C-弱超有效解, C-超有效解, C-齐次超有效解,以及C-强超有效解的对偶形式. 又在赋范线性空间中讨论了向量均衡问题的以上各种超有效解之间的等价性,并且在赋范线性空间具正规锥的条件下讨论了向量均衡问题的以上各种超有效解的对偶形式. 作为它的应用,给出了向量优化问题各种超有效解的对偶形式.     

Cones of multipowers and combinatorial optimization problems

The cone of multipowers is dual to the cone of nonnegative polynomials. The relation of the former cone to combinatorial optimization problems is examined. Tensor extensions of polyhedra of combinatorial optimization problems are used for this purpose. The polyhedron of the MAX-2-CSP problem (optimization version of the two-variable constraint satisfaction problem) of tensor degree 4k is shown to be the intersection of the cone of 4k-multipowers and a suitable affine space. Thus, in contrast to SDP relaxations, the relaxation to a cone of multipowers becomes tight even for an extension of degree 4.     

New results on the cp-rank and related properties of co(mpletely )positive matrices

Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This paper establishes some new relations between orthogonal pairs of such matrices lying on the boundary of either cone. As a consequence, we can establish an improvement on the upper bound of the cp-rank of completely positive matrices of general order and a further improvement for such matrices of order six.     

赋β-范空间中的最佳逼近问题

This paper deals with the problems of best approximation in β-normed spaces.With the tool of conjugate cone introduced in [1] and via the Hahn-Banach extension theorem of β-subseminorm in [2],the characteristics that an element in a closed subspace is the best approximation are given in Section 2.It is obtained in Section 3 that all convex sets or subspaces of a β-normed space are semi-Chebyshev if and only if the space is itself strictly convex.The fact that every finite dimensional subspace of a strictly convex β-normed space must be Chebyshev is proved at last.     

锥Pf的若干性质

利用实赋范线性空间E上非零连续线性泛函f,确定了E上半序关系和锥Pf,证明了锥Pf的几个性质,给出了H ilbert空间中Pf的对偶锥的表现形式及由Pf确定的H ilbert投影距离与T hom pson距离.     

A dual dynamic programming for minimax optimal control problems governed by parabolic equation

In the article, minimax optimal control problems governed by parabolic equations are considered. We apply a new dual dynamic programming approach to derive sufficient optimality conditions for such problems. The idea is to move all the notions from a state space to a dual space and to obtain a new verification theorem providing the conditions, which should be satisfied by a solution of the dual partial differential equation of dynamic programming. We also give sufficient optimality conditions for the existence of an optimal dual feedback control and some approximation of the problem considered, which seems to be very useful from a practical point of view.     

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.     

赋$\beta$-范空间中的最佳逼近问题

本文讨论赋$\beta$-范空间中的最佳逼近问题.以[1]引进的共轭锥为工具,借助[2]中关于$\beta$-次半范的Hahn-Banach延拓定理,第二节给出赋$\beta$-范空间的闭子空间中最佳逼近元的特征,第三节得到赋$\beta$-范空间中任何凸子集或子空间均为半Chebyshev集的充要条件是空间本身严格凸,文章最后证明了严格凸的赋$\beta$-范空间中任何有限维子空间都是Chebyshev集.     

Generalized tangent cone and an optimization problem in a normed space

Most abstract multiplier rules in the literature are based on the tangential approximation at a point to some set in a Banach space. The present paper is concerned with the study of a generalized tangent cone, which is a tangential approximation to that set at a common point of two sets. The new notion of tangent cone generalizes previous concepts of tangent cones. This generalized tangent cone is used to characterize the optimality conditions for a simultaneous maximization and minimization problem. The paper is of theoretical character; practical applications are not found so far.     

Factor normal wedges of semi-ordered spaces

A concept of a factor normal cone in a linear topological space is introduced and basic properties of semiordered spaces possessing a positive factor normal cone are studied. The main aim of the paper is to investigate topologies of semiordered spaces whose dual positive cone in the conjugate space is factor normal.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

Approximation of the Fourier Transform and the Dual Gabor Window

Many results and problems in Fourier and Gabor analysis are formulated in the continuous variable case, i.e., for functions on . In contrast, a suitable setting for practical computations is the finite case, dealing with vectors of finite length. We establish fundamental results for the approximation of the continuous case by finite models, namely, the approximation of the Fourier transform and the approximation of the dual Gabor window of a Gabor frame. The appropriate function space for our approach is the Feichtinger space S₀. It is dense in L², much larger than the Schwartz space, and it is a Banach space.     

Inverse final observation problems for Maxwell’s equations in the quasi-stationary magnetic approximation and stable sequential Lagrange principles for their solving

An initial–boundary value problem for Maxwell’s equations in the quasi-stationary magnetic approximation is investigated. Special gauge conditions are presented that make it possible to state the problem of independently determining the vector magnetic potential. The well-posedness of the problem is proved under general conditions on the coefficients. For quasi-stationary Maxwell equations, final observation problems formulated in terms of the vector magnetic potential are considered. They are treated as convex programming problems in a Hilbert space with an operator equality constraint. Stable sequential Lagrange principles are stated in the form of theorems on the existence of a minimizing approximate solution of the optimization problems under consideration. The possibility of applying algorithms of dual regularization and iterative dual regularization with a stopping rule is justified in the case of a finite observation error.     

0-1多项式规划问题的SDP松弛方法(英)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.