Asymptotic optimality conditions for linear semi-infinite programming

In this paper, the classical KKT, complementarity and Lagrangian saddle-point conditions are generalized to obtain equivalent conditions characterizing the optimality of a feasible solution to a general linear semi-infinite programming problem without constraint qualifications. The method of this paper differs from the usual convex analysis methods and its main idea is rooted in some fundamental properties of linear programming.     

On representations of the feasible set in convex optimization

We consider the convex optimization problem \({\min_{\mathbf{x}} \{f(\mathbf{x}): g_j(\mathbf{x})\leq 0, j=1,\ldots,m\}}\) where f is convex, the feasible set \({\mathbf{K}}\) is convex and Slater’s condition holds, but the functions g _j ’s are not necessarily convex. We show that for any representation of \({\mathbf{K}}\) that satisfies a mild nondegeneracy assumption, every minimizer is a Karush-Kuhn-Tucker (KKT) point and conversely every KKT point is a minimizer. That is, the KKT optimality conditions are necessary and sufficient as in convex programming where one assumes that the g _j ’s are convex. So in convex optimization, and as far as one is concerned with KKT points, what really matters is the geometry of \({\mathbf{K}}\) and not so much its representation.     

First Order Optimality Conditions for Generalized Semi-Infinite Programming Problems

We study first-order optimality conditions for the class of generalized semi-infinite programming problems (GSIPs). We extend various well-known constraint qualifications for finite programming problems to GSIPs and analyze the extent to which a corresponding Karush-Kuhn-Tucker (KKT) condition depends on these extensions. It is shown that in general the KKT condition for GSIPs takes a weaker form unless a certain constraint qualification is satisfied. In the completely convex case where the objective of the lower-level problem is concave and the constraint functions are quasiconvex, we show that the KKT condition takes a sharper form. The authors thank the anonymous referees for careful reading of the paper and helpful suggestions. The research of the first author was partially supported by NSERC.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

Optimality conditions in convex optimization revisited

The phrase convex optimization refers to the minimization of a convex function over a convex set. However the feasible convex set need not be always described by convex inequalities. In this article we consider a convex feasible set which is described by inequality constraints that are locally Lipschitz and not necessarily convex or differentiable. We show that if the Slater constraint qualification and a simple non-degeneracy condition is satisfied then the Karush–Kuhn–Tucker type optimality condition is both necessary and sufficient.     

Robust optimization revisited via robust vector Farkas lemmas

This paper provides characterizations of the weakly minimal elements of vector optimization problems and the global minima of scalar optimization problems posed on locally convex spaces whose objective functions are deterministic while the uncertain constraints are treated under the robust (or risk-averse) approach, i.e. requiring the feasibility of the decisions to be taken for any possible scenario. To get these optimality conditions we provide Farkas-type results characterizing the inclusion of the robust feasible set into the solution set of some system involving the objective function and possibly uncertain parameters. In the particular case of scalar convex optimization problems, we characterize the optimality conditions in terms of the convexity and closedness of an associated set regarding a suitable point.     

Nonsmooth semi-infinite programming problems with mixed constraints

We consider a nonsmooth semi-infinite programming problem with a feasible set defined by inequality and equality constraints and a set constraint. First, we study some alternative theorems which involve linear and sublinear functions and a convex set and we propose several generalizations of them. Then, alternative theorems are applied to obtain, under different constraint qualifications, several necessary optimality conditions in the type of Fritz-John and Karush-Kuhn-Tucker.     

Order-Preserving Transformations and Applications

In this paper, we study the effects of a linear transformation on the partial order relations that are generated by a closed and convex cone in a finite-dimensional space. Sufficient conditions are provided for a transformation preserving a given order. They are applied to derive the relationship between the efficient set of a set and its image under a linear transformation, to characterize generalized convex vector functions by using order-preserving transformations, to establish some calculus rules for the subdifferential of a convex vector function, and develop an optimality condition for a convex vector problem.     

一类稀疏约束非线性规划的约束规格

研究一类带有闭凸集约束的稀疏约束非线性规划问题,这类问题在变量选择、模式识别、投资组合等领域具有广泛的应用.首先引进了限制性Slater约束规格的概念,证明了该约束规格强于限制性M-F约束规格,然后在此约束规格成立的条件下,分析了其局部最优解成立的充分和必要条件.最后,对约束集合的两种具体形式,指出限制性Slater约束规格必满足,并给出了一阶必要性条件的具体表达形式.     

An extension of the Basic Constraint Qualification to nonconvex vector optimization problems

In this paper a Basic Constraint Qualification is introduced for a nonconvex infinite-dimensional vector optimization problem extending the usual one from convex programming assuming the Hadamard differentiability of the maps. Corresponding KKT conditions are established by considering a decoupling of the constraint cone into half-spaces. This extension leads to generalized KKT conditions which are finer than the usual abstract multiplier rule. A second constraint qualification expressed directly in terms of the data is also introduced, which allows us to compute the contingent cone to the feasible set and, as a consequence, it is proven that this condition is a particular case of the first one. Relationship with other constraint qualifications in infinite-dimensional vector optimization, specially with the Kurcyuscz-Robinson-Zowe constraint qualification, are also given.     

ε-Pareto Optimality Conditions for Convex Multiobjective Programming via Max Function

We consider a nondifferentiable convex multiobjective optimization problem whose feasible set is defined by affine equality constraints, convex inequality constraints, and an abstract convex set constraint. We obtain Fritz John and Kuhn–Tucker necessary and sufficient conditions for ε-Pareto optimality via a max function. We also provide some relations among ε-Pareto solutions for such a problem and approximate solutions for several associated scalar problems.     

Convex Semi-Infinite Programming: Implicit Optimality Criterion Based on the Concept of Immobile Indices

We state a new implicit optimality criterion for convex semi-infinite programming (SIP) problems. This criterion does not require any constraint qualification and is based on concepts of immobile index and immobility order. Given a convex SIP problem with a continuum of constraints, we use an information about its immobile indices to construct a nonlinear programming (NLP) problem of a special form. We prove that a feasible point of the original infinite SIP problem is optimal if and only if it is optimal in the corresponding finite NLP problem. This fact allows us to obtain new efficient optimality conditions for convex SIP problems using known results of the optimality theory of NLP. To construct the NLP problem, we use the DIO algorithm. A comparison of the optimality conditions obtained in the paper with known results is provided.     

The Karush–Kuhn–Tucker optimality conditions in an optimization problem with interval-valued objective function

The KKT conditions in an optimization problem with interval-valued objective function are derived in this paper. Two solution concepts of this optimization problem are proposed by considering two partial orderings on the set of all closed intervals. In order to consider the differentiation of an interval-valued function, we invoke the Hausdorff metric to define the distance between two closed intervals and the Hukuhara difference to define the difference of two closed intervals. Under these settings, we derive the KKT optimality conditions.     

A sequential parametric convex approximation method with applications to nonconvex truss topology design problems

We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions. Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence large scale TTD problems can be efficiently solved by the proposed method.     

The nonlinear bilevel programming problem:formulations,regularity and optimality conditions

In this paper, we study regularity and optimality conditions for the BLPP by using a marginal function formulation, where the marginal function is defined by the optimal value function of the lower problem. We address the regularity issue by exploring the structure of the tangent cones of the feasible set of the BLPP. These regularity results indicate that the nonlinear/nonlinear BLPP is most likely degenerate and a class of nonlinear/linear BLPP is regular in the conventional sense. Existence of exact penalty function is proved for a class of nonlinear/linear BLPP. Fritz-John type optimality conditions are derived for nonlinear BLPP, while KKT type conditions are obtained for a class of nonlinear/linear BLPP in the framework of nonsmooth analysis. A typical example is examined for these conditions and some applications of these conditions are pointed out     

METHOD OF CENTERS ALGORITHM FOR MULTI-OBJECTIVE PROGRAMMING PROBLEMS

In this paper, we consider a method of centers for solving multi-objective programming problems, where the objective functions involved are concave functions and the set of feasible points is convex. The algorithm is defined so that the sub-problems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the KKT conditions. Finally, we establish convergence of the proposed method of centers algorithm for solving multiobjective programming problems.     

Characterization of (weakly/properly/robust) efficient solutions in nonsmooth semi-infinite multiobjective optimization using convexificators

The main aim of this paper is to investigate weakly/properly/robust efficient solutions of a nonsmooth semi-infinite multiobjective programming problem, in terms of convexificators. In some of the results, we assume the feasible set to be locally star-shaped. The appearing functions are not necessarily smooth/locally Lipschitz/convex. First, constraint qualifications and the normal cone to the feasible set are studied. Then, as a major part of the paper, various necessary and sufficient optimality conditions for solutions of the problem under consideration are presented. The paper is closed by a linear approximation problem to detect the solutions and by studying a gap function.     

Asymptotic behavior of solutions: An application to stochastic NLP

In this article we study the consistency of optimal and stationary (KKT) points of a stochastic non-linear optimization problem involving expectation functionals, when the underlying probability distribution associated with the random variable is weakly approximated by a sequence of random probability measures. The optimization model includes constraints with expectation functionals those are not captured in direct application of the previous results on optimality conditions exist in the literature. We first study the consistency of stationary points of a general NLP problem with convex and locally Lipschitz data and then apply those results to the stochastic NLP problem and stochastic minimax problem. Moreover, we derive an exponential bound for such approximations using a large deviation principle.

     

The bilevel programming problem: reformulations, constraint qualifications and optimality conditions

We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential calculus of Mordukhovich.     

A simplified test for optimality

A simplification of recent characterizations of optimality in convex programming involving the cones of decrease and constancy of the objective and constraint functions is presented. In the original characterization due to Ben-Israelet al., optimality was verified or a feasible direction of decrease was determined by considering a number of sets equal to the number of subsets of the set of binding constraints. By first finding the set of constraints which is binding at every feasible point, it is possible to verify optimality or determine a feasible direction of decrease by considering a single set. In the case of faithfully convex functions, this set can be found by solving at mostp systems of linear equations and inequalities, wherep is the number of constraints.This work was partly supported by NSF Grant No. Eng 76-10260.