This paper presents a bounded confidence gossip algorithm for describing the process of opinion formation over a communication network. Each agent in the network keeps a time-varying opinion vector (or state) which represents its opinion about a set of matters. A common confidence threshold is set for all of the agents. The states of agents in the network will be updated time by time according to an iterative procedure: At each time, (i) one agent is chosen randomly, then it chooses one of its neighbors on the communication graph to contact with; (ii) they exchange their states; and (iii) if they have different states and the distance between t eir states is strictly smaller than the confidence threshold, they update their states as the average of the two. This algorithm converges almost surely to some equilibrium point such that any two adjacent agents either have the same state or have distinct states whose distance is no less than the confidence threshold. This is called the constant confidence threshold algorithm. An increasing confidence threshold algorithm, which repeats the constant confidence threshold algorithm several times with increasing confidence threshold, is also proposed. The algorithm is also convergent almost surely to some equilibrium point. Applicability of the method to clustering problems is shown through numerical examples.

Sequential randomized algorithms are considered for robust convex optimization which minimizes a linear objective function subject to a parameter dependent convex constraint. Employing convex optimization and random sampling of parameter, these algorithms enable us to obtain a suboptimal solution within reasonable computational time. The suboptimal solution is feasible in a probabilistic sense and the suboptimal value belongs to an interval which contains the optimal value. The maximum of the interval is the optimal value of the robust convex optimization plus a specified tolerance. On the other hand, its minimum is the optimal value of the chance constrained optimization which is a probabilistic relaxation of the robust convex optimization, with high probability.

Opinion formation is investigated over signed gossip networks, where asymptotic and transient opinion behaviors are analyzed in detail. The network is modeled by a connected signed graph, where each edge of the graph has positive or negative weight, i.e., these edges represent friendly or hostile relationship. Interactions each of which occurs between two persons chosen randomly follow an asynchronous procedure. Then it is shown that their opinions always converge in mean square and converge almost surely. A convergence time is defined as the smallest time such that it takes for the values of nodes to get within a given neighborhood of the consensus value with high probability, regardless of initial state. An upper bound and a lower bound of the convergence time of the gossip algorithm are given in terms of a structure of the given network.