Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

Implementation of a subgradient projection algorithm

This paper discusses the implementation of an algorithm due to Sreedharan [8] for the minimization, subject to linear constraints, of an objective function composed of the sum of a piecewise-affine, convex function with a smooth, strictly convex function. Successful techniques for two subproblems arising in the algorithm, a projection problem and a line search problem, are described in detail. Computational experience with the algorithm on several test problems is presented.     

基于凸集论的稠密视差图优化算法

针对计算机视觉领域中立体匹配算法在图像无纹理区产生的误匹配问题,提出以全变差函数为凸约束集,使用次梯度投影法,对通过初始视差变换后的立体图像对之间的像素误差函数和视差二次平滑因子形成的严格凸函数进行求解,寻求立体图像对之间的最优视差图。实验结果表明,该方法不仅能保留初始视差图的边缘,而且减少了由先前立体匹配算法求得的视差图在无纹理区产生的误匹配点,取得了良好的视差图优化效果。     

VC环境下Delaunay三角剖分算法的设计及实现

三角剖分算法在计算机图形学、模式识别等方面有重要的作用．本文以VisualC＋＋为平台实现空间离散点的三角剖分．重建方法采用的是Bowyer—Watson算法来生成Delaunay三角网,并改进了其点定位搜索策略,还提出了一种新的数据结构,提高了三角剖分程序的执行效率,最后给出了此算法在双日立体视觉中的应用．     

一种子载波配对和功率分配联合最优算法

在基于正交频分复用的多载波两跳中继系统中有两个关键的问题亟需解决:子载波间的功率分配和子载波配对.子载波功率分配和配对之间存在复杂的耦合关系,通过现有的方法对子载波功率分配和配对进行联合优化比较困难.在深入研究这种耦合关系的基础上,针对解码转发,利用凸优化思想,提出一种功率受限下的子载波配对和功率分配联合最优算法.仿真结果表明,本算法可以有效提升中继系统的系统容量.     

关于凸集的一些性质

考虑微分包含的选择问题时,对于微分包含里的集值映射F,其像集一般要求为具有非空内部的紧凸集。文章主要讨论了具有非空内部的紧凸集与其重心之间的关系,并进而给出了紧凸集的广义重心以及关于函数的重心与紧凸集的关系。     

基于可见性约束的自动表面重构算法研究

提出了一种基于可见性约束的自动表面重构算法.此算法首先介绍了一种通过插入法实现的3维Delaunay三角网自动重构算法,然后利用给定的离散点,构建包围所有点的凸包.在完成初始的Delaunay三角剖分基础上,提出了利用特征点在影像中的可见性信息,对初始的3维模型进行修正,从而得到物体的实际表面模型.实验结果表明,该方法是有效的.     

格序群的本质子群

G是一个格序群（简称l-群），C（G）是G的凸l-子群格。E∈C（G）称为本质的，如果对于A↓∈C（G），且E∩C=0,则C=0。本文通过本质子群的刻划，研究了本质子群的特征及由本质子群所决定的l-群的结构。     

关于凸性模的一点注记

证明了Banach空间X的凸系数ε0(X)=sup{ε>0:δα(ε)=O}对于每一个α∈(0,1)成立,其中δαx(ε)=inf{1-‖αtx+(1-α)y‖;‖x‖≤1,‖y‖≤1,‖x-y‖≥ε}.同时,计算了6::(8).     

Computationally Efficient Algorithm For Frequency‐Weighted Optimal H∞ Model Reduction

In this paper, a frequency‐weighted optimal H_∞ model reduction problem for linear time‐invariant (LTI) systems is considered. The objective of this class of model reduction problems is to minimize H_∞ norm of the frequency‐weighted truncation error between a given LTI system and its lower order approximation. A necessary and sufficient solvability condition is derived in terms of LMIs with one extra coupling rank constraint, which generally leads to a non‐convex feasibility problem. Moreover, it has been shown that the reduced‐order model is stable when both stable input and output weights are included, and its state‐space data are given explicitly by the solution of the feasibility problem. An efficient model reduction scheme based on cone complementarity algorithm (CCA) is proposed to solve the non‐convex conditions involving rank constraint.