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

learn more… | top users | synonyms

2
votes
1answer
55 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
59 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
70 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
96 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
76 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
650 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
127 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
76 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
263 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
49 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
56 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
2answers
738 views

Strong convexity and Lipschitz

What can you say about the L and $\lambda$ for a $\lambda$-strongly convex differentiable function, if its gradient if L-Lipschitz? Also, it is given that $\lVert \nabla f(y) - \nabla f(x)\rVert_2 ...
2
votes
1answer
305 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
77 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
189 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
40 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
269 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
239 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
542 views

A property of the minimum of a sum of convex functions

Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in ...
2
votes
1answer
302 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
150 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
67 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
226 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
98 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
159 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
819 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
240 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
449 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
134 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
960 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
22 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
2
votes
0answers
26 views

Maximin problem as LP?

Consider the following setting. Let $A\in \mathbb{R}^{3 \times m}$ and $B\in \mathbb{R}^{m\times 3}$ be two matrices such that each of their columns must add up to a given $c\in \mathbb{R}$. Denote by ...
2
votes
0answers
34 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
2
votes
0answers
20 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
2
votes
0answers
21 views

Dual Decomposition with multiple coupling constraints

This is probably a a simple question, but have been stuck on this for a while and unable to figure out my issue from the standard Boyd/Vandhenbergen decomposition references. I am interested in dual ...
2
votes
0answers
34 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
2
votes
1answer
39 views

Minimum Distance between a Triangle and a Distance Field 3D

I am looking for (possibly numerical) solution to this geometric problem: Given a filled 3D triangle $T = \text{conv}(p_1, p_2, p_3) \subseteq R^3$, and a distance field $D(x) : R^3 \to R$, what ...
2
votes
0answers
79 views

Strong duality for nonconvex quadratic program (with multiple constraints)

Consider the following optimization \begin{eqnarray} P_1: \quad &\underset{x\in\mathbb{C}^N}{\mathrm{minimize}}&\; f_0(x) \\ &\mathrm{subject\;to}&\; f_i(x) \leq 0, i=1,\ldots,m \\ ...
2
votes
0answers
19 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
2
votes
0answers
41 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
2
votes
0answers
29 views

proving that the ewma is convex

Hi: I know it's true but I don't know how to prove that exponentially weighted moving average when view ed as a function of $\lambda$, is strictly convex. The exponentially weighted moving average ...
2
votes
0answers
34 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
2
votes
0answers
64 views

Affine functions as equality constraints in convex optimization problems

I am studying on an introduction to convex optimization problems. When defining a convex optimization problem, we have a convex object function, $f(x)$, a set of convex functions $g_i(x)$ where the ...
2
votes
0answers
49 views

Normalize gradient

I want to minimize a function $f \, : \, \mathbb{R}^{N} \, \longrightarrow \, \mathbb{R}$ (with $N \in \mathbb{N}^{\ast}$. In my problem, $N = 315$). I know that $f$ is differentiable on ...
2
votes
1answer
26 views

Will continuous extension preserve strict convexity?

The problem I am thinking about is like follows. Suppose that $h$ is a strictly convex function on an open convex set $S$. Then, we extend $h$ continuously to the closure of $S$ that is denoted by ...
2
votes
1answer
29 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
2
votes
1answer
46 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
2
votes
0answers
67 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
2
votes
0answers
40 views

Solve the linear program

Please help to solve this problem. I am new to this type of problems and any help will be greatly appreciated $$\text{ Minimize } 7x-5y+3z$$ $$\text{ Such that } \ \ \ 0 ≤ x ≤ 6 , -2 ≤ y ≤ 7 , -4 ...