Unifying Optimal Partition Approach to Sensitivity Analysis in Conic Optimization

We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as functions of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the optimal partition approach to sensitivity analysis in LP and SDP, the range of perturbations for which the optimal partition remains constant can be computed by solving two conic optimization problems. Under a weaker notion of nondegeneracy, this range is simply given by a minimum ratio test. We discuss briefly the properties of the optimal value function under such perturbations.     

Local stability of solutions to differentiable optimization problems in banach spaces

This paper considers a class of nonlinear differentiable optimization problems depending on a parameter. We show that, if constraint regularity, a second-order sufficient optimality condition, and a stability condition for the Lagrange multipliers hold, then for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions locally obey a type of Lipschitz condition. The results are applied to finite-dimensional problems, equality constrained problems, and optimal control problems.     

Stability and accuracy functions in multicriteria linear combinatorial optimization problems

We consider a vector linear combinatorial optimization problem in which initial coefficients of objective functions are subject to perturbations. For Pareto and lexicographic principles of efficiency we introduce appropriate measures of the quality of a given feasible solution. These measures correspond to so-called stability and accuracy functions defined earlier for scalar optimization problems. Then we study properties of such functions and calculate the maximum norms of perturbations for which an efficient solution preserves the efficiency. This work was partially supported through NATO Science Fellowship grant.     

Conjugate dual problems in constrained set-valued optimization and applications

In this paper, two conjugate dual problems are proposed by considering the different perturbations to a set-valued vector optimization problem with explicit constraints. The weak duality, inclusion relations between the image sets of dual problems, strong duality and stability criteria are investigated. Some applications to so-called variational principles for a generalized vector equilibrium problem are shown.     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

A nonisolated optimal solution for special reverse convex programming problems

In this paper, an efficient algorithm is proposed for globally solving special reverse convex programming problems with more than one reverse convex constraints. The proposed algorithm provides a nonisolated global optimal solution which is also stable under small perturbations of the constraints, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiment is given to illustrate the feasibility of the presented algorithm.     

Stability of Discrete Approximations and Necessary Optimality Conditions for Delay-Differential Inclusions

This paper is devoted to the study of optimization problems for dynamical systems governed by constrained delay-differential inclusions with generally nonsmooth and nonconvex data. We provide a variational analysis of the dynamic optimization problems based on their data perturbations that involve finite-difference approximations of time-derivatives matched with the corresponding perturbations of endpoint constraints. The key issue of such an analysis is the justification of an appropriate strong stability of optimal solutions under finite-dimensional discrete approximations. We establish the required pointwise convergence of optimal solutions and obtain necessary optimality conditions for delay-differential inclusions in intrinsic Euler–Lagrange and Hamiltonian forms involving nonconvex-valued subdifferentials and coderivatives of the initial data.     

Scalarization and Stability in Vector Optimization

A class of scalarizations of vector optimization problems is studied in order to characterize weakly efficient, efficient, and properly efficient points of a nonconvex vector problem. A parallelism is established between the different solutions of the scalarized problem and the various efficient frontiers. In particular, properly efficient points correspond to stable solutions with respect to suitable perturbations of the feasible set.     

Continuous perturbations of infinite optimization problems

In this paper, continuity properties of the extremal value function and the solution function are studied for general optimization problems with perturbations in the objective function and the constraints. A classical stability condition is extended and compared with constraint qualification conditions.     

Descent methods with linesearch in the presence of perturbations

We consider the class of descent algorithms for unconstrained optimization with an Armijo-type stepsize rule in the case when the gradient of the objective function is computed inexactly. An important novel feature in our theoretical analysis is that perturbations associated with the gradient are not assumed to be relatively small or to tend to zero in the limit (as a practical matter, we expect them to be reasonably small, so that a meaningful approximate solution can be obtained). This feature makes our analysis applicable to various difficult problems encounted in practice. We propose a modified Armijo-type rule for computing the stepsize which guarantees that the algorithm obtains a reasonable approximate solution. Furthermore, if perturbations are small relative to the size of the gradient, then our algorithm retains all the standard convergence properties of descent methods.     

Conical diffraction by periodic structures: Variation of interfaces and gradient formulas

This paper studies the dependence of solutions to conical diffraction problems upon geometric parameters of non–smooth profiles and interfaces between different materials of diffractive gratings. This problem arises in the design of those optical devices to diffract time–harmonic oblique incident plane waves to a specified far–field pattern. We prove the stability of solutions and give analytic formulas for the derivatives of reflection and transmission coefficients with respect to Lipschitz perturbations of interfaces. These derivatives are expressible as contour integrals involving the direct and adjoint solutions of conical diffraction problems.     

Well-Posedness by Perturbations of Variational Problems

In this paper, we consider the extension of the notion of well-posedness by perturbations, introduced by Zolezzi for optimization problems, to other related variational problems like inclusion problems and fixed-point problems. Then, we study the conditions under which there is equivalence of the well-posedness in the above sense between different problems. Relations with the so-called diagonal well-posedness are also given. Finally, an application to staircase iteration methods is presented.     

Sensitivity analysis to perturbations of the weight of a subset of items: The knapsack case study

In this paper, we study the sensitivity of the optimum to perturbations of the weight of a subset of items of both the knapsack problem (denoted KP) and knapsack sharing problem (denoted KSP). The sensitivity interval of the weight associated to an item is characterized by two limits, called lower and upper values, which guarantee the optimality of the solution at hand whenever the new weight’s value belongs to such an interval. For each perturbed weight, we try to establish approximate values of the sensitivity interval whenever the original problem is solved. We do it by applying a dynamic programming method where all established results require a negligible runtime. First, two cases are studied when considering an optimal solution of KP: (i) the case in which all perturbations are (non)negatives and (ii) the general case in which the set of the perturbed items is divided into two disjoint subsets (the first subset contains the nonnegative perturbations and the second one represents the subset of negative perturbations). Second, we show how we can adapt the results of KP to the KSP. All established results require a negligible runtime which grows the interest of such a study. Finally, for each of these problems, we will see the impact of the established results on an example while considering the various cases.     

Different Conjugate Dual Problems in Vector Optimization and Their Relations

In this paper, three kinds of conjugate dual problems are constructed by virtue of different perturbations to a constrained vector optimization problem. Weak duality, strong duality, and some inclusion relations for the image sets of the three dual problems are established. This research was partially supported by the National Natural Science Foundation of China (Grant Number 60574073) and the Natural Science Foundation Project of CQ CSTC (Grant Number 2007BB6117). The authors thank two anonymous referees for valuable comments and suggestions, which helped improving the paper.     

Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem

In this article we consider the boolean optimization problem of finding the set of Pareto optimal solutions. The vector objectives are the positive cuts of linear functions to the non-negative semi-axis. Initial data are subject to perturbations, measured by the l ₁-norm in the parameter space of the problem. We present the formula expressing the extreme level (stability radius) of such perturbations, for which a particular solution remains Pareto optimal.     

On Quantitative Stability in Optimization and Optimal Control

We study two continuity concepts for set-valued maps that play central roles in quantitative stability analysis of optimization problems: Aubin continuity and Lipschitzian localization. We show that various inverse function theorems involving these concepts can be deduced from a single general result on existence of solutions to an inclusion in metric spaces. As applications, we analyze the stability with respect to canonical perturbations of a mathematical program in a Hilbert space and an optimal control problem with inequality control constraints. For stationary points of these problems, Aubin continuity and Lipschitzian localization coincide; moreover, both properties are equivalent to surjectivity of the map of the gradients of the active constraints combined with a strong second-order sufficient optimality condition.     

Stability of solutions for a class of nonlinear cone constrained optimization problems,part 1: Basic theory

We Gonsider a class of nonlinear cone constrained optimization problems depending on a parameter. Under the assumption of a constraint qualification, a second order sufficient optimality condition and a stability condition for the Lagrange multipliers it is shown, that for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions obey a type of Lipschitz condition.     

Selected topics in robust convex optimization

Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but- bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional chance constrained settings of problems with stochastic data, and (4) a novel generic application of the RO methodology in Robust Linear Control.