A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

Twenty years of linear programming based portfolio optimization

Markowitz formulated the portfolio optimization problem through two criteria: the expected return and the risk, as a measure of the variability of the return. The classical Markowitz model uses the variance as the risk measure and is a quadratic programming problem. Many attempts have been made to linearize the portfolio optimization problem. Several different risk measures have been proposed which are computationally attractive as (for discrete random variables) they give rise to linear programming (LP) problems. About twenty years ago, the mean absolute deviation (MAD) model drew a lot of attention resulting in much research and speeding up development of other LP models. Further, the LP models based on the conditional value at risk (CVaR) have a great impact on new developments in portfolio optimization during the first decade of the 21st century. The LP solvability may become relevant for real-life decisions when portfolios have to meet side constraints and take into account transaction costs or when large size instances have to be solved. In this paper we review the variety of LP solvable portfolio optimization models presented in the literature, the real features that have been modeled and the solution approaches to the resulting models, in most of the cases mixed integer linear programming (MILP) models. We also discuss the impact of the inclusion of the real features.     

Clustering Effect for Stationary Points of Discrepancy Functionals Associated with Conditionally Well-Posed Inverse Problems

In a Hilbert space we consider a class of conditionally well-posed inverse problems for which a Hölder-type estimate of conditional stability on a closed convex bounded subset holds. We investigate the Ivanov quasi-solution method and its finite-dimensional version associated with minimization of a multi-extremal discrepancy functional over a conditional stability set or over a finite-dimensional section of this set, respectively. For these optimization problems, we prove that each of their stationary points that is located not too far from the desired solution of the original inverse problem belongs to a small neighborhood of the solution. Estimates for the diameter of this neighborhood in terms of error levels in input data are also given.     

Inverse problems for stationary Navier-Stokes systems

An inverse problem for a nonlinear equation in a Hilbert space is considered in which the right-hand side that is a linear combination of given functionals is found from given values of these functionals on the solution. Sufficient conditions for the existence of a solution are established, and the solution set is shown to be homeomorphic to a finite-dimensional compact set. A boundary inverse problem for the three-dimensional thermal convection equations for a viscous incompressible fluid and an inverse magnetohydrodynamics problem are considered as applications.     

Efficient optimization of the reward-risk ratio with polyhedral risk measures

In problems of portfolio selection the reward-risk ratio criterion is optimized to search for a risky portfolio offering the maximum increase of the mean return, compared to the risk-free investment opportunities. In the classical model, following Markowitz, the risk is measured by the variance thus representing the Sharpe ratio optimization and leading to the quadratic optimization problems. Several polyhedral risk measures, being linear programming (LP) computable in the case of discrete random variables represented by their realizations under specified scenarios, have been introduced and applied in portfolio optimization. The reward-risk ratio optimization with polyhedral risk measures can be transformed into LP formulations. The LP models typically contain the number of constraints proportional to the number of scenarios while the number of variables (matrix columns) proportional to the total of the number of scenarios and the number of instruments. Real-life financial decisions are usually based on more advanced simulation models employed for scenario generation where one may get several thousands scenarios. This may lead to the LP models with huge number of variables and constraints thus decreasing their computational efficiency and making them hardly solvable by general LP tools. We show that the computational efficiency can be then dramatically improved by alternative models based on the inverse ratio minimization and taking advantages of the LP duality. In the introduced models the number of structural constraints (matrix rows) is proportional to the number of instruments thus not affecting seriously the simplex method efficiency by the number of scenarios and therefore guaranteeing easy solvability.     

A new regularized stochastic approximation framework for stochastic inverse problems

We study the nonlinear inverse problem of estimating stochastic parameters in the fourth-order partial differential equation with random data. The primary focus is on developing a novel stochastic approximation framework for inverse problems consisting of three key components. As a first step, we reformulate the inverse problem into a stochastic convex optimization problem. The second step includes developing a new regularized stochastic extragradient framework for a nonlinear variational inequality, which subsumes the optimality conditions for the optimization formulation of the inverse problem. The third step involves modeling random variables by a Karhunen–Loève type finite-dimensional noise representation, allowing the direct and the inverse problems to be conveniently discretized. We show that the regularized extragradient methods are strongly convergent in a Hilbert space setting, and we also provide several auxiliary results for the inverse problem, including Lipschitz continuity and a derivative characterization of the solution map. We provide the outcome of computational experiments to estimate stochastic and deterministic parameters. The numerical results demonstrate the feasibility and effectiveness of the developed framework and validate stochastic approximation as an effective method for stochastic inverse problems.     

Characterizations of the Nonemptiness and?Boundedness of Weakly Efficient Solution Sets of?Convex Vector Optimization Problems in Real Reflexive?Banach Spaces

Under a weak compactness assumption on the functions involved, which always holds in finite-dimensional normed linear spaces, this paper extends various characterizations of the nonemptiness and boundedness of weakly efficient solution sets of convex vector optimization problems, obtained previously by the author (Deng in J. Optim. Theory Appl. 96:123–131, 1998) in the real finite-dimensional normed linear space setting, to those in the real reflexive Banach space setting.     

Two-stage fuzzy production planning expected value model and its approximation method

This work develops a novel two-stage fuzzy optimization method for solving the multi-product multi-period (MPMP) production planning problem, in which the market demands and some of the inventory costs are assumed to be uncertainty and characterized by fuzzy variables with known possibility distributions. Some basic properties about the MPMP production planning problem are discussed. Since the fuzzy market demands and inventory costs usually have infinite supports, the proposed two-stage fuzzy MPMP production planning problem is an infinite-dimensional optimization problem that cannot be solved directly by conventional numerical solution methods. To overcome this difficulty, this paper adopts an approximation method (AM) to turn the original two-stage fuzzy MPMP production planning problem into a finite-dimensional optimization problem. The convergence about the AM is discussed to ensure the solution quality. After that, we design a heuristic algorithm, which combines the AM and simulated annealing (SA) algorithm, to solve the proposed two-stage fuzzy MPMP production planning problem. Finally, one real case study about a furniture manufacturing company is presented to illustrate the effectiveness and feasibility of the proposed modeling idea and designed algorithm.     

On an inverse linear programming problem

A method for solving the following inverse linear programming (LP) problem is proposed. For a given LP problem and one of its feasible vectors, it is required to adjust the objective function vector as little as possible so that the given vector becomes optimal. The closeness of vectors is estimated by means of the Euclidean vector norm. The inverse LP problem is reduced to a problem of unconstrained minimization for a convex piecewise quadratic function. This minimization problem is solved by means of the generalized Newton method.     

Optimal Prioritized Infeasibility Handling in Model Predictive Control: Parametric Preemptive Multiobjective Linear Programming Approach

All practical implementations of model-based predictive control (MPC) require a means to recover from infeasibility. We propose a strategy designed for linear state-space MPC with prioritized constraints. It relaxes optimally an infeasible MPC optimization problem into a feasible one by solving a single-objective linear program (LP) online in addition to the standard online MPC optimization problem at each sample. By optimal, it is meant that the violation of a lower prioritized constraint cannot be made less without increasing the violation of a higher prioritized constraint. The problem of computing optimal constraint violations is naturally formulated as a parametric preemptive multiobjective LP. By extending well-known results from parametric LP, the preemptive multiobjective LP is reformulated into an equivalent standard single-objective LP. An efficient algorithm for offline design of this LP is given, and the algorithm is illustrated on an example.     

An approximate solution of a Fredholm integral equation of the first kind by the residual method

A Tikhonov finite-dimensional approximation is applied to a Fredholm integral equation of the first kind. This allows using a variational regularization method with a regularization parameter from the residual principle and reducing the problem to a system of linear algebraic equations. The accuracy of the approximate solution is estimated with allowance for the error of the finitedimensional approximation of the problem. The use of this approach is illustrated by solving an inverse boundary value problem for the heat conduction equation.     

On an optimal shape design problem to control a thermoelastic deformation under a prescribed thermal treatment

A shape optimization problem concerned with thermal deformation of elastic bodies is considered. In this article, measure theory approach in function space is derived, resulting in an effective algorithm for the discretized optimization problem. First the problem is expressed as an optimal control problem governed by variational forms on a fixed domain. Then by using an embedding method, the class of admissible shapes is replaced by a class of positive Borel measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this finite-dimensional linear programming problem. Numerical examples are also given.     

A multidimensional tropical optimization problem with a non-linear objective function and linear constraints

We examine a multidimensional optimization problem in the tropical mathematics setting. The problem involves the minimization of a non-linear function defined on a finite-dimensional semimodule over an idempotent semifield subject to linear inequality constraints. We start with an overview of known tropical optimization problems with linear and non-linear objective functions. A short introduction to tropical algebra is provided to offer a formal framework for solving the problem under study. As a preliminary result, a solution to a linear inequality with an arbitrary matrix is presented. We describe an example optimization problem drawn from project scheduling and then offer a general representation of the problem. To solve the problem, we introduce an additional variable and reduce the problem to the solving of a linear inequality, in which the variable plays the role of a parameter. A necessary and sufficient condition for the inequality to hold is used to evaluate the parameter, whereas the solution to the inequality is considered a solution to the problem. Based on this approach, a complete direct solution in a compact vector form is derived for the optimization problem under fairly general conditions. Numerical and graphical examples for two-dimensional problems are given to illustrate the obtained results.     

A column generation method for inverse shortest path problems

In this paper we formulate an inverse shortest path problem as a special linear programming problem. A column generation scheme is developed that is able to keep most columns of the LP model implicit and to generate necessary columns by shortest path algorithms. This method can get an optimal solution in finitely many steps. Some numerical results are reported to show that the algorithm has a good performance.The authors gratefully acknowledge the partial support of Croucher Foundation.     

A new approach for solving fully intuitionistic fuzzy transportation problems

In this paper, a well-known network-structured problem called the transportation problem (TP) is considered in an uncertain environment. The transportation costs, supply and demand are represented by trapezoidal intuitionistic fuzzy numbers (TrIFNs) which are the more generalized form of trapezoidal fuzzy numbers involving a degree of acceptance and a degree of rejection. We formulate the intuitionistic fuzzy TP (IFTP) and propose a solution approach to solve the problem. The IFTP is converted into a deterministic linear programming (LP) problem, which is solved using standard LP algorithms. The main contributions of this paper are fivefold: (1) we convert the formulated IFTP into a deterministic classical LP problem based on ordering of TrIFNs using accuracy function; (2) in contrast to most existing approaches, which provide a crisp solution, we propose a new approach that provides an intuitionistic fuzzy optimal solution; (3) in contrast to existing methods that include negative parts in the obtained intuitionistic fuzzy optimal solution and intuitionistic fuzzy optimal cost, we propose a new method that provides non-negative intuitionistic fuzzy optimal solution and optimal cost; (4) we discuss about the advantages of the proposed method over the existing methods for solving IFTPs; (5) we demonstrate the feasibility and richness of the obtained solutions in the context of two application examples.     

Inverse optimization: towards the optimal parameter set of inverse LP with interval coefficients

We study the inverse optimization problem in the following formulation: given a family of parametrized optimization problems and a real number called demand, determine for which values of parameters the optimal value of the objective function equals to the demand. We formulate general questions and problems about the optimal parameter set and the optimal value function. Then we turn our attention to the case of linear programming, when parameters can be selected from given intervals (“inverse interval LP”). We prove that the problem is NP-hard not only in general, but even in a very special case. We inspect three special cases—the case when parameters appear in the right-hand sides, the case when parameters appear in the objective function, and the case when parameters appear in both the right-hand sides and the objective function. We design a technique based on parametric programming, which allows us to inspect the optimal parameter set. We illustrate the theory by examples.     

A new method for interpolating in a convex subset of a Hilbert space

In this paper, interpolating curve or surface with linear inequality constraints is considered as a general convex optimization problem in a Reproducing Kernel Hilbert Space. The aim of the present paper is to propose an approximation method in a very general framework based on a discretized optimization problem in a finite-dimensional Hilbert space under the same set of constraints. We prove that the approximate solution converges uniformly to the optimal constrained interpolating function. Numerical examples are provided to illustrate this result in the case of boundedness and monotonicity constraints in one and two dimensions.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

Plastic Structural Analysis Under Stochastic Uncertainty

Problems from limit load or shakedown analysis are based on the convex, linear or linearized yield/strength condition and the linear equilibrium equation for the generic stress vector. Having to take into account, in practice, stochastic variations of the model parameters (e.g., yield stresses, plastic capacities) and external loadings, the basic stochastic plastic analysis problem must be replaced by an appropriate deterministic substitute problem. Instead of calculating approximatively the probability of failure based on a certain choice of failure modes, here, a direct approach is presented based on the costs for missing carrying capacity and the failure costs (e.g., costs for damage, repair, compensation for weakness within the structure, etc.). Based on the basic mechanical survival conditions, the failure costs may be represented by the minimum value of a convex and often linear program. Several mathematical properties of this program are shown. Minimizing then the total expected costs subject to the remaining (simple) deterministic constraints, a stochastic optimization problem is obtained which may be represented by a “Stochastic Convex Program (SCP) with recourse”. Working with linearized yield/strength conditions, a “Stochastic Linear Program (SLP) with complete fixed recourse” is obtained. In case of a discretely distributed probability distribution or after the discretization of a more general probability distribution of the random structural parameters and loadings as well as certain random cost factors one has a linear program (LP) with a so-called “dual decomposition data” structure. For stochastic programs of this type many theoretical results and efficient numerical solution procedures (LP-solver) are available. The mathematical properties of theses substitute problems are considered. Furthermore approximate analytical formulas for the limit load factor are given.     

Characterizations of the nonemptiness and compactness for solution sets of convex set-valued optimization problems

In this paper, we first derive several characterizations of the nonemptiness and compactness for the solution set of a convex scalar set-valued optimization problem (with or without cone constraints) in which the decision space is finite-dimensional. The characterizations are expressed in terms of the coercivity of some scalar set-valued maps and the well-posedness of the set-valued optimization problem, respectively. Then we investigate characterizations of the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) in which the objective space is a normed space ordered by a nontrivial, closed and convex cone with nonempty interior and the decision space is finite-dimensional. We establish that the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) can be exactly characterized as those of a family of linearly scalarized convex set-valued optimization problems and the well-posedness of the original problem.