共查询到20条相似文献,搜索用时 15 毫秒
1.
《Optimization》2012,61(6):535-543
In this article we discuss weak and strong duality properties of convex semi-infinite programming problems. We use a unified framework by writing the corresponding constraints in a form of cone inclusions. The consequent analysis is based on the conjugate duality approach of embedding the problem into a parametric family of problems parameterized by a finite-dimensional vector. 相似文献
2.
3.
Y. C. Cheng 《Journal of Optimization Theory and Applications》1987,53(2):237-246
A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given. 相似文献
4.
Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions. 相似文献
5.
Lagrangian bounds, i.e. bounds computed by Lagrangian relaxation, have been used successfully in branch and bound bound methods
for solving certain classes of nonconvex optimization problems by reducing the duality gap. We discuss this method for the
class of partly linear and partly convex optimization problems and, incidentally, point out incorrect results in the recent
literature on this subject. 相似文献
6.
Fenchel's duality theorem in generalized geometric programming 总被引:1,自引:0,他引:1
E. L. Peterson 《Journal of Optimization Theory and Applications》1978,26(1):51-57
Fenchel's duality theorem is extended to generalized geometric programming with explicit constraints—an extension that also generalizes and strengthens Slater's version of the Kuhn-Tucker theorem.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516. 相似文献
7.
It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results. 相似文献
8.
A pair of symmetric dual multiobjective variational mixed integer programs for the polars of arbitrary cones are formulated, which some primal and dual variables are constrained to belong to the set of integers. Under the separability with respect to integer variables and partial-invexity assumptions on the functions involved, we prove the weak, strong, converse and self-duality theorems to related minimax efficient solution. These results include some of available results. 相似文献
9.
We show a Lagrange-type duality theorem for a DC programming problem, which is a generalization of previous results by J.-E. Martínez-Legaz, M. Volle [5] and Y. Fujiwara, D. Kuroiwa [1] when all constraint functions are real-valued. To the purpose, we decompose the DC programming problem into certain infinite convex programming problems. 相似文献
10.
《Stochastics An International Journal of Probability and Stochastic Processes》2013,85(8):1145-1169
ABSTRACTIn this paper, we study a constrained utility maximization problem following the convex duality approach. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of forward and backward stochastic differential equations (FBSDEs) plus some additional conditions. Such formulation then allows us to explicitly characterize the primal optimal control as a function of the adjoint process coming from the dual FBSDEs in a dynamic fashion and vice versa. We also find that the optimal wealth process coincides with the adjoint process of the dual problem and vice versa. Finally we solve three constrained utility maximization problems, which contrasts the simplicity of the duality approach we propose and the technical complexity of solving the primal problem directly. 相似文献
11.
E. L. Peterson 《Journal of Optimization Theory and Applications》1978,26(1):43-50
A specialization of unconstrained duality (involving problems without explicit constraints) to constrained duality (involving problems with explicit constraints) provides an efficient mechanism for extending to the latter many important theorems that were previously established for the former.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516. 相似文献
12.
O. Barrientos R. Correa P. Reyes A. Valdebenito 《Computational Optimization and Applications》2003,26(2):155-171
A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported. 相似文献
13.
We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86. 相似文献
14.
Satoru Ibaraki Masao Fukushima Toshihide Ibaraki 《Computational Optimization and Applications》1992,1(2):207-226
A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs. 相似文献
15.
O. Güler 《Journal of Optimization Theory and Applications》1992,75(3):445-470
We introduce new augmented Lagrangian algorithms for linear programming which provide faster global convergence rates than the augmented algorithm of Polyak and Treti'akov. Our algorithm shares the same properties as the Polyak-Treti'akov algorithm in that it terminates in finitely many iterations and obtains both primal and dual optimal solutions. We present an implementable version of the algorithm which requires only approximate minimization at each iteration. We provide a global convergence rate for this version of the algorithm and show that the primal and dual points generated by the algorithm converge to the primal and dual optimal set, respectively. 相似文献
16.
We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d
2), the expected total number of major Karmarkar's iterations is O(d
2(logn)L), compared to the best known deterministic bound of O(
L). We also present several other results which follow from the general scheme. 相似文献
17.
Conjugate duality in generalized fractional programming 总被引:2,自引:0,他引:2
The concepts of conjugate duality are used to establish dual programs for a class of generalized nonlinear fractional programs. It is now known that, under certain restrictions, a symmetric duality exists for generalized linear fractional programs. In this paper, we establish this symmetric duality for the nonlinear case. 相似文献
18.
We study Lagrange duality theorems for canonical DC programming problems. We show two types Lagrange duality results by using a decomposition method to infinite convex programming problems and by using a previous result by Lemaire (1998) [6]. Also we observe these constraint qualifications for the duality theorems. 相似文献
19.
J. F. Andrus 《Journal of Optimization Theory and Applications》1992,72(1):37-63
This paper gives a proof of convergence of an iterative method for maximizing a concave function subject to inequality constraints involving convex functions. The linear programming problem is an important special case. The primary feature is that each iteration is very simple computationally, involving only one of the constraints. Although the paper is theoretical in nature, some numerical results are included.The author wishes to express his gratitude to Ms. A. Dunham, who provided a great deal of assistance in carrying out the computations presented in this paper. 相似文献
20.
On a decomposition method for nonconvex global optimization 总被引:1,自引:0,他引:1
Hoang Tuy 《Optimization Letters》2007,1(3):245-258
A rigorous foundation is presented for the decomposition method in nonconvex global optimization, including parametric optimization,
partly convex, partly monotonic, and monotonic/linear optimization. Incidentally, some errors in the recent literature on
this subject are pointed out and fixed. 相似文献