Calculating the cone of directions of constancy

This note presents an algorithm that finds the cone of directions of constancy of a differentiable, faithfully convex function.This work was supported by the National Research Council of Canada. The author is indebted to Professor S. Zlobec for suggesting the topic and for his guidance.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

Existence of Global Minima for Constrained Optimization

We present a unified approach to establishing the existence of global minima of a (non)convex constrained optimization problem. Our results unify and generalize previous existence results for convex and nonconvex programs, including the Frank-Wolfe theorem, and for (quasi) convex quadratically constrained quadratic programs and convex polynomial programs. For example, instead of requiring the objective/constraint functions to be constant along certain recession directions, we only require them to linearly recede along these directions. Instead of requiring the objective/constraint functions to be convex polynomials, we only require the objective function to be a (quasi)convex polynomial over a polyhedral set and the constraint functions to be convex polynomials or the composition of coercive functions with linear mappings.We thank Professor Dimitri Bertsekas for his comments and support in the writing of this paper.     

A simplified test for optimality

A simplification of recent characterizations of optimality in convex programming involving the cones of decrease and constancy of the objective and constraint functions is presented. In the original characterization due to Ben-Israelet al., optimality was verified or a feasible direction of decrease was determined by considering a number of sets equal to the number of subsets of the set of binding constraints. By first finding the set of constraints which is binding at every feasible point, it is possible to verify optimality or determine a feasible direction of decrease by considering a single set. In the case of faithfully convex functions, this set can be found by solving at mostp systems of linear equations and inequalities, wherep is the number of constraints.This work was partly supported by NSF Grant No. Eng 76-10260.     

Biconjugate directions

It is shown that the generalization of the conjugate direction method of Van Wyk (Ref. 1) is the direction counterpart to Fletcher's biconjugate gradient algorithm (Ref. 2).     

K-Drop凸空间与局部K-Drop凸空间

引入了Banach空间的局部k-drop凸性质，研究了k-drop凸与局部k-drop凸的一些性质以及两者之间的关系，并用单位球的切片统一而简洁地处理了这两个性质．     

非常极凸空间

本文使用非常极凸的定义，证明了非常极凸和非常光滑是互为对偶空间且严格介于弱k凸和非常凸之间的空间，最后得到了非常极凸的一些特征．     

度量凸函数的延拓

每个度量空间都能等距嵌入到实Banach空间,所以度量凸函数可视为Banach空间子集上的函数．本文举出反例说明不是所有度量凸函数都能延拓为凸函数,并给出度量凸函数能延拓为凸函数的充分条件．     

A new approach to the analysis of random methods for detecting necessary linear inequality constraints

A new approach is given for the analysis of random methods for detecting necessary constraints in systems of linear inequality constraints. This new approach directly accounts for the fact that two constraints are detected as necessary (hit) at each iteration of a random method. The significance of this two-hit analysis is demonstrated by comparing it with the usual one-hit analysis.     

交替最小化算法求解强凸函数与弱凸函数和的极小值问题

交替最小化算法(简称AMA)最早由[SIAM J.Control Optim.,1991,29(1):119-138]提出,并能用于求解强凸函数与凸函数和的极小值问题.本文直接利用AMA算法来求解强凸函数与弱凸函数和的极小值问题.在强凸函数的模大于弱凸函数的模的假设下,我们证明了AMA生成的点列全局收敛到优化问题的解,并且若该优化问题中的某个函数是光滑函数时,AMA所生成的点列的收敛率是线性的.     

关于亚纯代数体函数奇异方向的存在性

本文证明了如下结果:对于有穷正级亚纯代数体函数,一定存在一条奇异方向L∶arg z=θ0(0≤θ0＜2π),使得对于任意δ∈(0,π/2),在角域Δ(θ0,δ)内,对任意复数a,对任意ε＞0,有∑i1|zi(a;Δ(θ0,δ))|σ=∞(σ等于ρ或ρ-ε)至多有2v个例外a值.     

An algorithm for the minimax weber problem

The paper presents an algorithm for finding the weighted absolute center of a given set of points in the Euclidean plane.The algorithm is a specialized implementation of the method of feasible directions.The presentation includes a proof of convergence as well as computational experience.     

N元Stolarsky平均的凸性和几何凸性

讨论了n个正数的Stolarsky平均的S-凸性和S-几何凸性,证明了:n元Stolarsky平均在r>1时是S-凸的和S-几何凸的;在r<1时是S-凹的.作为推论,此文也比较了n个正数的Stolarsky平均和算术平均的大小.     

关于凸曲面的几个定义的关系

本文讨论了凸曲面的几种定义及其关系，发现有的定义是局部凸的定义，有的是整体凸的定义，有的则对于局部凸和整体凸都适合，最后给出了各种定义之间互推的证明，对于局部凸和整体凸定义之间不能推证的，则说明了原因．     

An O(n log n) algorithm for the convex bipartite matching problem

An efficient algorithm to solve the maximum cardinality matching problem in convex bipartite graphs is presented. In the algorithm use is made of a special data structure based on a binary heap.     

A feasible direction method for linear programming

We discuss a finite method of a feasible direction for linear programming problems. The method begins with a feasible basic vector for the problem, constructs a profitable direction to move using the updated column vectors of the nonbasic variables eligible to enter this basic vector. It then moves in this direction as far as possible, while retaining feasibility. This move in general takes it though the relative interior of a face of th set of a feasible solutions. The final point, $\text{x}$, obtained at the end of this move will not in general be a basic solution. Using $\text{x}$ the method then constructs a basic feasible solution at which the objective value is better than, or the same as that at $\text{x}$. The whole process repeats with the new basic feasible solution. We show that this method can be implemented using basis inverses. Initial computer runs of this method in comparison with the usual edge following primary simplex algorithms are very encouraging.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.      

An elementary new proof of the determination of a convex function by its subdifferential

Rockafellar proved that any closed, convex function is uniquely determined by its subdifferential mapping up to an additive constant. The aim of this article is to provide an elementary proof of the same result.