Narrow Results

In this paper, the delayed projection neural network for a class of solving convex programming problem is proposed. The existence of solution and global exponential stability of the proposed network are proved, which can guarantee to converge at an exact optimal solution of the convex programming problems. Several examples are given to show the effectiveness of the proposed network.

Simultaneous exploitation of task and data parallelism provides significant benefits for many applications. The basic approach for exploiting task and data parallelism is to use a task graph representation (Macro Dataflow Graph) for programs to decide on the degree of data parallelism to be used for each task (allocation) and an execution order for the tasks (scheduling). Previously, we presented a two step approach for allocation and scheduling by considering the two steps to be independent of each other. In this paper, we present a new simultaneous approach which uses constraints to model the scheduler during allocation. The new simultaneous approach provides significant benefits over our earlier approach for the benchmark task graphs that we have considered.

In this paper, we present an algorithm to solve a particular convex model explicitly. The model may massively arise when, for example, Benders decomposition or Lagrangean relaxation-decomposition is applied to solve large design problems in facility location and capacity expansion. To attain the optimal solution of the model, we analyze its Karush–Kuhn–Tucker optimality conditions and develop a constructive algorithm that provides the optimal primal and dual solutions. This approach yields better performance than other convex optimization techniques.

In this paper, we consider a class of convex nonlinear knapsack problems in which all decision variables are integer and the objective and knapsack functions are nonlinear. This generalized problem is characterized by positive marginal cost (PMC) and increasing marginal loss-cost ratio (IMLCR). By analyzing the structural properties of the problem, we develop an efficient heuristic and propose search and branching rules to improve the branch and bound method for solving exact solution. Numerical study is done for showing the effectiveness of the proposed heuristic and the modified branch and bound method.

We consider the linearly constrained separable convex programming problem whose objective function is separable into m individual convex functions with non-overlapping variables. The alternating direction method of multipliers (ADMM) has been well studied in the literature for the special case m = 2, but the direct extension of ADMM for the general case m ≥ 2 is not necessarily convergent. In this paper, we propose a new linearized ADMM-based contraction type algorithms for the general case m ≥ 2. For the proposed algorithm, we prove its convergence via the analytic framework of contractive type methods and we derive a worst-case O(1/t) convergence rate in ergodic sense. Finally, numerical results are reported to demonstrate the effectiveness of the proposed algorithm.

In this paper, we focus on the primal-dual hybrid gradient (PDHG) method, which is being widely used to solve a broad spectrum of saddle-point problems. Despite of its wide applications in different areas, the study of inexact versions of PDHG still seems to be in its infancy. We investigate how to design implementable inexactness criteria for solving the subproblems in PDHG scheme so that the convergence of an inexact PDHG can be guaranteed. We propose two specific inexactness criteria and accordingly some inexact PDHG methods for saddle-point problems. The convergence of both inexact PDHG methods is rigorously proved, and their convergence rates are estimated under different scenarios. Moreover, some numerical results on image restoration problems are reported to illustrate the efficiency of the proposed methods.

In both practical applications and theoretical analysis, there are many fuzzy chance-constrained optimization problems. Currently, there is short of real-time algorithms for solving such problems. Therefore, in this paper, a continuous-time neurodynamic approach is proposed for solving a class of fuzzy chance-constrained optimization problems. Firstly, an equivalent deterministic problem with inequality constraint is discussed, and then a continuous-time neurodynamic approach is proposed. Secondly, a sufficient and necessary optimality condition of the considered optimization problem is obtained. Thirdly, the boundedness, global existence and Lyapunov stability of the state solution to the proposed approach are proved. Moreover, the convergence to the optimal solution of considered problem is studied. Finally, several experiments are provided to show the performance of proposed approach.

Hyperbolic programming is the problem of computing the infimum of a linear function when restricted to the hyperbolicity cone of a hyperbolic polynomial, a generalization of semidefinite programming (SDP). We propose an approach based on symbolic computation, relying on the multiplicity structure of the algebraic boundary of the cone, without the assumption of determinantal representability. This allows us to design exact algorithms able to certify the multiplicity of the solution and the optimal value of the linear function.

In this paper, we consider the noisy phase retrieval problem which occurs in many different areas of science and physics. The PhaseMax algorithm is an efficient convex method to tackle with phase retrieval problem. On the basis of this algorithm, we propose two kinds of extended formulations of the PhaseMax algorithm, namely, PhaseMax with bounded and non-negative noise and PhaseMax with outliers to deal with the phase retrieval problem under different noise corruptions. Then we prove that these extended algorithms can stably recover real signals from independent sub-Gaussian measurements under optimal sample complexity. Specially, such results remain valid in noiseless case. As we can see, these results guarantee that a broad range of random measurements such as Bernoulli measurements with erasures can be applied to reconstruct the original signals by these extended PhaseMax algorithms. Finally, we demonstrate the effectiveness of our extended PhaseMax algorithm through numerical simulations. We find that with the same initialization, extended PhaseMax algorithm outperforms Truncated Wirtinger Flow method, and recovers the signal with corrupted measurements robustly.

In this work, we establish the linear convergence estimate for the gradient descent involving the delay $\tau \in \mathbb{N}$ when the cost function is $\mu$-strongly convex and $L$-smooth. This result improves upon the well-known estimates in [Y. Arjevani, O. Shamir and N. Srebro, A tight convergence analysis for stochastic gradient descent with delayed updates, Proc. Mach. Learn. Res. 117 (2020) 111–132; S. U. Stich and S. P. Karimireddy, The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates, J. Mach. Learn. Res. 21(1) (2020) 9613–9648] in the sense that it is non-ergodic and is still established in spite of weaker constraint of cost function. Also, the range of learning rate $\eta$ can be extended from $\eta \le 1/(10L\tau )$ to $\eta \le 1/(4L\tau )$ for $\tau =1$ and $\eta \le 3/(10L\tau )$ for $\tau \ge 2$, where $L>0$ is the Lipschitz continuity constant of the gradient of cost function. In a further research, we show the linear convergence of cost function under the Polyak–Łojasiewicz(PL) condition, for which the available choice of learning rate is further improved as $\eta \le 9/(10L\tau )$ for the large delay $\tau$. The framework of the proof for this result is also extended to the stochastic gradient descent with time-varying delay under the PL condition. Finally, some numerical experiments are provided in order to confirm the reliability of the analyzed results.

Image restoration problems can naturally be cast as constrained convex programming problems in which the constraints arise from a priori information and the observation of signals physically related to the image to be recovered. In this paper, the focus is placed on the construction of constraints based on wavelet representations. Using a mix of statistical and convex-analytical tools, we propose a general framework to construct wavelet-based constraints. The resulting optimization problem is then solved with a block-iterative parallel algorithm which offers great flexibility in terms of implementation. Numerical results illustrate an application of the proposed framework.

This paper presents a numerical model for analyzing the stresses and displacements of deformable bodies in contact with the presence of friction and material nonlinearity. Based on the finite element method (FEM), the elastoplastic frictional contact problem is formulated as an incremental convex programming model (ICPM) under inequality contact constraints and friction conditions. The classical Coulomb's friction law and the Prandtl–Reuss flow rule with the von Mises yield criterion are used to simulate the interface friction conditions and the elastoplastic behavior of the contacting bodies, respectively. The Lagrange multiplier approach is adopted for imposing the contact constraints. Furthermore, an effective adaptive incremental procedure is developed for solving the elastoplastic frictional contact problems. Examples for the frictional contact having advancing and receding nature are analyzed. The obtained results prove the ability of the developed procedure to investigate the sequence of different events during monotonic application of external loads. In addition, the results elucidate the effect of external side force on the friction behavior in the presence of plastic deformation. Good agreement has been found with published results.

In density-based topological design, 0/1 solutions are often sought. The SIMP (Solid Isotropic Microstructure with Penalization) method is widely employed to achieve binary values. The solution is not the same when the penalization exponent is different in SIMP. As a possible alternative to SIMP, a new method is introduced. The design variables are still the densities of the finite elements but Young's modulus is a linear function of these densities. In order to drive the solution to a 0/1 layout a new constraint, labeled the sum of squares of the variables (SSV), is added in the topology optimization model. The SSV constraint is convex, which will work effectively with the method of moving asymptotes (MMA) belonging to the convex programming schemes in classical structural topological design. Some examples are given to show the effectiveness of the proposed method. It is turned out that the SSV method improves the total stiffness and can thoroughly remove the grey areas.

We examine the differences in complexity for distributed and non-distributed algorithms by focusing on the example of resource allocation. We construct lower bounds for these problems which are valid in many models of computation. We then present an efficient primal-dual algorithm for allocating one or two resources and describe a method for constructing one for an arbitrary number of resources that is easily implemented in parallel.

We describe the two methods of Y. E. Nesterov [18, 19, 20] for minimizing a convex function with a Lipschitz continuous derivative over a closed convex set. These methods are optimal in the oracle model of computational complexity. We extend the applicability of one of the methods and give a simple proof of the other. We present results of our numerical experiments with one of the methods in solving randomly generated quadratic problems with box constraints. These and other numerical experiments of the author in [7] indicate that Nesterov's methods are promising for solving sparse, large scale convex programs.

Consider a convex set in R^d and a piecewise polynomial concave function . Let be an algorithm that given a point x ∈ R^d computes F(x) if , or returns a concave polynomial p such that p(x) < 0 but for any , p(y) ≥ 0. We assume that d is fixed and that all comparisons in depend on the sign of polynomial functions of the input point. We show that under these conditions, one can find in time which is polynomial in the number of arithmetic operations of . Using our method we give the first strongly polynomial algorithms for many non-linear parametric problems in fixed dimension, such as the parametric max flow problem, the parametric minimum s-t distance, the parametric spanning tree problem and other problems. We also present an efficient algorithm for a very general convex programming problem in fixed dimension.