共查询到20条相似文献,搜索用时 859 毫秒
1.
《European Journal of Operational Research》1999,114(1):188-197
Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem. 相似文献
2.
The paper describes a numerically stable algorithm to solveconstrained linear least-squares problems and allows rank deficientor underdetermined observation matrices. The method starts withthe calculation of the rank of the observation matrix and thetransformation into a least distance problem. The proposed techniquefor solving the least distance problem can be considered asa generalization of the projection method of Stoer (1971). Startingwith a feasible point, a sequence of iterates is calculatedby minimizing the objective function on the linear boundarymanifold determined by the active constraints. Numerical examplesshow the feasibility of the algorithm. 相似文献
3.
4.
Marian G. Marcovecchio María L. Bergamini Pio A. Aguirre 《Journal of Global Optimization》2006,34(3):339-368
A new algorithm to solve nonconvex NLP problems is presented. It is based on the solution of two problems. The reformulated
problem RP is a suitable reformulation of the original problem and involves convex terms and concave univariate terms. The
main problem MP is a nonconvex NLP that outer-approximates the feasible region and underestimate the objective function. MP
involves convex terms and terms which are the products of concave univariate functions and new variables. Fixing the variables
in the concave terms, a convex NLP that overestimates the feasible region and underestimates the objective function is obtained
from the MP. Like most of the deterministic global optimization algorithms, bounds on all the variables in the nonconvex terms
must be provided. MP forces the objective value to improve and minimizes the difference of upper and lower bound of all the
variables either to zero or to a positive value. In the first case, a feasible solution of the original problem is reached
and the objective function is improved. In general terms, the second case corresponds to an infeasible solution of the original
problem due to the existence of gaps in some variables. A branching procedure is performed in order to either prove that there
is no better solution or reduce the domain, eliminating the local solution of MP that was found. The MP solution indicates
a key point to do the branching. A bound reduction technique is implemented to accelerate the convergence speed. Computational
results demonstrate that the algorithm compares very favorably to other approaches when applied to test problems and process
design problems. It is typically faster and it produces very accurate results. 相似文献
5.
M. Patriksson 《Journal of Optimization Theory and Applications》1993,78(2):227-246
In this paper, we characterize a class of feasible direction methods in nonlinear programming through the concept of partial linearization of the objective function. Based on a feasible point, the objective is replaced by an arbitrary convex and continuously differentiable function, and the error is taken into account by a first-order approximation of it. A new feasible point is defined through a line search with respect to the original objective, toward the solution of the approximate problem. Global convergence results are given for exact and approximate line searches, and possible interpretations are made. We present some instances of the general algorithm and discuss extensions to nondifferentiable programming.The author wishes to thank Drs. K. Holmberg, T. Larsson, and A. Migdalas for their helpful comments. 相似文献
6.
In this paper, we prove that an optimal solution to the linear fractional bilevel programming problem occurs at a boundary feasible extreme point. Hence, the Kth-best algorithm can be proposed to solve the problem. This property also applies to quasiconcave bilevel problems provided that the first level objective function is explicitly quasimonotonic. 相似文献
7.
8.
《Optimization》2012,61(2):141-156
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 相似文献
9.
This paper presents a purification algorithm for a class of infinite-dimensional linear programs called separated continuous linear programs (SCLP). This takes an initial feasible solution and produces an extreme point solution without a decrease in objective function value. The algorithm presented here for SCLP is also shown to be the best possible purification algorithm in a certain class. 相似文献
10.
Shalabh Bhatnagar K. Lakshmanan 《Journal of Optimization Theory and Applications》2012,153(3):688-708
We develop an online actor–critic reinforcement learning algorithm with function approximation for a problem of control under
inequality constraints. We consider the long-run average cost Markov decision process (MDP) framework in which both the objective
and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange
multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm
to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multi-stage
queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance
on this setting and converges to a feasible point. 相似文献
11.
Dirk A. Lorenz Marc E. Pfetsch Andreas M. Tillmann 《Computational Optimization and Applications》2014,57(2):271-306
We propose a new subgradient method for the minimization of nonsmooth convex functions over a convex set. To speed up computations we use adaptive approximate projections only requiring to move within a certain distance of the exact projections (which decreases in the course of the algorithm). In particular, the iterates in our method can be infeasible throughout the whole procedure. Nevertheless, we provide conditions which ensure convergence to an optimal feasible point under suitable assumptions. One convergence result deals with step size sequences that are fixed a priori. Two other results handle dynamic Polyak-type step sizes depending on a lower or upper estimate of the optimal objective function value, respectively. Additionally, we briefly sketch two applications: Optimization with convex chance constraints, and finding the minimum ? 1-norm solution to an underdetermined linear system, an important problem in Compressed Sensing. 相似文献
12.
In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem. 相似文献
13.
《Optimization》2012,61(8):1283-1295
In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration. 相似文献
14.
H. P. Benson 《Journal of Optimization Theory and Applications》2010,146(1):1-18
In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional
programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an
indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer
approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer
approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added.
Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible
regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal
solution to one problem can potentially be used to good effect as a starting solution for the next problem. 相似文献
15.
通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程. 相似文献
16.
Ali Abbasi Molai 《Journal of Computational and Applied Mathematics》2010,233(8):2090-2103
This paper studies the optimization model of a linear objective function subject to a system of fuzzy relation inequalities (FRI) with the max-Einstein composition operator. If its feasible domain is non-empty, then we show that its feasible solution set is completely determined by a maximum solution and a finite number of minimal solutions. Also, an efficient algorithm is proposed to solve the model based on the structure of FRI path, the concept of partial solution, and the branch-and-bound approach. The algorithm finds an optimal solution of the model without explicitly generating all the minimal solutions. Some sufficient conditions are given that under them, some of the optimal components of the model are directly determined. Some procedures are presented to reduce the search domain of an optimal solution of the original problem based on the conditions. Then the reduced domain is decomposed (if possible) into several sub-domains with smaller dimensions that finding the components of the optimal solution in each sub-domain is very easy. In order to obtain an optimal solution of the original problem, we propose another more efficient algorithm which combines the first algorithm, these procedures, and the decomposition method. Furthermore, sufficient conditions are suggested that under them, the problem has a unique optimal solution. Also, a comparison between the recently proposed algorithm and the known ones will be made. 相似文献
17.
Jing Zhou Shu-Cherng Fang Wenxun Xing 《Computational Optimization and Applications》2017,66(1):97-122
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. 相似文献
18.
解带有二次约束二次规划的一个整体优化方法 总被引:1,自引:0,他引:1
在本文中,我们提出了一种解带有二次约束二次规划问题(QP)的新算法,这种方法是基于单纯形分枝定界技术,其中包括极小极大问题和线性规划问题作为子问题,利用拉格朗日松弛和投影次梯度方法来确定问题(QP)最优值的下界,在问题(QP)的可行域是n维的条件下,如果这个算法有限步后终止,得到的点必是问题(QP)的整体最优解;否则,该算法产生的点的序列{v^k}的每一个聚点也必是问题(QP)的整体最优解。 相似文献
19.
Summary An algorithm for the ranking of the feasible solutions of a bottleneck linear programming problem in ascending order of values
of a concave bottleneck objective function is developed in this paper. The “best” feasible solution for a given value of the
bottleneck objective is obtained at each stage. It is established that only the extreme points of a convex polytope need to
be examined for the proposed ranking. Another algorithm, involving partitioning of the nodes, to rank the feasible solutions
of the bottleneck linear programming problem is proposed, and numerical illustrations for both are provided. 相似文献
20.
In [6], a polynomial algorithm based on successive piecewise linear approximation was described. The algorithm is polynomial for constrained nonlinear (convex or concave) optimization, when the constraint matrix has a polynomial size subdeterminant. We propose here a practical adaptation of that algorithm with the idea of successive piecewise linear approximation of the objective on refined grids, and the testing of the gap between lower and upper bounds. The implementation uses the primal affine interior point method at each approximation step. We develop special features to speed up each step and to evaluate the gap. Empirical study of problems of size up to 198 variables and 99 constraints indicates that the procedure is very efficient and all problems tested were terminated after 171 interior point iterations. The procedure used in the implementation is proved to converge when the objective is strongly convex.Supported in part by the Office of Naval Research under Grant No. N00014-88-K-0377 and Grant No. ONR N00014-91-J-1241. 相似文献