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.     

Solution approach to infinite linear programming problem with capacity constraints

The purpose of this article is to investigate a kind of infinite linear programming problem (ILPP) arising from infinite multiclass network equilibrium problems. In several cases, we construct special feasible solutions to the ILPP. By virtue of the nature of network, we prove that the solutions are optimal. Marcotte and Zhu (Oper Res Lett 37:211?C214, 2009) proved the existence of the valid tolls for the infinite multiclass network equilibrium problems. Based on this, we analyze the property of the tolls vector, i.e., the relationship between breakpoints and the tolls. We also consider the solutions in the network where origin-destination pairs may differ in their probability density functions.     

Solution of the linear inverse vector optimization problem by a single linear program

It is shown that finding a solution to a linear vector optimization problem which is efficient with respect to the constraints as well as to the objectives is equivalent to solving a single linear program.The research of this author was supported by NSF Grant DCR74-20584.The research of this author was partially supported by Canada Council Grant W760467.     

On convex optimization with linear constraints

In this paper, we propose an interior-point method for minimizing a convex function subject to linear constraints. Our method employs ideas from a previously studied method due to Fan and Nekooie in a different context. Under certain assumptions, we show that the proposed method has a fast rate of convergence. A numerical example is included to illustrate the method.     

Multiobjective optimization problem with variational inequality constraints

 We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints. Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel programming problem. Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002 Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming problem – Preference – Utility function – Subdifferential calculus – Variational principle Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496 Mathematics Subject Classification (2000): Sub49K24, 90C29     

Necessary conditions for a domain optimization problem with various constraints

In this paper, a scheme for obtaining the necessary conditions in a wide class of domain optimization problems is given. In the case of a linear boundary-value problem of the Dirichlet type, necessary conditions are given.     

Conic approximation to quadratic optimization with linear complementarity constraints

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm.     

Solution of a possibilistic multiobjective linear programming problem

The estimate of the parameters which define a conventional multiobjective decision making model is a difficult task. Normally they are either given by the Decision Maker who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from the past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets and several fuzzy approaches to multiobjective programming have been developed 1, 9, 10, 11. The fuzziness of the parameters gives rise to a problem whose solution will also be fuzzy, see 2, 3, and which is defined by its possibility distribution. Once the possibility distribution of the solution has been obtained, if the decision maker wants more precise information with respect to the decision vector, then we can pose and solve a new problem. In this case we try to find a decision vector, which approximates as much as possible the fuzzy objectives to the fuzzy solution previously obtained. In order to solve this problem we shall develop two different models from the initial solution and based on Goal Programming: an Interval Goal Programming Problem if we define the relation “as accurate as possible” based on the expected intervals of fuzzy numbers, as we showed in [4], and an ordinary Goal Programming based on the expected values of the fuzzy numbers that defined the goals. Finally, we construct algorithms that implement the above mentioned solution method. Our approach will be illustrated by means of a numerical example.     

Optimal control problem with phase constraints for a linear system of equations with delay

The optimal control problem for a linear system of differential equations with delay for which the initial function on the initial set is the control function is considered. Phase constraints with variable times are imposed on the trajectory of the object. Necessary optimality conditions of controls in admissible classes are obtained.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 12, pp. 1647–1652, December, 1991.     

Completely positive reformulations of polynomial optimization problems with linear constraints

A polynomial optimization problem (POP) is an optimization problem in which both the objective and constraints can be written in terms of polynomials on the decision variables. Recently, it has been shown that under appropriate assumptions POPs can be reformulated as conic problems over the cone of completely positive tensors; which generalize the set of completely positive matrices. Here, we show that by explicitly handling the linear constraints in the formulation of the POP, one obtains a generalization of the completely positive reformulation of quadratically constrained quadratic programs recently introduced by Bai et al. (Math Program 1–28, 2016).     

Proper efficiency in a linear fractional vector maximum problem with generalized convex constraints

In the present paper, a vector maximum problem (VMP) with linear fractional objectives and generalized convex constraints is considered. A necessary and sufficient condition for an efficient solution of (VMP) is derived in Kuhn-Tucker's form. Moreover, it is proved that under a certain boundedness assumption an efficient solution is properly efficient. This extends the results of Choo [3] for a linear fractional vector maximum problem with linear constraints to generalized convex constraints. An example is given to illustrate the results.     

A linear programming priority method for a fuzzy transportation problem with non-linear constraints

Demand and supply pattern for most products varies during their life cycle in the markets. In this paper, the author presents a transportation problem with non-linear constraints in which supply and demand are symmetric trapezoidal fuzzy value. In order to reflect a more realistic pattern, the unit of transportation cost is assumed to be stochastic. Then, the non-linear constraints are linearized by adding auxiliary constraints. Finally, the optimal solution of the problem is found by solving the linear programming problem with fuzzy and crisp constraints and by applying fuzzy programming technique. A new method proposed to solve this problem, and is illustrated through numerical examples. Multi-objective goal programming methodology is applied to solve this problem. The results of this research were developed and used as one of the Decision Support System models in the Logistics Department of Kayson Co.     

Generalized Newton method for linear optimization problems with inequality constraints

A dual problem of linear programming is reduced to the unconstrained maximization of a concave piecewise quadratic function for sufficiently large values of a certain parameter. An estimate is given for the threshold value of the parameter starting from which the projection of a given point to the set of solutions of the dual linear programming problem in dual and auxiliary variables is easily found by means of a single solution of the unconstrained maximization problem. The unconstrained maximization is carried out by the generalized Newton method, which is globally convergent in an a finite number of steps. The results of numerical experiments are presented for randomly generated large-scale linear programming problems.     

Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints

The well known DIRECT (DIviding RECTangles) algorithm for global optimization requires bound constraints on variables and does not naturally address additional linear or nonlinear constraints. A feasible region defined by linear constraints may be covered by simplices, therefore simplicial partitioning may tackle linear constraints in a very subtle way. In this paper we demonstrate this advantage of simplicial partitioning by applying a recently proposed deterministic simplicial partitions based DISIMPL algorithm for optimization problems defined by general linear constraints (Lc-DISIMPL). An extensive experimental investigation reveals advantages of this approach to such problems comparing with different constraint-handling methods, proposed for use with DIRECT. Furthermore the Lc-DISIMPL algorithm gives very competitive results compared to a derivative-free particle swarm algorithm (PSwarm) which was previously shown to give very promising results. Moreover, DISIMPL guarantees the convergence to the global solution, whereas the PSwarm algorithm sometimes fails to converge to the global minimum.     

非负约束稀疏优化问题的一个等价性条件

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究,给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义,并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步,本文给出了"s-权优"的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。     

An integer optimization problem with mixed algebraic and number-theoretic constraints

Two problems dealing with theory of numbers are considered. First, an unusual integer optimization problem characterized by mixed algebraic and number-theoretic constraints is studied, which has application in the sharing of secrets or sensitive resources. Next, a linear difference algorithm is proposed for generating sequences of prime numbers with accelerated growth rate in the number of digits produced.     

非负约束稀疏优化问题的一个等价性条件

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究,给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义,并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步,本文给出了"s-权优"的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。     

On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling

Mathematical Programming -     

A remark on a standard and linear vector network equilibrium problem with capacity constraints

In this paper, (weak) vector equilibrium principle with capacity constraints is introduced. A necessary condition that a vector minimum cost flow is a vector equilibrium flow with capacity constraints is obtained. When the number of paths connecting with each pair of source and sink is less than or equal to 2, a sufficient condition for a vector minimum cost flow to be a vector equilibrium flow is also obtained. A generalized (weak) vector equilibrium principle is also introduced. Without any additional assumption, a necessary and sufficient condition for a (weak) vector minimum cost flow to be a generalized (weak) vector equilibrium flow is obtained.