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

learn more… | top users | synonyms

0
votes
1answer
32 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
22 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
56 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
33 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
29 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
22 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
44 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
42 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
41 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
24 views

Hyperplane optimization for Support Vector Machines

I am trying to learn about the theory behind the Support Vector Machines, by reading the tutorial at: http://research.microsoft.com/pubs/67119/svmtutorial.pdf In its most basic form, SVMs is a binary ...
0
votes
0answers
42 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
21 views

Differentiability of Moreau-Yosida Regularization? [duplicate]

I'm looking for a proof of the differentiability of the Moreau-Yosida regularization of a proper closed convex function $f(y)$ defined on an n-dimensional Banach space $Y$. namely the function is ...
1
vote
1answer
81 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 ...
0
votes
0answers
27 views

how to prove this sparse coding equation

How can I prove the following? $\sum_i \frac{1}{2} \|\mathbf{x}_i - D\mathbf{\alpha_i}\|^2 = \frac{1}{2}Tr(D^TDA_t) - Tr(D^TB_t)$ where, $A_t = \sum_{i=1}^T \mathbf{\alpha}_i\mathbf{\alpha}_i^T\\ ...
1
vote
0answers
108 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
35 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
41 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
17 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
46 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
34 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
62 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
59 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
1
vote
1answer
43 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
72 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
26 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
22 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
16 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
86 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
24 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
15 views

A strange sufficient condition for quasiconcavity

I think I learned this from a lecture today If a multivariate C2 function is increasing and its bordered Hessian has positive determinant, then f is quasiconcave. ...
0
votes
0answers
7 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
62 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
32 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 ...
1
vote
0answers
73 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
0
votes
1answer
32 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
0
votes
1answer
65 views

$x^2+y^2+z^2 +3 \geq 2(xy+xz+yz)$, for $xyz=1$ [closed]

$x,y,z > 0$ such that $xyz=1$ can you prove that $x^2+y^2+z^2 +3 \geq 2(xy+xz+yz)$ without lagrange multiplier Thanks
2
votes
1answer
44 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 ...
0
votes
0answers
37 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
1
vote
1answer
42 views

Projection onto hypercube [0,1]^n

Given a positive n-dimensional vector $\mathbf{z}$ (all its elements are positive), my goal is to project it to a unit hyperplane $[0,1]^n$. However my projection is defined with respect to ...
0
votes
1answer
27 views

Why Am i standing in a global minimum?

I`been asked the following in optimization If I am located in a point where all the possible factible directions turn out to be worse for the function, Am I located in a global minimum? The answer is ...
0
votes
1answer
65 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
2
votes
1answer
63 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.
1
vote
0answers
29 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
0
votes
0answers
17 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
34 views

closed form vs gradient descent baseed methods

I am a beginner to optimization. Could anybody give me a simple example to illustrate when I should use closed form and when I should use iterative methods like gradient descent? Thanks in advance.
2
votes
0answers
64 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 ...
0
votes
0answers
20 views

Are iterations involving quantization going to converge?

For $i = 1,2,3$, let $~f_i(y_i)~$ be a convex and differentiable function and $y_i$ a scalar variable. Consider the following iteration $$\left[ \begin{array}{c} \nabla f_1(y_1^{k+1}) \\ \nabla ...
0
votes
1answer
44 views

Convex matrix function

Please give me some hints for the following problem: Let $S = \{D \in R^{m \times n}, \|d_i\| \leq 1, i = 1, 2, \dots, n \}$. Find condition of $F \in R^{m \times m}$ such that the function: $ f(D) ...
0
votes
1answer
43 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
1answer
24 views

how to differentiate to optimize this function?

I have an optimization function in the following form: $E = \operatorname*{argmin}_{A} \sum_j \| A\bf{x}_j - B \|_2^2 + \mu\sum_i a_{ii}^2$ Where, A is an unknown diagonal matrix with elements ...