Search

In this paper, we introduce the concept of ϕ-strongly pseudomonotone bifunctions in Banach spaces and present two simple subgradient-type methods for solving ϕ-strongly pseudomonotone equilibrium p...

Qualitative and quantitative aspects for variational inequalities governed by strongly pseudomonotone operators on Hilbert space are investigated in this paper. First, we establish a global error bound for the solution set of the given problem with the residual function being the normal map. Second, we will prove that the iterative sequences generated by gradient projection method (GPM) with stepsizes forming a non-summable diminishing sequence of positive real numbers converge to the unique solution of the problem when the operator is bounded over the constraint set. Two counter-examples are given to show the necessity of the boundedness assumption and the variation of stepsizes. We also analyze the convergence rate of the iterative sequences generated by this method. Finally, we give an in-depth comparison between our algorithm and a recent related algorithm through several numerical experiments., 22 pages

In this paper, we study convergence analysis of a new gradient projection algorithm for solving convex minimization problems in Hilbert spaces. We observe that the proposed gradient projection algorithm weakly converges to a minimum of convex function f which is defined from a closed and convex subset of a Hilbert space to $\mathbb {R}$ . Also, we give a nontrivial example to illustrate our result in an infinite dimensional Hilbert space. We apply our result to solve the split feasibility problem.

This article is concerned with the problem of minimizing a smooth function over the Stiefel manifold. In order to address this problem, we introduce two adaptive scaled gradient projection methods that incorporate scaling matrices that depend on the step-size and a parameter that controls the search direction. These iterative algorithms use a projection operator based on the QR factorization to preserve the feasibility in each iteration. However, for some particular cases, the proposals do not require the use of any projection operator. In addition, we consider a Barzilai and Borwein-like step-size combined with the Zhang–Hager nonmonotone line-search technique in order to accelerate the convergence of the proposed procedures. We proved the global convergence for these schemes, and we evaluate their effectiveness and efficiency through an extensive computational study, comparing our approaches with other state-of-the-art gradient-type algorithms.

We consider the problem of minimization for a function with Lipschitz continuous gradient on a proximally smooth and smooth manifold in a finite dimensional Euclidean space. We consider the Lezanski-Polyak-Lojasiewicz (LPL) conditions in this problem of constrained optimization. We prove that the gradient projection algorithm for the problem converges with a linear rate when the LPL condition holds.

This paper is concerned with studying the numerical solution for the discrete classical optimal control problem (NSDCOCP) governed by a variable coefficients nonlinear hyperbolic boundary value problem (VCNLHBVP). The DSCOCP is solved by using the Galerkin finite element method (GFEM) for the space variable and implicit finite difference scheme (GFEM-IFDS) for the time variable to get the NS for the discrete weak form (DWF) and for the discrete adjoint weak form (DSAWF) While, the gradient projection method (GRPM), also called the gradient method (GRM), or the Frank Wolfe method (FRM) are used to minimize the discrete cost function (DCF) to find the DSCOC. Within these three methods, the Armijo step option (ARMSO) or the optimal step option (OPSO) are used to improve the discrete classical control (DSCC). Finally, some illustrative examples for the problem are given to show the accuracy and efficiency of the methods.

We consider the minimization problem for a nonconvex function with Lipschitz continuous gradient on a proximally smooth (possibly nonconvex) subset of a finite-dimensional Euclidean space. We introduce the error bound condition with exponent for the gradient mapping. Under this condition, it is shown that the standard gradient projection algorithm converges to a solution of the problem linearly or sublinearly, depending on the value of the exponent . This paper is theoretical. Bibliography: 23 titles.

Minimization of a smooth function on a sphere or, more generally, on a smooth manifold, is the simplest non-convex optimization problem. It has a lot of applications. Our goal is to propose a version of the gradient projection algorithm for its solution and to obtain results that guarantee convergence of the algorithm under some minimal natural assumptions. We use the Lezanski-Polyak-Lojasiewicz condition on a manifold to prove the global linear convergence of the algorithm. Another method well fitted for the problem is the conditional gradient (Frank-Wolfe) algorithm. We examine some conditions which guarantee global convergence of full-step version of the method with linear rate.

In this paper, we propose a derivative free algorithm for solving non-linear monotone equations with convex constraints. The proposed algorithm combines the method of spectral gradient and the projection method. We also modify the backtracking line search technique. The global convergence of the proposed method is guaranteed, under the mild conditions. Further, the numerical experiments show that the large-scale non-linear equations with convex constraints can be effectively solved with our method. The $L_{1}$ -norm regularized problems in signal reconstruction are studied by using our method.

Consider the minimization of a nonconvex differentiable function over a polyhedron. A popular primal-dual first-order method for this problem is to perform a gradient projection iteration for the augmented Lagrangian function and then update the dual multiplier vector using the constraint residual. However, numerical examples show that this approach can exhibit "oscillation" and may not converge. In this paper, we propose a proximal alternating direction method of multipliers for the multi-block version of this problem. A distinctive feature of this method is the introduction of a "smoothed" (i.e., exponentially weighted) sequence of primal iterates, and the inclusion, at each iteration, to the augmented Lagrangian function a quadratic proximal term centered at the current smoothed primal iterate. The resulting proximal augmented Lagrangian function is inexactly minimized (via a gradient projection step) at each iteration while the dual multiplier vector is updated using the residual of the linear constraints. When the primal and dual stepsizes are chosen sufficiently small, we show that suitable "smoothing" can stabilize the "oscillation", and the iterates of the new proximal ADMM algorithm converge to a stationary point under some mild regularity conditions. Furthermore, when the objective function is quadratic, we establish the linear convergence of the algorithm. Our proof is based on a new potential function and a novel use of error bounds., Comment: 31 pages,6 figures. Accepted for publication by SIAM Journal on Optimization

In this paper, we propose a novel primal–dual inexact gradient projection method for nonlinear optimization problems with convex-set constraint. This method only needs inexact computation of the pr...

This paper addresses the positive semi-definite procrustes problem (PSDP). The PSDP corresponds to a least squares problem over the set of symmetric and semi-definite positive matrices. These kinds of problems appear in many applications such as structure analysis, signal processing, among others. A non-monotone spectral projected gradient algorithm is proposed to obtain a numerical solution for the PSDP. The proposed algorithm employs the Zhang and Hager's non-monotone technique in combination with the Barzilai and Borwein's step size to accelerate convergence. Some theoretical results are presented. Finally, numerical experiments are performed to demonstrate the effectiveness and eficiency of the proposed method, and comparisons are made with other state-of-the-art algorithms. Resumen En este artículo abordamos el problema de mínimos cuadrados lineales sobre el conjunto de matrices simétricas y definidas positivas (PSDP). Esta clase de problemas surge en un gran número de aplicaciones tales como análisis de estructuras, procesamiento de señales, análisis de componentes principales, entre otras. Para resolver este tipo de problemas, proponemos un método de gradiente proyectado espectral no-monótono. El algoritmo propuesto usa la técnica de globalización no-monótona de Zhang y Hager, en combinación con los tamaños de paso de Barzilai y Borwein para acelerar la convergencia del método. Además, presentamos y comentamos algunos resultados teóricos concernientes al algoritmo desarrollado. Finalmente, llevamos a cabo varios experimentos numéricos con el fin de demostrar la efectividad y la eficiencia del nuevo enfoque, y realizamos comparaciones con algunos métodos existentes en la literatura.

Stochastic approximation procedures have been extensively used in solving stochastic optimization problems. Gradient projection algorithm (GPA) plays an important role in solving constrained convex...

Conjugate gradient projection methods are widely used for solving large-scale nonlinear systems of monotone equations because of their low memory requirements and research continues to be d...

The semi-smooth Newton method for solving discretized contact problems with Tresca friction in three-dimensional space is analysed. The slanting function is approximated to get symmetric in...

The gradient projection method is generalized to the case of nonconvex sets of constraints representing the set-theoretic intersection of a smooth surface with a convex closed set. Necessary optimality conditions are studied, and the convergence of the method is analyzed.

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ1 regularizer to encourage sparsity is common practice, the combinatorial ℓ0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ0 constraint. We introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ0-constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods. Summary of Contribution: The inverse covariance estimation problem underpins many domains, including statistics, operations research, and machine learning. We propose a scalable optimization algorithm for solving the nonconvex ℓ0-constrained problem.

Nonnegative sparsity-constrained optimization problem arises in many fields, such as the linear compressing sensing problem and the regularized logistic regression cost function. In this paper, we introduce a new stepsize rule and establish a gradient projection algorithm. We also obtain some convergence results under milder conditions.

In this paper, we consider the varying stepsize gradient projection algorithm (GPA) for solving the split equality problem (SEP) in Hilbert spaces, and study its linear convergence. In particular, ...

In this paper, the original C Q algorithm, the relaxed C Q algorithm, the gradient projection method ( G P M ) algorithm, and the subgradient projection method ( S P M ) algorithm for the convex split feasibility problem are reviewed, and a renewed S P M algorithm with S-subdifferential functions to solve nonconvex split feasibility problems in finite dimensional spaces is suggested. The weak convergence theorem is established.

We analyse the convergence of the gradient projection algorithm, which is finalized with the Newton method, to a stationary point for the problem of nonconvex constrained optimization $\min_{x \in S} f(x)$ with a proximally smooth set $S = \{x \in R^n : g(x) = 0 \}, \; g : R^n \rightarrow R^m$ and a smooth function $f$. We propose new Error bound (EB) conditions for the gradient projection method which lead to the convergence domain of the Newton method. We prove that these EB conditions are typical for a wide class of optimization problems. It is possible to reach high convergence rate of the algorithm by switching to the Newton method.

Using a small number of sampling views during a CT (computed tomography) exam is a widely accepted technique for low-dose CT reconstruction, which reduces the risk of inducing cancer or other diseases in patients. In this scenario, total variation (TV) based compressed sensing (CS) methods, which uses a regularization term that penalizes the $\ell_{1}$ norm of the reconstructed image's gradient, outperform the traditional FBP (filtered back-projection) based algorithms in CT reconstruction. Furthermore, in order to reduce well-known artifacts (smoothed edges and texture details) favored by TV-based CS methods, several variants have been proposed, which, in a general context, can be understood as using a regularization term that approximates the $\ell_{0}$ norm of the reconstructed image's gradient. These type of methods yield state-of-the-art reconstruction results. In this paper we exploit a variant of the $\ell_{0}$ gradient minimization problem, which directly penalizes the number of non-zero gradients in the reconstructed image, and propose to solve the low-dose CT reconstruction problem. Extended experiments, based on the ASTRA toolbox, show that the propose method is faster (almost twice as fast) and delivers higher quality reconstructions than TV-based CS methods and alternatives that reduce smooth artifacts.

The scaled gradient projection (SGP) method, which can be viewed as a promising improvement of the classical gradient projection method, is a quite efficient solver for real-world problems arising ...

The continuous gradient projection method and the continuous gradient-type method in a space with a variable metric are studied for the numerical solution of quasi-variational inequalities, and conditions for the convergence of the methods proposed are established.

A weighted Bregman-Gradient Projection denoising method, based on the Bregman iterative regularization (BIR) method and Chambolle’s Gradient Projection method (or dual denoising method) is established. Some applications to image denoising on a 1-dimensional curve, 2-dimensional gray image and 3-dimensional color image are presented. Compared with the main results of the literatures, the present numerical results of the proposed method are improved.

The execution of a hybrid model predictive controller (MPC) on an embedded platform requires solving a Mixed-Integer Quadratic Programming (MIQP) in real time. The MIQP problem is NP-hard, which poses a major challenge in an environment where computational and memory resources are limited. To address this issue, we propose the use of accelerated dual gradient projection (GPAD) to find both the exact and an approximate solution of the MIQP problem. In particular, an existing GPAD algorithm is specialized to solve the relaxed Quadratic Programming (QP) subproblems that arise in a Branch and Bound (B&B) method for solving the MIQP to optimality. Furthermore, we present an approach to find a suboptimal integer feasible solution of a MIQP problem without using B&B. The GPAD algorithm is very simple to code and requires only basic arithmetic operations which makes it well suited for an embedded implementation. The performance of the proposed approaches is comparable with the state of the art MIQP solvers for small-scale problems.

Gold immunochromatographic strip (GICS) assay provides a quick, convenient, single-copy and on-site approach to determine the presence or absence of the target analyte when applied to an extensive variety of point-of-care tests. It is always desirable to quantitatively detect the concentration of trace substance in the specimen so as to uncover more useful information compared with the traditional qualitative (or semi-quantitative) strip assay. For this purpose, this paper is concerned with the GICS image denoising and deblurring problems caused by the complicated environment of the intestine/intrinsic restrictions of the strip characteristics and the equipment in terms of image acquisition and transmission. The gradient projection approach is used, together with the total variation minimization approach, to denoise and deblur the GICS images. Experimental results and quantitative evaluation are presented, by means of the peak signal-to-noise ratio, to demonstrate the performance of the combined algorithm. The experimental results show that the gradient projection method provides robust performance for denoising and deblurring the GICS images, and therefore serves as an effective image processing methodology capable of providing more accurate information for the interpretation of the GICS images.

With the previously proposed non-uniform norm called l N -norm, which consists of a sequence of l 1 -norm or l 0 -norm elements according to relative magnitude, a novel l N -norm sparse recovery algorithm can be derived by projecting the gradient descent solution to the reconstruction feasible set. In order to gain analytical insights into the performance of this algorithm, in this letter we analyze the steady state mean square performance of the gradient projection l N -norm sparse recovery algorithm in terms of different sparsity, as well as additive noise. Numerical simulations are provided to verify the theoretical results.

In this paper, we propose a new alternate gradient (AG) method to solve a class of optimization problems with orthogonal constraints. In particular, our AG method alternately takes several gradient reflection steps followed by one gradient projection step. It is proved that any accumulation point of the iterations generated by the AG method satisfies the first-order optimal condition. Numerical experiments show that our method is efficient.

Tensor is a hot topic in the past decade and eigenvalue problems of higher order tensors become more and more important in the numerical multilinear algebra. Several methods for finding the Z-eigenvalues and generalized eigenvalues of symmetric tensors have been given. However, the convergence of these methods when the tensor is not symmetric but weakly symmetric is not assured. In this paper, we give two convergent gradient projection methods for computing some generalized eigenvalues of weakly symmetric tensors. The gradient projection method with Armijo step-size rule (AGP) can be viewed as a modification of the GEAP method. The spectral gradient projection method which is born from the combination of the BB method with the gradient projection method is superior to the GEAP, AG and AGP methods. We also make comparisons among the four methods. Some competitive numerical results are reported at the end of this paper.

A FrTV combined with sparsifying transforms for CS sparse image reconstruction model is proposed.A method for estimating the regularization parameter is proposed.A gradient projection algorithm is developed to solve this reconstruction model.The algorithm has a higher PSNR and better detail preservation. The total variation (TV) model has been considered to be one of the most successful and representative model for compressive sensing (CS) sparse image reconstruction due to its advantage of preserving image edges. However, TV regularized term often favors piecewise constant solution and therefore it fails to preserve the details and textures. To overcome this defect and reconstruct the fine details, this paper proposes a two-dimensional CS sparse image reconstruction model by introducing the fractional-order TV (FrTV) regularization constraint into CS optimization problem. Furthermore, in order to achieve sparser representation flexibly, a combination of discrete wavelet transform and curvelet transform ź 1 -norm regularization is also incorporated into the cost function and a method for estimating the regularization parameter that trades off the two terms in the cost function is proposed. By using a smooth approximation of the ź 1 -norm, a gradient projection algorithm is derived to solve the combined FrTV and sparsifying transforms constrained minimization problem effectively. Compared with several state-of-the-art reconstruction algorithms, the proposed algorithm is more efficient and robust, not only yielding higher peak-signal-to-noise ratio, but also reconstructing the fine details and textures more efficiently.

A model of a two-dimensional open-pit mine is proposed and an optimal control problem is formulated with mixed constraints on the control parameters and an integral objective functional. The problem is discretized in one of the phase variables and solved by the gradient projection method with penalty functions. Numerical results illustrating the the method are also represented.

In this article, we provide a general iterative method for solving an equilibrium and a constrained convex minimization problem. By using the idea of regularized gradient-projection algorithm (RGPA), we find a common element, which is also a solution of a variational inequality problem. Then the strong convergence theorems are obtained under suitable conditions.

First excursion problem of linear structures subjected to wind loads is considered.The geometry of the failure domain of the reliability problem is explored.An enhanced efficient simulation method is developed for the concerned problem. In this paper the first excursion problem of linear structures subjected to stochastic wind loads is considered. The geometry of the corresponding failure domain is further explored, with the finding that rotational relationship exists for the quadratic elementary failure domains comprising the overall failure domain. Besides, procedures using the gradient projection method are developed for obtaining the design point of the quadratic elementary failure domain, which can be used to modify the previously developed simulation method. An illustrative example shows the accuracy and the enhanced efficiency of the modified simulation method, compared with its original version.

Since compressed sensing was introduced in 2006, ? 1 - ? 2 minimization admits a large number of applications in signal processing, statistical inference, magnetic resonance imaging (MRI), computed tomography (CT), etc. In this paper, we present a neural network for ? 1 - ? 2 minimization based on scaled gradient projection. We prove that it is stable in the sense of Lyapunov and converges to an optimal solution of the ? 1 - ? 2 minimization. We show that the proposed neural network is feasible and efficient for compressed sensing via simulation examples.

We prove the weak and the strong convergence of the trajectories of the continuous gradient projection method under some mild assumptions on the objective function and the step size function. Moreover, we estimate the decay rate to equilibrium when the objective function satisfies a global Holderian error bound inequality., Comment: 17pages

Cooperative optimisation problems over multi-agent systems have attracted a lot of attention. Most of existing results have been developed for the case when a cost function is given as a summation of local utilities. Instead, this study focuses on a more general case when the cost function is not given as a summation form or cannot be readily changed into a summation form. The authors call this case as the cooperative optimisation with inseparable cost functions. The authors’ basic idea is to decompose the inseparable cost function into local utilities based on geometric theory. Each of the decomposed agent optimisation problems only contains its own variable and constraints, and a gradient projection algorithm is proposed to solve the obtained distributed optimisation problem. It is further shown that the proposed algorithm converges and its solution coincides with the globally optimal solution under certain conditions, such as convexity of the cost function. Finally, two examples are given to illustrate the method.

The gradient projection method and Newton’s method are extended to the case where the constraints are nonconvex and are represented by a smooth surface. Necessary extremum conditions and the convergence of the methods are examined.

In this paper, a class of separable convex optimization problems with linear coupled constraints is studied. According to the Lagrangian duality, the linear coupled constraints are appended to the objective function. Then, a fast gradient-projection method is introduced to update the Lagrangian multiplier, and an inexact solution method is proposed to solve the inner problems. The advantage of our proposed method is that the inner problems can be solved in an inexact and parallel manner. The established convergence results show that our proposed algorithm still achieves optimal convergence rate even though the inner problems are solved inexactly. Finally, several numerical experiments are presented to illustrate the efficiency and effectiveness of our proposed algorithm.

This paper considers the problem of calibrating the volatility function using regularization technique and the gradient projection method from given option price data. It is an ill-posed problem because of at least one of three well-posed conditions violating. We start with the European option pricing problem. We formulate the problem by obtaining the integral equation from Dupire equation and provide a theory of identifying the local volatility function $\sigma(y,\tau)$ when the parameter $\mu\neq 0$, and then we apply regularization technique for volatility function retrieval problems. A projected gradient method is developed for recovering the volatility function. Numerical simulations are given to illustrate the feasibility of our method.

Sequential order one negative exponential (SOONE) function is used to measure the sparsity of a two-dimensional (2D) signal. A 2D gradient projection (GP) method is developed to solve the SOONE function and thus the 2D-GP-SOONE algorithm is proposed. The algorithm can solve the sparse recovery of 2D signals directly. Theoretical analysis and simulation results show that the 2D-GP-SOONE algorithm has a better performance compared with the 2D smoothed L0 algorithm. Simulation results also show that the proposed algorithm has a better performance and requires less computation time than 2D iterative adaptive approach.

We formulate the economic dispatch problem of generating unit population over a multi-time interval. In this paper, we will propose a coordination method by applying the gradient projection method. This method can solve the economic dispatch problem considering ramping rate limits of generating units over a multi-time interval. Due to the decoupling relationship among the admissible sets of coordination behaviors of all the individual generating units, the gradient projection on an individual admissible coordination set is independent upon the admissible sets of all the others. Following this modeling issue, the coordination behavior of each individual generating units can be updated locally and simultaneously. We show that, by applying our proposed method, the system converges to the optimal solution in case the step-size parameter of the update procedure is in a certain region. The results developed in this paper are demonstrated with several numerical simulations.

U svrhu smanjenja prekomjernog pomicanja zglobova, u radu se predlaže nova metoda za izbjegavanje prepreka kod redundantnog manipulatora. U toj smo metodi dizajnirali funkcionalnu procjenu pokreta kako bismo dobili najkraću stazu kretanja zgloba manipulatora i dobili indeks optimizacije vektora gradijenta primjenom varijacijske (variational) metode da bi za vrijeme izbjegavanja prepreke kretanje zgloba bilo minimalno. U međuvremenu, kako bismo izbjegli neuspjeh algoritma za izbjegavanje prepreke ili prekoraćenje krajnjih granica zglobova, do kojih je došlo zbog velike razlike između solucije najmanje norme i homogene solucije kinematike inverzne brzine manipulatora, u radu je primijenjena kontinuirana funkcija 2-norme da bi se dinamički podesio homogeni faktor rješenja metode projekcije gradijenta. Da bi se provjerila ispravnosti u radu predložene metode izbjegavanja prepreka, provedeni su simulacijski eksperimenti na 7-DOF redundantnom manipulatoru. Rezultati pokazuju da u usporedbi s tradicionalnom metodom projekcije gradijenta za izbjegavanje prepreka, u radu predloženim algoritmom smanjio se pomak zgloba 1 do zgloba 6 za 38,3 %, 83,3 %, 3,81 %, 7,85 %, 50,1 % i 45,6 %, a cjelokupni pomak prizmatičkih zglobova i okretnih (revolute) zglobova za 62,2 % i 26,4 %. U isto vrijeme, promjena brzine i ubrzanja zgloba 1 do zgloba 6 između početnog i završnog vremena tijekom izbjegavanja prepreke smanjila se 43,2 %, 97,3 %, 2,23 %, 36,6 %, 96,7 %, 72,7 % (brzina) i 91,04 %, 98,28 %, 73,33 %, 98,40 %, 93,86 % i 91,94 % (ubrzanje). Ispitivanje je pokazalo da je predložena metoda za izbjegavanje prepreka temeljena na varijacijskoj metodi, izvediva i praktična., To reduce the excessive joints movement, this paper proposed a new obstacle avoidance method for a redundant manipulator. In this method, we designed the performance evaluation functional to realize the shortest joints motion path of manipulator, and deduced the gradient vector optimizing index by variational method to make the joint movement minimum during obstacle avoiding. Meanwhile, in order to avoid the obstacle avoidance algorithm failure or joints exceeding their limits, which arose from the great difference between least-norm solution and homogeneous solution of velocity inverse kinematics of the manipulator, this paper used 2-norm continuous function to adjust homogeneous solution factor of gradient projection method dynamically. To verify the validity of the proposed obstacle avoidance method in the paper, simulation experiments were conducted on a 7-DOF redundant manipulator. The results show that, compared to the traditional gradient projection method for obstacle avoidance, the proposed algorithm in this paper has decreased the displacement of joint 1 to joint 6 by 38,3 %, 83,3 %, 3,81 %, 7,85 %, 50,1 % and 45,6 % respectively, and the total displacement of prismatic joints and revolute joints has reduced 62,2 % and 26,4 %. At the same time, the changes of joint 1 to joint 6’s velocity and acceleration between initial time and final time during obstacle avoiding has been decreased 43,2 %, 97,3 %, 2,23 %, 36,6 %, 96,7 %, 72,7 % (velocity) and 91,04 %, 98,28 %, 73,33 %, 98,40 %, 93,86 % and 91,94 % (acceleration) respectively. The test validated that the proposed obstacle avoidance method based on variational method is feasible and practicable.

We propose a gradient-based method for quadratic programming problems with a single linear constraint and bounds on the variables. Inspired by the GPCG algorithm for bound-constrained convex quadratic programming [J.J. Mor\'e and G. Toraldo, SIAM J. Optim. 1, 1991], our approach alternates between two phases until convergence: an identification phase, which performs gradient projection iterations until either a candidate active set is identified or no reasonable progress is made, and an unconstrained minimization phase, which reduces the objective function in a suitable space defined by the identification phase, by applying either the conjugate gradient method or a recently proposed spectral gradient method. However, the algorithm differs from GPCG not only because it deals with a more general class of problems, but mainly for the way it stops the minimization phase. This is based on a comparison between a measure of optimality in the reduced space and a measure of bindingness of the variables that are on the bounds, defined by extending the concept of proportioning, which was proposed by some authors for box-constrained problems. If the objective function is bounded, the algorithm converges to a stationary point thanks to a suitable application of the gradient projection method in the identification phase. For strictly convex problems, the algorithm converges to the optimal solution in a finite number of steps even in case of degeneracy. Extensive numerical experiments show the effectiveness of the proposed approach., Comment: 30 pages, 17 figures

We study the power allocation problem for maximizing the sum rate in orthogonal frequency-division multiplexing systems, where multiple point-to-point links share a set of subcarriers. This problem is hard to solve, in general, due to its nonconvexity. In this letter, we characterize the conditions for the problem to be convex, in which case the problem can be solved efficiently using known algorithms such as gradient projection method. We validate our analysis through simulations.