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

learn more… | top users | synonyms

1
vote
2answers
36 views

Explain why for an extreme point some inequalities in the constraints become equalities

Suppose we have a linear program $$ \max_x c^Tx\\ \text{subject to } Ax \leq b $$ where $\leq$ denotes pairwise inequality, i.e. $a^T_i x \leq b_i, i = 1,..., n$. If $y$ is an extreme point, why is ...
0
votes
2answers
51 views

Combinations, vertices and LPs

This suggests the following (I know it is a very inefficient one) This will work but there would be many vertices. In fact for $Ax \leq b, \ x \geq 0$ there can be $\binom {n+m}{m}$ ...
0
votes
1answer
40 views

Strong duality of SDPs

On pp. 654 of Boyd's book, it is claimed that strong duality holds between the SDPs B.2 and B.3 (at the bottom of this page). Does it require additional assumption that one of them is strictly ...
0
votes
1answer
14 views

Brief explaination on convex optimization problem

I have following type optimization problem (I transformed original max-min problem into this kind), and I can show that all $g_1(l_1),\cdots,g_M(l_1,\cdots,l_M)$ functions are concave. $$\max_{\...
1
vote
1answer
41 views

Maximizing the volume of the convex hull of $N$ points in the unit ball

Suppose we are given an integer $N\ge4$, and we have to pick $N$ points in a unit ball in $\mathbb R^3$ to maximize the volume of their convex hull. Are those points necessarily on the surface of the ...
0
votes
0answers
26 views

Need optimal tableaus be unique assuming unique solution?

If so, why? If not, do they differ by some ERO/s? That is, they are row equivalent? This is the problem (taken from Chapter 2 here): My classmate gave an optimal tableau that is different ...
0
votes
1answer
60 views

Proximity operator for logistic function

I am reading the ADMM paper by S. Boyd et al: http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf I'm interested in implementing a L1-regularized feature-wise distributed multinomial ...
3
votes
0answers
34 views

Reference for elementary result in optimization

Let $U(\mathbf{z})$ be a convex, twice differentiable function, and $F(\mathbf{z},\mathbf{q})$ be convex and twice differentiable separately in $\mathbf{z}$ and $\mathbf{q}$. Consider the problem of ...
2
votes
1answer
52 views

what is the closed form solution for $\min_x ||y-x||^2_2+\lambda ||x||_2$

$y$ and $x$ are vectors. $\|\cdot\|_2$ is Euclidean norm. In one paper I read, they say the closed form solution is $x=\max\{y-\lambda \frac{y}{\|y\|_2}, 0\}$. I don't know why $x$ need to be non-...
1
vote
1answer
26 views

How to find a realisable starting point with the Simplex algorithm?

Let be the following linear program: \begin{equation*} \begin{cases} \max f(x_1,x_2) =3x_1+2x_2\\ 5x_1 + 2x_2 \ge 8\\ x_1 - x_2 \le 1\\ x_1 + x_2 \le 3\\ ...
1
vote
0answers
40 views

Generalizations of Positive Definiteness

What, if any, notions of positive definiteness can be extended to 3rd order tensors (and beyond)? The reason I ask is because the Hessian matrix of a convex function is positive semi-definite, but ...
2
votes
1answer
37 views

Matrix optimization over a quadratic function

I want to find matrices $F$, $G$, and $H$ minimizing $\begin{bmatrix} x^T & y^T& z^T \end{bmatrix} \begin{bmatrix} I & 0& 0 \\ 0 & F &0 \\ 0 & G &H \end{bmatrix}^{...
0
votes
1answer
46 views

Is the set of probability density functions convex?

Given is the set of probability density functions defined as $P:=\left \{ p(x)\mid p(x)\, is\ a\ probability \ density \ function \right \}$ Is $P$ a convex set? I am not sure that here i have to ...
0
votes
1answer
51 views

What is the closed form for this norm $\|Z\|=\sup_{\|u\|=1,\|v\|=1} u^TZv$?

I read a paper, which has the equation above $\|Z\|=\sup_{\|u\|=1,\|v\|=1} u^TZv$. Is this a well known norm and what is the closed form for this norm. Also what does this norm describe? Thanks in ...
0
votes
0answers
32 views

Proof of convergence of coordinate descent for non differentiable function

Prove that a function $f(x)$ given by: $$ f(x) = g(x) + \sum_{i=1}^{n} h_{i}(x_{i}) $$ where $g(x)$ is convex and differentiable, and each $h(x)$ is convex, can be minimized by co-ordinate descent (...
0
votes
0answers
20 views

Strong Duality for Euclidean distance

i have an optimization problem in the form: $min ||x - y||$ sbj to: $A.x = 0$ $A.y = 0$ $l_x \leq x \leq u_x, l_y \leq y \leq u_y$ I'm trying to find the dual form of this optimization problem, ...
2
votes
0answers
28 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
0
votes
1answer
30 views

Show that that optimal Ridge Regression beta is minimizing

I have the constrained regression (Ridge) of the form $$S(\beta)=(y-X\beta)'(y-X\beta)+\lambda(\beta'\beta)$$ where $\lambda$ is just a scaler. I am able to find an optimizing solution for the beta ...
0
votes
0answers
30 views

A supremum problem

Let $a=\underset{\|u\|_c\leq 1, \|v\|_r\leq 1}{\sup}v^TY^Tu$. If $\lambda<a$, $\underset{u_m, v_m}{\sup}v_m^TY^Tu_m-\lambda\|u_m\|_c\|v_m\|_r=+\infty$. While if $\lambda > a$, then $\...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
0
votes
0answers
36 views

How can the ADMM algorithm be distributed?

I am reading Boyd's tutorial paper on ADMM. One question I had after I reached the formulation of the algorithm on pp.14 is: how can the alternating or sequential fashion of x-minimization step and z-...
1
vote
1answer
44 views

Is there Any Benefits for Casting a Convex Program Problem into Linear Program Problem?

I'm curious a relative broad question: Suppose I have a convex program problem in hand. (hence, I could use many well-developed software packages to solve this problem for sure; e.g., CVX..) But ...
1
vote
3answers
39 views

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$?

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$ is the statement correct? Can I prove like this: $sup_x [ f(x)+sup_x g(x)] = sup_x[f(x)] + sup_x[g(x)] = sup[f(x)+g(x)]$.
0
votes
0answers
36 views

Why Gradient Descent Runs Away from Possible Solution?

I am trying to solve a multivariate optimization problem (actually trying to minimize a first order objective function) using gradient descent. The objective function is simple: ...
4
votes
2answers
158 views

Minimum of $\sum\limits_{k=0}^n { n \choose k} (1-x)^{n-k} x^k a_{n-k}b_k$ over $x \in [0,1] $

Given \begin{align} f(x)=\sum_{k=0}^n { n \choose k} (1-x)^{n-k} \cdot x^k \cdot a_{n-k} \cdot b_k \end{align} Find \begin{align} \min _{x \in [0,1] } f(x) \end{align} We can assume that $a_k$ and ...
0
votes
0answers
50 views

Computing Direction of Descent for General Fermat Problem

Suppose that $k \geq 3$, and let $X_1, \dots , X_k$ be $k$ points in $\mathbb{R}^2$, and let $w_1, \dots , w_k$ be $k$ positive real-valued constant weights. Given this, consider the function $g(p) = \...
1
vote
0answers
29 views

Converting a norm-computation SemiDefinite program to standard SDP form.

I'm trying to express this norm-computation semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$ $$\gamma_{2}^{\epsilon}(A):= \min\,t\,\, subject\, to\, \left( \...
1
vote
0answers
20 views

Boyd & Vandenberghe's proof that all simplexes are polyhedra.

On page 33 of B&V's convex optimization book, during the proof that any simplex can be represented as a polyhedron, they discuss a $n \times k$ matrix $B$ with full column rank and conclude that: ...
0
votes
0answers
79 views

matrix optimization in diagonal and orthonormality constraint

I'd like to solve the following optimization problem. Y is a CxN matrix A is a CxC and diagonal matrix Q is a CxC and orthonormal matrix X is a CxN matrix $$ min_{A,Q} {|| Y − AQX ||}^2_F $$ The ...
0
votes
0answers
18 views

Convexity of Maximum Inscribed Ellipsoid Problem

I am confused about the problem of finding the ellipsoid of maximum volume inscribed in a polyhedron as discussed in section 8.4.2 of Convex Optimization by Boyd and Vandenberghe. I've followed the ...
4
votes
0answers
126 views

Conditions under which the damped Newton method is globally convergent?

Consider the problem of minimizing a convex function over $\mathbb{R}^n$ \begin{align} \min_{x\in\mathbb{R}^n}f(x) \end{align} Consider the damped Newton method (from Nesterov's book Introductory ...
1
vote
0answers
36 views

Logarithmic Function Behaivour

I have read about Logarithmic function. We can use the second-order condition to show that the $f(x)=\log_2(1+x), x \geq 0$ is a concave function. Now, is $g(x)$ a concave function? How can I prove ...
1
vote
0answers
57 views

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in ...
0
votes
0answers
18 views

Two way partitioning problem's lower bound

In the two-way partitioning problem (as laid out in Slide 7 here), as an example, one possible value for $\nu$ is $-\lambda_{min}(W)1$ which gives the bound as $p^* \ge n\lambda_{min}(W)$. My ...
0
votes
0answers
30 views

Optimization related to reduced SVD

The reduced SVD of $B_{m\times n}$ is $USV^T$ and we know the columns of $U$ and $V$ are orthonormal. $e_i$ is the $i$th standard basis vector. I want to know the range of the following optimization ...
0
votes
1answer
71 views

Difference between Gradient Descent method and Steepest Descent

What is the difference between Gradient Descent method and Steepest Descent methods? In this book, they have come under different sections: http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ...
2
votes
1answer
43 views

Convolution of convex function and Gaussian is convex

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, i. e., for all $x_1, x_2 \in \mathbb{R}$ and $t \in [0, 1]$, $$ \qquad f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2).$$ I want to prove that the ...
1
vote
0answers
14 views

Condition on linearly separable datasets

I am trying to understand linear classification with hyperplanes. So far I understood that for a binary classifier with labels $y_i \in \lbrace -1, 1\rbrace$ points $(x_i, y_i)$ are separable if ...
0
votes
0answers
30 views

Is this objective function with exponentiated parameters convex?

I'm working on a function fitting problem. I have fixed basis functions $B_0, ..., B_M$ and parameters $t_0,...,t_M$ and I want to solve the least squares problem of minimizing $$\sum_i\left(y_i - \...
0
votes
1answer
30 views

Monotonic optimal value function

Are there any theorems/sufficient conditions about when the optimal value function of a parametrized optimization problem is monotonic in the parameter? Specifically, are there simple conditions ...
1
vote
1answer
19 views

Non convex objective in SVM

In the formulation of svm.. The line underline says the norm of the vector w is a non convex constraint.. But how is this so.. Isn't norm a convex function.. Also aren't the other objectives affine.. ...
0
votes
2answers
47 views

Finding the optimal value in an optimization problem

Given the optimization problem $$\text{minimize}\ f_0(x_1,x_2)$$ $$\text{subject to}\ 2x_1+x_2 \ge 1$$ $$x_1+3x_2 \ge 1$$ $$x_1 \ge 0, x_2 \ge 0$$ Let the objective function be $f_0(x_1,x_2) = x_1^2 ...
1
vote
0answers
30 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
0
votes
0answers
19 views

convex optimization with multiple nonsmooth terms

Is there a general algorithm for solving $$ \min f(x) + g(x) + h(x) $$ where all three functions are convex and proximable, $f(x)$ is smooth, and $g(x)$ and $h(x)$ are both nonsmooth? Note that if ...
0
votes
2answers
34 views

Proving f cannot be convex

The following question I encountered in a convex optimization course and I can't seem to understand the solution.
0
votes
1answer
46 views

Proximal operator to Huber function

I want to solve the following problem: $$ \arg\min_x |x|_\mu + \frac{1}{2\sigma} |x-x^k|^2 $$ , where $$|x|_\mu = \begin{cases} \frac{|x|^2}{2\mu}, & |x|<\mu \\ |x|-\frac \mu 2 & |x|\geq \...
0
votes
1answer
14 views

Hessian of function regarding convexity

Consider the function $f(x,y) = xy$ for $x,y>0$. Isn't $f$ a convex function? I computed the Hessian to be a matrix with only off diagonal entries equal to one and others zero. For any vector $z$ ...
2
votes
3answers
50 views

Convexity of a non linear optimization problem

I have a non linear optimization problem, namely: $$\min {\sqrt{(x-u)^2 + (y-v)^2 + (z-w)^2)}}$$ How can i show that the above function is convex. Doing via Hessian is a difficult task.
0
votes
0answers
25 views

Nonlinear Optimization

I have a nonlinear optimization problem, but constraints are ODE. Cost function is $J= x1+x1*x2+x1^2$ while constraints are, $\underline{x_i} < x < \bar{x_i}$ (for i=1,2,3) ; $\frac{dx3}{dt}=...
0
votes
0answers
30 views

Convex optimization of a fractional objective function involving matrix determinants

I am interested in convex representation of the following fractional optimization problem. I have also described my approach in the following. However, as I am new to convex optimization, I am not ...