Is bilevel programming a special case of a mathematical program with complementarity constraints?

Bilevel programming problems are often reformulated using the Karush–Kuhn–Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints(MPCC). Clearly, both problems are closely related. But the answer to the question posed is “No” even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater’s constraint qualification. We also show by examples that this correspondence can fail if the Slater’s constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

A variational problem determined by probability measures

ABSTRACT

An optimization problem of maximizing an integral of a function over a family of probability measures is considered. The problem is a generalization of a well-studied variational problem in mathematical economics, concerning optimal allocations. The specific generalization that we examine arises also in the limit of singularly perturbed optimal control problems. We examine the mathematical problem and allude to the singular perturbation motivation.     

Note on local quadratic growth estimates in bang–bang optimal control problems

Abstract

Strong second-order conditions in mathematical programming play an important role not only as optimality tests but also as an intrinsic feature in stability and convergence theory of related numerical methods. Besides of appropriate firstorder regularity conditions, the crucial point consists in local growth estimation for the objective which yields inverse stability information on the solution. In optimal control, similar results are known in case of continuous control functions, and for bang–bang optimal controls when the state system is linear. The paper provides a generalization of the latter result to bang–bang optimal control problems for systems which are affine-linear w.r.t. the control but depend nonlinearly on the state. Local quadratic growth in terms of L₁ norms of the control variation are obtained under appropriate structural and second-order sufficient optimality conditions.     

The inverse optimal value problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.Mathematics Subject Classification (1999):49N45, 90C05, 90C25, 90C26, 90C31, 90C60Acknowledgement This research has been supported in part by the National Science Foundation under CAREER Award DMII-0133943. The authors thank two anonymous reviewers for valuable comments.     

Uniqueness and stability of the minimizer for a binary functional arising in an inverse heat conduction problem

The local well-posedness of the minimizer of an optimal control problem is studied in this paper. The optimization problem concerns an inverse problem of simultaneously reconstructing the initial temperature and heat radiative coefficient in a heat conduction equation. Being different from other ordinary optimization problems, the cost functional constructed in the paper is a binary functional which contains two independent variables and two independent regularization parameters. Particularly, since the status of the two unknown coefficients in the cost functional are different, the conjugate theory which is extensively used in single-parameter optimization problems cannot be applied for our problem. The necessary condition which must be satisfied by the minimizer is deduced. By assuming the terminal time T is relatively small, an L² estimate regarding the minimizer is obtained, from which the uniqueness and stability of the minimizer can be deduced immediately.     

Solving Ill-posed Bilevel Programs

This paper deals with ill-posed bilevel programs, i.e., problems admitting multiple lower-level solutions for some upper-level parameters. Many publications have been devoted to the standard optimistic case of this problem, where the difficulty is essentially moved from the objective function to the feasible set. This new problem is simpler but there is no guaranty to obtain local optimal solutions for the original optimistic problem by this process. Considering the intrinsic non-convexity of bilevel programs, computing local optimal solutions is the best one can hope to get in most cases. To achieve this goal, we start by establishing an equivalence between the original optimistic problem and a certain set-valued optimization problem. Next, we develop optimality conditions for the latter problem and show that they generalize all the results currently known in the literature on optimistic bilevel optimization. Our approach is then extended to multiobjective bilevel optimization, and completely new results are derived for problems with vector-valued upper- and lower-level objective functions. Numerical implementations of the results of this paper are provided on some examples, in order to demonstrate how the original optimistic problem can be solved in practice, by means of a special set-valued optimization problem.     

Presentations of Bruck-Reilly Extensions and Decision Problems

We show that any Bruck-Reilly extension of an inverse monoid is an HNN extension of a certain inverse monoid. We also discuss several decision problems. The word problem for a Bruck-Reilly extension of an inverse monoid is solvable under a reasonable condition. On the other hand, many algebraic properties for Bruck-Reilly extensions of inverse monoids are undecidable. Key words : Inverse monoids, Bruck-Reilly extensions, HNN extensions, Decision problems. AMS Mathematics Subject Classification: 20M18, 20M05     

Solution of bilevel optimization problems using the KKT approach

ABSTRACT

Using the Karush–Kuhn–Tucker conditions for the convex lower level problem, the bilevel optimization problem is transformed into a single-level optimization problem (a mathematical program with complementarity constraints). A regularization approach for the latter problem is formulated which can be used to solve the bilevel optimization problem. This is verified if global or local optimal solutions of the auxiliary problems are computed. Stationary solutions of the auxiliary problems converge to C-stationary solutions of the mathematical program with complementarity constraints.     

Nonlinear Periodic Optimal Control: A Pseudospectral Fourier Approach

Abstract

A pseudospectral method for generating optimal trajectories of the class of periodic optimal control problems is proposed. The method consists of representing the solution of the periodic optimal control problem by an mth degree trigonometric interpolating polynomial, using Fourier nodes as grid points, and then discretizing the problem using the trapezoidal rule as the quadrature formula for smoothly differentiable periodic functions. The periodic optimal control problem is thereby transformed into an algebraic nonlinear programming problem. Due to its dynamic nature, the pseudospectral Fourier approach avoids many of the numerical difficulties typically encountered in solving standard periodic optimal control problems. An illustrative example is provided to demonstrate the applicability of the proposed method.     

Inverse problems for multi-valued quasi variational inequalities and noncoercive variational inequalities with noisy data

ABSTRACT

We study the inverse problem of identifying a variable parameter in variational and quasi-variational inequalities. We consider a quasi-variational inequality involving a multi-valued monotone map and give a new existence result. We then formulate the inverse problem as an optimization problem and prove its solvability. We also conduct a thorough study of the inverse problem of parameter identification in noncoercive variational inequalities which appear commonly in applied models. We study the inverse problem by posing optimization problems using the output least-squares and the modified output least-squares. Using regularization, penalization, and smoothing, we obtain a single-valued parameter-to-selection map and study its differentiability. We consider optimization problems using the output least-squares and the modified output least-squares for the regularized, penalized and smoothened variational inequality. We give existence results, convergence analysis, and optimality conditions. We provide applications and numerical examples to justify the proposed framework.     

On inverse traveling salesman problems

The inverse traveling salesman problem belongs to the class of ??inverse combinatorial optimization?? problems. In an inverse combinatorial optimization problem, we are given a feasible solution for an instance of a particular combinatorial optimization problem, and the task is to adjust the instance parameters as little as possible so that the given solution becomes optimal in the new instance. In this paper, we consider a variant of the inverse traveling salesman problem, denoted by ITSP _W,A , by taking into account a set W of admissible weight systems and a specific algorithm. We are given an edge-weighted complete graph (an instance of TSP), a Hamiltonian tour (a feasible solution of TSP) and a specific algorithm solving TSP. Then, ITSP _W,A , is the problem to find a new weight system in W which minimizes the difference from the original weight system so that the given tour can be selected by the algorithm as a solution. We consider the cases ${W \in \{\mathbb{R}^{+m}, \{1, 2\}^m , \Delta\}}$ where ?? denotes the set of edge weight systems satisfying the triangular inequality and m is the number of edges. As for algorithms, we consider a local search algorithm 2-opt, a greedy algorithm closest neighbor and any optimal algorithm. We devise both complexity and approximation results. We also deal with the inverse traveling salesman problem on a line for which we modify the positions of vertices instead of edge weights. We handle the cases ${W \in \{\mathbb{R}^{+n}, \mathbb{N}^n\}}$ where n is the number of vertices.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。     

Necessary conditions for optimality in relaxed stochastic control problems

In this paper, we are concerned with optimal control problems where the system is driven by a stochastic differential equation of the Ito type. We study the relaxed model for which an optimal solution exists. This is an extension of the initial control problem, where admissible controls are measure valued processes. Using Ekeland's variational principle and some stability properties of the corresponding state equation and adjoint processes, we establish necessary conditions for optimality satisfied by an optimal relaxed control. This is the first version of the stochastic maximum principle that covers relaxed controls.     

Well-posedness and inverse Robin estimate for a multiscale elliptic/parabolic system

Abstract

We establish the well-posedness of a coupled micro–macro parabolic–elliptic system modeling the interplay between two pressures in a gas–liquid mixture close to equilibrium that is filling a porous media with distributed microstructures. Additionally, we prove a local stability estimate for the inverse micro–macro Robin problem, potentially useful in identifying quantitatively a micro–macro interfacial Robin transfer coefficient given microscopic measurements on accessible fixed interfaces. To tackle the solvability issue we use two-scale energy estimates and two-scale regularity/compactness arguments cast in the Schauder’s fixed point theorem. A number of auxiliary problems, regularity, and scaling arguments are used in ensuring the suitable Fréchet differentiability of the solution and the structure of the inverse stability estimate.     

Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value, in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis over the convex hull of the upper-level integer variables.     

An inverse spectral problem for integro-differential Dirac operators with general convolution kernels

ABSTRACT

An integro-differential Dirac system with a convolution kernel consisting of four independent functions is considered. We prove that the kernel is uniquely determined by specifying the spectra of two boundary value problems with one common boundary condition. The proof is based on the reduction of this nonlinear inverse problem to solving some nonlinear integral equation, which we solve globally. On this basis we also obtain a constructive procedure for solving the inverse problem along with necessary and sufficient conditions for its solvability in an appropriate class of kernels.     

Identifying the radiative coefficient of an evolutional type heat conduction equation by optimization method

This paper studies an evolutional type inverse problem of identifying the radiative coefficient of heat conduction equation when the over-specified data is given. Problems of this type have important applications in several fields of applied science. Being different from other ordinary inverse coefficient problems, the unknown coefficient in this paper depends on both the space variable x and the time t. Based on the optimal control framework, the inverse problem is transformed into an optimization problem and a new cost functional is constructed in the paper. The existence, uniqueness and stability of the minimizer of the cost functional are proved, and the necessary conditions which must be satisfied by the minimizer are also given. The results obtained in the paper are interesting and useful, and can be extended to more general parabolic equations.     

Contingent derivatives and regularization for noncoercive inverse problems

Abstract

We study the inverse problem of parameter identification in noncoercive variational problems that commonly appear in applied models. We examine the differentiability of the set-valued parameter-to-solution map using the first-order and the second-order contingent derivatives. We explore the inverse problem using the output least-squares and the modified output least-squares objectives. By regularizing the noncoercive variational problem, we obtain a single-valued regularized parameter-to-solution map and investigate its smoothness and boundedness. We also consider optimization problems using the output least-squares and the modified output least-squares objectives for the regularized variational problem. We give a complete convergence analysis showing that for the output least-squares and the modified output least-squares, the regularized minimization problems approximate the original optimization problems suitably. We also provide the first-order and the second-order adjoint method for the computation of the first-order and the second-order derivatives of the output least-squares objective. We provide discrete formulas for the gradient and the Hessian calculation and present numerical results.