Proximal methods are an important class of algorithms for solving nonsmooth, constrained, large-scale or distributed optimization problems. Because of their flexibility and scalability, they are widely used in current applications in engineering, machine learning, and data science. The key idea of proximal algorithms is the decomposition of a large-scale optimization problem into several smaller, simpler problems, in which the basic operation is the evaluation of the proximal operator of a function. The proximal operator minimizes the function regularized by a squared Euclidean distance, and it generalizes the Euclidean projection onto a closed convex set. Since the cost of the evaluation of proximal operators often dominates the per-iteration complexity in a proximal algorithm, efficient evaluation of proximal operators is critical. To this end, generalized Bregman proximal operators based on non-Euclidean distances have been proposed and incorporated in many algorithms and applications. In the first part of this dissertation, we present primal–dual proximal splitting methods for convex optimization, in which generalized Bregman distances are used to define the primal and dual update steps. The proposed algorithms can be viewed as Bregman extensions of many well- known proximal methods. For these algorithms, we analyze the theoretical convergence and develop techniques to improve practical implementation.In the second part of the dissertation, we apply the Bregman proximal splitting algorithms to the centering problem in large-scale semidefinite programming with sparse coefficient matrices. The logarithmic barrier function for the cone of positive semidefinite completable sparse matrices is used as the distance-generating kernel. For this distance, the complexity of evaluating the Bregman proximal operator is shown to be roughly proportional to the cost of a sparse Cholesky factorization. This is much cheaper than the standard proximal operator with Euclidean distances, which requires an eigenvalue decomposition. Therefore, the proposed Bregman proximal algorithms can handle sparse matrix constraints with sizes that are orders of magnitude larger than the problems solved by standard interior-point methods and proximal methods.

In recent years, semidefinite programming has been an important topic in the area of convex optimization, and several methods for exploiting the sparse structure in semidefinite programming problems have been developed. Some methods have been proposed to transform the standard semidefinite program into a conic optimization problem with respect to the cone of positive semidefinite completable matrices, and to take advantage of the sparsity pattern of the completable matrices. However, the problem arises of how to recover an optimal solution for the original semidefinite program, \ie, how to find a positive semidefinite completion for the positive semidefinite completable solution. In particular, a low-rank completion is of great interest in many applications. In general, it is difficult to determine the minimum rank among all positive semidefinite completions. However, if the sparsity pattern is chordal, efficient algorithms are known for constructing a positive semidefinite matrix completion with minimum rank.

In the thesis, we investigate this completion approach as an inexpensive post-processing technique for semidefinite relaxations of nonconvex quadratic problems. We test the method on semidefinite relaxations of the optimal power flow problem. By numerical experiments, we show that the completion results substantially reduce the rank of the solution for the semidefinite relaxation.

The dissertation consists of three experimental studies on economics, including in-group bias, deception heuristics, and belief elicitation.

Chapter 1 studies the root of in-group bias. Literature has found that social identities and minimal group paradigm can generate in-group bias, but seldom studies what non- label activities could generate group affiliation. I study the effect of common experience on group affiliation through a lab experiment. The results show that common fortune experience works, while common misfortune does not. These results violate results from previous studies, and suggest that some other perspectives work beyond pure in-group favoritism, for example, the sense of deservingness.

Chapter 2 studies the response time in lying detection. The inclusion of response time indicators has become a common feature in the contemporary landscape of social media sites. What private information does the response time carry when there is a conflict of interest, and do people use it to improve their welfare? We portray a model and design a modified cheap talk game to study the intricate interplay between response time, private information, and its influence on users’ well-being, tailored to situations where truth discovery is time consuming. Our investigation uncovers a noteworthy sender hope to not have to lie to get what she wants. Given this preference, the private information reveals the consideration process, instead of the mechanical discovery process. We find that when there is an apparent conflict of interest, the longer the response time, the less credible the message. However, receivers are unable to extract substantial welfare gains viithrough the response time. Furthermore, when senders are aware of the availability of their response time, they are able to manipulate it.

Chapter 3 studies the belief elicitation method. Beliefs or perceptions play a central role in studying economic behavior, yet eliciting them accurately presents challenges. We introduce a novel elicitation method, called the Dynamic Binary Method (DBM), designed to address the common challenge individuals face in pinpointing the best point estimate of their beliefs, particularly when their beliefs are imprecise. Unlike Classical Methods (CM), which require respondents to make absolute judgments and form a point estimate of their true beliefs, DBM guides them through a series of binary relative judg- ments, enabling them to express interval beliefs by exiting the process at any step. To as- sess the empirical validity of DBM, we conduct both within-subject and between-subject experiments using a diverse range of perception tasks drawn from previous literature and CM as a benchmark of performances in each task. We find that DBM does not perform significantly differently from CM at the aggregate level, regardless of whether the per- ception questions use artificial/laboratory settings or real-life settings, and irrespective of the measurement used. Notably, DBM outperforms CM when the objective truth is extreme. Furthermore, we find a negative correlation between the length of stated beliefs in tasks using DBM and their accuracy. Additionally, we find that the length stated in DBM can predict respondents’ performance in CM tasks at the aggregate level, albeit not strictly in a monotonic manner. Finally, we explore methods to use DBM-collected data for predicting stated point beliefs in DBM, offering insights into potential applications of the method beyond its immediate implementation.