Subgradient Algorithm on Riemannian Manifolds

The subgradient method is generalized to the context of Riemannian manifolds. The motivation can be seen in non-Euclidean metrics that occur in interior-point methods. In that frame, the natural curves for local steps are the geodesies relative to the specific Riemannian manifold. In this paper, the influence of the sectional curvature of the manifold on the convergence of the method is discussed, as well as the proof of convergence if the sectional curvature is nonnegative.     

Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds

In this paper, a notion of generalized gradient on Riemannian manifolds is considered and a subdifferential calculus related to this subdifferential is presented. A characterization of the tangent cone to a nonempty subset S of a Riemannian manifold M at a point x is obtained. Then, these results are applied to characterize epi-Lipschitz subsets of complete Riemannian manifolds.     

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题，引进加权中心路径的概念，并利用单目标半定规划的中心路径法，提出了求解多目标半定规划问题的加权中心路径法，先得型对一个叔向量的有效解，然后在此基础上，提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．     

Globally Convergent Optimization Algorithms on Riemannian Manifolds: Uniform Framework for Unconstrained and Constrained Optimization

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space R ⁿ (corresponding to constrained optimization) and the R ⁿ space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than R ⁿ , the new algorithms are very efficient. Convergence rates are obtained. Applications are discussed. This paper is based on part of the Ph.D Thesis of the author under the supervision of Professor Tits, University of Maryland, College Park, Maryland. The author is in debt to him for invaluable suggestions on earlier versions of this paper. The author is grateful to the Associate Editor and anonymous reviewers, who pointed out a number of papers that have been included in the references; they made also detailed suggestions that lead to significant improvements of the paper. Finally, the author thanks Dr. S.T. Smith for making available his Ph.D Thesis.     

Primal Central Paths and Riemannian Distances for Convex Sets

In this paper, we study the Riemannian length of the primal central path in a convex set computed with respect to the local metric defined by a self-concordant function. Despite some negative examples, in many important situations, the length of this path is quite close to the length of a geodesic curve. We show that in the case of a bounded convex set endowed with a ν-self-concordant barrier, the length of the central path is within a factor O(ν ^1/4) of the length of the shortest geodesic curve. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming.     

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.     

Local Minima and Convergence in Low-Rank Semidefinite Programming

The low-rank semidefinite programming problem LRSDP_r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP_r via the nonconvex change of variables X=RR^T. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.     

Exterior Minimum-Penalty Path-Following Methods in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.     

Sufficiency and Duality in Multiobjective Programming under Generalized Type I Functions

In this paper, new classes of generalized (F,α,ρ,d)-V-type I functions are introduced for differentiable multiobjective programming problems. Based upon these generalized convex functions, sufficient optimality conditions are established. Weak, strong and strict converse duality theorems are also derived for Wolfe and Mond-Weir type multiobjective dual programs.     

求解非线性等式和不等式约束优化问题的三项记忆梯度广义投影算法

利用广义投影矩阵，对求解无约束规划的三项记忆梯度算法中的参数给一条件，确定它们的取值范围，以保证得到目标函数的三项记忆梯度广义投影下降方向，建立了求解非线性等式和不等式约束优化问题的三项记忆梯度广义投影算法，并证明了算法的收敛性．同时给出了结合FR，PR，HS共轭梯度参数的三项记忆梯度广义投影算法，从而将经典的共轭梯度算法推广用于求解约束规划问题．数值例子表明算法是有效的．     

Cost,Revenue and Profit Efficiency Models in Generalized Fuzzy Data Envelopment Analysis

One of the most important information given by data envelopment analysis models is the cost, revenue and profit efficiency of decision making units (DMUs). Cost efficiency is defined as the ratio of minimum costs to current costs, while revenue efficiency is defined as the ratio of maximum revenue to current revenue of the DMU. This paper presents a framework where data envelopment analysis (DEA) is used to measure cost, revenue and profit efficiency with fuzzy data. In such cases, the classical models cannot be used, because input and output data appear in the form of ranges. When the data are fuzzy, the cost, revenue and profit efficiency measures calculated from the data should be uncertain as well. Fuzzy DEA models emerge as another class of DEA models to account for imprecise inputs and outputs for DMUs. Although several approaches for solving fuzzy DEA models have been developed, numerous deficiencies including the $\alpha$-cut approaches and types of fuzzy numbers must still be improved. This scheme embraces evaluation method based on vector for proposed fuzzy model. This paper proposes generalized cost, revenue and profit efficiency models in fuzzy data envelopment analysis. The practical application of these models is illustrated by a numerical example.     

Generalized (η,ρ)-Invex Functions and Semiparametric Duality Models for Multiobjective Fractional Programming Problems Containing Arbitrary Norms

In this paper, we construct several semiparametric duality models and prove appropriate duality theorems under various generalized (η,ρ)-invexity assumptions for a multiobjective fractional programming problem involving arbitrary norms.     

广义逆ATS^（2）的表示与逼近

给出了广义逆AT,S(2)的一个新的表示式．由此建立了基于两个特殊的Hermite插值多项式的广义逆迭代计算格式,数值例子说明方法是可行的．