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

learn more… | top users | synonyms

0
votes
0answers
21 views

Complementary Slackness Condition clarification

So for the dual part of the complementary slackness, the theorem says this: If $y_i^* > 0$, then the $i^{th}$ constraint is binding in Primal $\ \ \ (1)$ If the $i^{th}$ constraint in Primal is ...
0
votes
1answer
29 views

Are these two optimization problems equivalent?

I have two problems as follow. $min_x: ||x-y||_2^2 + \lambda_1 ||x|| \quad \ \ (1)$ and $min_x: ||x-y||_2^2 + \lambda_2 ||x||^2 \quad (2)$ Here $||\cdot||$ could be any norm and ...
1
vote
2answers
35 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
50 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 ...
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. ...
0
votes
1answer
27 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
25 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
47 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
51 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 ...
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
35 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
35 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 ...
0
votes
0answers
31 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
26 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
19 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
25 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
34 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 ...
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
32 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
155 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
22 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
51 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
15 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
117 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
33 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
44 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
11 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
24 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
47 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
39 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
27 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
24 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
16 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 ...
0
votes
2answers
42 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
27 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
30 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
12 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
48 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.