Saturation in Linear Optimization

In a solvable linear optimization problem, a constraint is saturated if it is binding at a certain optimal solution and it is weakly saturated if it is binding at a proper subset of the optimal set. Nonsaturation and weak saturation can be seen as redundancy phenomena in the sense that the elimination of a finite number of these constraints preserves the value of the given problem. We consider also the effect of sufficiently small perturbations of the cost coefficients in the classification of a given constraint as either saturated or nonsaturated.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization

Active constraint set invariancy sensitivity analysis is concerned with finding the range of parameter variation so that the perturbed problem has still an optimal solution with the same support set that the given optimal solution of the unperturbed problem has. However, in an optimization problem with inequality constraints, active constraint set invariancy sensitivity analysis aims to find the range of parameter variation, where the active constraints in a given optimal solution remains invariant.For the sake of simplicity, we consider the primal problem in standard form and consequently its dual may have an optimal solution with some active constraints. In this paper, the following question is answered: “what is the range of the parameter, where for each parameter value in this range, a dual optimal solution exists with exactly the same set of positive slack variables as for the current dual optimal solution?”. The differences of the results between the linear and convex quadratic optimization problems are highlighted too.     

A Note on Redundancy and Linear Parametric Programming

A simple redundancy criterion for a system of linear inequalities is given. Considering a linear programming problem with linear inequality constraints the sensitivity analysis of the optimal solution of the right-hand side in combination with the redundancy criterion can help to identify redundant inequalities (constraints). The redundancy criterion is applied to a linear parametric problem which is enlarged by an auxiliary condition such as "stop the parametric procedure when a chosen constraint becomes redundant".     

Regularity properties of optimal controls for problems with time-varying state and control constraints

In this paper we report new results on the regularity of optimal controls for dynamic optimization problems with functional inequality state constraints, a convex time-dependent control constraint and a coercive cost function. Recently, it has been shown that the linear independence condition on active state constraints, present in the earlier literature, can be replaced by a less restrictive, positive linear independence condition, that requires linear independence merely with respect to non-negative weighting parameters, provided the control constraint set is independent of the time variable. We show that, if the control constraint set, regarded as a time-dependent multifunction, is merely Lipschitz continuous with respect to the time variable, then optimal controls can fail to be Lipschitz continuous. In these circumstances, however, a weaker Hölder continuity-like regularity property can be established. On the other hand, Lipschitz continuity of optimal controls is guaranteed for time-varying control sets under a positive linear independence hypothesis, when the control constraint sets are described, at each time, by a finite collection of functional inequalities.     

A Lower Bound for the Penalty Parameter in the Exact Minimax Penalty Function Method for Solving Nondifferentiable Extremum Problems

In the paper, we consider the exact minimax penalty function method used for solving a general nondifferentiable extremum problem with both inequality and equality constraints. We analyze the relationship between an optimal solution in the given constrained extremum problem and a minimizer in its associated penalized optimization problem with the exact minimax penalty function under the assumption of convexity of the functions constituting the considered optimization problem (with the exception of those equality constraint functions for which the associated Lagrange multipliers are negative—these functions should be assumed to be concave). The lower bound of the penalty parameter is given such that, for every value of the penalty parameter above the threshold, the equivalence holds between the set of optimal solutions in the given extremum problem and the set of minimizers in its associated penalized optimization problem with the exact minimax penalty function.     

On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}

While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value ofk such that all valid inequalities for the set covering polytope with integer coefficients no greater thank are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation.Research supported by the National Science Foundation through grant ECS-8503198 and the Office of Naval Research through contract N0001485-K-0198.     

On the Gap Functions of Prevariational Inequalities

Gap functions play a crucial role in transforming a variational inequality problem into an optimization problem. Then, methods solving an optimization problem can be exploited for finding a solution of a variational inequality problem. It is known that the so-called prevariational inequality is closely related to some generalized convex functions, such as linear fractional functions. In this paper, gap functions for several kinds of prevariational inequalities are investigated. More specifically, prevariational inequalities, extended prevariational inequalities, and extended weak vector prevariational inequalities are considered. Furthermore, a class of gap functions for inequality constrained prevariational inequalities is investigated via a nonlinear Lagrangian.     

Linear programming in measure spaces

This paper studies a linear programming problem in measure spaces (LPM). Several results are obtained. First, the optimal value of LPM can be equal to the optimal value of the dual problem (DLPM), but the solution of DLPM may be not exist in its feasible region. Sccond, :he relations between the optimal solution of LPM and the extreme point of the feasible region of LPM are discussed. In order to investigate the conditions under which a feasible solution becomes an extremal point, the inequality constraint of LPM is transformed to an equality constraint. Third, the LPM can be reformulated to be a general capacity problem (GCAP) or a linear semi-infinite programming problem (LSIP = SIP), and under appropriate restrictioiis, the algorithm developed by the authors in [7] and [8] are applicable for developing an approximation scheme for the optimal solution of LPM     

Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.     

Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

A Result on Vector Variational Inequalities with Polyhedral Constraint Sets

In this note, by using some well-known results on properly efficient solutions of vector optimization problems, we show that the Pareto solution set of a vector variational inequality with a polyhedral constraint set can be expressed as the union of the solution sets of a family of (scalar) variational inequalities.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

Deriving crisp and consistent priorities for fuzzy AHP-based multicriteria systems using non-linear constrained optimization

Fuzzy optimization models are used to derive crisp weights (priority vectors) for the fuzzy analytic hierarchy process (AHP) based multicriteria decision making systems. These optimization models deal with the imprecise judgements of decision makers by formulating the optimization problem as the system of constrained non linear equations. Firstly, a Genetic Algorithm based heuristic solution for this optimization problem is implemented in this paper. It has been found that the crisp weights derived from this solution for fuzzy-AHP system, sometimes lead to less consistent or inconsistent solutions. To deal with this problem, we have proposed a consistency based constraint for the optimization models. A decision maker can set the consistency threshold value and if the solution exists for that threshold value then crisp weights can be derived, otherwise it can be concluded that the fuzzy comparison matrix for AHP is not consistent for the given threshold. Three examples are considered to demonstrate the effectiveness of the proposed method. Results with the proposed constraint based fuzzy optimization model are more consistent than the existing optimization models.     

On proto-differentiability of generalized perturbation maps

This paper is devoted to the sensitivity analysis in optimization problems and variational inequalities. The concept of proto-differentiability of set-valued maps (see [R.T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré Anal. Non Linéaire 6 (1989) 449-482]) plays the key role in our investigation. It is proved that, under some suitable qualification conditions, the generalized perturbation maps (that is, the solution set map to a parameterized constraint system, to a parameterized variational inequality, or to a parameterized optimization problem) are proto-differentiable.     

On Approximate KKT Condition and its Extension to Continuous Variational Inequalities

In this work, we introduce a necessary sequential Approximate-Karush-Kuhn-Tucker (AKKT) condition for a point to be a solution of a continuous variational inequality, and we prove its relation with the Approximate Gradient Projection condition (AGP) of Gárciga-Otero and Svaiter. We also prove that a slight variation of the AKKT condition is sufficient for a convex problem, either for variational inequalities or optimization. Sequential necessary conditions are more suitable to iterative methods than usual punctual conditions relying on constraint qualifications. The AKKT property holds at a solution independently of the fulfillment of a constraint qualification, but when a weak one holds, we can guarantee the validity of the KKT conditions.     

A note on issues of over-conservatism in robust optimization with cost uncertainty

We identify and discuss issues of hidden over-conservatism in robust linear optimization, when the uncertainty set is polyhedral with a budget of uncertainty constraint. The decision-maker selects the budget of uncertainty to reflect his degree of risk aversion, i.e. the maximum number of uncertain parameters that can take their worst-case value. In the first setting, the cost coefficients of the linear programming problem are uncertain, as is the case in portfolio management with random stock returns. We provide an example where, for moderate values of the budget, the optimal solution becomes independent of the nominal values of the parameters, i.e. is completely disconnected from its nominal counterpart, and discuss why this happens. The second setting focusses on linear optimization with uncertain upper bounds on the decision variables, which has applications in revenue management with uncertain demand and can be rewritten as a piecewise linear problem with cost uncertainty. We show in an example that it is possible to have more demand parameters equal their worst-case value than what is allowed by the budget of uncertainty, although the robust formulation is correct. We explain this apparent paradox.