参数规划中最优值函数的次线性及齐次拟凹凸性

本文主要对参数最优化问题P(u): max f(x,u) s.t.x∈C(u) 的最优值函数的次线性和齐次拟凹凸性进行了系统研究,同时还探讨了通过特殊化P(u)的目标函数或约束条件而得到的其它几个参数最优化问题。许多新结果对一般的抽象空间,如线性空间、线性拓扑空间、线性赋范空间或Banach空间等亦是有效的。有关结论可应用于许多最优控制问题和经济数学,也可应用到分式规划的研究中去。     

ON THE CONVEXITY OF VALUE FUNCTIONS FOR A CERTAIN CLASS OF STOCHASTIC DYNAMIC PROGRAMMING PROBLEM

It is a common practice in stochastic dynamic programming problems to assume a priori that the value function is either concave or convex and later verify this assumption after the value function has been identified. It is often a difficult task to establish the concavity or convexity of the value function directly. In this paper, we prove that the value function of a certain type of infinite horizon stochastic dynamic programming problem is convex. This type of value function arises frequently in economic modeling.     

Monotonicity and convexity properties of matrix Riccati equations

Using a Fréchet-derivative-based approach some monotonicity,convexity/concavity and comparison results concerning strictlyunmixed solutions of continuous- and discrete-time algebraicRiccati equations are obtained; it turns out that these solutionsare isolated and smooth functions of the input data. Similarly,it is proved that the solutions of initial value problems forboth Riccati differential and difference equations are smoothand monotonic functions of the input data and of the initial value. They are also convex or concave functions with respectto certain matrix coefficients.     

Geometrically concave univariate distributions

In this paper our aim is to show that if a probability density function is geometrically concave (convex), then the corresponding cumulative distribution function and the survival function are geometrically concave (convex) too, under some assumptions. The proofs are based on the so-called monotone form of l'Hospital's rule and permit us to extend our results to the case of the concavity (convexity) with respect to Hölder means. To illustrate the applications of the main results, we discuss in details the geometrical concavity of the probability density function, cumulative distribution function and survival function of some common continuous univariate distributions. Moreover, at the end of the paper, we present a simple alternative proof to Schweizer's problem related to the Mulholland's generalization of Minkowski's inequality.     

Finitely convergent cutting planes for concave minimization

In 1964 Tuy introduced a new type of cutting plane, the concavity cut, in the context of concave minimization. These cutting planes, which are also known as convexity cuts, intersection cuts and Tuy cuts, have found application in several algorithms, e.g., branch and bound algorithm, conical algorithm and cutting plane algorithm, and also in algorithms for other optimization problems, e.g., reverse convex programming, bilinear programming and Lipschitzian optimization. Up to now, however, it has not been possible to either prove or disprove the finite convergence of a pure cutting plane algorithm for concave minimization based solely on these cutting planes. In the present paper a modification of the concavity cut is proposed that yields deeper cutting planes and ensures the finite convergence of a pure cutting plane algorithm based on these cuts.     

非可微参数规划极值函数方向导数的表示

参数规划的极值函数一般是非可微的且没有显示表示。为了讨论极值函数的变化性质，研究其方向导数有重要作用。本文对两类非可微函数（凸函数和拟可微函数）构成的参数规划问题的极值函数，给出了其普通方向导数的等式表示。     

An optimal adaptive algorithm for the approximation of concave functions

Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case. This work was partially supported by NSERC (Canada) and FCAR (Québec).     

An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality

We treat a concave programming problem with a compact convex feasible set. Assuming the differentiability of the convex functions which define the feasible set, we propose two solution methods. Those methods utilize the convexity of the feasible set and the property of the normal cone to the feasible set at each point over the boundary. Based on the proposed two methods, we propose a solution algorithm. This algorithm takes advantages over classical methods: (1) the obtained approximate solution is always feasible, (2) the error of such approximate value can be evaluated properly for the optimal value of such problem, (3) the algorithm does not have any redundant iterations.     

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Saddle-Point Optimality: A Look Beyond Convexity

The fact that two disjoint convex sets can be separated by a plane has a tremendous impact on optimization theory and its applications. We begin the paper by illustrating this fact in convex and partly convex programming. Then we look beyond convexity and study general nonlinear programs with twice continuously differentiable functions. Using a parametric extension of the Liu-Floudas transformation, we show that every such program can be identified as a relatively simple structurally stable convex model. This means that one can study general nonlinear programs with twice continuously differentiable functions using only linear programming, convex programming, and the inter-relationship between the two. In particular, it follows that globally optimal solutions of such general programs are the limit points of optimal solutions of convex programs.     

Some Farkas-type results for fractional programming problems with DC functions

For a kind of fractional programming problem that the objective functions are the ratio of two DC (difference of convex) functions with finitely many convex constraints, in this paper, its dual problems are constructed, weak and strong duality assertions are given, and some sufficient and necessary optimality conditions which characterize their optimal solutions are obtained. Some recently obtained Farkas-type results for fractional programming problems that the objective functions are the ratio of a convex function to a concave function with finitely many convex constraints are the special cases of the general results of this paper.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Fixed point theorems of ? convex −ψ concave mixed monotone operators and applications

In this paper, ? convex −ψ concave mixed monotone operators are introduced and some new existence and uniqueness theorems of fixed points for mixed monotone operators with such convexity concavity are obtained. As an application, we give one example to illustrate our results.     

On the uniqueness of Cournot equilibrium in case of concave integrated price flexibility

We consider a class of homogeneous Cournot oligopolies with concave integrated price flexibility and convex cost functions. We provide new results about the semi-uniqueness and uniqueness of (Cournot) equilibria for the oligopolies that satisfy these conditions. The condition of concave integrated price flexibility is implied by (but does not imply) the log-concavity of a continuous decreasing price function. So, our results generalize previous results for decreasing log-concave price functions and convex cost functions. We also discuss the particular type of quasi-concavity that characterizes the conditional revenue and profit functions of the firms in these oligopolies and we point out an error of the literature on the equilibrium uniqueness in oligopolies with log-concave price functions. Finally, we explain how the condition of concave integrated price flexibility relates to other conditions on the price and aggregate revenue functions usually considered in the literature, e.g., their concavity.     

Optimal Concavity of the Torsion Function

It is well known that the torsion function of a convex domain has a square root which is concave. The power one half is optimal in the sense that no greater power ensures concavity for every convex set. In this paper, we investigate concavity, not of a power of the torsion function itself, but of the complement to its maximum. Requiring that the torsion function enjoys such a property for the power one half leads to an unconventional overdetermined problem. Our main result is to show that solutions of this problem exist, if and only if they are quadratic polynomials, finding, in fact, a new characterization of ellipsoids.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

When is rounding allowed in integer nonlinear optimization?

In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.     

拓扑向量空间中非光滑向量极值问题的最优性条件与对偶

本文提出了向量值函数的锥D-s凸，锥D-s拟凸，s右导数及锥D-s伪凸等新概念，探讨了锥D-s凸函数的有关性质，建立了带约束非光滑向量极值问题(VP)的最优性必要条件与涉及锥D-s凸(拟凸，伪凸)函数的约束极值问题(VP)的最优性充分条件，给出了原问题(VP)与其Mond-Weir型对偶问题的弱对偶与强对偶结论，揭示了(VP)的局部锥D-(弱)有效解与整体锥D-(弱)有效解，(VP)的锥D-弱有效解与锥D-有效解的关系，所得结果拓广了凸规划及部分广义凸规划的有关结论．     

Programming with a special class of nonlinear functionals

Summary In this paper we consider programming problems in which the constraints are linear and the objective function is the product or the quotient of two functions, each function being a homogeneous form of first degree with a constant added to it.With the proper assumptions of concavity or convexity of the homogeneous forms, this nonlinear programming problem is reduced to that of maximization of a concave function over a convex constraint set.

---

Zusammenfassung In der vorliegenden Arbeit werden Programme untersucht, bei denen die Nebenbedingungen linear sind und die Zielfunktion als Produkt bzw. Quotient zweier Funktionen darstellbar ist, die bis auf additive Konstanten homogen von 1. Grad sind. Bei geeigneten Konvexitäts- oder Konkavitätsannahmen für diese Funktionen lassen sich solche Programme auf die Maximierung einer konkaven Funktion in einem konvexen Gebiet zurückführen.

---

---

Prepared with the partial support of the C.S.I.R., India.

---

Vorgel. v.:J. Nitsche.     

Proximal-gradient algorithms for fractional programming

In this paper, we propose two proximal-gradient algorithms for fractional programming problems in real Hilbert spaces, where the numerator is a proper, convex and lower semicontinuous function and the denominator is a smooth function, either concave or convex. In the iterative schemes, we perform a proximal step with respect to the nonsmooth numerator and a gradient step with respect to the smooth denominator. The algorithm in case of a concave denominator has the particularity that it generates sequences which approach both the (global) optimal solutions set and the optimal objective value of the underlying fractional programming problem. In case of a convex denominator the numerical scheme approaches the set of critical points of the objective function, provided the latter satisfies the Kurdyka-?ojasiewicz property.