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

learn more… | top users | synonyms

2
votes
1answer
116 views

Is there a nice representation for KKT conditions for matrix constraints?

I have a convex programming problem: $\min \left\lVert J - R \right\rVert _F$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
2
votes
1answer
112 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
2
votes
1answer
92 views

How to minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$ subject to constraints?

My textbook came up with a solution without explanation. I'm looking for a systematic way of solving the following optimization problems and similar ones (by hand), because I'm drawing a blank: ...
2
votes
1answer
267 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
2
votes
1answer
115 views

Help with a proof of a theorem about convex sets

I'm studying the following theorem: Theorem 1. Let $C$ be a convex set and let $\textbf{y}$ be a point exterior to the closure of $C$. Then there is a vector $\textbf{a}$ such that ...
2
votes
2answers
241 views

Is alpha divergence a convex divergence measure?

Alpha divergence is defined as following : $$ D_\alpha(p||q) = \frac{1}{\alpha (1-\alpha)} \left( 1- \int _x p(x)^{\alpha} q(x)^{(1-\alpha)} dx \right) $$ if the distributions are restricted to ...
2
votes
1answer
156 views

Prove or disprove that the given expression is “always” positive

I have previously asked a question and I tried to solve it by my own and it led to the question below: Prove or disprove that ...
2
votes
2answers
594 views

Linear optimization problem: Minimizing a linear function over an affine set.

The problem is as follows: Give an explicit solution of the linear optimization problem below. $$ \text{minimize}\ c^Tx \\ \text{subject to}\ Ax\ =\ b $$ No other information is given. My ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
2
votes
2answers
518 views

What does it mean to restricting a function to a line in convex optimization?

In lecture 3 of the course Convex Optimization conducted by Stephen Boyd at 21 minutes mark he says that a function is convex if its convex when we restrict it to a line. What does he mean by ...
2
votes
1answer
103 views

Approximating a function with a convex function

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous, differentiable function. Is there a known algorithm that fits $f$ with $g$, which is an order-$n$ polynomial that is convex, in the least ...
2
votes
1answer
75 views

Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
1answer
75 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
714 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
270 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
482 views

Moreau-Yosida regularization problem

Let $$F(x)=\min\limits_{y\in \mathbb R^n}\{f(y)+\|x-y\|^2\} ,$$ where $f(y)$ is convex and bounded below. How to show that if $x^*\in \arg \min \{F(x)\}$, then $x^*$ is in the closure of the ...
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
220 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
73 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
189 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
196 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
20 views

Check if convex polygon is completely contained completely within another convex polygon.

How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities: pcp = ...
2
votes
1answer
40 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
66 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
32 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
42 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
171 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
50 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
1answer
43 views

Analytical solution to the first PCA direction

It is known that the first PCA direction for a dataset of $n$ points is the unit vector with max variance after projecting the points onto this vector. I wonder whether there are some analytical ...
2
votes
2answers
75 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
101 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
32 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
38 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
85 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
75 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
78 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
113 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
93 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
134 views

Tangent Cone is a cone?

I first give two definitions. Def1: A set $S$ is a cone if $x \in S, \lambda \geq 0 \implies \lambda x \in S$. Def2: Let $S$ be any set (we may assume $\mathbb{R}^n$ with the usual Euclidean ...
2
votes
1answer
900 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
167 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
80 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
337 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
65 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
70 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
365 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
203 views

Find conjugate indicator function

I'm doubt with this problem. Let $C=\left\{(x,y)\in \mathbb{R}^2|x+\frac{y^2}{2}\le 0\right\}$. I have to find $I_C^{*}(Y)$ defined by $I_C^{*}(Y)=\sup_{X \in \mathbb{R}^2} \left\{\langle ...
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 ...