A non-interior continuation algorithm for solving the convex feasibility problem

In this paper, a specific class of convex feasibility problems are considered and a non-interior continuation algorithm based on a smoothing function to solve this class of problems is introduced. The proposed algorithm solves at most one system of linear equations at each iteration. Under some weak assumptions, we show that the algorithm is globally linearly and locally quadratically convergent. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed algorithm.     

The CoMirror algorithm for solving nonsmooth constrained convex problems

We introduce a first-order Mirror-Descent (MD) type algorithm for solving nondifferentiable convex problems having a combination of simple constraint set X (ball, simplex, etc.) and an additional functional constraint. The method is tuned to exploit the structure of X by employing an appropriate non-Euclidean distance-like function. Convergence results and efficiency estimates are derived. The performance of the algorithm is demonstrated by solving certain image deblurring problems.     

Extrapolated cyclic subgradient projection methods for the convex feasibility problems and their numerical behaviour

ABSTRACT

We present two versions of the extrapolated cyclic subgradient projections method for solving the convex feasibility problem. Moreover, we present the results of numerical tests, where we compare the methods with the classical cyclic subgradient projections method.     

Hilbertian convex feasibility problem: Convergence of projection methods

The classical problem of finding a point in the intersection of countably many closed and convex sets in a Hilbert space is considered. Extrapolated iterations of convex combinations of approximate projections onto subfamilies of sets are investigated to solve this problem. General hypotheses are made on the regularity of the sets and various strategies are considered to control the order in which the sets are selected. Weak and strong convergence results are established within thisbroad framework, which provides a unified view of projection methods for solving hilbertian convex feasibility problems. This work was supported by the National Science Foundation under Grant MIP-9308609.     

A condition-based algorithm for solving polyhedral feasibility problems

It is known that Polyhedral Feasibility Problems can be solved via interior-point methods whose real number complexity is polynomial in the dimension of the problem and the logarithm of a condition number of the problem instance. A limitation of these results is that they do not apply to ill-posed instances, for which the condition number is infinite. We propose an algorithm for solving polyhedral feasibility problems in homogeneous form that is applicable to all problem instances, and whose real number complexity is polynomial in the dimension of the problem instance and in the logarithm of an “extended condition number” that is always finite.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

A finite algorithm for solving general quadratic problems

Here we propose a global optimization method for general, i.e. indefinite quadratic problems, which consist of maximizing a non-concave quadratic function over a polyhedron inn-dimensional Euclidean space. This algorithm is shown to be finite and exact in non-degenerate situations. The key procedure uses copositivity arguments to ensure escaping from inefficient local solutions. A similar approach is used to generate an improving feasible point, if the starting point is not the global solution, irrespective of whether or not this is a local solution. Also, definiteness properties of the quadratic objective function are irrelevant for this procedure. To increase efficiency of these methods, we employ pseudoconvexity arguments. Pseudoconvexity is related to copositivity in a way which might be helpful to check this property efficiently even beyond the scope of the cases considered here.     

A dynamic system model for solving convex nonlinear optimization problems

This paper proposes a feedback neural network model for solving convex nonlinear programming (CNLP) problems. Under the condition that the objective function is convex and all constraint functions are strictly convex or that the objective function is strictly convex and the constraint function is convex, the proposed neural network is proved to be stable in the sense of Lyapunov and globally convergent to an exact optimal solution of the original problem. The validity and transient behavior of the neural network are demonstrated by using some examples.     

A greedy algorithm for solving a class of convex programming problems and its connection with polymatroid theory

We present a greedy algorithm for solving a special class of convex programming problems and establish a connection with polymatroid theory which yields a theoretical explanation and verification of the algorithm via some recent results of S. Fujishige.     

A new projection algorithm for solving constrained equilibrium problems in Hilbert spaces

ABSTRACT

In this paper, we introduce a new iterative scheme by combining the hyperplane projection method and the inertial technique for constrained equilibrium problems in real Hilbert spaces. The convergence of the proposed algorithm is established without requiring strict paramonotonicity property. The results presented in the paper extend and improve some recent results in the literature. In addition, a numerical example is given to illustrate the efficiency and performance of the proposed method.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.     

A capacity scaling algorithm for convex cost submodular flows

This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange capacities is available.     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming

In this paper we propose a new iterative method for solving a class of linear complementarity problems:u 0,Mu + q 0, u^T(Mu + q)=0, where M is a givenl ×l positive semidefinite matrix (not necessarily symmetric) andq is a givenl-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.On leave from the Department of Mathematics, University of Nanjing, Nanjing, People's Republic of China.     

How good are projection methods for convex feasibility problems?

We consider simple projection methods for solving convex feasibility problems. Both successive and sequential methods are considered, and heuristics to improve these are suggested. Unfortunately, particularly given the large literature which might make one think otherwise, numerical tests indicate that in general none of the variants considered are especially effective or competitive with more sophisticated alternatives. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This work was supported by the EPSRC grant GR/S42170.     

A splitting primal-dual proximity algorithm for solving composite optimization problems

Our work considers the optimization of the sum of a non-smooth convex function and a finite family of composite convex functions, each one of which is composed of a convex function and a bounded linear operator. This type of problem is associated with many interesting challenges encountered in the image restoration and image reconstruction fields. We developed a splitting primal-dual proximity algorithm to solve this problem. Furthermore, we propose a preconditioned method, of which the iterative parameters are obtained without the need to know some particular operator norm in advance. Theoretical convergence theorems are presented. We then apply the proposed methods to solve a total variation regularization model, in which the L2 data error function is added to the L1 data error function. The main advantageous feature of this model is its capability to combine different loss functions. The numerical results obtained for computed tomography (CT) image reconstruction demonstrated the ability of the proposed algorithm to reconstruct an image with few and sparse projection views while maintaining the image quality.