Constraint qualifications for constrained Lipschitz optimization problems and applications to a MPCC

Three constraint qualifications (the weak generalized Robinson constraint qualification, the bounded constraint qualification, and the generalized Abadie constraint qualification), which are weaker than the generalized Robinson constraint qualification (GRCQ) given by Yen (1997) [1], are introduced for constrained Lipschitz optimization problems. Relationships between those constraint qualifications and the calmness of the solution mapping are investigated. It is demonstrated that the weak generalized Robinson constraint qualification and the bounded constraint qualification are easily verifiable sufficient conditions for the calmness of the solution mapping, whereas the proposed generalized Abadie constraint qualification, described in terms of graphical derivatives in variational analysis, is weaker than the calmness of the solution mapping. Finally, those constraint qualifications are written for a mathematical program with complementarity constraints (MPCC), and new constraint qualifications ensuring the C-stationary point condition of a MPCC are obtained.     

New Constraint Qualifications and Optimality Conditions for Second Order Cone Programs

We introduce three new constraint qualifications for nonlinear second order cone programming problems that we call constant rank constraint qualification, relaxed constant rank constraint qualification and constant rank of the subspace component condition. Our development is inspired by the corresponding constraint qualifications for nonlinear programming problems. We provide proofs and examples that show the relations of the three new constraint qualifications with other known constraint qualifications. In particular, the new constraint qualifications neither imply nor are implied by Robinson’s constraint qualification, but they are stronger than Abadie’s constraint qualification. First order necessary optimality conditions are shown to hold under the three new constraint qualifications, whereas the second order necessary conditions hold for two of them, the constant rank constraint qualification and the relaxed constant rank constraint qualification.

     

Abadie Constraint Qualifications for Convex Constraint Systems and Applications to Calmness Property

In this paper, we mainly study concepts of Abadie constraint qualification and strong Abadie constraint qualification for a convex constraint system defined by a closed convex multifunction and a closed convex subset. These concepts can cover Abadie constraint qualifications for the feasible region of convex optimization problem and the convex multifunction. Several characterizations for these Abadie constraint qualifications are also provided. As applications, we use these Abadie constraint qualifications to characterize calmness properties of the convex constraint system.     

On Several Types of Basic Constraint Qualifications via Coderivatives for Generalized Equations

In this paper, we study several types of basic constraint qualifications in terms of Clarke/Fréchet coderivatives for generalized equations. Several necessary and/or sufficient conditions are given to ensure these constraint qualifications. It is proved that basic constraint qualification and strong basic constraint qualification for convex generalized equations can be obtained by these constraint qualifications, and the existing results on constraint qualifications for the inequality system can be deduced from the given conditions in this paper. The main work of this paper is an extension of the study on constraint qualifications from inequality systems to generalized equations.     

Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Various stationary conditions for MPECs exist in literature due to different reformulations. We give a simple proof to the M-stationary condition and show that it is sufficient for global or local optimality under some MPEC generalized convexity assumptions. Moreover, we propose new constraint qualifications for M-stationary conditions to hold. These new constraint qualifications include piecewise MFCQ, piecewise Slater condition, MPEC weak reverse convex constraint qualification, MPEC Arrow-Hurwicz-Uzawa constraint qualification, MPEC Zangwill constraint qualification, MPEC Kuhn-Tucker constraint qualification, and MPEC Abadie constraint qualification.     

Locally Farkas–Minkowski Systems in Convex Semi-Infinite Programming

A pair of constraint qualifications in convex semi-infinite programming, namely the locally Farkas–Minkowski constraint qualification and generalized Slater constraint qualification, are studied in the paper. We analyze the relationship between them, as well as the behavior of the so-called active and sup-active mappings, accounting for the tightness of the constraint system at each point of the variables space. The generalized Slater constraint qualification guarantees a regular behavior of the supremum function (defined as supremum of the infinitely many functions involved in the constraint system), giving rise to the well-known Valadier formula.     

线性规划的约束条件“滚雪球”算法

为使线性规划的每个约束条件部分或全部地拥有原整个约束条件所包含的信息,将线性规划的约束条件“滚雪球”后得到与原约束条件等价的新约束条件,对新约束条件所构成的线性规划采用目标函数最速递减算法.有一定规模的随机数值算例显示了该算法只需进行m(约束条件数)次迭代即可求得最优解.     

均衡约束数学规划的约束规格和最优性条件综述

约束规格在约束优化问题的最优性条件中起着重要的作用,介绍了近几年国际上关于均衡约束数学规划(简记为MPEC)的约束规格以及最优性条件的研究成果, 包括以下主要内容: (1) MPEC常用的约束规格(如线性无关约束规格 (MPEC-LICQ)、Mangasarian-Fromovitz约束规格 (MPEC-MFCQ)等)和新的约束规格(如恒秩约束规格、常数正线性相关约束规格等), 以及它们之间的关系; (2) MPEC常用的稳定点; (3) MPEC的最优性条件. 最后还对MPEC的约束规格和最优性条件的研究前景进行了探讨.     

On Error Bounds for Quasinormal Programs

The Mangasarian-Fromovitz constraint qualification is a central concept within the theory of constraint qualifications in nonlinear optimization. Nevertheless there are problems where this condition does not hold though other constraint qualifications can be fulfilled. One of such constraint qualifications is the so-called quasinormality by Hestenes. The well known error bound property (R-regularity) can also play the role of a general constraint qualification providing the existence of Lagrange multipliers. In this note we investigate the relation between some constraint qualifications and prove that quasinormality implies the error bound property, while the reciprocal is not true.     

Second-Order Conditions for Efficiency in Nonsmooth Multiobjective Optimization Problems

In this paper, we are concerned with a nonsmooth multiobjective optimization problem with inequality constraints. We introduce a second-order constraint qualification, which is a generalization of the Abadie constraint qualification and derive second-order Kuhn-Tucker type necessary conditions for efficiency under the constraint qualification. Moreover, we give some conditions which ensure the constraint qualification holds.     

A Relaxed Constant Positive Linear Dependence Constraint Qualification for Mathematical Programs with Equilibrium Constraints

We introduce a relaxed version of the constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints (MPEC). This condition is weaker but easier to check than the MPEC constant positive linear dependence constraint qualification, and stronger than the MPEC Abadie constraint qualification (thus, it is an MPEC constraint qualification for M-stationarity). Neither the new constraint qualification implies the MPEC generalized quasinormality, nor the MPEC generalized quasinormality implies the new constraint qualification. The new one ensures the validity of the local MPEC error bound under certain additional assumptions. We also have improved some recent results on the existence of a local error bound in the standard nonlinear program.     

Book Review of Introduction to the theory of toeplitz operators with infinite index,Vladimir Dybin and Sergei M. Grudsky (Translated from Russian by Andrei Jacob), operator theory: advances and applications,Birkhäuser Verlag,Basel-Boston-Berlin, 2002, volume 137, 299 pages. ISBN 3-7643-6728-8.

We consider a special class of optimization problems that we call a Mathematical Programme with Vanishing Constraints. It has a number of important applications in structural and topology optimization, but typically does not satisfy standard constraint qualifications like the linear independence and the Mangasarian–Fromovitz constraint qualification. We therefore investigate the Abadie and Guignard constraint qualifications in more detail. In particular, it follows from our results that also the Abadie constraint qualification is typically not satisfied, whereas the Guignard constraint qualification holds under fairly mild assumptions for our particular class of optimization problems.     

约束半环诱导的赋值代数的轮廓解及其算法

本文研究了约束半环所诱导的赋值代数的轮廓解及其算法的问题.利用约束半环的性质,以及基于记忆约束半环赋值的方法,获得了约束半环所诱导的赋值代数的轮廓解的概念,性质以及算法的相关结论,推广了文献[2]关于全序幂等半环诱导的赋值代数的轮廓解的结果.     

Necessary and Sufficient Constraint Qualification for Surrogate Duality

In mathematical programming, constraint qualifications are essential elements for duality theory. Recently, necessary and sufficient constraint qualifications for Lagrange duality results have been investigated. Also, surrogate duality enables one to replace the problem by a simpler one in which the constraint function is a scalar one. However, as far as we know, a necessary and sufficient constraint qualification for surrogate duality has not been proposed yet. In this paper, we propose necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, which are closely related with ones for Lagrange duality.     

Necessary and sufficient conditions for some constraint qualifications in quasiconvex programming

In this paper, we investigate relations between constraint qualifications in quasiconvex programming. At first, we show a necessary and sufficient condition for the closed cone constraint qualification for quasiconvex programming (Q-CCCQ), and investigate some sufficient conditions for the Q-CCCQ. Also, we consider a relation between the Q-CCCQ and the basic constraint qualification for quasiconvex programming (Q-BCQ) and we compare the Q-BCQ with some constraint qualifications.     

On relaxing the Mangasarian–Fromovitz constraint qualification

For the classical nonlinear program, two new relaxations of the Mangasarian–Fromovitz constraint qualification are discussed and their relationship with some standard constraint qualifications is examined. In particular, we establish the equivalence of one of these constraint qualifications with the recently suggested by Andreani et al. Constant rank of the subspace component constraint qualification. As an application, we make use of this new constraint qualification in the local analysis of the solution map to a parameterized equilibrium problem, modeled by a generalized equation.     

基于网络优化模型的变电站选址决策研究

利用Cplex优化软件,设计C语言程序,求解有资金约束与无资金约束的变电站最小费用模型。证明在无资金约束条件下修建的变电站数量可能比有资金约束条件下修建的变电站数量要少,建议决策者在进行电网规划时比较使用上述两种模型,使总费用最低,避免主观决策失误。同时指出了Hakimi文章中的计算错误。     

Computational Discretization Algorithms for Functional Inequality Constrained Optimization

In this paper, a functional inequality constrained optimization problem is studied using a discretization method and an adaptive scheme. The problem is discretized by partitioning the interval of the independent parameter. Two methods are investigated as to how to treat the discretized optimization problem. The discretization problem is firstly converted into an optimization problem with a single nonsmooth equality constraint. Since the obtained equality constraint is nonsmooth and does not satisfy the usual constraint qualification condition, relaxation and smoothing techniques are used to approximate the equality constraint via a smooth inequality constraint. This leads to a sequence of approximate smooth optimization problems with one constraint. An adaptive scheme is incorporated into the method to facilitate the computation of the sum in the inequality constraint. The second method is to apply an adaptive scheme directly to the discretization problem. Thus a sequence of optimization problems with a small number of inequality constraints are obtained. Convergence analysis for both methods is established. Numerical examples show that each of the two proposed methods has its own advantages and disadvantages over the other.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

一类带概率互补约束的随机优化问题的最优性条件

主要讨论了一类带概率互补约束的随机优化问题的最优性条件.首先利用一类非线性互补(NCP)函数将概率互补约束转化成为一个通常的概率约束.然后,利用概率约束的相关理论结果,将其等价地转化成一个带不等式约束的优化问题.最后给出了这类问题的弱驻点和最优解的最优性条件.