Second Order Optimality Conditions in Nonsmooth Unconstrained Optimization

AMS subject classification: 49J52, 90C30.

Convex Optimization Algorithms and Statistical Bounds for Learning Structured Models

Thesis (Ph.D.)--University of Washington, 2016-08

Sensitivity Analysis in Convex Optimization through the Circatangent Derivative

The main goal of this paper is to analyse the sensitivity of a vector convex optimization problem according to variations in the right-hand side. We measure the quantitative behavior of a certain set of Pareto optimal points characterized to become minimum when the objective function is composed with a positive function. Its behavior is analysed quantitatively using the circatangent derivative for set-valued maps. Particularly, it is shown that the sensitivity is closely related to a Lagrange multiplier solution of a dual program.

Implementation of novel methods of global and nonsmooth optimization : GANSO programming library

We discuss the implementation of a number of modern methods of global and nonsmooth continuous optimization, based on the ideas of Rubinov, in a programming library GANSO. GANSO implements the derivative-free bundle method, the extended cutting angle method, dynamical system-based optimization and their various combinations and heuristics. We outline the main ideas behind each method, and report on the interfacing with Matlab and Maple packages.

Non-smooth optimization methods for computation of the conditional value-at-risk and portfolio optimization

We examine numerical performance of various methods of calculation of the Conditional Value-at-risk (CVaR), and portfolio optimization with respect to this risk measure. We concentrate on the method proposed by Rockafellar and Uryasev in (Rockafellar, R.T. and Uryasev, S., 2000, Optimization of conditional value-at-risk. Journal of Risk, 2, 21-41), which converts this problem to that of convex optimization. We compare the use of linear programming techniques against a non-smooth optimization method of the discrete gradient, and establish the supremacy of the latter. We show that non-smooth optimization can be used efficiently for large portfolio optimization, and also examine parallel execution of this method on computer clusters.

Lower-semicontinuity and optimization of convex functionals

The result that we treat in this article allows to the utilization of classic tools of convex analysis in the study of optimality conditions in the optimal control convex process for a Volterra-Stietjes linear integral equation in the Banach space G([a, b],X) of the regulated functions in [a, b], that is, the functions f : [a, 6] → X that have only descontinuity of first kind, in Dushnik (or interior) sense, and with an equality linear restriction. In this work we introduce a convex functional Lβf(x) of Nemytskii type, and we present conditions for its lower-semicontinuity. As consequence, Weierstrass Theorem garantees (under compacity conditions) the existence of solution to the problem min{Lβf(x)}. © 2009 Academic Publications.

Primal Attainment in Convex Infinite Optimization Duality

This article provides results guarateeing that the optimal value of a given convex infinite optimization problem and its corresponding surrogate Lagrangian dual coincide and the primal optimal value is attainable. The conditions ensuring converse strong Lagrangian (in short, minsup) duality involve the weakly-inf-(locally) compactness of suitable functions and the linearity or relative closedness of some sets depending on the data. Applications are given to different areas of convex optimization, including an extension of the Clark-Duffin Theorem for ordinary convex programs.

New glimpses on convex infinite optimization duality

Given a convex optimization problem (P) in a locally convex topological vector space X with an arbitrary number of constraints, we consider three possible dual problems of (P), namely, the usual Lagrangian dual (D), the perturbational dual (Q), and the surrogate dual (Δ), the last one recently introduced in a previous paper of the authors (Goberna et al., J Convex Anal 21(4), 2014). As shown by simple examples, these dual problems may be all different. This paper provides conditions ensuring that inf(P)=max(D), inf(P)=max(Q), and inf(P)=max(Δ) (dual equality and existence of dual optimal solutions) in terms of the so-called closedness regarding to a set. Sufficient conditions guaranteeing min(P)=sup(Q) (dual equality and existence of primal optimal solutions) are also provided, for the nominal problems and also for their perturbational relatives. The particular cases of convex semi-infinite optimization problems (in which either the number of constraints or the dimension of X, but not both, is finite) and linear infinite optimization problems are analyzed. Finally, some applications to the feasibility of convex inequality systems are described.

Constraint qualifications in convex vector semi-infinite optimization

Convex vector (or multi-objective) semi-infinite optimization deals with the simultaneous minimization of finitely many convex scalar functions subject to infinitely many convex constraints. This paper provides characterizations of the weakly efficient, efficient and properly efficient points in terms of cones involving the data and Karush–Kuhn–Tucker conditions. The latter characterizations rely on different local and global constraint qualifications. The results in this paper generalize those obtained by the same authors on linear vector semi-infinite optimization problems.

Dynamic, convex, and robust optimization with Bayesian learning for response-guided dosing

Thesis (Ph.D.)--University of Washington, 2016-08

Relay Precoder Optimization in MIMO-Relay Networks With Imperfect CSI

In this paper, we consider robust joint designs of relay precoder and destination receive filters in a nonregenerative multiple-input multiple-output (MIMO) relay network. The network consists of multiple source-destination node pairs assisted by a MIMO-relay node. The channel state information (CSI) available at the relay node is assumed to be imperfect. We consider robust designs for two models of CSI error. The first model is a stochastic error (SE) model, where the probability distribution of the CSI error is Gaussian. This model is applicable when the imperfect CSI is mainly due to errors in channel estimation. For this model, we propose robust minimum sum mean square error (SMSE), MSE-balancing, and relay transmit power minimizing precoder designs. The next model for the CSI error is a norm-bounded error (NBE) model, where the CSI error can be specified by an uncertainty set. This model is applicable when the CSI error is dominated by quantization errors. In this case, we adopt a worst-case design approach. For this model, we propose a robust precoder design that minimizes total relay transmit power under constraints on MSEs at the destination nodes. We show that the proposed robust design problems can be reformulated as convex optimization problems that can be solved efficiently using interior-point methods. We demonstrate the robust performance of the proposed design through simulations.

A geometric analysis of convex demixing

Demixing is the task of identifying multiple signals given only their sum and prior information about their structures. Examples of demixing problems include (i) separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis; (ii) decomposing an observed matrix into low-rank and sparse components; and (iii) identifying a binary codeword with impulsive corruptions. This thesis describes and analyzes a convex optimization framework for solving an array of demixing problems.

Our framework includes a random orientation model for the constituent signals that ensures the structures are incoherent. This work introduces a summary parameter, the statistical dimension, that reflects the intrinsic complexity of a signal. The main result indicates that the difficulty of demixing under this random model depends only on the total complexity of the constituent signals involved: demixing succeeds with high probability when the sum of the complexities is less than the ambient dimension; otherwise, it fails with high probability.

The fact that a phase transition between success and failure occurs in demixing is a consequence of a new inequality in conic integral geometry. Roughly speaking, this inequality asserts that a convex cone behaves like a subspace whose dimension is equal to the statistical dimension of the cone. When combined with a geometric optimality condition for demixing, this inequality provides precise quantitative information about the phase transition, including the location and width of the transition region.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.

A Numerically efficient power optimization scheme for coded OFDM systems in achieving minimum frame error rate

Coded OFDM is a transmission technique that is used in many practical communication systems. In a coded OFDM system, source data are coded, interleaved and multiplexed for transmission over many frequency sub-channels. In a conventional coded OFDM system, the transmission power of each subcarrier is the same regardless of the channel condition. However, some subcarrier can suffer deep fading with multi-paths and the power allocated to the faded subcarrier is likely to be wasted. In this paper, we compute the FER and BER bounds of a coded OFDM system given as convex functions for a given channel coder, inter-leaver and channel response. The power optimization is shown to be a convex optimization problem that can be solved numerically with great efficiency. With the proposed power optimization scheme, near-optimum power allocation for a given coded OFDM system and channel response to minimize FER or BER under a constant transmission power constraint is obtained