Search

Error bounds are a requisite for trusting or distrusting solutions in an informed way. Until recently, provable error bounds in the absence of constraint qualifications were unattainable for many classes of cones that do not admit projections with known succinct expressions. We build such error bounds for the generalized power cones, using the recently developed framework of onestep facial residual functions. We also show that our error bounds are tight in the sense of that framework. Besides their utility for understanding solution reliability, the error bounds we discover have additional applications to the algebraic structure of the underlying cone, which we describe. In particular we use the error bounds to compute the automorphisms of the generalized power cones, and to identify a set of generalized power cones that are self-dual, irreducible, nonhomogeneous, and perfect. [ABSTRACT FROM AUTHOR]

Given closed convex sets Ci, i=1, ... l, and some nonzero linear maps Ai, i=1, ... l, of suitable dimensions, the multiset split feasibility problem aims at finding a point in ... based on computing projections onto Ci and multiplications by Ai and AiT. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto ...; we refer to this problem as the best approximation problem in multiset split feasibility settings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving the BA-MSF in the special case when all Ai - I, to solve the general BA-MSF. Our Dykstra-type projection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrange dual problem, and it only requires computing projections onto Ci and multiplications by Ai and AiT in each iteration. Under a standard relative interior condition and a genericity assumption on the point we need to project, we show that the dual objective satisfies the Kurdyka-Łojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each Ci is C1,α.-cone reducible for some α∈ (0,1]: this class of sets covers the class of C²-cone reducible sets, which include all polyhedrons, second-order cone, and the cone of positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear or sublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concrete examples are constructed to illustrate the necessity of some of our assumptions. [ABSTRACT FROM AUTHOR]

In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method in [C. W. Royer, M. O'Neill, and S. J. Wright, Math. Program., 180 (2020), pp. 451-488]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of O(ε7/peration complexity of O(ε7/2 min\{ n, ε3/4\}) for finding an (ε, ε)-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method in [Y. Xie and S. J. Wright, J. Sci. Comput., 86 (2021), pp. 1-30]. In addition, we show that it has a total inner iteration complexity of O(ε11/2) and an operation complexity of O(ε11/2 min\{ n, ε5/4\}) when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the other competing algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we study the sequential convex programming method with monotone line search (SCPls) in [Z. Lu, Sequential Convex Programming Methods for a Class of Structured Nonlinear Programming, https://arxiv.org/abs/1210.3039, 2012] for a class of difference-of-convex optimization problems with multiple smooth inequality constraints. The SCPls is a representative variant of moving-ball-approximation-type algorithms [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259; J. Bolte, Z. Chen, and E. Pauwels, Math. Program., 182 (2020) pp. 1-36; J. Bolte and E. Pauwels, Math. Oper. Res., 41 (2016), pp. 442-465; R. Shefi and M. Teboulle, Math. Program., 159 (2016), pp. 137-164] for constrained optimization problems. We analyze the convergence rate of the sequence generated by SCPls in both nonconvex and convex settings by imposing suitable Kurdyka--Löjasiewicz (KL) assumptions. Specifically, in the nonconvex settings, we assume that a special potential function related to the ob jective and the constraints is a KL function, while in the convex settings we impose KL assumptions directly on the extended ob jective function (i.e., sum of the ob jective and the indicator function of the constraint set). A relationship between these two different KL assumptions is established in the convex settings under additional differentiability assumptions. We also discuss how to deduce the KL exponent of the extended ob jective function from its Lagrangian in the convex settings, under additional assumptions on the constraint functions. Thanks to this result, the extended ob jectives of some constrained optimization models such as minimizing\ell1 sub ject to logistic/Poisson loss are found to be KL functions with exponent 1 under mild assumptions. To illustrate how our results can be applied, we consider SCPs for minimizing 1-2 [P-Yin, Y. Lou, Q. He, and J. Xin, SIAM J. Sci. Comput., 37 (2015), pp. A536--A563] subject to residual error measured by norm/Lorentzian norm [R. E. Carrillo, A. B. Ramirez, G. R. Arce, K. E. Barner, and B. M. Sadler, EURASIP J. Adv. Signal Process. (2016), 108]. We first discuss how the various conditions required in our analysis can be verified, and then perform numerical experiments to illustrate the convergence behaviors of SCPls. [ABSTRACT FROM AUTHOR]

Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of ℓ1 and ℓ2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing ℓ1/ℓ2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka--Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the ℓ1/ℓ2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell 2 norm or Lorentzian norm via solving the corresponding ℓ1/ℓ2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of minimizing a smooth objective over multiple rank constraints on Hankel structured matrices. These kinds of problems arise in system identification, system theory, and signal processing, where the rank constraints are typically "hard constraints." To solve these problems, we propose a hybrid penalty method that combines a penalty method with a postprocessing scheme. Specifically, we solve the penalty subproblems until the penalty parameter reaches a given threshold, and then switch to a local alternating pseudoprojection"" method to further reduce constraint violation. Pseudoprojection is a generalization of the concept of projection. We show that a pseudoprojection onto a single low-rank Hankel structured matrix constraint can be computed efficiently by existing software such as SLRA [I. Markovsky and K. Usevich, J. Comput. Appl. Math., 256 (2014), pp. 278--292], under mild assumptions. We also demonstrate how the penalty subproblems in the hybrid penalty method can be solved by pseudoprojection-based optimization methods, and then present some convergence results for our hybrid penalty method. Finally, the efficiency of our method is illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper we consider a general matrix factorization model which covers a large class of existing models with many applications in areas such as machine learning and imaging sciences. To solve this possibly nonconvex, nonsmooth, and non-Lipschitz problem, we develop a nonmonotone alternating updating method based on a potential function. Our method essentially updates two blocks of variables in turn by inexactly minimizing this potential function, and updates another auxiliary block of variables using an explicit formula. The special structure of our potential function allows us to take advantage of efficient computational strategies for nonnegative matrix factorization to perform the alternating minimization over the two blocks of variables. A suitable line search criterion is also incorporated to improve the numerical performance. Under some mild conditions, we show that the line search criterion is well defined, and establish that the sequence generated is bounded and any cluster point of the sequence is a stationary point. Finally, we conduct some numerical experiments using real datasets to compare our method with some existing efficient methods for nonnegative matrix factorization and matrix completion. The numerical results show that our method can outperform these methods for these specific applications. [ABSTRACT FROM AUTHOR]

In this paper, we study the proximal gradient algorithm with extrapolation for minimizing the sum of a Lipschitz differentiable function and a proper closed convex function. Under the error bound condition used in [Ann. Oper. Res., 46 (1993), pp. 157--178] for analyzing the convergence of the proximal gradient algorithm, we show that there exists a threshold such that if the extrapolation coefficients are chosen below this threshold, then the sequence generated converges B-linearly to a stationary point of the problem. Moreover, the corresponding sequence of objective values is also B-linearly convergent. In addition, the threshold reduces t o 1 for convex problems, and as a consequence we obtain the B-linear convergence of the sequence generated by FISTA with fixed restart. Finally, we present some numerical experiments to illustrate our results. [ABSTRACT FROM AUTHOR]

In this paper, we study a general optimization model, which covers a large class of existing models for many applications in imaging sciences. To solve the resulting possibly nonconvex, nonsmooth, and non-Lipschitz optimization problem, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solve a reformulation that contains three blocks of variables and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a computable threshold such that if the penalty parameter is chosen above such a threshold and the sequence thus generated by our ADMM is bounded, then the cluster point of the sequence gives a stationary point of the nonconvex optimization problem. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence if, in addition, this special potential function is a Kurdyka{ Lojasiewicz function. Furthermore, we present a simple strategy for initializing the algorithm to guarantee boundedness of the sequence. Finally, we perform numerical experiments comparing our ADMM with the proximal alternating linearized minimization proposed in [Bolte, Sabach, and Teboulle, Math. Program., 146 (2014), pp. 459{494] on the background/foreground extraction problem with real data. The numerical results show that our ADMM with a nontrivial dual step-size is efficient. [ABSTRACT FROM AUTHOR]

We consider a class of constrained optimization problems with a possibly nonconvex non-Lipschitz objective and a convex feasible set being the intersection of a polyhedron and a possibly degenerate ellipsoid. Such problems have a wide range of applications in data science, where the objective is used for inducing sparsity in the solutions while the constraint set models the noise tolerance and incorporates other prior information for data fitting. To solve this class of constrained optimization problems, a common approach is the penalty method. However, there is little theory on exact penalization for problems with nonconvex and non-Lipschitz objective functions. In this paper, we study the existence of exact penalty parameters regarding local minimizers, stationary points, and epsilonε-minimizers under suitable assumptions. Moreover, we discuss a penalty method whose subproblems are solved via a nonmonotone proximal gradient method with a suitable update scheme for the penalty parameters and prove the convergence of the algorithm to a KKT point of the constrained problem. Preliminary numerical results demonstrate the efficiency of the penalty method for finding sparse solutions of underdetermined linear systems. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the sum of a smooth function h with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function P and a surjective linear map M, with the proximal mappings of τP, τ > 0, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions h and P are semialgebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the l1/2 regularization. Finally, when M is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex h. [ABSTRACT FROM AUTHOR]

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47-67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems allows for a special kind of duality framework. This paper explores the duality framework proposed by Freund, and proposes a particular form of the problem that exposes some useful properties of the gauge optimization framework (such as the variational properties of its value function), and yet maintains most of the generality of the abstract form of gauge optimization. [ABSTRACT FROM AUTHOR]

In this paper, we study optimal experimental design problems with a broad class of smooth convex optimality criteria, including the classical A-, D-, and pth mean criterion. In particular, we propose an interior point (IP) method for them and establish its global convergence. Further, by exploiting the structure of the Hessian matrix of the optimality criteria, we derive an explicit formula for computing its rank. Using this result, we then demonstrate that the Newton direction arising in the IP method can be computed efficiently via the Sherman-Morrison-Woodbury formula when the size of the moment matrix is small relative to the size of the design space. Finally, we compare our IP method with the widely used multiplicative algorithm introduced by [S. D. Silvey, D. M. Titterington, and B. Torsney, Commun. Statist. Theory Methods, 7 (1978), pp. 1379-1389] and the standard IP solver SDPT3 [K. C. Toh, M. J. Todd, and R. H. Tütüncü, Optim. Methods Softw., 11/12 (1999), pp. 545-581], [R. H. Tütüncü, K. C. Toh, and M. J. Todd, Math. Program. Ser. B, 95 (2003), pp. 189-217]. The computational results show that our IP method generally outperforms these two methods in both speed and solution quality. [ABSTRACT FROM AUTHOR]

In this paper we consider minimizing the spectral condition number of a positive semidefinite matrix over a nonempty closed convex set Ω. We show that it can be solved as a convex programming problem, and moreover, the optimal value of the latter problem is achievable. As a consequence, when Ω is positive semidefinite representable, it can be cast into a semidefinite programming problem. We then propose a first-order method to solve the convex programming problem. The computational results show that our method is usually faster than the standard interior point solver SeDuMi [J. F. Sturm, Optim. Methods Softw., 11/12 (1999), pp. 625-653] while producing a comparable solution. We also study a closely related problem, that is, finding an optimal preconditioner for a positive definite matrix. This problem is not convex in general. We propose a convex relaxation for finding positive definite preconditioners. This relaxation turns out to be exact when finding optimal diagonal preconditioners. [ABSTRACT FROM AUTHOR]