Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
1answer
11 views

Maximum hyperrectangle

Is there a way to determine the coordinates of the maximum hyper-rectangle in n-D space subject to linear constraints and $x_i\ge0$ ? Example: Argument Maximum of $x_1 x_2 x_3$ Given ...
0
votes
1answer
21 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
0answers
12 views

Designing an aggregate weighted cost function

In my undergraduate thesis, I am trying to solve a problem which finds an optimal POI (e.g. a restaurant) for a group of users. Each user $q_i$ is assigned a cost $c_{ij}$ with respect to a POI $o_j$. ...
0
votes
0answers
16 views

Travelling Salesperson MTZ

I have been solving a $10$ city travelling salesperson problem. Having solved the assignment based relaxation problem, I have $5$ subtours: $1 \rightarrow 10 \rightarrow 1$ $2 \rightarrow 8 ...
0
votes
1answer
16 views

Maximize two variables function subject to quadratic constraint

Two mariners end up on a island, with 1800 pounds of food to share, i.e. $F1 + F2 = 1800$. I'm expected to maximize the social welfare function given by $W=U1^{0.25}*U2^{0.75}$ where $U1=\sqrt{F1}$ ...
1
vote
0answers
10 views

Estimation of binomial probabilities $f(r)$ over $r \in [0,\frac{1}{2}]$

I want to fit a (decreasing) univariate function, \begin{equation} f(r), \end{equation} over $r \in [0,\frac{1}{2}]$ to a series ($r =\frac{1}{100}, \frac{2}{100}, \frac{3}{100} ,\ldots,\frac{1}{2}$) ...
0
votes
1answer
28 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.
1
vote
2answers
40 views

Solving the devil's penny puzzle

I was reading an article about the devil's penny puzzle. We are given $n$ boxes, one of which contains the devil's penny while the others contain an amount of money $a_1,\ldots,a_{n-1}$. These numbers ...
2
votes
0answers
145 views

Prove an artificial variable that leaves the basis will never return.

Prove an artificial variable that leaves the basis will never return. Edit: This is for the simplex method (I think). I have no idea how to start this. Anyone know any books with these kinds of ...
2
votes
1answer
758 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...
0
votes
0answers
12 views

What star rating is representative of this distribution? [on hold]

100 people vote. They can vote 1, 2, 3, or 4 stars. Distribution: 1 = 33, 2 = 26, 3 = 12, and 4 = 28. What star rating would you say is "representative" of these 100 people: 2.36 (2), the average, ...
1
vote
1answer
418 views

How to solve nonlinear constrained optimization in Matlab?

I have to solve a nonlinear constrained function in matlab, and I am not familiar with it's commands. the problem is: minimize $E(b,c)$ constraints: $k1< c\sqrt{b}< k2 ; c/6>k3$ Note: E(b,c) ...
1
vote
1answer
16 views

Signed angle difference without conditions

I've got two angles in $0 \leqslant a < 360$ and I need to find the signed difference between them which should be $-180 < \Delta < 180$. Is there a way to calculate the difference with ...
-1
votes
0answers
18 views

Effects of degenerate basic feasible solutions in the simplex algorithm? [on hold]

Let $P$ =$\{x\in \mathbb{R}^n :Ax=b,x\geq 0\}$,where $A$ is a $d×n$ matrix of rank $d$. Suppose that all basic feasible solutions are nondegenerate. Let $x \in P$ have exactly $d$ positive entries. ...
0
votes
1answer
37 views

why are the Bisection and Newton Method for finding roots complementary to each other?

my lecture note states that the bisection and newton method for finding roots are most of the time complementary to each other but I can not figure out why. I have basic understanding of both of the ...
2
votes
2answers
31 views

Am I allowed to do this chain-rule type thing when optimizing wrt to a functional?

So we have a function $f(x) = g(x)h(y(x))$ that is convex in $y$ which we want to optimize by choosing the appropriate $y(x)$. I have seen the following done in engineering books, but it just looks so ...
0
votes
1answer
52 views

Maximum of polynomial [on hold]

I was studying statics and came across this problem: Find the value $\beta$ such that $P$ has a maximum value in $R^2 - 1000^2 = P^2 + 2000P\cos(75^{\circ}+\beta)$. When $R$ is constant, the ...
0
votes
0answers
16 views

Singularities of composite function

Given a smooth, compact manifold $M$ (of dimension much less than $n$) and two maps $f:\mathbb{R}^n \rightarrow M$, $g:M\rightarrow \mathbb{R}$, I want to understand the topology of the critical set ...
0
votes
0answers
19 views

Maximization over minimum function

I want to solve the following optimization problem. Suppose we are given $p_r^i \in [0,1]$ for $r={1,2,...,N}$ and $i={1,2}$ such that $\sum_{r=1}^N p_r^i =1$ for i={1,2}. We want to find $x_r \in ...
0
votes
0answers
30 views

minimize this objective function

I have a function to minimize and I don't understand how I should proceed. The function is coming from a publication. Background: In a 2D image, $P_1$ and $P_2$ represents 2 patches of colors (RGB) ...
1
vote
2answers
52 views

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$ for positive integers $a,b,c$. Find all integers $a,b,c$ which give the smallest value. Since it is generally hard to find the minimum ...
0
votes
1answer
29 views

Optimizing the area of a rectangle with one side against a wall using the am-gm inequality

Given 300 meters of fence, how can I find the dimensions of a rectangle that is built against a wall the encloses the maximum area. I found this question in a calculus book and saw a simple solution ...
0
votes
0answers
12 views

Using the Fourier Series in Variational Optimization Problems

Say I have a functional $L(f)$ which takes as input the function $f:\mathbb{R}\to\mathbb{R}$, and I want to find the function that optimizes $L$. Unfortunately, there's no way to define a functional ...
0
votes
1answer
17 views

Find the positions of $A$ and $B$ which minimizes the length $AB$.

The line $AB$ joins the points $A(a, 0 )$, $B(0, b)$ on the $x$ and $y$ axes respectively and passes through the points $(8, 27)$. Find the positions of $A$ and $B$ which minimizes the length $AB$. ...
3
votes
1answer
103 views

Is this limit finite, or infinite?

Is $$\lim_{x\uparrow 1}\left(\frac{1-x}{x}\max\{nx^n|n\in\mathbb{N}\} \right)$$ infinite, or finite? ($\mathbb{N}$ is the set of the natural numbers). According to Mathematica, it looks like ...
0
votes
1answer
10 views

Softmax Regression Derivative

This website, http://deeplearning.stanford.edu/wiki/index.php/Softmax_Regression, claims the derivative of a multinomial regression: $$ J(\theta) = -\frac{1}{m}\sum_{i=1}^m \sum_{j=1}^k 1\{y^i =j\} ...
0
votes
0answers
12 views

Derivation of SVM algorithm (Lagrangian)

I have a question about the derivation of the SVM algorithm (for example, page 3 here ). The question is about the math, so that's why I'm asking this here. Suppose I have the following optimization ...
5
votes
2answers
199 views

Set is Convex regardless of b

Let the function $f$ be convex, $f :\Bbb R^n \rightarrow \Bbb R$ and let $$S = \{x : f(x) \le b\}$$ The proposition states that the set $S$ is convex regardless of $b$. Can someone explain to me how ...
3
votes
1answer
26 views

How do you find $∠XPC$ + $∠XPB$ such that $PB+PC$ is maximum where $P$ is a point on $f(x) = (x-1)(x-3)(x-5)$?

Problem: $f(x) = (x-1)(x-3)(x-5)$ intersects the x axis at $A(1,0)$, $B(3,0)$ and $C(5,0)$. A point $P(t,f(t))$ is selected on the curve such that $PB+PC$ is maximum and $t \in (3,5).$ Let $PX$ be ...
2
votes
1answer
502 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
8 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
0
votes
1answer
25 views

How can we solve this system of linear inequalities?

Let $c_i$ be a given non-negative integer for all $i\in\{1,\ldots,n\}$. I would like to find the non-negative integers $a_i$ and $b_i$ for all $i\in\{1,\ldots,n\}$ such that: \begin{align} ...
1
vote
1answer
50 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + ...
0
votes
0answers
23 views

Local maximum of $(2^{xy}{z \choose y})^{z+1}$

I have an optimization problem where I need to calculate the maximum of the following function $$ f(x,y,z) = (2^{xy}{z \choose y})^{z+1} $$ where $$ (z+1)(a+y(\lceil{\log_2{(z+1)}}\rceil+x))\leq C $$ ...
0
votes
0answers
8 views

ADMM Formulation for fractional programs?

I have a fractional program $$ \min \frac{f(x)}{g(x)} $$ where $f(x)$ and $g(x)$ are both quadratic functions (i.e. they are convex). It has been shown that this can be alternatively represented by ...
0
votes
2answers
707 views

Optimization, rectangle inscribed inside arch of the curve.

A rectangle is to be inscribed under the arch of the curve $y = 4\cos(0.5x)$ from $x = \pi$ to $x = -\pi$. What are the dimensions of the rectangle with largest area, and what is the largest area? ...
7
votes
3answers
156 views

How do you find the maximum value of $|z^2 - 2iz+1|$ given that $|z|=3$, using triangle inequality?

Problem: How do you find the maximum value of $|z^2 - 2iz+1|$ given that $|z|=3$, using triangle inequality? My attempt: $$|z^2 - 2iz+1|\le|z|^2+2|i||z|+1$$ $$\implies |z^2 - 2iz+1|\le16$$ ...
0
votes
2answers
26 views

SVD with Sparisty Penalties

I am trying to solve a problem like $$\min_{u,v} \Vert X-uv^T \Vert_F^2 + \beta \Vert v \Vert_1 \mbox{ s.t. } \Vert u \Vert_2 \le 1$$ where $X \in \mathbb{R}^{N\times N}$, $u, v \in ...
2
votes
0answers
42 views

How to prove that the following function has a unique mode?

I am trying to prove that the function $$f(\alpha)=n\ln \alpha-n\ln\Big(\sum_{i=1}^{n}t_i^\alpha+\int_{a}^{b}x^{\alpha+\beta-1}e^{-\lambda x^\beta}\,dx\Big)+(\alpha-1)\sum_{i=1}^{n}\ln t_i,$$ where ...
1
vote
0answers
29 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
1
vote
0answers
54 views
+100

Interpolation and mapping between scattered vectors in two unequally dimensioned spaces

Imagine two spaces: An ‘input’ space with dimension $m$. An ‘output’ space with dimension $n$. $m \geq n$ There are points in each of these spaces defined such that some characteristic is ...
34
votes
1answer
585 views
+500

A System of Matrix Equations (2 Riccati, 1 Lyapunov)

Setup: Consider the following system of real matrices, \begin{align} {\bf P} &={\bf F}({\bf I}_{n}-{\bf K} {\bf H}^\top){\bf P}{\bf F}^\top+{\bf Q}, \;\;\;\;\;\;\;\;\text{where}\;\;\;\;{\bf ...
0
votes
0answers
13 views

Optimizing functions with a complex domain and a real codomain

In general I want to understand if it makes sense to optimize a function of the following form $f: \mathbb{C} → \mathbb{R}$ for my specific problem $f(z) = | z | ^{2} $ (wich I is not analytic since ...
-1
votes
0answers
12 views

Removing variables from convex linear program

I am solving linear program (possibly non-convex). Then we know that dual is always convex. Then I noticed that depending on objective functional I can sometimes remove particular variables from this ...
0
votes
0answers
29 views

Understanding ADMM: how is it applied to this particular problem?

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
1
vote
1answer
533 views

Absolute extrema

Find the absolute extrema of the function $f(x,y)=2xy-x-y$ over the region of the xy-plane bounded by the parabola $y=x^2$ and the line $y=4$ I was wondering if I needed to use Lagrange multipliers to ...
1
vote
0answers
67 views

Making a Matrix singular

During my research I came across the following problem. Intuitively this should be an easy one. However, the simplest version of it looks like this: Let $C \geq \frac{1}{2}$ be some fixed ...
0
votes
0answers
19 views

Negative eigenvalue of a hessian matrix entails a local decrease in function value?

I was reading up on non-convex optimization, and I can across this sentence: "Since Hessian(f(w)) has a negative eigenvalue, there is always a point that is near w which has smaller function value" ...
2
votes
1answer
25 views

Win/Lose ratios and selection strategies

Imagine the following scenario: You're on a TCG tournament which allowed you to bring N decks with you. After each game, you might select another deck for your next game. You are allowed to keep ...
2
votes
1answer
69 views

Find and Evaluate Critical Points

I need to find al the critical points of the following function $f(x,y)=y^2-x^2y-3y+x^4-x^3$ Determine if they are local minima, local maxima, or saddle points, by looking at the Hessian matrices ...