On minimizing the ratio of quadratic functions over an ellipsoid

We study the optimization problem (RQ) of minimizing the ratio of two quadratic functions over a possibly degenerate ellipsoid. The well definition of problem (RQ) is fully characterized. We show any well-defined (RQ) admits a semidefinite programming reformulation (SDP) without any assumption. Moreover, the minimum of (RQ) is attained if and only if (SDP) has a unique solution.     

Decomposition method of descent for minimizing the sum of convex nonsmooth functions

This paper presents a descent method for minimizing a sum of possibly nonsmooth convex functions. Search directions are found by solving subproblems obtained by replacing all but one of the component functions with their polyhedral approximations and adding a quadratic term. The algorithm is globally convergent and terminates when the objective function happens to be polyhedral. It yields a new decomposition method for solving large-scale linear programs with dual block-angular structure.Supported by Program CPBP 02.15.The author thanks the two referees for their helpful suggestions.     

A regularized stochastic decomposition algorithm for two-stage stochastic linear programs

In this paper a regularized stochastic decomposition algorithm with master programs of finite size is described for solving two-stage stochastic linear programming problems with recourse. In a deterministic setting cut dropping schemes in decomposition based algorithms have been used routinely. However, when only estimates of the objective function are available such schemes can only be properly justified if convergence results are not sacrificed. It is shown that almost surely every accumulation point in an identified subsequence of iterates produced by the algorithm, which includes a cut dropping scheme, is an optimal solution. The results are obtained by including a quadratic proximal term in the master program. In addition to the cut dropping scheme, other enhancements to the existing methodology are described. These include (i) a new updating rule for the retained cuts and (ii) an adaptive rule to determine when additional reestimation of the cut associated with the current solution is needed. The algorithm is tested on problems from the literature assuming both descrete and continuous random variables.A majority of this work is part of the author's Ph.D. dissertation prepared at the University of Arizona in 1990.     

A method for minimizing the sum of a convex function and a continuously differentiable function

This paper presents a method for minimizing the sum of a possibly nonsmooth convex function and a continuously differentiable function. As in the convex case developed by the author, the algorithm is a descent method which generates successive search directions by solving quadratic programming subproblems. An inexact line search ensures global convergence of the method to stationary points.     

Convergence of the steepest descent method for minimizing quasiconvex functions

To minimize a continuously differentiable quasiconvex functionf: ⁿ , Armijo's steepest descent method generates a sequencex ^k+1 =x ^k –t _k f(x ^k ), wheret _k >0. We establish strong convergence properties of this classic method: either , s.t. ; or arg minf = , x ^k andf(x ^k ) inff. We also discuss extensions to other line searches.The research of the first author was supported by the Polish Academy of Sciences. The second author acknowledges the support of the Department of Industrial Engineering, Hong Kong University of Science and Technology.We wish to thank two anonymous referees for their valuable comments. In particular, one referee has suggested the use of quasiconvexity instead of convexity off.     

Lagrangian decomposition of block-separable mixed-integer all-quadratic programs

The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The results indicate that appropriate block-separable reformulations of MIQQPs could accelerate the running time of dual solution algorithms considerably.The work was supported by the German Research Foundation (DFG) under grant NO 421/2-1Mathematics Subject Classification (2000): 90C22, 90C20, 90C27, 90C26, 90C59     

A modified Newton's method for minimizing factorable functions

Many functions of several variables used in nonlinear programming are factorable, i.e., complicated compositions of transformed sums and products of functions of a single variable. The Hessian matrices of twice-differentiable factorable functions can easily be expressed as sums of outer products (dyads) of vectors. A modified Newton's method for minimizing unconstrained factorable functions which exploits this special form of the Hessian is developed. Computational experience with the method is presented.This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-04106.The author would like to thank Professor G. P. McCormick, George Washington University, for several enlightening discussions on factorable programming and for his valuable comments which improved an earlier version of this paper.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF MAX-BISECTION

A successive quadratic programming algorithm for solving SDP relaxation of Max- Bisection is provided and its convergence result is given.The step-size in the algorithm is obtained by solving n easy quadratic equations without using the linear search technique.The numerical experiments show that this algorithm is rather faster than the interior-point method.     

A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.     

An Interior-Point Method for a Class of Saddle-Point Problems

We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization formulations of convex quadratic programming problems with uncertain input parameters. As an application of our approach, we discuss a robust formulation of the Markowitz portfolio selection model.     

A proximal alternating linearization method for minimizing the sum of two convex functions

In this paper, we develop a novel alternating linearization method for solving convex minimization whose objective function is the sum of two separable functions. The motivation of the paper is to extend the recent work Goldfarb et al.(2013) to cope with more generic convex minimization. For the proposed method,both the separable objective functions and the auxiliary penalty terms are linearized. Provided that the separable objective functions belong to C1,1(Rn), we prove the O(1/?) arithmetical complexity of the new method. Some preliminary numerical simulations involving image processing and compressive sensing are conducted.     

A modified predictor-corrector method for linear programming

In the predictor-corrector method of Mizuno, Todd and Ye [1], the duality gap is reduced only at the predictor step and is kept unchanged during the corrector step. In this paper, we modify the corrector step so that the duality gap is reduced by a constant fraction, while the predictor step remains unchanged. It is shown that this modified predictor-corrector method retains the iteration complexity as well as the local quadratic convergence property.     

Local properties of inexact methods for minimizing nonsmooth composite functions

Methods for minimization of composite functions with a nondifferentiable polyhedral convex part are considered. This class includes problems involving minimax functions and norms. Local convergence results are given for “active set” methods, in which an equality-constrained quadratic programming subproblem is solved at each iteration. The active set consists of components of the polyhedral convex function which are active or near-active at the current iteration. The effects of solving the subproblem inexactly at each iteration are discussed; rate-of-convergence results which depend on the degree of inexactness are given.     

A quadratically convergent method for minimizing a sum of euclidean norms

We consider the problem of minimizing a sum of Euclidean norms. \(F(x) = \sum\nolimits_{i = 1}^m {||r_i } (x)||\) here the residuals {r _i(x)} are affine functions fromR ⁿ toR ¹ (n≥1≥2,m>-2). This arises in a number of applications, including single-and multi-facility location problems. The functionF is, in general, not differentiable atx if at least oner _i (x) is zero. Computational methods described in the literature converge quite slowly if the solution is at such a point. We present a new method which, at each iteration, computes a direction of search by solving the Newton system of equations, projected, if necessary, into a linear manifold along whichF is locally differentiable. A special line search is used to obtain the next iterate. The algorithm is closely related to a method recently described by Calamai and Conn. The new method has quadratic convergence to a solutionx under given conditions. The reason for this property depends on the nature of the solution. If none of the residuals is zero at^* x, thenF is differentiable at^* x and the quadratic convergence follows from standard properties of Newton's method. If one of the residuals, sayr _i ^* x), is zero, then, as the iteration proceeds, the Hessian ofF becomes extremely ill-conditioned. It is proved that this illconditioning, instead of creating difficulties, actually causes quadratic convergence to the manifold (x?r _i (x)=0}. If this is a single point, the solution is thus identified. Otherwise it is necessary to continue the iteration restricted to this manifold, where the usual quadratic convergence for Newton's method applies. If several residuals are zero at^* x, several stages of quadratic convergence take place as the correct index set is constructed. Thus the ill-conditioning property accelerates the identification of the residuals which are zero at the solution. Numerical experiments are presented, illustrating these results.     

A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid

We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special case of the problem’s class we study. We prove that under a certain mild assumption on the problem’s data, problem (RQ) admits an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge superlinearly to a global solution of (RQ) and show that the dependency of the number of iterations on the optimality tolerance grows as . This research is partially supported by the Israel Science Foundation, ISF grant #489-06.     

A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

A convergent decomposition algorithm for support vector machines

In this work we consider nonlinear minimization problems with a single linear equality constraint and box constraints. In particular we are interested in solving problems where the number of variables is so huge that traditional optimization methods cannot be directly applied. Many interesting real world problems lead to the solution of large scale constrained problems with this structure. For example, the special subclass of problems with convex quadratic objective function plays a fundamental role in the training of Support Vector Machine, which is a technique for machine learning problems. For this particular subclass of convex quadratic problem, some convergent decomposition methods, based on the solution of a sequence of smaller subproblems, have been proposed. In this paper we define a new globally convergent decomposition algorithm that differs from the previous methods in the rule for the choice of the subproblem variables and in the presence of a proximal point modification in the objective function of the subproblems. In particular, the new rule for sequentially selecting the subproblems appears to be suited to tackle large scale problems, while the introduction of the proximal point term allows us to ensure the global convergence of the algorithm for the general case of nonconvex objective function. Furthermore, we report some preliminary numerical results on support vector classification problems with up to 100 thousands variables.     

A Log-Barrier method with Benders decomposition for solving two-stage stochastic linear programs

An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time. Received: August 1998 / Accepted: August 2000?Published online April 12, 2001     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.