Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

2
votes
1answer
73 views

Is this operator monotone?

Consider a convex optimization problem. $$\min_{u\in\Re^k} f(u)$$ s.t. $g_i(u)\leq0,\ i=1,\ldots,m$ Let ...
2
votes
2answers
704 views

Lasso with linear constraints

I want to efficiently solve the following optimization problem: \begin{align} \min &\quad \left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2 + \lambda\left\|\mathbf{x}\right\|_1\\ \text{Subject to}& ...
2
votes
2answers
265 views

Gradient descent vs ternary search

Consider a strictly convex function $f: [0; 1]^n \rightarrow \mathbb{R}$. The question is why people (especially experts in machine learning) use gradient descent in order to find a global minimum of ...
2
votes
1answer
77 views

Convexity of k points

Let $C \subset \mathbb{R}^n$ be a convex set. Additionally, $x_1, x_2,\dots, x_k \in C$ and $\theta_1,\theta_2,\dots,\theta_k \in \mathbb{R}, \theta_i \ge 0, \sum\theta_i = 1$. I have to proof that ...
2
votes
1answer
156 views

$\epsilon$-normals to convex sets

I am reading the book by B. Mordukhovich, Variational analysis and generalized differentiation I. On page 6 it is stated the following inclusion: $$ \hat{N}_{\varepsilon }\left( \bar{x};\Omega ...
2
votes
1answer
217 views

Maximal mapping of a convex set to the unit disk

EDIT: To make my question more precise i think we can narrow it down to this. Say you have a simple polygon that includes the origin, that is completely contained in the unit disk, we can 'blow up' ...
2
votes
1answer
72 views

Positive Semi-Definiteness of Least Squares Estimator

I am reading Boyd's Convex Optimization Text, and I am curious to know why the following is true: $$F F^T \succeq F^* {F^*}^T,$$ where $F^* {F^*}^T = (A^T A)^{-1}$ and $FA = I.$ I already tried ...
2
votes
1answer
187 views

Non-negative solution to matrix equation

I want to solve $Ax = b$ subject to the constraint that all of the elements of $x$ are non-negative. If such a solution does not exist, I want to find non-negative $x$ such that the quadratic form ...
2
votes
1answer
194 views

study objects of convex analysis and optimization

In the area of convex analysis and the area of optimization in their general sense, are convex subsets assumed to be in vector spaces or topological vector spaces? Are convex functions defined to be ...
2
votes
1answer
38 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
2
votes
1answer
51 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...
2
votes
1answer
27 views

Does $\log(f(X))$ concave implies $\log(f(X^{-1}))$ convex?

One of my professor claims that $\log f(X)$ concave implies that $\log(f(X^{-1}))$ convex where $X$ is symmetric positive definite matrix. $\log(f(X))$ is a function defined on symmetric positive ...
2
votes
1answer
36 views

How to set up Lagrangian optimization with matrix constrains

Suppose we have a function $f: \mathbb{R} \to \mathbb{R} $ which we want to optimize subject to some constraint $g(x) \le c$ where $g:\mathbb{R} \to \mathbb{R} $ What we do is that we can set up a ...
2
votes
1answer
140 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
2
votes
1answer
43 views

Is there Lipschitz property for subdifferential?

I'm trying to bound the quantity $\langle \nabla \Psi(x),\bar{x}-x \rangle$ above, with the bound depending on $\|x-\bar{x}\|$ and perhaps also of $\|x-y\|$ for fixed (but not varying) points $y$. ...
2
votes
1answer
31 views

What is the solution for this quadratic program?

Given scalars $p_1\geq p_2\geq \cdots \geq p_r > 0$, can we find a solution for following problem? \begin{align} \text{minimize} & & & \sum_{j=1}^{r} p_j (1-t_j)^2 \\ \text{s.t.} \\ ...
2
votes
2answers
61 views

Boundedness of sublevel sets of convex function (Boyd VandenBerghe)

(This is from the book Convex Optimization on p.474 on algorithms for unconstrained minimization) Assumptions The function $f : \mathbb{R}^N \mapsto \mathbb{R}$ is convex and twice-differentiable ...
2
votes
2answers
97 views

Conditional expectation of a random vector taking values in convex sets

on a probability space $(\Omega, \mathcal{F},\mathbb{P})$ i have a random vector $X\in L^1_{\mathbb{P}}(\mathbb{R}^d)$ (integrable with values in $\mathbb{R}^n$), such that $\mathcal{P}-a.s.$ $$X\in ...
2
votes
1answer
31 views

Relation between Symmetric matrix and Convex Cone

The "Positive Semedefinite Cone" is defined as $\mathbb{S}^{n}_{+} = \{\mathbf{X}\in\mathbb{S}^{n}: \mathbf{X}\succeq\mathbf{0}\}$. To my knowledge, this representation contains 2 contents: ...
2
votes
1answer
37 views

Matrix representation of the following equation - for finding optimal weights for regularized linear regression

If I have the following equation, $$E(w)=\sum_{i=1}^n (y_n -\beta^T x_n) +\lambda \sum_{i=1}^d \beta_i^2 $$ which is the cost function of regularized linear regression ($\beta$ and $x_n$ are ...
2
votes
1answer
74 views

Proximal operator, scaling by a matrix

Proximal operator is defined for matrices as a map prox$_f:R^m\times R^n \rightarrow R^m\times R^n$: prox$_f$(X) := argmin$_{Y\in R^m\times R^n}$ $ f(Y) + \frac{1}{2}||Y-X||^2$ In case of vectors, ...
2
votes
1answer
68 views

Dual formulation of an SDP problem

Could you help me formulate the dual problem to this SDP? maximize $\frac{1}{2} Tr(GW)$, subject to $ G \ge 0$ (and G symmetric), and $ \forall i$, $ G_{ii} = G_{1i} = G_{i1} $ Note that $G$ and ...
2
votes
1answer
73 views

Difference between maximize $\sum\limits_{k=1}^Kg_k(\mathbf{x})$ and $\sum\limits_{k=1}^{K}\log(1+g_k(\mathbf{x}))$ in convex optimization

I have a problem of the following form: maximize $\;\;\;\,\sum\limits_{k=1}^Kg_k(\mathbf{x})$ subject to: $\;\,\,f_i(\mathbf{x})\leq\,1\,\forall\,i\in\{1, 2, \dotsc, m\}$ ...
2
votes
1answer
105 views

Is the following objective function jointly convex?

I have the following optimization problem: $$ \begin{aligned} & \underset{\alpha, \gamma}{\text{minimize}} & & \end{aligned} \frac{1}{2} \|y - \sum\limits_{i=1}^{S}\gamma_{i}\cdot ...
2
votes
1answer
90 views

“Support function of a set” and supremum question.

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly. As an example, my ...
2
votes
1answer
835 views

How to find closest positive definite matrix of non-symmetric matrix

I have a matrix A given and I want to find the matrix B which is closest to A in the frobenius norm and is positiv definite. B does not need to be symmetric. I found a lot of solutions if the input ...
2
votes
1answer
157 views

The convex conjugate of a quadratic form with positive semi definite matrix

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so ...
2
votes
1answer
79 views

Does the center of a convex region lie within that region?

There's probably a simple result that says this is true, but I sure can't find it. It seems obvious, though. Let $D$ be a closed, compact region in $\Re^n$. Further, let $D \subseteq [0,l]^n$ and ...
2
votes
1answer
307 views

Smooth Hinge Loss Lipschitz Constant

Given the smooth hinge loss $L_\epsilon$ as follows $L_\epsilon(y_i (w^T x_i + b)) = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{(1-y_i (w^T x_i + b))^2}{2 \delta} & 1 - \delta < y_i (w^T ...
2
votes
1answer
57 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
2
votes
1answer
62 views

Minimization of norms

How do I minimize the following? $ min_{z>0} - zt + 1/2\ z\ ||\ Y + X_k\ /\ z\ ||_2^2 $ Also, $X_k^TX_k = 1 \ \ \forall k $ I am given that the answer should be : $ \sqrt{Y^T - 2t} + Y^TX$ ...
2
votes
1answer
342 views

Karush-Kuhn-Tucker (KKT) conditions

I am having difficulties understanding the graphical interpretation as well as why the two following KKT conditions is necessary for a point x* being a minimum. It is my understanding that the (d) ...
2
votes
1answer
79 views

Convex analysis problem

I have the following problem. Let $f:[a,b]\to \mathbb{R}$ be continuously convex. I have to prove that there exists $c\in (a,b)$ such that $$\frac{f(a)-f(b)}{b-a}\in \partial f(c)$$ Firstly, I'm ...
2
votes
2answers
201 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
2
votes
1answer
43 views

supremum of an array of a convex functions

If $\{J_n\}$ is an array of a convex functions on a convex set $U$ and $G(u)=\sup J_i(u), u\in U$, how to show that $G(u)$ is convex too? I've done this, but I am not sure about properties of a ...
2
votes
1answer
308 views

Maximum of quasi-convex functions

A function $f$ is quasiconvex if all its sub-level sets are convex (i.e., $\{ x: f(x) \le \alpha\}$ is convex for all $\alpha$.) For a convex function $f$, it is true that $f$ acheives its maximum ...
2
votes
3answers
246 views

A robust convex optimization problem

Consider a function $ f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} $ such that $\forall x \in \mathbb{R}^n$ the map $f(x,\cdot)$ is convex, and $\forall y\in \mathbb{R}^m$ the map ...
2
votes
1answer
325 views

Is this function quasi convex

I have a function $f(x,y) = y(k_1x^2 + k_2x + k_3)$ which describes chemical potential of a species ($y$ is mole fraction and $x$ is temperature) I only want to check quasi convexity over a limited ...
2
votes
2answers
155 views

optimality of quadratic programming problems

Suppose we have a general quadratic programming problem: \begin{align} \min_{x}\,\,&c^Tx+\frac{1}{2}x^TQx,\\ \mbox{s.t.}\,\,& Ax=b,\\ &x\geq0, \end{align} where $Q$ is positive ...
2
votes
1answer
68 views

Convex relaxation for the complement of Lorentz cone

Is it possible to obtain a convex relaxation for $$ \{ (x,t): t \le \|x\|_2\} \in \mathbb{R}^{d+1} $$ where $x \in \mathbb{R}^d$ and $\|x\|_2$ is the usual Euclidean norm, by moving to higher ...
2
votes
2answers
237 views

maximize log determinant subject to a linear constraint

Does anyone know any efficient method to solve the following problem? $ (\alpha,\beta) = \text{argmax} \log \det (\alpha K_1 + \beta K_2)$ s.t. $c_1 \alpha + c_2 \beta = c_3, \alpha\geq0, \beta\geq ...
2
votes
1answer
62 views

Possibility of Unboundedness in Least Squares Minimization

Suppose we have the quadratic minimization problem \begin{equation} \min_x \frac{1}{2} x^TPx + q^Tx +r \end{equation} We know that when $P$ is symmetric positive semi-definite, but the optimality ...
2
votes
1answer
101 views

Initial solution to a Convex Optimization problem

I am aware that in a convex optimization problem, the initial solution does not matter as the algorithm guarantees convergence to the global minimum/maximum. But what if the initial solution does not ...
2
votes
1answer
172 views

Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)

Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian. ...
2
votes
1answer
907 views

Maximum likelihood covariance estimation of Gaussian

I was reading these notes on matrix calculus http://research.microsoft.com/en-us/um/people/minka/papers/matrix/minka-matrix.pdf and I could not figure out how to go from equation (30) to (31). Any ...
2
votes
1answer
245 views

Convex Optimization: $\min \left(\sum f(x_i)\right)$ s.t.: $\sum g(x_i) \le C$, where x has no closed-form expression

I am a newbie here and now facing to a hard convex optimization problem, sincerely wish anyone can help me : ) There is a variable vector $\textbf{x}$, and we wish to minimize the sum of $f()$: ...
2
votes
1answer
488 views

How can I simplify this quadratic optimization?

I want to minimize $x^t P x + q^t x$ subject to the following constraint: For all $b \in B$, $|x^b| \le C \sum_{b' \in B} |x^{b'}|$ where $B = {1, ..., n}$ and $x^b$ is the $b$th component ...
2
votes
1answer
137 views

Local min and differentiability of a function

Suppose there is a function $f: X \rightarrow \mathbb{R}$, where $X \subseteq \mathbb{R}^n$. If $x^*$ is a local minimizer of $f$ over $X$, must $x^*$ be either of the two cases: if $f$ is ...
2
votes
2answers
982 views

Using KKT conditions to maximize function

The goal is to maximize the following function: \begin{align} K_p(q) = q\log \frac{q}{p} + (1-q)\log \frac{1-q}{1-p} \end{align} where \begin{align} 0 \leq q \leq 1 \end{align} and $p \in (0,0.5)$ and ...
2
votes
0answers
52 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...