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

learn more… | top users | synonyms

1
vote
0answers
39 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
50 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
41 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 ...
1
vote
0answers
155 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
2answers
107 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
71 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
35 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: ...
4
votes
1answer
118 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
48 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
32 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
95 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
37 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
31 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
105 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
148 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 ...
2
votes
1answer
40 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
38 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
27 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 ...
2
votes
1answer
30 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
1answer
435 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
57 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
48 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
26 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
67 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 ...
1
vote
1answer
56 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
44 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 ...
0
votes
1answer
37 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 ...
0
votes
1answer
49 views

The relation between two different definitions of Affine sets

I am following a presentation, which says that for an affine set $L \subseteq \mathbb{R}^n$ it is: $$L=\left\{x|Ax=b \right\}$$ for some $A,b$. The first definition of $L$ as an affine set is given ...
1
vote
1answer
55 views

Dual Optimization Problem

I have the following optimization problem, $$ \text{minimize}_{X,Y} \ \lVert X\rVert_* + \lambda \lVert Y\rVert_1 \\ \text{subject to }X + Y = C$$ $C \in \mathcal{R}^{m \times n}$, $\lVert ...
0
votes
0answers
136 views

Fenchel dual vs Lagrange dual

Consider the Fenchel dual and the Lagrangian dual. Are these duals equivalent? In other words, is using one of the these duals (say for solving an optimization), would give the same answer as using ...
0
votes
0answers
48 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 ...
2
votes
1answer
349 views

Proving convexity of a function whose Hessian is positive semidefinite over a convex set

C is a convex set in R^n and f:R^n --> R is twice continuously differentiable over C. The Hessian of f is positive semidefinite over C, and I want to show that f is therefore a convex function. I ...
1
vote
1answer
154 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
0
votes
1answer
48 views

Find Maximum of Lower Envelope

Okay, I'm not really sure whether the title is good. Consider \begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + ...
0
votes
1answer
102 views

Prove that f has at least one global minimizer

$f: \mathbb{R}^n \to \mathbb{R}$ is a continuous function such that $\displaystyle\lim_{\|x\| \to \infty} f(x) = \infty$ On a side note: how can a function have more than one global minimizer? Is a ...
0
votes
0answers
21 views

online algorithm for nested optimization

How to construct a sequence {x_t;\theta_t}, which is online algorithm for following optimization problem: $\arg\min_\theta \sum_t \min_{x_t} \ell_t(x_t;\theta)$ For simply, we can assume ...
1
vote
1answer
77 views

Relation between Riccati Algebraic Equation and optimization problem

Reading this page: http://www.mathworks.com/help/robust/ug/minimizing-linear-objectives-under-lmi-constraints.html I got stuck in the result that says it can be show that minimizing Trace of X (a ...
0
votes
1answer
45 views

Feasible Condition with a single constraint

A linear program with a single constraint minimize $z = c_{1}x_{1} + c_{2}x_{2} +· · ·+c_{n}x_{n}$ subject to $a_{1}x_{1} + a_{2}x_{2} +· · ·+a_{n}x_{n} ≤ b$, $x_{1}, x_{2}, . . . , x_{n} ≥ 0.$ (a) ...
4
votes
1answer
111 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
0
votes
0answers
73 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
1
vote
1answer
59 views

Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is convex. Does anyone know how to prove ...
1
vote
1answer
100 views

Why geometric median cannot be solved analytically

$\DeclareMathOperator*{\argmin}{argmin}$ For a given set of $m$ points $x_1,...,x_m$ with each $x_i\in \mathbb{R}^n$, the geometric median (or the weber point) is defined as $$\argmin\limits_{y \in ...
0
votes
0answers
31 views

Convex sets and minimum points

Let $X$ be the convex set formed by the convex combination of the $n$ points $\{x_1, x_2, ... x_n\}$ in $\mathbb{R}^n$. Let $X^* \subseteq X$ be the convex set of minimal points w.r.t to the convex ...
0
votes
0answers
27 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
23 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
0
votes
0answers
122 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
2
votes
1answer
44 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 ...
0
votes
0answers
10 views

Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...
0
votes
1answer
72 views

Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
0
votes
0answers
62 views

Least squares and simplex

I am interested in the linear least square problem with the solution with the following constraints : $$ \min_x \|Ax-b\|^2$$ subject to $0 \le x_i \le 1$ and $\Sigma_{i=1}^n x_i= 1$. Because of the ...