共查询到20条相似文献,搜索用时 468 毫秒
1.
Ya-Xiang Yuan 《计算数学(英文版)》1991,9(4):348-359
In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided. 相似文献
2.
A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature. 相似文献
3.
We consider the augmented Lagrangian method (ALM) as a solver for the fused lasso signal approximator (FLSA) problem. The ALM is a dual method in which squares of the constraint functions are added as penalties to the Lagrangian. In order to apply this method to FLSA, two types of auxiliary variables are introduced to transform the original unconstrained minimization problem into a linearly constrained minimization problem. Each updating in this iterative algorithm consists of just a simple one-dimensional convex programming problem, with closed form solution in many cases. While the existing literature mostly focused on the quadratic loss function, our algorithm can be easily implemented for general convex loss. We also provide some convergence analysis of the algorithm. Finally, the method is illustrated with some simulation datasets. 相似文献
4.
Michael Krätzschmar 《Numerische Mathematik》1989,54(5):507-531
Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in 1 discretized by using piecewise quadratic finite elements and in 2 by using the five-point difference approximation are presented. 相似文献
5.
Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of
the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains
that are essentially linear. However, the objective function is not differentiable over the constraint region.
In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual
program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled
perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an
arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution
to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this
controlled perturbation scheme. 相似文献
6.
We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic
constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems),
we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then
consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints,
which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations
which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special
cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent
convex programs.
This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and
by the Binational Science Foundation.
This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871. 相似文献
7.
Jean-Paul Penot 《Journal of Global Optimization》2001,19(2):163-182
Calling anticonvex a program which is either a maximization of a convex function on a convex set or a minimization of a convex function on the set of points outside a convex subset, we introduce several dual problems related to each of these problems. We give conditions ensuring there is no duality gap. We show how solutions to the dual problems can serve to locate solutions of the primal problem. 相似文献
8.
Radu Ioan Boţ Ernö Robert Csetnek 《Journal of Optimization Theory and Applications》2013,159(3):576-589
In this paper we deal with the minimization of a convex function over the solution set of a range inclusion problem determined by a multivalued operator with convex graph. We attach a dual problem to it, provide regularity conditions guaranteeing strong duality and derive for the resulting primal–dual pair necessary and sufficient optimality conditions. We also discuss the existence of optimal solutions for the primal and dual problems by using duality arguments. The theoretical results are applied in the context of the control of linear discrete systems. 相似文献
9.
Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems. 相似文献
10.
R. Chandrasekaran 《Operations Research Letters》1982,1(3):111-112
We present a polynomial algorithm for the weighted 1-center problem (indeed minimization of the ratio of convex quadratic and an affine function over a polyhedral set). In the location problem, the complexity is polynomial in the dimension of the space. 相似文献
11.
G. A. Amirkhanova A. I. Golikov Yu. G. Evtushenko 《Proceedings of the Steklov Institute of Mathematics》2016,295(1):21-27
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. 相似文献
12.
In the present work, we intend to derive conditions characterizing globally optimal solutions of quadratic 0-1 programming
problems. By specializing the problem of maximizing a convex quadratic function under linear constraints, we find explicit
global optimality conditions for quadratic 0-1 programming problems, including necessary and sufficient conditions and some
necessary conditions. We also present some global optimality conditions for the problem of minimization of half-products. 相似文献
13.
In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems. 相似文献
14.
Wu Li 《Mathematical Programming》1996,72(1):17-32
In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving
the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program
with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the
conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic
program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method
finds the solution in a finite number of iterations.
This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15. 相似文献
15.
《Optimization》2012,61(3):359-369
In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations. 相似文献
16.
On piecewise quadratic Newton and trust region problems 总被引:1,自引:0,他引:1
J. Sun 《Mathematical Programming》1997,76(3):451-467
Some recent algorithms for nonsmooth optimization require solutions to certain piecewise quadratic programming subproblems.
Two types of subproblems are considered in this paper. The first type seeks the minimization of a continuously differentiable
and strictly convex piecewise quadratic function subject to linear equality constraints. We prove that a nonsmooth version
of Newton’s method is globally and finitely convergent in this case. The second type involves the minimization of a possibly
nonconvex and nondifferentiable piecewise quadratic function over a Euclidean ball. Characterizations of the global minimizer
are studied under various conditions. The results extend a classical result on the trust region problem.
Partially supported by National University of Singapore under grant 930033. 相似文献
17.
Abdelmalek Aboussoror Samir Adly 《Journal of Optimization Theory and Applications》2011,149(2):254-268
In this paper, for a bilevel programming problem (S) with an extremal-value function, we first give its Fenchel–Lagrange dual problem. Under appropriate assumptions, we show
that a strong duality holds between them. Then, we provide optimality conditions for (S) and its dual. Finally, we show that the resolution of the dual problem is equivalent to the resolution of a one-level convex
minimization problem. 相似文献
18.
V. D. Skarin 《Proceedings of the Steklov Institute of Mathematics》2015,289(1):182-191
For the correction of a convex programming problem with potentially inconsistent constraint system (an improper problem), we apply the residual method, which is a standard regularization procedure for ill-posed optimization models. A problem statement typical for the residual method is reduced to a minimization problem for an appropriate penalty function. We apply two classical penalty functions: the quadratic penalty function and the exact Eremin-Zangwill penalty function. For each of the approaches, we establish convergence conditions and bounds for the approximation error. 相似文献
19.
Duality relations for the programming problem of a special class where the objective function is a sum of positive-semidefinite quadratic forms, and a sum of square roots of positive-semidefinite quadratic forms, over a convex polyhedral cone in complex space are considered. The duality relations between the primal problem and its dual are established. 相似文献