Tagged Questions

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

learn more… | top users | synonyms

0
votes
0answers
6 views

Linear independence of equality constraint gradients in constraint qualifications

I'm, trying to get an intuitive feel for the various constraint qualifications for KKT points. Most of them seem to rely on the linear independence of $\nabla g_i(x^*)$ where $g_i$ are the equality ...
-1
votes
0answers
13 views

Proving that a twice continuously differentiable function is convex iff it has positive second derivative [on hold]

Show that if a function is twice continuously differentiable, it is strictly convex if and only if the second derivative of the function is positive. (Hint: Show that if condition $(2.4a)$ holds, then ...
-3
votes
0answers
9 views

Show that a continuously differentiable function is strictly convex iff underestimated by any linear approximation [on hold]

Show that if a function is continuously differentiable, it is strictly convex if and only if a linear approximation to the function always underestimates it. (Hint: Show that if condition $(2.4a)$ ...
1
vote
1answer
14 views

Difference between tangent cone and this constraint cone

Define the cone $G(\textbf{x} = \{\textbf{p} \in \mathbb{R}^n | \nabla g_i(\textbf{x}^T \textbf{p} \leq 0, i \in I(\textbf{x})\}$ So this is a cone associated with the inequality constraints that is ...
0
votes
0answers
11 views

constraint optimization: sparsity with non zero constraints

I have an obtimization problem in the following form. $\min f(x)\\ s.t \|x_i\|_0\leq\lambda\\ x_i \geq0\\ \sum_i x_i = 1$ where $f(x)$ is convex. What is the easy way to optimize it as I have a ...
2
votes
0answers
15 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 ...
0
votes
0answers
6 views

Can the tangent cone contain more than the closure of the cone of feasible directions?

We know that the closure of the cone of feasible directions is contained in the tangent cone, but I'm wondering if it's possible for the tangent cone to consist of more than this closure?
2
votes
0answers
20 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 _2$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
1
vote
2answers
28 views

$\,f:[0,1)\to\mathbb R$ is a concave differentiable function st $\,f(0)=0$. Show that $g:[0,1),g(z)=f(zx)/z$, for $x > 0$ is decreasing

Question: Suppose that $f : [0, 1) \to\mathbb R$ is a concave differentiable function such that $\,f(0) = 0$. Show that $g : [0, 1) \to\mathbb R$ defined by $g(z) = f(zx)/z$, for some given $x > ...
0
votes
1answer
39 views

distance between solutions in a convex optimization

Assume that you have the following convex optimization problem: $\min_{M} \|b+A\ M\ v\|_2$ subject to : $\|M\|_{2}<1$ (maximum singular value less than 1) where M is a suare matrix (n by n), A ...
0
votes
1answer
39 views

matrix convex optimization

How to solve the following problem explicitly? I mean closed form solution if possible. $\min_{M} \|M\ a-b\|_2$ subject to : $\|M\|_{\infty}<1$ (maximum singular value) where $M$ is a square ...
0
votes
0answers
35 views
+50

Rank reduction to satisfy Barvinok's upper bound & Rank of a set notation

After reading n times the four first sections of the 4th Chapter of J.Dattorro's book (Convex Optimization & Euclidean Distance Geometry). I am confused between yes or no, every extreme point of ...
2
votes
2answers
14 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 ...
1
vote
0answers
22 views

A minimization question about the convexity of KL-divergence

Let $f_1$ be a continuous density function which is given and consider the closed ball around $f_1$: $$\mathcal{G}=\left\{g:\int g(x) \ln\frac{g(x)}{f_1(x)}\mathrm{d}x \leq \epsilon\right\}$$ ...
0
votes
1answer
24 views

Confusion with a proof about the continuity of convex functions

I studying convex analysis and in my book I have the following statement and proof: Lets assume that $f:S\rightarrow \mathbb{R}, \;S\subset \mathbb{R}^n$ is a convex function. Then $f$ is ...
1
vote
1answer
28 views

Optimization with changing objective function

Is there any theory about (convex) optimization where the objective function is allowed to change during the optimization process? I have a problem where the objective function depends on some ...
0
votes
2answers
65 views

Why is any subspace affine?

I am studying 'Convex Optimization' written by Stephen Boyd. I am confused by an assertion in the book(page 27). Any one can tell me why and give an explanation ? Any subspace is affine, and a ...
1
vote
0answers
21 views

Maximization over concave subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
1
vote
2answers
44 views

Why does gradient descent make sense?

Suppose I define two functions of $x$ in terms of a convex function $f$ with a unique minimum $x_0$: $$f_1(x) = 1 \times f(x)$$ $$f_2(x) = 2 \times f(x)$$ Suppose I wanted to minimize each of these ...
0
votes
0answers
18 views

How to show that this function is finite?

I have the following function: $$Q(x) = \mathbb{E}_{\omega}\Big{[}v(h(\omega)-T(\omega)x)\Big{]}$$ with $\mathbb{E}[|\omega_i|]<\infty$ and $v(z)$ finite for all $z\in \mathbb{R}^m$. $v$ is a ...
0
votes
1answer
14 views

An optimal solution that is also smooth

I am given a vector x. My objective is to find an optimal y (minimize $||y-x||_2^2$). With the constraint $y(c) = a$ (a and c are known scalars). $$\text{minimize}_y ||y-x||_2^2 \\ \text{subject to}\ ...
1
vote
1answer
25 views

Optimisation over matrix entries

I was looking to write the KKT conditions to solve this optimisation problem. $$\min_{\substack{\sum_j x_{ij}\le k_i \\ i=1,2,\ldots N}} a^\top (I-X)^{-1} b $$ Since there are $N^2$ decision ...
0
votes
0answers
15 views

Projection onto a matrix where the diagonals are identity matrix

I'm trying the understand intersection of convex sets given in "Convex Optimization - Boyd" which I'm also trying to code in cvx. The two convex sets I'm trying to find the intersection are given ...
3
votes
0answers
9 views

The difference between affine set and affine hull

According to the definition of affine hull and affine set. $$aff [C] = [\theta_1x_1+...+\theta_nx_n|x_1,...x_n \in C, ...
1
vote
0answers
19 views

What is the left derivative of the hinge loss function in the context of subgradients?

Let: $$|a|_+ = max\{0,a\}$$ Then the Hinge loss function (in the context of classification in Machine Learning) is: $$V(-yf(x)) = |1 - yf(x)|_+$$ Note that $y \in \{-1,1\}$ Let $f(x) = \langle w, ...
0
votes
0answers
7 views

Second derivative of Bregman divergence

Suppose I define an exponential family distribution: $$ f(x; \theta) = \exp \left( \langle x, \theta \rangle - h(x) - \psi(\theta)\right) $$ where the log-partition function is: $$ \psi(\theta) = ...
1
vote
0answers
41 views

Proving/deciding concavity of a function of two variables

I would like to formally prove that the function $f(x,y) = \frac{(c+1)e^{-x}(xe^{x+y}+y)}{(c+2)(e^{x+y}-1)+e^y} $ is concave ($ c>2$ is a constant, and both $x,\, y \in \mathbf{R_+}$). Plots of ...
2
votes
1answer
27 views

Convex optimization: interpretation of the dual variable

Let us consider the convex optimization problem $$ \tag{P} \underset{x\in\mathbb R^n}{\sf minimize} ~~ f(x) ~+~ g({\bf L}x) $$ where ${\bf L}\in\mathbb R^{m\times n}$. Using the convex conjugate, ...
0
votes
0answers
17 views

gradient descent - cost reduces and then increases

I am optimizing a function using Gradient Descent. The learning rate is fixed. First for few iterations the cost decreases after that it starts increases. What is the reason for this?
2
votes
0answers
40 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 ...
0
votes
1answer
19 views

Explanation for Zeroth Order Condition for Convexity

First of all, please let me admit that my math is very rusty so that I may not understand some basic concepts. I'm reading the book named "Convex Optimization" by Stephen Boyd and Lieven ...
1
vote
0answers
26 views

When result of max of min problem is equal to min of max problem

Let's assume there are two functions $f(x)$ and $g(x)$. I want to know when the optimal $x$ of max of min of $f(x)$ and $g(x)$ is not equal to optimal $x$ of min of max of $\frac{1}{f(x)}$ and ...
1
vote
2answers
43 views

Is the set of all projection matrices a convex set?

The set $\phi=\{P| P^2=P\}$ contains all projection matrix. Is this set $\phi$ convex?
0
votes
0answers
32 views

Describing the minimizers of this function

Consider the following continuous function over $x$, with $a,b>0$: $$f(x)=\begin{cases} ax-\sqrt{x} & \text{for }x\leq b^{2}\\ ab\sqrt{x}-b & \text{for }x>b^{2} \end{cases}$$Note that ...
0
votes
0answers
19 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
2
votes
1answer
39 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 ...
1
vote
1answer
68 views

Minimization over two lines

This is a minimization question where the minimizing points can be chosen freely on two lines: $$\mbox{minimize}\, \prod_{i=1}^K {y_i}\quad \mbox{such that}\quad \prod_{i=1}^K ...
2
votes
1answer
20 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: ...
3
votes
1answer
31 views

recover primal solution from dual for matrix completion

Consider the following primal/dual SDPs $$ \min\limits_X \; \lVert X \rVert_* : \mathcal{A}(X) = b \qquad \max\limits_z \; b^T z : \lVert \mathcal{A}^*(z) \rVert \leq 1 $$ where $\lVert X \rVert_* = ...
0
votes
0answers
41 views

$f:D\subset \Bbb R^2 \rightarrow \Bbb R$, where $D$ is a compact and convex set, reaches it maximum at $int(D)$

I'm trying to prove that if $D$ is a compact and convex (for every two elements of $D$, the line that connects them is contained in $D$) then: If $f:D\subset \Bbb R^2 \rightarrow \Bbb R$ and at ...
0
votes
1answer
26 views

how to differentiate this equation (contains absolute and norm)

how can I differentiate the following wrt $\mathbf{d}_i$? $\frac{|\mathbf{d}_i^T\mathbf{d}_j|}{\|\mathbf{d}_i\|_2\|\mathbf{d}_j\|_2}$ Thanks in advance.
1
vote
1answer
75 views

Argument to “linearize” an objective function

I have this optimization problem on the variables $\lambda_\ell^+, \lambda_\ell^-$ such that $ \lambda_\ell^+ \geq \lambda_\ell^-$ with $\ell=1,\ldots,n$ , and fixed $P\in [1/(n+1),1]$ \begin{align} ...
0
votes
0answers
32 views

is $R^N_{ ++}$ a convex set?

Is $R^N_{ ++}$ a convex set? I'm working on some optimization hw problems that have some functions of the type: $f:\mathbb{R}^2_{++} \rightarrow \mathbb{R}$ And it seems like in general whenever ...
0
votes
0answers
23 views

Conservative perceptron update rule - convex optimization

Suppose I have a condition on a perceptron update rule should be a little conservative. For example, it minimizes the distance between the new update and previous classifier $w_i$, i.e. $||w_{i+1} - ...
0
votes
2answers
35 views

When is the difference of two convex functions convex?

Assume that $X$ is a finite dimensional Banach space. I know that in general if two functions $f:X \mapsto \mathbb{R}$, $g:X \mapsto \mathbb{R}$ are convex then the function $(f-g):X \mapsto ...
0
votes
1answer
70 views

Give example of a set which has No Extreme Point !!..

Give example of a set in R^2 , which has no extreme point ?? We were given this question for assignment !!..I thought of a simple line but doing some research i stumbled upon this solution which ...
0
votes
0answers
26 views

how to derive this equation?

How can I derive this? $\min_{d_m} \|Y - DX\|_2^2 = \min_{d_m} x_m^Tx_md_m^Td_m - 2R_mx_m$ where $R_m = Y - \sum_{i \neq m } d_ix_i^T$ $x_m $ is a vector represents a row in $X$
2
votes
1answer
30 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 ...
0
votes
0answers
26 views

Solving with Newton's Optimization Method

I am aware of how to implement the Newton's method for minimization for a smooth analytic function. I am also aware of log-barrier for constraint minimization. Now, I am looking to solve the the ...
1
vote
0answers
13 views

Extra information needed to distinguish combinatorially isomorphic polytopes

The title pretty much sums up my question: what extra information do we need (or what is an example of sufficient information) on top of the face lattice in order to completely characterize a convex ...