Optimization and Control (math.OC)

  • PDF
    Classifiers and rating scores are prone to implicitly codifying biases, which may be present in the training data, against protected classes (i.e., age, gender, or race). So it is important to understand how to design classifiers and scores that prevent discrimination in predictions. This paper develops computationally tractable algorithms for designing accurate but fair support vector machines (SVM's). Our approach imposes a constraint on the covariance matrices conditioned on each protected class, which leads to a nonconvex quadratic constraint in the SVM formulation. We develop iterative algorithms to compute fair linear and kernel SVM's, which solve a sequence of relaxations constructed using a spectral decomposition of the nonconvex constraint. Its effectiveness in achieving high prediction accuracy while ensuring fairness is shown through numerical experiments on several data sets.
  • PDF
    Electric vehicle (EV) charging can negatively impact electric distribution networks by exceeding equipment thermal ratings and causing voltages to drop below standard ranges. In this paper, we develop a decentralized EV charging control scheme to achieve "valley-filling" (i.e., flattening demand profile during overnight charging), meanwhile meeting heterogeneous individual charging requirements and satisfying distribution network constraints. The formulated problem is an optimization problem with a non-separable objective function and strongly coupled inequality constraints. We propose a novel shrunken primal-dual subgradient (SPDS) algorithm to support the decentralized control scheme, derive conditions guaranteeing its convergence, and verify its efficacy and convergence with a representative distribution network model.
  • PDF
    Multi-agent systems are being increasingly deployed in challenging environments for performing complex tasks such as multi-target tracking, search-and-rescue, and intrusion detection. Notwithstanding the computational limitations of individual robots, such systems rely on collaboration to sense and react to the environment. This paper formulates the generic target tracking problem as a time-varying optimization problem and puts forth an inexact online gradient descent method for solving it sequentially. The performance of the proposed algorithm is studied by characterizing its dynamic regret, a notion common to the online learning literature. Building upon the existing results, we provide improved regret rates that not only allow non-strongly convex costs but also explicating the role of the cumulative gradient error. Two distinct classes of problems are considered: one in which the objective function adheres to a quadratic growth condition, and another where the objective function is convex but the variable belongs to a compact domain. For both cases, results are developed while allowing the error to be either adversarial or arising from a white noise process. Further, the generality of the proposed framework is demonstrated by developing online variants of existing stochastic gradient algorithms and interpreting them as special cases of the proposed inexact gradient method. The efficacy of the proposed inexact gradient framework is established on a multi-agent multi-target tracking problem, while its flexibility is exemplified by generating online movie recommendations for Movielens $10$M dataset.
  • PDF
    The \emphoptimal value function is one of the basic objects in the field of mathematical optimization, as it allows the evaluation of the variations in the \emphcost/revenue generated while \emphminimizing/maximizing a given function under some constraints. In the context of stability/sensitivity analysis, a large number of publications have been dedicated to the study of continuity and differentiability properties of the optimal value function. The differentiability aspect of works in the current literature has mostly been limited to first order analysis, with focus on estimates of its directional derivatives and subdifferentials, given that the function is typically nonsmooth. With the progress made in the last two to three decades in major subfields of optimization such as robust, minmax, semi-infinite and bilevel optimization, and their connection to the optimal value function, there is a crucial need for a \emphsecond order analysis of the generalized differentiability properties of this function. This type of analysis will promote the development of robust solution methods, such as the Newton method, which is very popular in nonlinear optimization. The main goal of this paper is to provide results in this direction. In fact, we derive estimates of the \emphgeneralized Hessian (also known as the second order subdifferential) for the optimal value function. Our results are based on two handy tools from parametric optimization, namely the optimal solution and Lagrange multiplier mappings, for which completely detailed estimates of their generalized derivatives are either well-known or can easily be obtained.
  • PDF
    Mixed-Integer Second-Order Cone Programs (MISOCPs) form a nice class of mixed-inter convex programs, which can be solved very efficiently due to the recent advances in optimization solvers. Our paper bridges the gap between modeling a class of optimization problems and using MISOCP solvers. It is shown how various performance metrics of M/G/1 queues can be molded by different MISOCPs. To motivate our method practically, it is first applied to a challenging stochastic location problem with congestion, which is broadly used to design socially optimal service networks. Four different MISOCPs are developed and compared on sets of benchmark test problems. The new formulations efficiently solve large-size test problems, which cannot be solved by the best existing method. Then, the general applicability of our method is shown for similar optimization problems that use queue-theoretic performance measures to address customer satisfaction and service quality.
  • PDF
    In this paper, we generalize (accelerated) Newton's method with cubic regularization under inexact second-order information for (strongly) convex optimization problems. Under mild assumptions, we provide global rate of convergence of these methods and show the explicit dependence of the rate of convergence on the problem parameters. While the complexity bounds of our presented algorithms are theoretically worse than those of their exact counterparts, they are at least as good as those of the optimal first-order methods. Our numerical experiments also show that using inexact Hessians can significantly speed up the algorithms in practice.
  • PDF
    We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a nonnegative smooth function and a bunch of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises naturally in various applications when different regularizers are introduced for inducing simultaneous structures in the solutions. Solving these problems, however, can be challenging because of the coupled nonsmooth functions: the corresponding proximal mapping can be hard to compute so that standard first-order methods such as the proximal gradient algorithm cannot be applied efficiently. In this paper, we propose a successive difference-of-convex approximation method for solving this kind of problems. In this algorithm, we approximate the nonsmooth functions by their Moreau envelopes in each iteration. Making use of the simple observation that Moreau envelopes of nonnegative proper closed functions are continuous difference-of-convex functions, we can then approximately minimize the approximation function by first-order methods with suitable majorization techniques. These first-order methods can be implemented efficiently thanks to the fact that the proximal mapping of each nonsmooth function is easy to compute. Under suitable assumptions, we prove that the sequence generated by our method is bounded and clusters at a stationary point of the objective. We also discuss how our method can be applied to concrete applications such as nonconvex fused regularized optimization problems and simultaneously structured matrix optimization problems, and illustrate the performance numerically for these two specific applications.
  • PDF
    Frank-Wolfe methods (FW) have gained significant interest in the machine learning community due to its ability to efficiently solve large problems that admit a sparse structure (e.g. sparse vectors and low-rank matrices). However the performance of the existing FW method hinges on the quality of the linear approximation. This typically restricts FW to smooth functions for which the approximation quality, indicated by a global curvature measure, is reasonably good. In this paper, we propose a modified FW algorithm amenable to nonsmooth functions by optimizing for approximation quality over all affine approximations given a neighborhood of interest. We analyze theoretical properties of the proposed algorithm and demonstrate that it overcomes many issues associated with existing methods in the context of nonsmooth low-rank matrix estimation.
  • PDF
    We consider a repeated newsvendor problem where the inventory manager has no prior information about the demand, and can access only censored/sales data. In analogy to multi-armed bandit problems, the manager needs to simultaneously "explore" and "exploit" with her inventory decisions, in order to minimize the cumulative cost. We make no probabilistic assumptions---importantly, independence or time stationarity---regarding the mechanism that creates the demand sequence. Our goal is to shed light on the hardness of the problem, and to develop policies that perform well with respect to the regret criterion, that is, the difference between the cumulative cost of a policy and that of the best fixed action/static inventory decision in hindsight, uniformly over all feasible demand sequences. We show that a simple randomized policy, termed the Exponentially Weighted Forecaster, combined with a carefully designed cost estimator, achieves optimal scaling of the expected regret (up to logarithmic factors) with respect to all three key primitives: the number of time periods, the number of inventory decisions available, and the demand support. Through this result, we derive an important insight: the benefit from "information stalking" as well as the cost of censoring are both negligible in this dynamic learning problem, at least with respect to the regret criterion. Furthermore, we modify the proposed policy in order to perform well in terms of the tracking regret, that is, using as benchmark the best sequence of inventory decisions that switches a limited number of times. Numerical experiments suggest that the proposed approach outperforms existing ones (that are tailored to, or facilitated by, time stationarity) on nonstationary demand models. Finally, we extend the proposed approach and its analysis to a "combinatorial" version of the repeated newsvendor problem.
  • PDF
    In this note, we deal with a problem of the type $$\cases -h\left ( \int_\Omega|∇u(x)|^2dx\right ) ∆u=f(u) & in $\Omega$\cr & \cr u_|∂\Omega=0\ .\cr$$ As an application of a new general multiplicity result, we establish the existence of at least three solutions, two of which are global minima of the related energy functional. The only condition assumed on $f$ is that it be subcritical and superlinear: no condition on the behaviour of $f$ at $0$ is requested.
  • PDF
    We investigate lattice energies for radially symmetric, spatially extended particles interacting via a radial potential and arranged on the sites of a two-dimensional Bravais lattice. We show the global minimality of the triangular lattice among Bravais lattices of fixed density in two cases: In the first case, the distribution of mass is sufficiently concentrated around the lattice points, and the mass concentration depends on the density we have fixed. In the second case, both interacting potential and density of the distribution of mass are described by completely monotone functions in which case the optimality holds at any fixed density.
  • PDF
    The Hybrid Minimum Principle (HMP) is established for the optimal control of deterministic hybrid systems where autonomous and controlled state jumps are allowed at the switching instants and, in addition to running costs, switching between discrete states incurs costs. A feature of special interest in this work is the possibility of state space dimension change, i.e. the hybrid state space is considered as the direct product of a set of discrete state components with finite cardinality and a set of Euclidean spaces whose dimensions depend upon the discrete state components. First order variational analysis is performed on the hybrid optimal control problem via the needle variation methodology and the necessary optimality conditions are established in the form of the HMP. A key aspect of the analysis is the relationship between the Hamiltonian and the adjoint process before and after the switching instants.
  • PDF
    Motivated by applications arising from large scale optimization and machine learning, we consider stochastic quasi-Newton (SQN) methods for solving unconstrained convex optimization problems. The convergence analysis of the SQN methods, both full and limited-memory variants, require the objective function to be strongly convex. However, this assumption is fairly restrictive and does not hold for applications such as minimizing the logistic regression loss function. To our knowledge, in the literature, no rate statements exist in the absence of this assumption for SQN methods. Also, there is no such rate for stochastic gradient methods addressing non-strongly convex problems with unbounded gradients. Motivated by these gaps, we consider optimization problems with non-strongly convex objectives with Lipschitz but possibly unbounded gradients. The main contributions of the paper are as follows: (i) Addressing large scale stochastic optimization problems, we develop a regularized stochastic limited-memory BFGS algorithm, where the stepsize, regularization parameter, and the Hessian inverse approximate matrix are updated iteratively. We establish the convergence to an optimal solution of the original problem both in an almost-sure and mean senses. We derive the convergence rate in terms of the objective function's values and show that it is of the order $\mathcal{O}\left(k^{-\left(\frac{1}{3}-\epsilon\right)}\right)$, where $\epsilon$ is an arbitrary small positive scalar; (ii) In deterministic regime, we show that the regularized limited-memory BFGS algorithm displays a rate of the order $\mathcal{O}\left(\frac{1}{k^{1 \epsilon'}}\right)$, where $\epsilon'$ is an arbitrary small positive scalar. We present our numerical experiments performed on a large scale text classification problem.
  • PDF
    Investigating the seasonality of disease incidences is very important in disease surveillance in regions with periodical climatic patterns. In lieu of the paradigm about disease incidences varying seasonally in line with meteorology, this work seeks to determine how well standard epidemic models can capture such seasonality for better forecasts and optimal futuristic interventions. Once incidence data are assimilated by a periodic model, asymptotic analysis in relation to the long-term behavior of the disease occurrences can be performed using the classical Floquet theory, which explains the stability of the existing periodic solutions. For a test case, we employed an IR model to assimilate weekly dengue incidence data from the city of Jakarta, Indonesia, which we present in their raw and moving-average-filtered versions. To estimate a periodic parameter toward performing the asymptotic analysis, eight optimization schemes were assigned returning magnitudes of the parameter that vary insignificantly across schemes. Furthermore, the computation results combined with the analytical results indicate that if the disease surveillance in the city does not improve, then the incidence will raise to a certain positive orbit and remain cyclical.
  • PDF
    This paper proposes an efficient approach for tuning L1-feedback filter of the adaptive controller for multi-input-multi-output (MIMO) systems. The feedback filter provides performance that trades off fast closed-loop dynamics, robustness margin, and control signal range. Thus appropriate tuning of the filter's parameters is crucial to achieving optimal performance. For MIMO systems, the parameters tuning is challenging and requires multi-objective performance indices to avoid instability. This paper proposes a fuzzy-based L1feedback filter design tuned with multiobjective particle swarm optimization (MOPSO) to remove these bottlenecks. MOPSO guarantees the appropriate selection of the fuzzy membership functions. The proposed approach is validated using twin rotor MIMO system and simulation results demonstrate the efficacy of here proposed while preserving the system stabilizability.
  • PDF
    Nonconvex optimization problems arise in different research fields and arouse lots of attention in signal processing, statistics and machine learning. In this work, we explore the accelerated proximal gradient method and some of its variants which have been shown to converge under nonconvex context recently. We show that a novel variant proposed here, which exploits adaptive momentum and block coordinate update with specific update rules, further improves the performance of a broad class of nonconvex problems. In applications to sparse linear regression with regularizations like Lasso, grouped Lasso, capped $\ell_1$ and SCAP, the proposed scheme enjoys provable local linear convergence, with experimental justification.
  • PDF
    Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations, the Searcher needs to find all the hidden objects by visiting these locations one by one. To study this problem, we formulate new game-theoretic models of discrete search between a Hider and a Searcher. The Hider hides $k$ balls in $n$ boxes, and the Searcher opens the boxes one by one with the aim of finding all the balls. Every time the Searcher opens a box she must pay its search cost, and she either finds one of the balls it contains or learns that it is empty. If the Hider is an adversary, an appropriate payoff function may be the expected total search cost paid to find all the balls, while if the Hider is Nature, a more appropriate payoff function may be the difference between the total amount paid and the amount the Searcher would have to pay if she knew the locations of the balls a priori (the regret). We give a full solution to the regret version of this game, and a partial solution to the search cost version. We also consider variations on these games for which the Hider can hide at most one ball in each box. The search cost version of this game has already been solved in previous work, and we give a partial solution in the regret version.
  • PDF
    Acceleration schemes can dramatically improve existing optimization procedures. In most of the work on these schemes, such as nonlinear GMRES, acceleration is based on minimizing the $\ell_2$ norm of some target on subspaces of $\mathbb{R}^n$. There are many numerical examples that show how accelerating general purpose and domain-specific optimizers with N-GMRES results in large improvements. We propose a natural modification to N-GMRES, which significantly improves the performance in a testing environment originally used to advocate N-GMRES. Our proposed approach, which we refer to as O-ACCEL, is novel in that it minimizes an approximation to the \emphobjective function on subspaces of $\mathbb{R}^n$. A convergence theorem is proved for our proposed approach. Comparisons with L-BFGS and N-CG indicate the competitiveness of O-ACCEL. As it can be combined with domain-specific optimizers, it may also be beneficial in areas where L-BFGS or N-CG are not suitable.
  • PDF
    Power system blackouts are usually triggered by the initial contingency and then deteriorate as the branch outage spreads quickly. Thus, it is crucial to eliminate the propagation of cascading outages in its infancy. In this paper, a model predictive approach is proposed to protect power grids against cascading blackout by timely shedding load on buses. The cascading dynamics of power grids is described by a cascading outage model of transmission lines coupled with the DC power flow equation. In addition, a nonlinear convex optimization formulation is established to characterize the optimal load shedding for the mitigation of cascading failures. As a result, two protection schemes are designed on the basis of the optimization formulation. One scheme carries out the remedial action once for all, while the other focuses on the consecutive protection measures. Saddle point dynamics is employed to provide a numerical solution to the proposed optimization problem, and its global convergence is guaranteed in theory. Finally, numerical simulations on IEEE 57 Bus Systems have been implemented to validate the proposed approach in terms of preventing the degradation of power grids.
  • PDF
    Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all model parameters (optimization variables) can be very costly. A promising solution is to use parameter servers to store different subsets of the model parameters, and update them asynchronously at different machines using local datasets. In this paper, we focus on distributed optimization of large linear models with convex loss functions, and propose a family of randomized primal-dual block coordinate algorithms that are especially suitable for asynchronous distributed implementation with parameter servers. In particular, we work with the saddle-point formulation of such problems which allows simultaneous data and model partitioning, and exploit its structure by doubly stochastic coordinate optimization with variance reduction (DSCOVR). Compared with other first-order distributed algorithms, we show that DSCOVR may require less amount of overall computation and communication, and less or no synchronization. We discuss the implementation details of the DSCOVR algorithms, and present numerical experiments on an industrial distributed computing system.

Recent comments

Bin Shi Oct 05 2017 00:07 UTC

Welcome to give the comments for this paper!