Today we are living in the era of big data, there is a pressing need for efficient, scalable and robust optimization methods to analyze the data we create and collect. Although Convex methods offer tractable solutions with global optimality, heuristic nonconvex methods are often more attractive in practice due to their superior efficiency and scalability. Moreover, for better representations of the data, the mathematical model we are building today are much more complicated, which often results in highly nonlinear and nonconvex optimizations problems. Both of these challenges require us to go beyond convex optimization. While nonconvex optimization is extraordinarily successful in practice, unlike convex optimization, guaranteeing the correctness of nonconvex methods is notoriously difficult. In theory, even finding a local minimum of a general nonconvex function is NP-hard – nevermind the global minimum. This thesis aims to bridge the gap between practice and theory of nonconvex optimization, by developing global optimality guarantees for nonconvex problems arising in real-world engineering applications, and provable, efficient nonconvex optimization algorithms. First, this thesis reveals that for certain nonconvex problems we can construct a model specialized initialization that is close to the optimal solution, so that simple and efficient methods provably converge to the global solution with linear rate. These problem include sparse basis learning and convolutional phase retrieval. In addition, the work has led to the discovery of a broader class of nonconvex problems – the so-called ridable saddle functions. Those problems possess characteristic structures, in which (i) all local minima are global, (ii) the energy landscape does not have any ''flat'' saddle points. More interestingly, when data are large and random, this thesis reveals that many problems in the real world are indeed ridable saddle, those problems include complete dictionary learning and generalized phase retrieval. For each of the aforementioned problems, the benign geometric structure allows us to obtain global recovery guarantees by using efficient optimization methods with arbitrary initialization.

Ng, Chi Kong. / "May 2003." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (p. 175-187). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

In this thesis, we consider the following two important subjects in the modern variational analysis for the corresponding nonconvex/nonmonotone and nonsmooth cases: geometric results and the variational inequality problem. By using the variational technique, we first present several nonsmooth (nonconvex) geometric results (including an approximate projection result, an extended extremal principle, nonconvex separation theorems, a nonconvex generalization of the Bishop-Phelps theorem and a separable point result) which extend some fundamental theorems in linear functional analysis, convex analysis and optimization theory. Then, by transforming the variational inequality problem into equivalent optimization problems, we establish some error bound result for the nonsmooth and nonmonotone variational inequality problem. / Variational arguments are classical techniques whose use can be traced back to the early development of the calculus of variations. Rooted in the physical principle of least action they have evolved greatly in connection with applications in optimization theory and optimal control. Recently, the discovery of modern variational principles and nonsmooth analysis further expand the range of applications of these techniques and give a new way for extending some geometric results in linear functional analysis and convex analysis. / Li, Guoyin. / "August 2007." / Adviser: Kung-Fu Ng. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1043. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 80-86). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Nemhauser, George; Committee Co-Chair: Ahmed, Shabbir; Committee Member: Bill Cook; Committee Member: Gu, Zonghao; Committee Member: Johnson, Ellis. Part of the SMARTech Electronic Thesis and Dissertation Collection.

No description available.

The primary objective of this thesis is to develop and implement a global optimization algorithm to solve a class of nonconvex programming problems, and to test it using a collection of engineering design problem applications.The class of problems we consider involves the optimization of a general nonconvex factorable objective function over a feasible region that is restricted by a set of constraints, each of which is defined in terms of nonconvex factorable functions. Such problems find widespread applications in production planning, location and allocation, chemical process design and control, VLSI chip design, and numerous engineering design problems. This thesis offers a first comprehensive methodological development and implementation for determining a global optimal solution to such factorable programming problems. To solve this class of problems, we propose a branch-and-bound approach based on linear programming (LP) relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials, coordinated with a {em Reformulation-Linearization Technique} (RLT). The initial stage of the lower bounding step generates a tight, nonconvex polynomial programming relaxation for the given problem. Subsequently, an LP relaxation is constructed for the resulting polynomial program via a suitable RLT procedure. The underlying motivation for these two steps is to generate a tight outer approximation of the convex envelope of the objective function over the convex hull of the feasible region. The bounding step is thenintegrated into a general branch-and-bound framework. The construction of the bounding polynomials and the node partitioning schemes are specially designed so that the gaps resulting from these two levels of approximations approach zero in the limit, thereby ensuring convergence to a global optimum. Various implementation issues regarding the formulation of such tight bounding problems using both polynomial approximations and RLT constructs are discussed. Different practical strategies and guidelines relating to the design of the algorithm are presented within a general theoretical framework so that users can customize a suitable approach that takes advantage of any inherent special structures that their problems might possess. The algorithm is implemented in C++, an object-oriented programming language. The class modules developed for the software perform various functions that are useful not only for the proposed algorithm, but that can be readily extended and incorporated into other RLT based applications as well. Computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. It is shown that, for all the test problems, a very competitive computational performance is obtained. In most cases, the LP solution obtained for the initial node itself provides a very tight lower bound. Furthermore, for nine of these fifteen problems, the application of a local search heuristic based on initializing the nonlinear programming solver MINOS at the node zero LP solution produced the actual global optimum. Moreover, in finding a global optimum, our algorithm discovered better solutions than the ones previously reported in the literature for two of these test instances. / Master of Science

Nonconvex optimization is NP-hard, even the goal is to compute a local minimizer. In applied disciplines, however, nonconvex problems abound, and simple algorithms, such as gradient descent and alternating direction, are often surprisingly effective. The ability of simple algorithms to find high-quality solutions for practical nonconvex problems remains largely mysterious. This thesis focuses on a class of nonconvex optimization problems which CAN be solved to global optimality with polynomial-time algorithms. This class covers natural nonconvex formulations of central problems in signal processing, machine learning, and statistical estimation, such as sparse dictionary learning (DL), generalized phase retrieval (GPR), and orthogonal tensor decomposition. For each of the listed problems, the nonconvex formulation and optimization lead to novel and often improved computational guarantees. This class of nonconvex problems has two distinctive features: (i) All local minimizer are also global. Thus obtaining any local minimizer solves the optimization problem; (ii) Around each saddle point or local maximizer, the function has a negative directional curvature. In other words, around these points, the Hessian matrices have negative eigenvalues. We call smooth functions with these two properties (qualitative) X functions, and derive concrete quantities and strategy to help verify the properties, particularly for functions with random inputs or parameters. As practical examples, we establish that certain natural nonconvex formulations for complete DL and GPR are X functions with concrete parameters. Optimizing X functions amounts to finding any local minimizer. With generic initializations, typical iterative methods at best only guarantee to converge to a critical point that might be a saddle point or local maximizer. Interestingly, the X structure allows a number of iterative methods to escape from saddle points and local maximizers and efficiently find a local minimizer, without special initializations. We choose to describe and analyze the second-order trust-region method (TRM) that seems to yield the strongest computational guarantees. Intuitively, second-order methods can exploit Hessian to extract negative curvature directions around saddle points and local maximizers, and hence are able to successfully escape from the saddles and local maximizers of X functions. We state the TRM in a Riemannian optimization framework to cater to practical manifold-constrained problems. For DL and GPR, we show that under technical conditions, the TRM algorithm finds a global minimizer in a polynomial number of steps, from arbitrary initializations.

Due to the broadcast nature of wireless medium, simultaneous transmissions interfere with each other (especially transmissions on nearby links), thus adversely affecting data rates and Quality of Service (QoS) in the system. Interference mitigation is therefore a fundamental issue that must be addressed in next generation wireless networks. An important technique for this is to control the links' transmission power. Driven by the wide spread of broadband wireless data services, a system-wide efficiency metric (i.e., system utility) is typically used to characterize the advantage of power control. / In interference-limited wireless networks where simultaneous transmissions on nearby links heavily interfere with each other, however, power control alone is not sufficient to eliminate strong levels of interference between close-by links. In this case, scheduling, which allows close-by links to take turns to be active, plays a crucial role for achieving high system performance. Joint power control and scheduling that maximizes the system utility has long been a challenging problem. The complicated coupling between the signal-to-interference ratio of concurrently active links as well as the flexibility to vary power allocation over time gives rise to a series of non-convex optimization problems, for which the global optimal solution is hard to obtain. The second goal of this thesis is to solve the non-convex joint power control and scheduling problems efficiently in a global optimal manner. In particular, it is the monotonicity rather than the convexity of the problem that we exploit to devise an efficient algorithm, referred to as S-MAPEL, to obtain the global optimal solution. To further reduce the complexity, we propose an accelerated algorithm, referred to as A-S-MAPEL, based on the inherent symmetry of the optimal solution. The optimal joint-power-control-and-scheduling solution obtained by the proposed algorithms serves as a useful benchmark for evaluating other existing schemes. With the help of this benchmark, we find that on-off scheduling is of much practical value in terms of system utility maximization if "off-the-shelf' wireless devices are to be used. / Maximizing a system-wide utility through power control is an NP-hard problem in general due to the complicated coupling interference between links. Thus, it is difficult to solve despite its paramount importance. The first goal of this thesis is to find global optimal power allocations to a variety of system utility maximization (SUM) problems based on the recent advances in monotonic optimization. Instead of tackling the non-convexity issue head on, we bypass non-convexity by exploiting the monotonic nature of the power control problem. In particular, we establish a monotonic optimization framework to maximize a system utility through power control in single-carrier or multi-carrier wireless networks. Furthermore, MAPEL and M-MAPEL are respectively proposed to obtain the global optimal power allocation efficiently in single-carrier or multi-carrier wireless networks. The main benefit of MAPEL and M-MAPEL is to provide an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL or M-MAPEL, we evaluate the performance of several existing algorithms through extensive simulations. On the other hand, by tuning the approximation factor in MAPEL and M-MAPEL, we could engineer a desirable tradeoff between optimality and convergence time. / With the proliferation of wireless infrastructureless networks such as ad hoc and sensor networks, it is increasingly crucial to devise an algorithm that solves the power control problem in a distributed fashion. In general, distributed power control is more complicated due to the lack of centralized infrastructure. As the third goal of this thesis, we consider a distributed power control algorithm for infrastructureless ad hoc wireless networks, where each link distributively and asynchronously updates its transmission power with limited message passing among links. This algorithm provably converges to the optimal strategy that picks global optimal solutions with probability 1 despite the non-convexity of the power control problem. In contrast with existing distributed power control algorithms, our algorithm makes no stringent assumptions on the system utility functions. In particular, the utility function is allowed to be concave or non-concave, differentiable or non-differentiable, continuous or discontinuous, and monotonic or non-monotonic. / Qian, Liping. / Adviser: Yingjun (Angela) Zhang. / Source: Dissertation Abstracts International, Volume: 72-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 133-139). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

In this thesis we study how to solve some nonconvex optimization problems by using methods that capitalize on the success of Linear Programming (LP) based solvers for Mixed Integer Linear Programming (MILP). A common aspect of our solution approaches is the use, development and analysis of small but strong extended LP/MILP formulations and approximations. In the first part of this work we develop an LP based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a lifted polyhedral relaxation of conic quadratic constraints by Ben-Tal and Nemirovski. We test the algorithm on a series of portfolio optimization problems and show that it provides a significant computational advantage. In the second part we study the modeling of a class of disjunctive constraints with a logarithmic number of variables. For specially structured disjunctive constraints we give sufficient conditions for constructing MILP formulations with a number of binary variables and extra constraints that is logarithmic in the number of terms of the disjunction. Using these conditions we introduce formulations with these characteristics for SOS1, SOS2 constraints and piecewise linear functions. We present computational results showing that they can significantly outperform other MILP formulations. In the third part we study the modeling of non-convex piecewise linear functions as MILPs. We review several new and existing MILP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise linear functions. Finally, in the fourth part we study the strength of MILP formulations for LPs with Probabilistic Constraints. We first study the strength of existing MILP formulations that only considers one row of the probabilistic constraint at a time. We then introduce an extended formulation that considers more than one row of the constraint at a time and use it to computationally compare the relative strength between formulations that consider one and two rows at a time.

Image recovery, especially image denoising and deblurring is widely studied during the last decades. Variational models can well preserve edges of images while restoring images from noise and blur. Some variational models are non-convex. For the moment, the methods for non-convex optimization are limited. This thesis finds new non-convex optimizing method called difference of convex algorithm (DCA) for solving different variational models for various kinds of noise removal problems. For imaging system, noise appeared in images can show different kinds of distribution due to the different imaging environment and imaging technique. Here we show how to apply DCA to Rician noise removal and Cauchy noise removal. The performance of our experiments demonstrates that our proposed non-convex algorithms outperform the existed ones by better PSNR and less computation time. The progress made by our new method can improve the precision of diagnostic technique by reducing Rician noise more efficiently and can improve the synthetic aperture radar imaging precision by reducing Cauchy noise within. When applying variational models to image denoising and deblurring, a significant subject is to choose the regularization parameters. Few methods have been proposed for regularization parameter selection for the moment. The numerical algorithms of existed methods for parameter selection are either complicated or implicit. In order to find a more efficient and easier way to estimate regularization parameters, we create a new image quality sharpness metric called SQ-Index which is based on the theory of Global Phase Coherence. The new metric can be used for estimating parameters for a various of variational models, but also can estimate the noise intensity based on special models. In our experiments, we show the noise estimation performance with this new metric. Moreover, extensive experiments are made for dealing with image denoising and deblurring under different kinds of noise and blur. The numerical results show the robust performance of image restoration by applying our metric to parameter selection for different variational models.