Karush–Kuhn–Tucker Conditions in Set Optimization

This paper investigates set optimization problems in finite dimensional spaces with the property that the images of the set-valued objective map are described by inequalities and equalities and that sets are compared with the set less order relation. For these problems new Karush–Kuhn–Tucker conditions are shown as necessary and sufficient optimality conditions. Optimality conditions without multiplier of the objective map are also presented. The usefulness of these results is demonstrated with a standard example.     

Enhanced Karush–Kuhn–Tucker condition and weaker constraint qualifications

In this paper we study necessary optimality conditions for nonsmooth optimization problems with equality, inequality and abstract set constraints. We derive the enhanced Fritz John condition which contains some new information even in the smooth case than the classical enhanced Fritz John condition. From this enhanced Fritz John condition we derive the enhanced Karush–Kuhn–Tucker condition and introduce the associated pseudonormality and quasinormality condition. We prove that either pseudonormality or quasinormality with regularity on the constraint functions and the set constraint implies the existence of a local error bound. Finally we give a tighter upper estimate for the Fréchet subdifferential and the limiting subdifferential of the value function in terms of quasinormal multipliers which is usually a smaller set than the set of classical normal multipliers. In particular we show that the value function of a perturbed problem is Lipschitz continuous under the perturbed quasinormality condition which is much weaker than the classical normality condition.     

Solution sensitivity for Karush–Kuhn–Tucker systems with non-unique Lagrange multipliers

This article is devoted to quantitative stability of a given primal-dual solution of the Karush–Kuhn–Tucker system subject to parametric perturbations. We are mainly concerned with those cases when the dual solution associated with the base primal solution is non-unique. Starting with a review of known results regarding the Lipschitz-stable case, supplied by simple direct justifications based on piecewise analysis, we then proceed with new results for the cases of Hölder (square root) stability. Our results include characterizations of asymptotic behaviour and upper estimates of perturbed solutions, as well as some sufficient conditions for (the specific kinds of) stability of a given solution subject to directional perturbations. We argue that Lipschitz stability of strictly complementary multipliers is highly unlikely to occur, and we employ the recently introduced notion of a critical multiplier for dealing with Hölder stability.     

Second-order Karush–Kuhn–Tucker optimality conditions for set-valued optimization

In this paper, we propose the concept of a second-order composed contingent derivative for set-valued maps, discuss its relationship to the second-order contingent derivative and investigate some of its special properties. By virtue of the second-order composed contingent derivative, we extend the well-known Lagrange multiplier rule and the Kurcyusz–Robinson–Zowe regularity assumption to a constrained set-valued optimization problem in the second-order case. Simultaneously, we also establish some second-order Karush–Kuhn–Tucker necessary and sufficient optimality conditions for a set-valued optimization problem, whose feasible set is determined by a set-valued map, under a generalized second-order Kurcyusz–Robinson–Zowe regularity assumption.     

Higher-order Karush–Kuhn–Tucker optimality conditions for set-valued optimization with nonsolid ordering cones

In this paper, we consider higher-order Karush–Kuhn–Tucker optimality conditions in terms of radial derivatives for set-valued optimization with nonsolid ordering cones. First, we develop sum rules and chain rules in the form of equality for radial derivatives. Then, we investigate set-valued optimization including mixed constraints with both ordering cones in the objective and constraint spaces having possibly empty interior. We obtain necessary conditions for quasi-relative efficient solutions and sufficient conditions for Pareto efficient solutions. For the special case of weak efficient solutions, we receive even necessary and sufficient conditions. Our results are new or improve recent existing ones in the literature.     

When the Karush–Kuhn–Tucker Theorem Fails: Constraint Qualifications and Higher-Order Optimality Conditions for Degenerate Optimization Problems

In this paper, we present higher-order analysis of necessary and sufficient optimality conditions for problems with inequality constraints. The paper addresses the case when the constraints are not assumed to be regular at a solution of the optimization problems. In the first two theorems derived in the paper, we show how Karush–Kuhn–Tucker necessary conditions reduce to a specific form containing the objective function only. Then we present optimality conditions of the Karush–Kuhn–Tucker type in Banach spaces under new regularity assumptions. After that, we analyze problems for which the Karush–Kuhn–Tucker form of optimality conditions does not hold and propose necessary and sufficient conditions for those problems. To formulate the optimality conditions, we introduce constraint qualifications for new classes of nonregular nonlinear optimization. The approach of p-regularity used in the paper can be applied to various degenerate nonlinear optimization problems due to its flexibility and generality.     

A Generalization of the Karush–Kuhn–Tucker Theorem for Approximate Solutions of Mathematical Programming Problems Based on Quadratic Approximation

In computations related to mathematical programming problems, one often has to consider approximate, rather than exact, solutions satisfying the constraints of the problem and the optimality criterion with a certain error. For determining stopping rules for iterative procedures, in the stability analysis of solutions with respect to errors in the initial data, etc., a justified characteristic of such solutions that is independent of the numerical method used to obtain them is needed. A necessary δ-optimality condition in the smooth mathematical programming problem that generalizes the Karush–Kuhn–Tucker theorem for the case of approximate solutions is obtained. The Lagrange multipliers corresponding to the approximate solution are determined by solving an approximating quadratic programming problem.     

On Weak and Strong Kuhn–Tucker Conditions for Smooth Multiobjective Optimization

We consider a smooth multiobjective optimization problem with inequality constraints. Weak Kuhn?CTucker (WKT) optimality conditions are said to hold for such problems when not all the multipliers of the objective functions are zero, while strong Kuhn?CTucker (SKT) conditions are said to hold when all the multipliers of the objective functions are positive. We introduce a new regularity condition under which (WKT) hold. Moreover, we prove that for another new regularity condition (SKT) hold at every Geoffrion-properly efficient point. We show with an example that the assumption on proper efficiency cannot be relaxed. Finally, we prove that Geoffrion-proper efficiency is not needed when the constraint set is polyhedral and the objective functions are linear.     

The Karush–Kuhn–Tucker optimality conditions in multiobjective programming problems with interval-valued objective functions

The KKT conditions in multiobjective programming problems with interval-valued objective functions are derived in this paper. Many concepts of Pareto optimal solutions are proposed by considering two orderings on the class 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 are able to consider the continuity and differentiability of an interval-valued function. The KKT optimality conditions can then be naturally elicited.     

A simple and elementary proof of the Karush–Kuhn–Tucker theorem for inequality-constrained optimization

We present an elementary proof of the Karush–Kuhn–Tucker Theorem for the problem with nonlinear inequality constraints and linear equality constraints. Most proofs in the literature rely on advanced optimization concepts such as linear programming duality, the convex separation theorem, or a theorem of the alternative for systems of linear inequalities. By contrast, the proof given here uses only basic facts from linear algebra and the definition of differentiability.     

Improvement of Karush–Kuhn–Tucker conditions under uncertainties using robust decision making indexes

Almost all practical engineering problems work with uncertainties. Particularly, in chemical engineering problems, uncertainties in process models and measurements increase complexity on optimization modeling. In these cases, points are transformed in regions, and the point conditions need to be extended to its neighborhood. Extension and validation of Karush–Kuhn–Tucker (KKT) conditions under uncertainties scenarios are not trivial. In this paper, we propose two new conditions to improve robustness at second order KKT conditions.     

Kuhn–Tucker Conditions for a Convex Programming Problem in Banach Spaces Partially Ordered by Cone with Empty Interior

The existence of saddle point of the Lagrange function for a convex programming problem in Banach spaces ordered by a cone with empty interior is established under a strong simultaneity condition. As a consequence, the Kuhn–Tucker conditions are derived. It is shown that the Slater and the strong simultaneity condition are equivalent if the cone determining the partial order has an interior.     

Levitin–Polyak Well-Posedness for Optimization Problems with Generalized Equilibrium Constraints

In this paper, we consider Levitin–Polyak well-posedness of parametric generalized equilibrium problems and optimization problems with generalized equilibrium constraints. Some criteria for these types of well-posedness are derived. In particular, under certain conditions, we show that generalized Levitin–Polyak well-posedness of a parametric generalized equilibrium problem is equivalent to the nonemptiness and compactness of its solution set. Finally, for an optimization problem with generalized equilibrium constraints, we also obtain that, under certain conditions, Levitin–Polyak well-posedness in the generalized sense is equivalent to the nonemptiness and compactness of its solution set.     

Properties of equation reformulation of the Karush–Kuhn–Tucker condition for nonlinear second order cone optimization problems

We give an equation reformulation of the Karush–Kuhn–Tucker (KKT) condition for the second order cone optimization problem. The equation is strongly semismooth and its Clarke subdifferential at the KKT point is proved to be nonsingular under the constraint nondegeneracy condition and a strong second order sufficient optimality condition. This property is used in an implicit function theorem of semismooth functions to analyze the convergence properties of a local sequential quadratic programming type (for short, SQP-type) method by Kato and Fukushima (Optim Lett 1:129–144, 2007). Moreover, we prove that, a local solution x* to the second order cone optimization problem is a strict minimizer of the Han penalty merit function when the constraint nondegeneracy condition and the strong second order optimality condition are satisfied at x*.     

An elementary proof of the Karush–Kuhn–Tucker theorem in normed linear spaces for problems with a finite number of inequality constraints

We present an elementary proof of the Karush–Kuhn–Tucker theorem for the problem with a finite number of nonlinear inequality constraints in normed linear spaces under the linear independence constraint qualification. Most proofs in the literature rely on advanced concepts and results such as the convex separation theorem and Farkas, lemma. By contrast, the proofs given in this article, including a proof of the lemma, employ only basic results from linear algebra. The lemma derived in this article represents an independent theoretical result.     

Solving the Karush–Kuhn–Tucker system of a nonconvex programming problem on an unbounded set

In the papers [G.C. Feng, B. Yu, Combined homotopy interior point method for nonlinear programming problems, in: H. Fujita, M. Yamaguti (Eds.), Advances in Numerical Mathematics; Proceedings of the Second Japan–China Seminar on Numerical Mathematics, in: Lecture Notes in Numerical and Applied Analysis, vol. 14, Kinokuniya, Tokyo, 1995, pp. 9–16; G.C. Feng, Z.H. Lin, B. Yu, Existence of an interior pathway to a Karush–Kuhn–Tucker point of a nonconvex programming problem, Nonlinear Analysis 32 (1998) 761–768; Z.H. Lin, B. Yu, G.C. Feng, A combined homotopy interior point method for convex programming problem, Applied Mathematics and Computation 84 (1997) 193–211], a combined homotopy interior method was presented and global convergence results obtained for nonconvex nonlinear programming when the feasible set is bounded and satisfies the so called normal cone condition. However, for when the feasible set is not bounded, no result has so far been obtained. In this paper, a combined homotopy interior method for nonconvex programming problems on the unbounded feasible set is considered. Under suitable additional assumptions, boundedness of the homotopy path, and hence global convergence, is proven.     

Convergence Properties of Modified and Partially-Augmented Lagrangian Methods for Mathematical Programs with Complementarity Constraints

We present new convergence properties of partially augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Four modified partially augmented Lagrangian methods for MPCC based on different algorithmic strategies are proposed and analyzed. We show that the convergence of the proposed methods to a B-stationary point of MPCC can be ensured without requiring the boundedness of the multipliers.     

New perspective on the Kuhn–Tucker theorem

A new proof of the Kuhn–Tucker theorem on necessary conditions for a minimum of a differentiable function of several variables in the case of inequality constraints is given. The proof relies on a simple inequality (common in textbooks) for the projection of a vector onto a convex set.     

Convergent Bounds for Stochastic Programs with Expected Value Constraints

This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.