Generalized linear multiplicative and fractional programming

This paper addresses itself to the algorithm for minimizing the sum of a convex function and a product of two linear functions over a polytope. It is shown that this nonconvex minimization problem can be solved by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in higher dimension and apply a parametric programming (path following) approach. Also it is shown that the same idea can be applied to a generalized linear fractional programming problem whose objective function is the sum of a convex function and a linear fractional function.     

交替最小化算法求解强凸函数与弱凸函数和的极小值问题

交替最小化算法(简称AMA)最早由[SIAM J.Control Optim.,1991,29(1):119-138]提出,并能用于求解强凸函数与凸函数和的极小值问题.本文直接利用AMA算法来求解强凸函数与弱凸函数和的极小值问题.在强凸函数的模大于弱凸函数的模的假设下,我们证明了AMA生成的点列全局收敛到优化问题的解,并且若该优化问题中的某个函数是光滑函数时,AMA所生成的点列的收敛率是线性的.     

Nonconvex Piecewise-Quadratic Underestimation for Global Minimization

Motivated by the fact that important real-life problems, such as the protein docking problem, can be accurately modeled by minimizing a nonconvex piecewise-quadratic function, a nonconvex underestimator is constructed as the minimum of a finite number of strictly convex quadratic functions. The nonconvex underestimator is generated by minimizing a linear function on a reverse convex region and utilizes sample points from a given complex function to be minimized. The global solution of the piecewise-quadratic underestimator is known exactly and gives an approximation to the global minimum of the original function. Successive shrinking of the initial search region to which this procedure is applied leads to fairly accurate estimates, within 0.0060%, of the global minima of synthetic nonconvex functions for which the global minima are known. Furthermore, this process can approximate a nonconvex protein docking function global minimum within four-figure relative accuracy in six refinement steps. This is less than half the number of refinement steps required by previous models such as the convex kernel underestimator (Mangasarian et al., Computational Optimization and Applications, to appear) and produces higher accuracy here.     

Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

Finite algorithm for generalized linear multiplicative programming

The nonconvex problem of minimizing the sum of a linear function and the product of two linear functions over a convex polyhedron is considered. A finite algorithm is proposed which either finds a global optimum or shows that the objective function is unbounded from below in the feasible region. This is done by means of a sequence of primal and/or dual simplex iterations.The first author gratefully acknowledges the research support received as Visiting Professor of the Dipartimento di Statistica e Matematica Applicata all' Economia, Universitá di Pisa, Pisa, Italy, Spring 1992.     

A Finite Algorithm for a Class of Nonlinear Multiplicative Programs

The nonconvex problem of minimizing the product of a strictly convex quadratic function and the p-th power of a linear function over a convex polyhedron is considered. Some theoretical properties of the problem, such as the existence of minimum points and the generalized convexity of the objective function, are deepened on and a finite algorithm which solves the problem is proposed.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Minimization of the sum of three linear fractional functions

In this paper, we will propose an efficient and reliable heuristic algorithm for minimizing and maximizing the sum of three linear fractional functions over a polytope. These problems are typical nonconvex minimization problems of practical as well as theoretical importance. This algorithm uses a primal-dual parametric simplex algorithm to solve a subproblem in which the value of one linear function is fixed. A subdivision scheme is employed in the space of this linear function to obtain an approximate optimal solution of the original problem. It turns out that this algorithm is much more efficient and usually generates a better solution than existing algorithms. Also, we will develop a similar algorithm for minimizing the product of three linear fractional functions.     

An outcome space approach for generalized convex multiplicative programs

This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.     

Minimizing the sum of a convex function and the product of two affine functions over a convex set

An efficient branch-and-bound algorithm for minimizing the sum of a convex function and the product of two affine functions over a convex set is proposed. The branching takes place in an interval of R the bounding is a relaxation     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

A finite concave minimization algorithm using branch and bound and neighbor generation

In this article we present a new finite algorithm for globally minimizing a concave function over a compact polyhedron. The algorithm combines a branch and bound search with a new process called neighbor generation. It is guaranteed to find an exact, extreme point optimal solution, does not require the objective function to be separable or even analytically defined, requires no nonlinear computations, and requires no determinations of convex envelopes or underestimating functions. Linear programs are solved in the branch and bound search which do not grow in size and differ from one another in only one column of data. Some preliminary computational experience is also presented.     

A row-action method for convex programming

We present a new method for minimizing a strictly convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions (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. Convergence of the algorithm is established and the method is compared with other row-action algorithms for several relevant particular cases.Corresponding author. Research of this author was partially supported by CNPq grant No. 301280/86.     

Generalized Convex Multiplicative Programming via Quasiconcave Minimization

We present a new method for minimizing the sum of a convex function and aproduct of k nonnegative convex functions over a convex set. This problem isreduced to a k-dimensional quasiconcave minimization problem which is solvedby a conical branch-and-bound algorithm. Comparative computational results areprovided on test problems from the literature.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

A subgradient algorithm for certain minimax and minisum problems

We present a subgradient algorithm for minimizing the maximum of a finite collection of functions. It is assumed that each function is the sum of a finite collection of basic convex functions and that the number of different subgradient sets associated with nondifferentiable points of each basic function is finite on any bounded set. Problems belonging to this class include the linear approximation problem and both the minimax and minisum problems of location theory. Convergence of the algorithm to an epsilon-optimal solution is proven and its effectiveness is demonstrated by solving a number of location problems and linear approximation problems.This research was partially supported by the Army Research Office, Triangle Park, NC, under contract number DAH-CO4-75-G-0150, and by NSF grants ENG 16-24294 and ENG 75-10225.     

An implementation of a reduced subgradient method via Luenberger-Mokhtar variant

We present an implementable algorithm for minimizing a convex function which is not necessarily differentiable subject to linear equality constraints and to nonnegativity bounds on the variables. The algorithm is based on extending the variant proposed by Luenberger to the nondifferentiable case and using the bundle techniques introduced by Lemaréchal to approximate the subdifferential of the objective function. In particular, at each iteration, we compute a search direction by solving a quadratic subproblem, and an inexact line search along this direction yields a decrease in the objective value. Under some assumptions, the convergence of the proposed algorithm is analysed. Finally, some numerical results are presented, which show that the algorithm performs efficiently.     

A STOCHASTIC MOVING BALLS APPROXIMATION METHOD OVER A SMOOTH INEQUALITY CONSTRAINT

We consider the problem of minimizing the average of a large number of smooth component functions over one smooth inequality constraint. We propose and analyze a stochastic Moving Balls Approximation (SMBA) method. Like stochastic gradient (SG) methods, the SMBA method's iteration cost is independent of the number of component functions and by exploiting the smoothness of the constraint function, our method can be easily implemented. Theoretical and computational properties of SMBA are studied, and convergence results are established. Numerical experiments indicate that our algorithm dramatically outperforms the existing Moving Balls Approximation algorithm (MBA) for the structure of our problem.