Regularity conditions via generalized interiority notions in convex optimization: New achievements and their relation to some classical statements

For the existence of strong duality in convex optimization regularity conditions play an indisputable role. In this article we mainly deal with regularity conditions formulated by means of different generalizations of the notion of interior of a set. The primal–dual pair we investigate is a general one expressed in the language of a perturbation function and by employing its Fenchel–Moreau conjugate. After providing an overview on the generalized interior-point conditions that exist in the literature we introduce several new ones formulated by means of the quasi-interior and quasi-relative interior. We underline the advantages of the new conditions vis-á-vis the classical ones and illustrate our investigations by numerous examples. We conclude this article by particularizing the general approach to the classical Fenchel and Lagrange duality concepts.     

Quasi-relative interior-type constraint qualifications ensuring strong Lagrange duality for optimization problems with cone and affine constraints

In this article we provide weak sufficient strong duality conditions for a convex optimization problem with cone and affine constraints, stated in infinite dimensional spaces, and its Lagrange dual problem. Our results are given by using the notions of quasi-relative interior and quasi-interior for convex sets. The main strong duality theorem is accompanied by several stronger, yet easier to verify in practice, versions of it. As exemplification we treat a problem which is inspired from network equilibrium. Our results come as corrections and improvements to Daniele and Giuffré (2007) [9].     

Infinite dimensional duality and applications

The usual duality theory cannot be applied to infinite dimensional problems because the underlying constraint set mostly has an empty interior and the constraints are possibly nonlinear. In this paper we present an infinite dimensional nonlinear duality theory obtained by using new separation theorems based on the notion of quasi-relative interior, which, in all the concrete problems considered, is nonempty. We apply this theory to solve the until now unsolved problem of finding, in the infinite dimensional case, the Lagrange multipliers associated to optimization problems or to variational inequalities. As an example, we find the Lagrange multiplier associated to a general elastic–plastic torsion problem.     

Looking for appropriate qualification conditions for subdifferential formulae and dual representations for convex risk measures

A fruitful idea, when providing subdifferential formulae and dual representations for convex risk measures, is to make use of the conjugate duality theory in convex optimization. In this paper we underline the outstanding role played by the qualification conditions in the context of different problem formulations in this area. We show that not only the meanwhile classical generalized interiority point conditions come here to bear, but also a recently introduced one formulated by means of the quasi-relative interior.     

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     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

基于拟相对内部集值优化问题弱有效元的最优性条件

本文研究了基于拟相对内部的非凸集值优化问题弱有效元的最优性条件.首先,讨论了弱有效元与线性子空间之间的关系,利用涉及拟相对内部的凸集分离定理,获得了弱有效元的最优性条件.其次,给出了基于拟相对内部弱有效元的Lagrange乘子定理.     

Duality Theory and Applications to Unilateral Problems

This paper is concerned with the problem of strong duality between an infinite dimensional convex optimization problem with cone and equality constraints and its Lagrange dual. A necessary and sufficient condition and sufficient conditions, really new, in order that the strong duality holds true are given. As an application, the existence of the Lagrange multiplier associated with the obstacle problem and to an elastic–plastic torsion problem, more general than the ones previously considered, is stated together with a characterization of the elastic–plastic torsion problem. This application is the main result of the paper. It is worth remarking that the usual conditions based on the interior, on the core, on the intrinsic core or on the strong quasi-relative interior cannot be used because they require the nonemptiness of the interior (and of the above mentioned generalized interior concepts) of the ordering cone, which is usually empty.     

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.     

Support vector machine classifiers with uncertain knowledge sets via robust optimization

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.     

Proving Strong Duality for Geometric Optimization Using a Conic Formulation

Geometric optimization¹ is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization.     

On optimality and duality theorems of nonlinear disjunctive fractional minmax programs

This paper is concerned with the study of optimality conditions for disjunctive fractional minmax programming problems in which the decision set can be considered as a union of a family of convex sets. Dinkelbach’s global optimization approach for finding the global maximum of the fractional programming problem is discussed. Using the Lagrangian function definition for this type of problem, the Kuhn–Tucker saddle point and stationary-point problems are established. In addition, via the concepts of Mond–Weir type duality and Schaible type duality, a general dual problem is formulated and some weak, strong and converse duality theorems are proven.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

A generalized duality and applications

The aim of this paper is to present a nonconvex duality with a zero gap and its connection with convex duality. Since a convex program can be regarded as a particular case of convex maximization over a convex set, a nonconvex duality can be regarded as a generalization of convex duality. The generalized duality can be obtained on the basis of convex duality and minimax theorems. The duality with a zero gap can be extended to a more general nonconvex problems such as a quasiconvex maximization over a general nonconvex set or a general minimization over the complement of a convex set. Several applications are given.On leave from the Institute of Mathematics, Hanoi, Vietnam.     

Set-Valued Systems with Infinite-Dimensional Image and Applications

In infinite-dimensional spaces, we investigate a set-valued system from the image perspective. By exploiting the quasi-interior and the quasi-relative interior, we give some new equivalent characterizations of (proper, regular) linear separation and establish some new sufficient and necessary conditions for the impossibility of the system under new assumptions, which do not require the set to have nonempty interior. We also present under mild assumptions the equivalence between (proper, regular) linear separation and saddle points of Lagrangian functions for the system. These results are applied to obtain some new saddle point sufficient and necessary optimality conditions of vector optimization problems.     

KKT Optimality Conditions and Nonsmooth Continuous Time Optimization Problems

We introduce a concept of generalized invexity for the nonsmooth continuous time optimization problems, namely, the concept of Karush-Kuhn-Tucker (KKT) invexity. Then, we prove that this notion is necessary and sufficient for global optimality of a KKT point. We also extend the notion of weak-invexity for nonsmooth continuous time optimization problems. Further, we show that weak-invexity is a necessary and sufficient condition for weak duality.     

SEQUENTIAL CONVEX PROGRAMMING METHODS FOR SOLVING LARGE TOPOLOGY OPTIMIZATION PROBLEMS： IMPLEMENTATION AND COMPUTATIONAL RESULTS

In this paper, we describe a method to solve large-scale structural optimization problems by sequential convex programming （SCP）. A predictor-corrector interior point method is applied to solve the strictly convex subproblems. The SCP algorithm and the topology optimization approach are introduced. Especially, different strategies to solve certain linear systems of equations are analyzed. Numerical results are presented to show the efficiency of the proposed method for solving topology optimization problems and to compare different variants.     

Pareto optimality and Walrasian equilibria

The paper concerns the study of a class of convex, constrained multiobjective optimization problems from the viewpoint of the existence issues. The main feature of the presented approach is that the classical qualification condition requiring the existence of interior points in the effective domains of functions under consideration does not hold. A variant of duality theory for multiobjective optimization problems based on the Fenchel theorem is formulated. Next, by using very recent results on the Walrasian general equilibrium model of economy obtained in Naniewicz [Z. Naniewicz, Pseudo-monotonicity and economic equilibrium problem in reflexive Banach space, Math. Oper. Res. 32 (2007) 436-466] the conditions ensuring the existence of Pareto optimal solutions for the class of multiobjective optimization problems are established. The concept of the proper efficiency is used as the solution notion. Finally, a new version of the second fundamental theorem of welfare economics is presented.     

On duality in multiobjective semi-infinite optimization

Abstract

In this paper, we consider multiobjective semi-infinite optimization problems which are defined in a finite-dimensional space by finitely many objective functions and infinitely many inequality constraints. We present duality results both for the convex and nonconvex case. In particular, we show weak, strong and converse duality with respect to both efficiency and weak efficiency. Moreover, the property of being a locally properly efficient point plays a crucial role in the nonconvex case.     

Surrogate duality for robust optimization

Robust optimization problems, which have uncertain data, are considered. We prove surrogate duality theorems for robust quasiconvex optimization problems and surrogate min–max duality theorems for robust convex optimization problems. We give necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, and show some examples at which such duality results are used effectively. Moreover, we obtain a surrogate duality theorem and a surrogate min–max duality theorem for semi-definite optimization problems in the face of data uncertainty.