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

learn more… | top users | synonyms

2
votes
2answers
56 views

References on probability theory, stochastic processes, Monte Carlo and convex optimisation, with similar writing style to Terence Tao

I learned a lot from prof Tao's notes and books because unlike many authors, he seems to prefer writing more words, explanations and intuitions rather than just mathematical formulae. His approach is ...
1
vote
0answers
10 views

Why this problem is unbounded, even though it's dual is feasible?

In this paper, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming,page 2, there is a problem called, (P): \begin{align} P: &\min_{X,s} && ‎ \frac{1}{2} ‎\Vert X-G\...
0
votes
0answers
15 views

Convert this problem with 2-norm cost to an SOCP?

I am solving a non-convex problem via sequential convex optimization. Here is a minimal example of my problem at iteration $i$: $$ \begin{align*} \min_{\Delta t,F_i}&\left( \Delta t+m\|\eta_{\...
1
vote
0answers
28 views

Variational inequality and saddle point problem

I refer to the following paper: (fix the wrong link) https://papers.nips.cc/paper/5723-adaptive-primal-dual-splitting-methods-for-statistical-learning-and-image-processing.pdf In that paper, we ...
3
votes
2answers
70 views

Maximum concyclic points

Given n points, find an algorithm to get a circle having maximum points.
0
votes
0answers
19 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a hint ...
0
votes
0answers
36 views

Positivity of the last component of non negative least squares based on active set method

I have followed the instructions given in Lawson and Hanson book for non-negative least squares using active set method. I am having a trouble in justifying one of the statements they have made about ...
1
vote
0answers
22 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: $...
0
votes
0answers
12 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
5
votes
1answer
90 views

Why is the Barycenter operation in Hadamard spaces Lipschitz continuous?

I am looking into exercise 9.2.22 of "A course in metric geometry" by Burago-Burago-Ivanov. For a Hadamard space $H$ (a complete simply connected metric space of nonpositive curvature in the ...
2
votes
0answers
92 views

Optimization of approximate functions using varying objective function

Let $g(\theta;x)$ and $f(\theta;x)$ be two convex functions such that $g$ asymptotically approximates $f$: $g(\theta;x)\approx f(\theta;x)$, specifically: $$ |g(\theta;x)-f(\theta;x)| \leq \mathcal{...
0
votes
1answer
44 views

On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

Please refer to Boyd et al.'s convergence analysis of ADMM (Chapter 3 and Appendix A). My question is: Why do we need $f$ and $g$ to be convex? I don't see the need of this assumption. If the ...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
0answers
35 views

How to deal with an $xy\le 1$ constraint?

I have to solve the following optimization problem: $$ \begin{align*} \min_{x,y} &\{-x-y\} \\ \text{such that} \\ y &\ge 3 \\ y &\le 30 \\ x &\ge 0 \\ xy &\le 1 \\ \end{align*} $$ ...
0
votes
1answer
20 views

Convexify $x\le a+by^2$

I have the following non-convex constraint: $$ x\le a+by^2\quad\text{where}\quad a,b>0,\,y\in[0,y_{max}]\text{ and }a\approx by_{max}^2 $$ On a drawing, it looks something like this: The above ...
0
votes
0answers
22 views

Coordinate descent with equality and inequality constraints

I have an intuitive understanding of why the simple method of coordinate descent does not work with linearly coupled constraints such as; $$\min_x\sum_if_i(x_i)$$ $$s.t.$$ $$Ax=b$$ If we try to ...
0
votes
0answers
10 views

How to compute norm bound error in robust approximation

I am reading convex optimization, and I am little confused about the following two prolems in norm bound error of robust approximation. How to compute $\{\|\bar{A}X-b+Ux\| | \|U\|\le a\}$ ? For the ...
0
votes
0answers
11 views

reference for convex function results

Here is a simple property of a concave function from $\mathbb{R}$ to $\mathbb{R}$, Given $x,x'\in \mathbb{R}$ with $x'>x$, if $\exists \kappa'\in (0,1)$ such that $$c(\kappa'x+(1-\kappa')x')=\...
0
votes
1answer
30 views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$...
1
vote
1answer
64 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 &+6x_2&+5x_3&-2x_4&+...
2
votes
1answer
30 views

Use of binary variables in LP problems

I can't figure out how to write the following condition to an LP. I have four nonnegative variables: $X_A$, $X_B$, $X_C$, and $X_D$. The condition which should be satisfied is this: If $X_A$ and $...
0
votes
0answers
14 views

Impact of removing active constraints in convex optimization

In active set methods for non negative least squares, we remove variables from the passive set to active set if the least squares solution gives negative values on those variables. What's the impact ...
1
vote
1answer
19 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
0
votes
0answers
26 views

Is the minimum point of a strictly convex function stable?

This is a problem I figured out after seeing the definition of minimum stable point and I think the following tense is true: Let $f(x)$ be a strictly convex function whose minimum values is $f^*=f(...
1
vote
0answers
59 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 \end{...
3
votes
2answers
84 views

Can you prove that this function is convex? $\sqrt{2x_1^2+3x_2^2+x_3^2+4x_1x_2+7} + (x_1^2+x_2^2+x_3^2+1)^2$.

My analysis: The second term can be proven to be convex as follows. It is basically a composition of norm with an affine transformation to the power of four: $(x_1^2+x_2^2+x_3^2+1)^2 = \|(x_1^2, x_2^2,...
0
votes
0answers
12 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
34 views

Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as \begin{...
1
vote
0answers
12 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: \begin{...
0
votes
0answers
31 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
1answer
36 views

characteristic cone of polyhedral

Let $$Q=\{x ∶ Ax ≤ b \}≠∅$$ If $Q = P + C$, where $P$ is a polytope and $C$ is a polyhedral cone, prove that $$\{y|Ay ≤ 0\} = \{y|x + y ∈ Q, ∀ x ∈ Q\}$$ The cone $C = \{y|Ay ≤ 0\}$ is called ...
0
votes
2answers
62 views

$\big\langle\nabla f(x)-\nabla f(y),\,(x-y)\big\rangle\ge m\,\left\| x-y\right\|^2,\;m>0\;$ for strictly and strong convex function [closed]

Prove that $\,\big\langle\nabla f(x) - \nabla f(y),\, (x-y)\big\rangle \geq m\,\left\lVert x-y\right\rVert^2, \;\,m > 0\,$ for strong convex function $f: \mathbb R^n \to\mathbb R$. Is it true for ...
1
vote
0answers
25 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
0answers
86 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
2answers
31 views

Is a convex cone a convex polyhedron?

Say that I have a convex cone $C=\{t|Ax = t, x\geq 0\}$. where $x\in R^n$, and $t\in R^m$, $A\in R^m\times R^n$. Can I say that this is a convex polyhedron? and why? EDIT: Just in order to avoid ...
0
votes
1answer
38 views

Is this the correct proximal operator?

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
1answer
46 views

Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
0
votes
2answers
31 views

$\max 2x_1 +x_2$ unbounded or unfeasible with the constraint $sx_1 +tx_2\le-1$

\begin{cases} \max & 2x_1 &{}+x_2\\ & sx_1 &{}+tx_2&\le-1\\ & x_1,x_2&&\ge 0 \end{cases} Find out when this program is not feasible, bounded Feasibility It is ...
0
votes
1answer
26 views

Show convexity of $f(x,y,z)= x^2+y^2+z^2+xyz$

Let $f(x,y,z)= x^2+y^2+z^2+xyz$. Show that $f$ is convex on $\Omega=${$(x,y,z)\in R^3 : x^2+y^2+z^2<\frac{5}{2}$}. To prove it, I want to show that $\nabla^2f(x,y,z)$ is positive definite. I ...
0
votes
0answers
13 views

Is the sum of a bivariate convex function Schur convex?

A well known fact is: Let $f(x)$ be a convex function. Then $g(\vec{x})=\sum_{i=1}^N f(x_i)$ is Schur convex in $\vec{x}$. Supose $f(\vec{z})$ is a convex function of $\vec{z}=(x,y)$. How to ...
1
vote
1answer
39 views

Choosing $\lambda$ to yield sparse solution

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
0answers
40 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
-1
votes
1answer
23 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
0
votes
0answers
9 views

Finding the lower bound of a linear program with the duality method

The issue I have some difficulties understanding the lower bound of a program when applying the duality method. It seems that it comes from $$c^T\underbrace{\le}_{x\ge 0\\y^TA\ge c^T} y^TAx\...
0
votes
0answers
22 views

Can the constrained optimization problem (1) be transformed into the unconstrained form (2)

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{\mathcal{C}_k} & \text{rank}(\mathcal{C}_k)\\ \mathrm{s.t.} & \mathcal{E}(\phi_{j}^{k})\le \epsilon \end{...
0
votes
0answers
20 views

general framework for proof of convexity in least square problem

Let $f(x_i,\theta) : X \times \Theta \rightarrow Z$ be a parametric function with parameter $\theta$ that we wish to fit to set of samples $S =\{(x_i,z_i)\}_{i=1}^N$, where $(x_i, z_i) \in X \times Z$....
2
votes
1answer
78 views

Linear program with two equality constraints

Compute the minimal value of $$x_1 + 2x_2 + 3x_3$$ when $x_1$, $x_2$, $x_3$ satisfy $$x_1 − 2x_2 + x_3 = 4$$ $$−x_1 + 3x_2 = 5$$ and $$x_1 \ge 0, \qquad x_2 \ge 0, \qquad ...
3
votes
1answer
50 views

Convex set: extreme points and distance to the origin

I'm fairly sure the following is true, although I wouldn't mind being proven wrong. If true, I would like to see an elegant proof, as my attempts are kind of messy. Let $K\subset\mathbb R^2$ be a ...
0
votes
0answers
14 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
26 views

Are the constrained optimization problem equal to the unconstrained one?

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{x} & \|Ax-b\|_2\\ \mathrm{s.t.} & \|x\|_1\le \epsilon \end{array} \end{equation} (2) \begin{equation}\label{...