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

learn more… | top users | synonyms

1
vote
0answers
9 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
17 views

Semi-definite-program setup

I am new to solving semi-definite programming problems and I am trying to solve the matrix norm minimization problem as described below for some $\boldsymbol{x}$ that appears as a vector in $\Sigma$. ...
0
votes
0answers
9 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
8 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
17 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
16 views

how to prove convex function for multy variables?pleese ansewr quickly [on hold]

If $f$, $f_y$ ,$f_z$ are continuous on $[a,b]\times R^2$, show $f(x,y,z)$ is convex on $[a,b]\times R^2$ if and only if $$f(x, \theta y_1+(1- \theta) y_2,\theta z_1+(1- \theta )z_2) \le \theta ...
0
votes
0answers
5 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
35 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, ...
2
votes
0answers
39 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 ...
3
votes
2answers
319 views

Solving Linearly Constrained Quadratic Programming with Coordinate Descent

Does anybody have any idea about how to solve the following problem with Coordinate Descent? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& ...
0
votes
0answers
14 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?
0
votes
1answer
18 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
2answers
327 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
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
42 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
31 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
15 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) ...
0
votes
0answers
12 views

What is the $R_{++}$ space? [closed]

I'm starting to study Convex Optimization but I don't know what is the $R_{++}$ space?
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
38 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 ...
0
votes
1answer
283 views

relation between size of matrix and condition number

I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
3
votes
1answer
27 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_* = ...
1
vote
1answer
325 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
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: ...
0
votes
0answers
39 views

How to Extract the dual feasible search directions for the primal-dual potential reduction algorithm?

I am trying to implement the 4.4 Primal-dual potential reduction algorithm introduced in M.S Lobo et al.. Here is a screenshot depicts the algorithm flow: As ...
0
votes
0answers
40 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 ...
1
vote
1answer
73 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
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
327 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
1answer
284 views

Generalization of soft threshold operator?

For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator: $\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$ where $\circ$ is ...
3
votes
1answer
257 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
0
votes
1answer
320 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
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
22 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
1answer
63 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
2answers
34 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
0answers
25 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
29 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 ...
1
vote
0answers
18 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 ...
0
votes
0answers
30 views

ADMM on non-convex problem

Suppose the minimization problem is $$\operatorname{arg min} \limits_x f(x) + g(x)$$ where function $f$ is not convex but $g$ is. If we solve it using ADMM $$\operatorname{arg min} ...
0
votes
1answer
36 views

Question about the structure of a convex optimization problem

I am reading a tutorial about Convex Optimization and it defines the general Convex Optimization problem as: $$ minimize_x f(x)$$ where $g_1(x) \leq 0, ... , g_m(x) \leq 0$ and $Ax=b$ and $x \in ...
0
votes
1answer
22 views

Logistic regression maximum likelihood derivation

the following equations are given: $\sum_{j=1}^c\hat{P}_j = 1$ $\sigma_i(\mathbf{z}; \theta) = \frac{exp(\mathbf{\theta}_i^T\mathbf{z})}{\sum_{j=1}^cexp(\mathbf{\theta}_j^T\mathbf{z})}$ $L = ...
0
votes
0answers
16 views

How to show this empirical risk minimization problem has a specific optimum?

I'm trying to show for general regularized empirical risk minimization problem that the minimizing $w$ for $$ \frac{1}{n}\sum_{i=1}^n \textrm{loss}(w^T y_i,x_i) + \mu \lVert{w\rVert}^2, $$ where the ...
2
votes
2answers
53 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
0
votes
1answer
27 views

Basis of the row-space of a matrix with non-negative entries.

Consider a matrix $A \in \mathbb{R}^{n \times m}$ such that all entries are non-negative. Denote the rank of $A$ as $k$. I am mostly interested in cases where $k \ll n$, but this probably isn't ...
1
vote
1answer
24 views

Proving an affine set's equivalence to the solution set of $Ax=b$

I am stuck with the following equivalence about Affine Sets: "$L$ being an affine set is equivalent to $L$ being the solution set of a set of equations $Ax=b$ for some $A,b$." In a more mathematical ...
0
votes
1answer
14 views

partial derivative of a vector with respect to a variable

I have a vector in the following form $\mathbf{w}^T = [a_1*w_1, a_2*w_2, \dots, a_d*w_d]$ what is the partial derivative of $\mathbf{w}$ with respect to $w_j$ ? (1 or 2) $\frac{\partial ...