Necessary optimality conditions for a special class of bilevel programming problems with unique lower level solution

We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control.     

Optimality and duality with generalized convexity

Hanson and Mond have given sets of necessary and sufficient conditions for optimality and duality in constrained optimization by introducing classes of generalized convex functions, called type I and type II functions. Recently, Bector defined univex functions, a new class of functions that unifies several concepts of generalized convexity. In this paper, optimality and duality results for several mathematical programs are obtained combining the concepts of type I and univex functions. Examples of functions satisfying these conditions are given.     

Variable Programming: A Generalized Minimax Problem. Part I: Models and Theory

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Optimality conditions and constraint qualifications in Banach space

In this paper, necessary optimality conditions for nonlinear programs in Banach spaces and constraint qualifications for their applicability are considered. A new optimality condition is introduced, and a constraint qualification ensuring the validity of this condition is given. When the domain space is a reflexive space, it is shown that the qualification is the weakest possible. If a certain convexity assumption is made, then this optimality condition is shown to reduce to the well-known extension of the Kuhn-Tucker conditions to Banach spaces. In this case, the constraint qualification is weaker than those previously given.This work was supported in part by the Office of Naval Research, Contract Number N00014-67-A-0321-0003 (NRO 47-095).     

2-Regularity and 2-Normality Conditions in Discrete Optimal Control Problems

The paper is devoted to general optimal control problems for discrete-time systems with equality type of constraints on end points and control. We derive first-order necessary optimality conditions that are meaningful under the new nontriviality condition.     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

On strong and weak second-order necessary optimality conditions for nonlinear programming

Second-order necessary optimality conditions play an important role in optimization theory. This is explained by the fact that most numerical optimization algorithms reduce to finding stationary points satisfying first-order necessary optimality conditions. As a rule, optimization problems, especially the high dimensional ones, have a lot of stationary points so one has to use second-order necessary optimality conditions to exclude nonoptimal points. These conditions are closely related to second-order constraint qualifications, which guarantee the validity of second-order necessary optimality conditions. In this paper, strong and weak second-order necessary optimality conditions are considered and their validity proved under so-called critical regularity condition at local minimizers.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

指数型增广拉格朗日函数在广义半无限规划中的应用

本文利用指数型增广拉格朗日函数将一类广义半无限极大极小问题在一定条件下转化为标准的半无限极大极小问题,使它们具有相同的局部与全局最优解.我们给出了两个转化条件:一个是充分与必要条件,另一个是在实际中易于验证的充分条件.通过这种转化,我们给出了广义半无限极大极小问题的一个新的一阶最优性条件.     

On Optimality Conditions for Generalized Semi-Infinite Programming Problems

Generalized semi-infinite optimization problems (GSIP) are considered. We generalize the well-known optimality conditions for minimizers of order one in standard semi-infinite programming to the GSIP case. We give necessary and sufficient conditions for local minimizers of order one without the assumption of local reduction. The necessary conditions are derived along the same lines as the first-order necessary conditions for GSIP in a recent paper of Jongen, Rückmann, and Stein (Ref. 1) by assuming the so-called extended Mangasarian–Fromovitz constraint qualification. Using the ideas of a recent paper of Rückmann and Shapiro, we give short proofs of necessary and sufficient optimality conditions for minimizers of order one under the additional assumption of the Mangasarian–Fromovitz constraint qualification at all local minimizers of the so-called lower-level problem.     

不可微向量优化问题严有效解的最优性条件

本文研究向量优化问题在严有效解意义下的最优性条件.在局部凸Hausdorff拓扑线性空间中.在近似锥一次类凸假设下,利用凸集分离定理得到了最优性必要条件.借助Gateaux导数引进了几种新的凸性,在新的凸性假设下得到了最优性充分条件.     

Reducing the number of variables in integer quadratic programming problem

In this paper, a new variable reduction technique is presented for general integer quadratic programming problem (GP), under which some variables of (GP) can be fixed at zero without sacrificing optimality. A sufficient condition and a necessary condition for the identification of dominated terms are provided. By comparing the given data of the problem and the upper bound of the variables, if they meet certain conditions, some variables can be fixed at zero. We report a computational study to demonstrate the efficacy of the proposed technique in solving general integer quadratic programming problems. Furthermore, we discuss separable integer quadratic programming problems in a simpler and clearer form.     

FATCOP 2.0: Advanced Features in an Opportunistic Mixed Integer Programming Solver

We describe FATCOP 2.0, a new parallel mixed integer program solver that works in an opportunistic computing environment provided by the Condor resource management system. We outline changes to the search strategy of FATCOP 1.0 that are necessary to improve resource utilization, together with new techniques to exploit heterogeneous resources. We detail several advanced features in the code that are necessary for successful solution of a variety of mixed integer test problems, along with the different usage schemes that are pertinent to our particular computing environment. Computational results demonstrating the effects of the changes are provided and used to generate effective default strategies for the FATCOP solver.     

Optimality conditions for discrete calculus of variations problems

Nonlinear discrete calculus of variations problems with variable endpoints and with equality type constraints on trajectories are considered. We derive new nontrivial first- and second-order necessary optimality conditions.     

Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.     

Radial Solutions and Orthogonal Trajectories in Multiobjective Global Optimization

This paper presents a new, ray-oriented method for the global solution of nonscalarized vector optimization problems and a framework for the application of the Karush–Kuhn–Tucker theorem to such problems. Properties of nonlinear multiobjective problems implied by the Karush–Kuhn–Tucker necessary conditions are investigated. The regular case specific to nonscalarized MOPs is singled out when a nonlinear MOP with nonlinearities only in the constraints reduces to a nondegenerate linear system. It is shown that the trajectories of the Lagrange multipliers corresponding to the components of the vector cost function are orthogonal to the corresponding trajectories of the vector deviations in the balance space (to the balance set for Pareto solutions). Illustrative examples are presented.     

Second order necessary optimality conditions for minimizing a sup-type function

The second derivative of an envelope cannot be expressed only by second derivatives of the constituent functions. By taking account of this fact, we derive new second order necessary optimality conditions for minimization of a sup-type function. The conditions involve an extra term besides the second derivative of the Lagrange function. Furthermore, we will comment on the relationship between the extra term and a kind of second order directional derivative of the sup-type function.     

非凸半定规划的广义Fakars引理及最优性条件

1引言在本文中,我们用(?),S~n,S_ ~n分别表示有限维向量空间,n阶对称矩阵空间及n阶半正定矩阵锥.我们考虑如下形式的非凸半定规划问题:     

Extremal points and optimal solutions for general capacity problems

This paper studies the infinite dimensional linear programming problems in the integration type. The variable is taken in the space of bounded regular Borel measures on compact Hausdorff spaces. It will find an optimal measure for a constrained optimization problem, namely a capacity problem. Relations between extremal points of the feasible region and optimal solutions of the optimization problem are investigated. The necessary/sufficient conditions for a measure to be optimal are established. The algorithm for optimal solution of the general capacity problem onX = Y = [0, 1] is formulated.     

The chance constrained critical path with location-scale distributions

The Chance Constrained Critical Path (CCCP) generally depends on the preassigned minimum probability level. It is shown that for a wide class of probability distributions there always exists a probability value for which the CCCP remains unchanged for all probabilities greater than or equal to that value. This probability value is easily obtained from an optimal solution of a simple network problem. In addition, necessary and sufficient conditions for the CCCP to be unconditionally independent of the minimum probability level are given for that class of probability distributions.