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
0answers
9 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
12
votes
4answers
675 views

Double obstructing wall problem, what is the optimal walk path and length?

Every day, you walk from point A to point B which are exactly $2$ miles apart straight line distance, however, each day, there is a $50$% chance of there being an obstructing wall perpendicular to the ...
1
vote
0answers
42 views

Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$

\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array} For this ...
1
vote
0answers
20 views

Deriving the E-Step and M-Steps of the EM-Algorithm?

Insects of a certain species were exposed to cold temperature and how long the insects survived was recorded. The survival times of 9 of the 10 insects, in hours, are given below. 0.8, ...
1
vote
0answers
14 views

Is convexity of the objective function sufficient for a local maxima to be a global maximum?

In my problem, I have to maximize a convex function $f(x_1,x_2,\cdots,x_n)$ subject to two equality constraints $g_1=0$ and $g_2=0$. As usual, I constructed the Lagrangian ...
1
vote
2answers
51 views

Local extrema and minima of the multivariable function $f(x,y) = x^2y+y^2+xy$

Let $f(x,y) = x^2y+y^2+xy$ be a function, I want to find its local extrema an minima. I easily find that $f$ has 2 critical points: $(x,y)=(0,0)$ and $(x,y) = (-1,0)$. In order to find its local ...
0
votes
0answers
11 views

How to solve an optimization problem with objective function as a time average expectation

I have an optimization problem with the objective as $$ \overline{h(x)}=\lim_{T \to \infty} \sum_{t=0}^{T-1} E[f(x)] $$ where $$ h(x)=\frac{f(x)}{g(x)} $$ and $f$ is convex and $g$ is linear. I ...
0
votes
1answer
15 views

Geometric interpretation of support vector values in primal space

The Linear Support Vector Machine classification ($y_{k} = -1\ \mathrm{or}\ +1$) with misclassification tolerance loss function in primal weight space looks like this: $$\min\limits_{w,b,\xi} ...
0
votes
1answer
31 views

Word Problem Lagrange Method

I am studying for my exams and got very very stuck at a word problem on the Lagrange Methods, my biggest difficulty is to properly identify the function to be maximized (in this case) and so its ...
2
votes
1answer
34 views

Non-convex QCQP

Consider the following optimization problem: $$\begin{array}{ll} \text{minimize} & \mathbf{x}^{T} \mathbf{A} \mathbf{x}\\ \text{subject to } & \mathbf{x}^{T} \mathbf{P}_i \mathbf{x} > 0, ...
1
vote
1answer
41 views

Finding Extremas of $|x|$.

I'm trying to find the extrema of$\mod(x)$ but I'm not being able to do so. My attempt: $f(x, y) = |x|$ $f_{xx} = 0, f_{yy} = 0, f_{xy} = 0.$ So, $D(x, y) = 0$. And second derivative test isn't ...
0
votes
1answer
22 views

Upper Bound of a Function defined on a Closed Interval

In my Textbook, I am given the follow function which is defined on the closed interval $[a,b] $ $$(1/21)\cdot(x*7-3x*4+x+4)\le 6/21$$ $$(1/21)\cdot |7x*6-12x*3+1| \le 20/21 $$ These functions are ...
-1
votes
0answers
10 views

Difference between mirror descent and dual averaging [closed]

What is the main differences between mirror descent and dual averaging methods? When the number of steps or accuracy are fixed, they are equivalent. But what can be said when these parameters are not ...
0
votes
1answer
22 views

Concavity condition for function of more than one variable

We know for single variable function $f(t)$, the necessary and sufficient condition for concavity is $$ f((1-\lambda)x+\lambda y) \ge (1-\lambda)f(x)-\lambda f(y) $$ for every $x$ and $y$ and $0 ...
0
votes
0answers
7 views

optimization technique to find the best result

i have two outcomes from two types of test. both the results are not 100% accurate. Is there any technique available to extract the final result from these two outcomes?
3
votes
1answer
80 views

Show that $(a + b)^4 + (a + c)^4 + (a + d)^4 + (b + c)^4 + (b + d)^4 + (c + d)^4 \le 6$ for $a^2 + b^2 + c^2 + d^2 = 1$.

For $a, b, c, d \in \Bbb R$ such that $a^2 + b^2 + c^2 + d^2 = 1$, show that $$(a + b)^4 + (a + c)^4 + (a + d)^4 + (b + c)^4 + (b + d)^4 + (c + d)^4 \le 6.$$ The answer uses the mysterious identity ...
0
votes
1answer
12 views

SVM / QP result for impossible to satisfy conditions

The theory behind Linear Support Vector Machines with tolerance of misclassifications states that we are trying to minimise in the primal weight space the following function: $$\min\limits_{w,b,\xi} ...
0
votes
2answers
39 views

Extrema Where the Derivative is Undefined

Say we are given the derivative of a function say, $$f'(x)=\begin{cases} 5 & x<3 \\ -5 & x>3 \end{cases}$$ Notice that the derivative has opposite signs on either side of $x=3$, so you ...
0
votes
1answer
14 views

How to read 3 dimensional parameter from Excel to GAMS?

I don't know it is the place to ask this GAMS question but I couldn't find any other source. My question is about reading 3 dimensional parameter to GAMS from Excel file. I know it if there is a 2 ...
3
votes
2answers
277 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
0
votes
0answers
44 views

Minimizing the “distance” between a finite set of elements in a finite length sequence.

Given a set of "options", $\{A,B,C,C\}$, I'd like to construct a certain kind of sequence of these elements. And example sequence would be: $ABCDABCD$ I define some average "distance" for this ...
1
vote
1answer
15 views

cost minimization knowing the cost of labor and capital

The production function is $f(L,M)=4L^{0.5}M^{0.5}$ , where L is the number of units of labor and M is the number of machines used . If the cost of labor is \$100 per unit and the cost of ...
3
votes
1answer
707 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
0
votes
1answer
19 views

Why this scheduling MIP model is not working?

I have an integer programming model for Parallel Machine Scheduling. The parallel machine scheduling problem have $i$ jobs, $j$ process and $k$ number of machines. Each processes has to be done in ...
5
votes
2answers
64 views

Different methods for finding the minimum of $|x-2y|$ when $x^2+1=2y^2$.

For $x, y \in \Bbb R$, $x^2 + 1 = 2y^2$, find the minimum of $|x - 2y|$. At a glance I found that the point $(x, y)$ lies on a hyperbola and $|x - 2y|$ is just the distance between the point and the ...
-1
votes
1answer
50 views

Derivative Optimization Problem [duplicate]

I need help with finding the area of the largest rectangle in an ellipse from $y^2 + (x^2)/4 = 1$. I got it to y = $\sqrt{ 1 - (x^2)/4}$ but then I don't really know what to do, please help.
0
votes
0answers
19 views

minimization problem: finding smallest deltas that satisfy equation.

After long derivations to find a better backpropagation algorithm for neural networks, I got this elegant optimization problem. Index $i=1..n$ given constants $c_i \in R, w_i \in R$ variables to ...
1
vote
1answer
39 views

How to get explicit solution of the fractional minimization problem?

I need to minimize $f(x) = \frac{x^tQx}{a^tx-b}$, $Q$ is positive definite, $a,b$ are constant vector. But when I take gradient and set it equal to $0$, it's hard to get an explicit expression for ...
2
votes
2answers
342 views

Area of Parallelogram in an Ellipse

A parallelogram is inscribed in the ellipse $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ with the fixed line $y=mx$ as one of its diagonals. Prove that the maximum area of the parallelogram is $2ab$. ...
6
votes
5answers
17k views

Find the area of largest rectangle that can be inscribed in an ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1.$$ I got as far as coming up with the equation ...
0
votes
1answer
24 views

Minima of two convex functions that are “close” to each other

Consider two convex functions $f_1 : \mathbb{R}^n \to \mathbb{R}$ and $f_2 : \mathbb{R}^n \to \mathbb{R}$ such that $\hspace{2cm} |f_1(x) - f_2(x)| \leq \epsilon \hspace{2cm} \forall x \in ...
2
votes
2answers
765 views

Optimization: maximum area of a triangle under a parabola

Optimization: maximum area of a triangle in a parabola Inside a curve ($x^2-25$ - Parabola) a triangle is drawn with A as the vertex at the origin and the line joining points B and C lie on the ...
3
votes
2answers
46 views

Is there a reason that the maximal volumes of rectangular prisms with multiple open faces but constant surface area follows this pattern?

Suppose a rectangular prism has a surface area of $12 \text{ m}^2$. The optimal volume of this prism is well known. If the side lengths of the prism are $x$, $y$, and $z$, then the surface area is ...
11
votes
5answers
2k views

Find two positive real numbers, whose difference is 100 and whose product is a minimum

First off, this is a single-variable calculus optimization problem. At first glance, the problem seemed extremely trivial, however the solution to it seems to be deceptively tricky (at least to me at ...
0
votes
1answer
411 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are ...
12
votes
3answers
269 views

When does a variable leave a basis (in linear programming)?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
1
vote
1answer
53 views

Trying to solve $\max \limits_{\mathbf{x}} \sum_{i=1}^K \log_2(1+\frac{x_i a_{ii} }{\sum_{n \ne i} x_n a_{ni} })$, s.t. $\sum_{i=1}^K x_i \le b$

I am trying to solve the following optimization problem: \begin{array}{rl} \max \limits_{\mathbf{x}} & \sum_{i=1}^K \log_2(1+\frac{x_i a_{ii} }{\sum_{n \ne i} x_n a_{ni} }) \\ \mbox{subject to} ...
1
vote
1answer
23 views

Stuck formulating constrained optimization problem with Simplex

I have an exercise to solve, and it is a constrained optimization problem. Here it is: "A company makes large championship trophies for youth athletic leagues. At the moment they are planning ...
1
vote
0answers
32 views

Matrix transformation for linear state-space systems

In http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-241j-dynamic-systems-and-control-spring-2011/lecture-notes/MIT6_241JS11_lec12.pdf on pages 11-12 it is said: For a stable ...
3
votes
2answers
25 views

Precalc Optimization?

I need help with an optimization problem. I have a rectangle space being fenced. Three sides are fenced with a material costing 4 dollars and the last side costs 16 dollars. I was given that the area ...
2
votes
2answers
67 views

League of Legends optimal items

In the popular game League of Legends, your effective amount of hit points ($E$) against physical damage is a function of your actual hit points ($H$) and the amount of armor ($A$) you have. $$E = ...
0
votes
0answers
14 views

Fixed point of a value function

Suppose that we solved a dynamic optimization problem and figured out that the value function takes the form: $v(p)=h(p)+\alpha(p)v(g_1(p))+(1-\alpha(p))v(g_2(p))$ where we have explicit expressions ...
1
vote
0answers
41 views

Minimum variance, fixed mean , discrete random variable

Consider the ordered set $\mathcal{S}$ $=$ $\{0,a_i,a_2,\ldots,a_n\}$, where $a_i$ are all stricly positive real numbers and $a_i< a_{i+1}$ forall indices i. What is the random variable $X$ which ...
0
votes
1answer
80 views

Find the Lagrange multipliers with one constraint: $f(x,y,z) = xyz$ and $g(x,y,z) = x^2+2y^2+3z^2 = 6$

Where $f(x,y,z) = xyz$ and the constraint is $g(x,y,z) = x^2+2y^2+3z^2 = 6$ I have tried this problem like three or four times and not gotten the solution, I even asked this question once and got the ...
0
votes
0answers
23 views

Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
-1
votes
0answers
14 views

Vertex-cover-like problem with reduction to maximum flow

I am trying to solve the following problem: Solve the following problem by reducing it to the computation of a maximum s-t-flow: Let G be an undirected graph, $c:V\rightarrow\mathbb{Z}$ and ...
2
votes
1answer
542 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 ...
2
votes
2answers
69 views

Finite Difference Approximation of Derivative [closed]

I want to build a finite-difference approximation of this derivative: $\frac{\partial^2T }{\partial x^2}$ There are given an error of approximation: $O(\Delta x^{4})$ and nodal values of function:$ ...
1
vote
1answer
71 views

Method to find the extremal values of $xyz$ subject to $x^2+2y^2+3z^2=a$

This question has been asked before but I want to lay out my method and get feedback on reasoning and process this took me a long to put together as I am new to the formatting: Let the function $f$ ...
1
vote
2answers
153 views

Global maximum and minimum of $f(x,y,z)=xyz$ with the constraint $x^2+2y^2+3z^2=6$ with Lagrange multipliers?

The global maximum and the global minimum of the function $f(x,y,z)=xyz$ with the constraint $x^2+2y^2+3z^2=6$ can be found using Lagrange multipliers. $\nabla f = \lambda \nabla g$ ...