Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Partially finite convex programming,Part II: Explicit lattice models

In Part I of this work we derived a duality theorem for partially finite convex programs, problems for which the standard Slater condition fails almost invariably. Our result depended on a constraint qualification involving the notion ofquasi relative interior. The derivation of the primal solution from a dual solution depended on the differentiability of the dual objective function: the differentiability of various convex functions in lattices was considered at the end of Part I. In Part II we shall apply our results to a number of more concrete problems, including variants of semi-infinite linear programming,L ¹ approximation, constrained approximation and interpolation, spectral estimation, semi-infinite transportation problems and the generalized market area problem of Lowe and Hurter (1976). As in Part I, we shall use lattice notation extensively, but, as we illustrated there, in concrete examples lattice-theoretic ideas can be avoided, if preferred, by direct calculation.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Generalized convex relations with applications to optimization and models of economic dynamics

We examine a notion of generalized convex set-valued mapping, extending the notions of a convex relation and a convex process. Under general conditions, we establish duality results for composite set-valued mappings and for convex programming problems involving convex set-valued mappings. We also present applications to the study of economic dynamical systems, by obtaining the characteristics of optimal paths generated by convex processes, and to optimization problems of a certain class of positively homogeneous increasing functions.     

On the use of the quasi-relative interior in optimization

The notion of quasi-relative interior was introduced by Borwein and Lewis in 1992 and applied for duality results in partially finite convex optimization problems. In the last 10 years, several articles were dedicated to duality results in infinite-dimensional scalar, vector and set-valued optimization problems using this notion. The aim of this paper is to refine and discuss such results. We do this observing that the notion of quasi-relative interior is related to (non-proper) separation of a convex set and some of its elements, then pointing out the relation between the subdifferentiability of a function associated to a set of epigraph type at a certain point and the fact that a corresponding point is not in the quasi-relative interior of the closed convex hull of the set.     

A weaker regularity condition for subdifferential calculus and Fenchel duality in infinite dimensional spaces

In this paper we present a new regularity condition for the subdifferential sum formula of a convex function with the precomposition of another convex function with a continuous linear mapping. This condition is formulated by using the epigraphs of the conjugates of the functions involved and turns out to be weaker than the generalized interior-point regularity conditions given so far in the literature. Moreover, it provides a weak sufficient condition for Fenchel duality regarding convex optimization problems in infinite dimensional spaces. As an application, we discuss the strong conical hull intersection property (CHIP) for a finite family of closed convex sets.     

Convex risk measures for portfolio optimization and concepts of flexibility

Due to their axiomatic foundation and their favorable computational properties convex risk measures are becoming a powerful tool in financial risk management. In this paper we will review the fundamental structural concepts of convex risk measures within the framework of convex analysis. Then we will exploit it for deriving strong duality relations in a generic portfolio optimization context. In particular, the duality relationship can be used for designing new, efficient approximation algorithms based on Nesterov's smoothing techniques for non-smooth convex optimization. Furthermore, the presented concepts enable us to formalize the notion of flexibility as the (marginal) risk absorption capacity of a technology or (available) resources. This paper is dedicated to R.T. Rockafellar for his stimulating and impressive work in convex optimization for decades. We thank you for the insights and inspirations we gained from your fundamental research.     

A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.     

A proximal-based decomposition method for convex minimization problems

This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297.     

Farkas-type results for fractional programming problems

Considering a constrained fractional programming problem, within the present paper we present some necessary and sufficient conditions, which ensure that the optimal objective value of the considered problem is greater than or equal to a given real constant. The desired results are obtained using the Fenchel–Lagrange duality approach applied to an optimization problem with convex or difference of convex (DC) objective functions and finitely many convex constraints. These are obtained from the initial fractional programming problem using an idea due to Dinkelbach. We also show that our general results encompass as special cases some recently obtained Farkas-type results.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

Facial reduction in partially finite convex programming

We consider the problem of minimizing an extended-valued convex function on a locally convex space subject to a finite number of linear (in)equalities. When the standard constraint qualification fails a reduction technique is needed to derive necessary optimality conditions. Facial reduction is usually applied in the range of the constraints. In this paper it is applied in the domain space, thus maintaining any structure (and in particular lattice properties) of the underlying domain. Applications include constrained approximation and best entropy estimation.Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

Duality for multiobjective optimization problems with convex objective functions and D.C. constraints

In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints.     

Duality for almost convex optimization problems via the perturbation approach

We deal with duality for almost convex finite dimensional optimization problems by means of the classical perturbation approach. To this aim some standard results from the convex analysis are extended to the case of almost convex sets and functions. The duality for some classes of primal-dual problems is derived as a special case of the general approach. The sufficient regularity conditions we need for guaranteeing strong duality are proved to be similar to the ones in the convex case. The research of the first and third authors was partially supported by DFG (German Research Foundation), project WA 922/1. The research of the second author was supported by the grant PN II, ID 523/2007.     

A simplicial branch and duality bound algorithm for the sum of convex–convex ratios problem

This article presents a simplicial branch and duality bound algorithm for globally solving the sum of convex–convex ratios problem with nonconvex feasible region. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme where the Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems during the algorithm search are all ordinary linear programs that can be solved very efficiently. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.     

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     

Collusive game solutions via optimization

A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional. In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish convergence properties of these procedures. Computational results with these procedures for solving some test problems are reported. It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted the computational solution of applied game problems. This author's research was partially supported by the National Science Foundation under grant ECS-0080577. This author's research was partially supported by the National Science Foundation under grant CCR-0098013.     

A new geometric condition for Fenchel's duality in infinite dimensional spaces

In 1951, Fenchel discovered a special duality, which relates the minimization of a sum of two convex functions with the maximization of the sum of concave functions, using conjugates. Fenchel's duality is central to the study of constrained optimization. It requires an existence of an interior point of a convex set which often has empty interior in optimization applications. The well known relaxations of this requirement in the literature are again weaker forms of the interior point condition. Avoiding an interior point condition in duality has so far been a difficult problem. However, a non-interior point type condition is essential for the application of Fenchel's duality to optimization. In this paper we solve this problem by presenting a simple geometric condition in terms of the sum of the epigraphs of conjugate functions. We also establish a necessary and sufficient condition for the ε-subdifferential sum formula in terms of the sum of the epigraphs of conjugate functions. Our results offer further insight into Fenchel's duality. Dedicated to Terry Rockafellar on his 70th birthday     

A branch-and-cut method for 0-1 mixed convex programming

We generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method. Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999