Convex programming for disjunctive convex optimization

Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization of the feasible region in a higher-dimensional space and propose a solution procedure akin to the interior-point approach for convex programming. Received November 27, 1996 / Revised version received June 11, 1999?Published online November 9, 1999     

A property of convex piecewise linear functions with applications to mathematical programming

Summary It is proved a lemma on convex piecewise linear functions and there are given some applications of this result to non-linear and parametric programming.

---

Zusammenfassung Es wird ein Hilfssatz über konvexe stückweise lineare Funktionen bewiesen und einige Anwendungen des erlangten Ergebnisses bei nichtlinearer und parametrischer Programmierung werden gegeben.

---

---

Vorgel. v.:H. P. Künzi     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

Affine minorants minimizing the sum of convex functions

It is often possible to replace a convex minimization problem by an equivalent one, in which each of the original convex functions is replaced by a suitably chosen affine minorant. In this paper we identify essentially the minimal conditions permitting this replacement, and also shed light on the close and complete link between such optimal affine minorants and certain optimal dual vectors. An application to the ordinary convex programming problem is included.This research was supported in part by the National Science Foundation, Grant No. MPS75-08025, at the University of Illinois at Urbana-Champaign.     

Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming

Duality results are established in convex programming with the set-inclusive constraints studied by Soyster. The recently developed duality theory for generalized linear programs by Thuente is further generalized and also brought into the framework of Soyster's theory. Convex programming with set-inclusive constraints is further extended to fractional programming.     

Penalization in non-classical convex programming via variational convergence

A penalty method for convex functions which cannot necessarily be extended outside their effective domains by an everywhere finite convex function is proposed and combined with the proximal method. Proofs of convergence rely on variational convergence theory.     

Fourier synthesis via partially finite convex programming

A dual algorithm for problems of Fourier Synthesis is proposed. Partially finite convex programming provides tools for a formulation which enables to elude static pixelization of the object to be reconstructed. This leads to a regularized reconstruction-interpolation formula for problems in which finitely many and possibly irregularly spaced samples of the Fourier transform of the unknown object are known, as is the case in Magnetic Resonance Imaging with non-Cartesian and sparse acquisitions.     

Convex envelopes of products of convex and component-wise concave functions

In this paper, we consider functions of the form f(x,y)=f(x)g(y){\phi(x,y)=f(x)g(y)} over a box, where f(x), x ? \mathbb R{f(x), x\in {\mathbb R}} is a nonnegative monotone convex function with a power or an exponential form, and g(y), y ? \mathbb Rⁿ{g(y), y\in {\mathbb R}^n} is a component-wise concave function which changes sign over the vertices of its domain. We derive closed-form expressions for convex envelopes of various functions in this category. We demonstrate via numerical examples that the proposed envelopes are significantly tighter than popular factorable programming relaxations.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

Intrinsic volumes of symmetric cones and applications in convex programming

Mathematical Programming - We express the probability distribution of the solution of a random (standard Gaussian) instance of a convex cone program in terms of the intrinsic volumes and curvature...     

Second order symmetric duality in nondifferentiable multiobjective fractional programming with cone convex functions

In the present paper, we consider Mond-Weir type nondifferentiable second order fractional symmetric dual programs over arbitrary cones and derive duality results under second order K?F-convexity/K?F-pseudoconvexity assumptions. Our results generalize several known results in the literature.     

Inequalities for convex functions via Stieltjes integral

We present a method of proving inequalities for convex functions with use of Stieltjes integral. First, we show how some well-known inequalities can be obtained, and then we show how new inequalities and stronger versions of some existing results can be obtained.     

Duality in multiobjective nonlinear programming involving semilocally convex and related functions

Necessary optimality conditions are established for a multiobjective nonlinear programming problem involving semilocally convex and related functions in terms of their right differentials. Wolfe type and Mond-Weir type duals are formulated and duality results are proved under the assumptions of semilocal convexity, semilocal quasiconvexity and semilocal pseudoconvexity.     

Whitney differentiability of optimal-value functions for bound-constrained convex programming problems

ABSTRACT

In the spirit of the Whitney Extension Theorem, consider a function on a compact subset of Euclidean space to be ‘Whitney-differentiable’ if it is a restriction of a continuously Fréchet-differentiable function with an open domain. Whitney-differentiable functions have been shown to have useful (yet possibly nonunique) derivatives and calculus properties even on the boundaries of their domains. This article shows that optimal-value functions for bound-constrained convex programmes with Whitney-differentiable objective functions are themselves Whitney-differentiable, even when the linear-independence constraint qualification is not satisfied. This result extends classic sensitivity results for convex programmes, and generalizes recent work. As an application, sufficient conditions are presented for generating continuously differentiable convex underestimators of nonconvex functions for use in methods for deterministic global optimization in the multivariate McCormick framework. In particular, the main result is applied to generate Whitney-differentiable convex underestimators for quotients of functions with known Whitney-differentiable relaxations.     

An algorithm for solving the problem of convex programming with several objective functions

This work aims to establish an algorithm for solving the problem of convex programming with several objective-functions, with linear constraints. Starting from the idea of Rosen’s algorithm for solving the problem of convex programming with linear constraints, and taking into account the solution concept from multidimensional programming, represented by a program which reaches ”the best compromise”, we are extending this method in the case of multidimensional programming. The concept of direction of minimization is introduced, and a necessary and sufficient condition is given for as ∈R ⁿ direction to be a direction of minimization, according to the values of a criteria ensemble in a given point. The algorithm is interactive, and the intervention of the decident is minimal. The two numerical examples presented at the end validate the algorithm.     

Decomposition method of descent for minimizing the sum of convex nonsmooth functions

This paper presents a descent method for minimizing a sum of possibly nonsmooth convex functions. Search directions are found by solving subproblems obtained by replacing all but one of the component functions with their polyhedral approximations and adding a quadratic term. The algorithm is globally convergent and terminates when the objective function happens to be polyhedral. It yields a new decomposition method for solving large-scale linear programs with dual block-angular structure.Supported by Program CPBP 02.15.The author thanks the two referees for their helpful suggestions.